Adding Parallel and Persistent Sets to Modula-3

Cours informatique Modula-3, tutoriel & guide de travaux pratiques en pdf.

Basic Concepts

The concept of persistent and parallel sets incorporated into general-purpose programming languages is suggested. Implementations of relational databases are based on the concept of set of tuples. Object oriented databases are based similarly on set of objects, or on a hierarchy of such sets (such as classes and views [Laas]). To build a safe object oriented database, the concept of typed sets is required.
Persistence is orthogonal to the type of the data. Nevertheless, persistence becomes interesting only in cases, where we have a large amount of data. Therefore, we are not so much interested on single persistent variables, rather on persistent aggregates. Especially on persistent sets.
Sets are unordered collections of some objects. Therefore, they can be processed in many cases in parallel in a natural way. The most typical operation is to select a subset whose members satisfy a given constraint. As sets are unordered, no assumption can be made on the order of the constraint evaluation. As a consequence, they can be evaluated in parallel.
A well-defined hierarchy of sets introduces an explicit clustering, which makes efficient parallel processing still easier (see the definition of classes in section 3.2 and [Day]).
Definition of sets
We define sets (based on the definitions of Georg Cantor [Cant], [Deux] and of [Elma]) as a limited, unordered collection of different, type compatible elements. All elements must be different and they must exist. A set is defined over a base type (sometimes simply called the type of the set). All elements of the set must be a subtype of this base type. The subtype relation is reflexive (and transitive), therefore this definition includes the case where elements are of the same type as the base type. Sets corresponding to this definition can be called typed and polymorphic. We are first of all interested in sets of objects.
Definition of a class
A class is an instance of a set of objects. It is related to other classes in a subclass or superclass relation1. A class may have several super- and subclasses (this does not require multiple inheritance in the type system). Since classes are defined as sets, all operations on sets are also available on classes. Classes are assignable to sets or views, and vice versa.
Is ClassSub a subclass of ClassSuper, we have the following relations:
1. The base type of ClassSub must be a subtype of the base type of ClassSuper. 2. The extension of ClassSub is a subset of that of ClassSuper. In other words, all elements of ClassSub are also contained in ClassSuper. This implies the so-called instance inheritance. If we insert a new element into a subclass, it becomes an element of all its superclasses. If we delete an element of a class, it is also deleted from all its subclasses. Let us suppose we have a class of students which is a subclass of persons. If we insert a new student into the class of students, then the student becomes also an element of the person class (we say, a student is a person). If we delete a person that is a student then it must disappear from the student class as well.
Definition of a view
A view is a set that is defined over some sets or classes or views, by means of a generator (e.g. a generator predicate). Views must be always in accordance with their generator. Therefore, they are usually not materialized, rather they are regenerated on every reference. Since views are defined as sets, all operations on sets are also available on views. Views are assignable to sets or classes, and vice versa. Views are updateable. An update of a view causes an update of the sets or classes over which it is defined. No invisible elements can be inserted into resp. deleted from a view.

Adding sets to Modula-3

Standard Modula-3 sets are defined as « a collection of values taken from some ordinal type » [Nels]. The following definitions relax some of the restrictions of this definition. Nevertheless, all standard Modula-3 set facilities remain unchanged.
Declaration of sets
We do not need a new type constructor for the generalized sets, the standard Modula-3 set 1Note that this definition of a class is quite different from the use of this notion by the programming language community, where a class is generally the same as an object type. The above definiton defines a class as an object container, rather than a type. This usage is very usual in the database community [Laas].
constructor can be used. The syntax of a set type remains unchanged, its form is:
SetType = SET OF Type
Type (which stands for the base type of the set) can be an ordinal type or any reference type. In the following discussion we consider only the most interesting case: where Type is an object type. Sets of non-ordinal types can only be instanced dynamically, via a reference to a set. This is analogous to dynamic (open) arrays. Sets can be instanced by the standard function NEW. New requires as a first parameter the type which is to be instanced (this is a standard Modula-3 feature). In the case of sets, an optional size parameter can be given, which serves as a hint for the compiler for the allocation of the set. The compiler may (and should) use this parameter for efficient allocation. The corresponding NEW-signature is:
NEW(Type [, Size])
Let us consider the following declarations (DP, DS and DE stand for display procedures):
Person = OBJECT name: TEXT METHODS display():= DP END; Student = Person OBJECT matriculation: CARDINAL OVERRIDES display:= DS END; Employee = Person OBJECT salary: CARDINAL OVERRIDES display:= DE END; PersonSet = REF SET OF Person; (*May contain Persons*) StudentSet = REF SET OF Student; (*May contain Persons and Students*) EmployeeSet = REF SET OF Employee; (*May contain Persons and Employee*)
Student and Employee are subtypes of Person. Both of them overrides the display method with an appropriate procedure. The sets may contain only elements which are compatible with their base type. For instancing sets consider the following example:
VAR persons := NEW(PersonSet, pSize); (*pSize: expected number of persons*) students := NEW(StudentSet, sSize); (*sSize: expected number of students*) employee := NEW(EmployeeSet, eSize); (*eSize: expected number of employee*)
Operations on sets
Set expressions
Set expressions take compatible sets as arguments and result in a set. The type of the result depends on the operation. Union, Intersection and Difference are defined as usual. An additional set expression is selection. Let be set1 a set of type T1 and set2 a set of T2, and RT the base type of the result. The general form of set expressions is as follows:
– Union: set1 + set2. RT=T1 if T2<:T1 or RT=T2 if T1<:T2 (RT is the more general one).
– Intersection: set1 * set2. RT=T1 if T1<:T2 or RT=T2 if T2<:T1 (the more special one).
– Difference: set1 – set2. RT=T1
Following shorthands can be used: s += s2 for s:= s+s2, s *= s2 for s:= s*s2 and s -= s2 for s:= s-s2. They can be (and should be) used by the compiler for a more efficient evaluation.
– Selection: elem FROM set-expression : Boolean expression
The result of a selection is a set, which contains all elements of the given set expression which satisfy the constraint given in the Boolean expression. The scope of elem is the
selection, its type is the base type of the given set expression. Examples: s FROM students : Text.Equal(, »Peter ») selects all students2, who are called « Peter ». p FROM persons – (students + employee) : Text.Equal(, »Paul ») selects persons who are neither students nor employee and whose name is « Paul ». Note that set expressions can be nested.
– The Assignment is defined as it is usual in Modula-3. Its general form is:
set-expression:= set-expression;
The set-expression on the left hand must evaluate to a writeable variable, the right-hand expression must evaluate to a set value. This value must be assignment compatible to the left-hand variable. That means that the base type of the right-hand expression must be a subtype of the type of the variable (as the subtype relation is reflexive, this includes the case when the types are equal). As a result of the assignment, the set designated by the right-hand expression is copied into the set designated by the left-hand expression. For example: students^:= SET OF Student{st1, st2, st3, st4, st5} initializes the student set with the given five student objects. After the assignment persons^:= students^ the old content of the person set is lost, its new content is the set of students. Note that objects are references in Modula-3, therefore the copy of a set of objects is the copy of a set of references. The assignment of a reference to a set, such as persons := students has the same semantics, as any other reference-assignment, i.e. persons points after that to the student set, no copy operation is performed. If the set originally referenced by persons is not referred by any other reference the entire set is collected by the garbage collector.
– Insert and Delete. With insert and delete we can add and remove single elements respectively. No action is taken if an element should be inserted twice or if a non-existing element should be deleted. The type of ei must be a subtype of the type of set. Their general form is: Insert: set =+ e1, e2, … en Delete: set =- e1, e2, … en For example students =+ st10,st11,st2 adds three given student objects to the set. Similarly students =- st1,st2 removes the two given objects.
– The Set-Iteration statement allows to iterate over all elements of a set. Its general form is:
FOR elem FROM set-expression DO Statements END.

Cours gratuitTélécharger le cours complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *