Lists, Sets and Instructions

Lists, Sets and Tuples

• /+(x:bag, y:bag) -> list
• /+(l1:list, l2:list) -> list
• <<(l:list, n:integer) -> list
• ^(s1:set, s2:set) -> set
• ^(l:list, y:integer) -> list
• add(l:list, x:any) -> list
• add(s:set, x:any) -> set
• add*(l1:list, l2:list) -> list
• car(self:list) -> any
• cast!(s:bag, t:type) -> bag
• cdr(l:list) -> type[l]
• cons(x:any, l:list) -> list
• copy(s:bag) -> bag
• delete(s:bag, x:any) -> bag
• difference(self:set, x:set) -> set
• get(l:list, x:any) -> integer
• hash(l:list, x:any) -> integer
• last(self:list) -> type[member(self)]
• length(self:bag) -> integer
• list!(s:set) -> type[list[member(s)]]
• make_list(t:type, n:integer) -> list [XL]
• make_list(n:integer, x:any) -> type[list[list<any>(x),list({})]]
• max(f:method, self:bag) -> type[member(self)]
• min(f:method, self:bag) -> type[member(self)]
• nil :: Id(nil)
• nth :: property(open = 3)
• nth(l:bag, i:integer) -> any
• nth+(l:list, i:integer, x:any) -> bag
• nth-(l:list, i:integer) -> bag
• nth=(self:list, x:integer, y:any) -> any
• nth= :: property(open = 3)
• rmlast(self:list) -> list
• shrink(l:list, n:integer) -> list
• sort(f:method, self:list) -> list
• tuple!(x:list) -> tuple

CLAIRE provides two easy means of manipulating collections of objects: sets and lists. Lists are ordered, possibly heterogeneous, collections. To create a list, one must use the list(...) instruction : it admits any number of arguments and returns the list of its arguments. Each argument to the list(...) constructor is evaluated.

list(a, b, c, d) list(1, 2 + 3), list()

Sets are collections without order and without duplicates. Sets are created similarly with the set(...) constructor :

set(a,b,c) set(1,2 + 3)

The major novelty in CLAIRE 3.2 is the fact that lists or sets may be typed. This means that each bag (set or list) may have a type slot named of, which contains a type to which all members of the list must belong. This type is optional, as is illustrated by the previous examples, where no typing was given for the lists or sets. To designate a type for a new list or a new set, we use a slightly different syntax :

list<thing>(a,b,c,d) list<integer>(1,2 + 3) list<float>()  set<thing>(a,b,c) set<integer>(1, 2 + 3)

Typing a list or a set is a way to ensure that adding new values to them will not violate typing assumptions, which could happen in earlier versions of CLAIRE. Insertion is now always a destructive operation (add(l,x) returns the list l, that has been augmented with the value x at its end).

Since typing is mandatory in order to assume type-safe updates onto a list or a set, if no type is provided, CLAIRE will forbid any future update: the list or the set is then a "read-only" structure. This is the major novelty in CLAIRE 3.2: there is a difference between:

list(a,b,c,d) set(1,2 + 3) list{i | i in (1 .. 2)}

which are read-only structures, and :

list<thing>(a, b) set<integer>(1, 2 + 3)  list<integer>{i | i in (1 .. 2)}

which are structures that can be updated.

List or set types can be arbitrarily complex, to represent complex list types such as list of lists of integers. However, it is recommended to use a global constant to represent a complex type that is used as a list type, as follows :

MyList :: list<integer>  set<MyList>(list<integer>(1), list<integer>(2, 3))

Constant sets are valid CLAIRE types and can be built using the following syntax :

{a,b,c,d} {3, 8}

The expressions inside a constant set expression are not evaluated and should be primitive entities, such as integers or strings, named objects or global constants. Constant sets are constant, which means that inserting a new value is forbidden and will provoke an error.

A set can also be formed by selection. The result can either be a set with {x in a | P(x)}, or a list with list{x in a | P(x)}, when one wants to preserve the order of a and keep the duplicates if a was a list. Similarly, one may decide to create a typed or an un-typed list or set, by adding the additional type information between angular brackets. For instance, here are two samples with and without typing :

{x in class | (thing % x.ancestors)}  list{x in (0 .. 14) | x mod 2 = 0}  set<class>{x in class | (thing % x.ancestors)}  list<integer>{x in (0 .. 14) | x mod 2 = 0}

When does one need to add typing information to a list or a set ? A type is needed when new insertions need to be made, for instance when the list or set is meant to be stored in an object's slot which is itself typed.

Also, the imageof a set via a function can be formed. Here again, the result can either be a set with {f(x)|x in a} or a list with list{f(x) | x in a}, when one wants to preserve the order of a and the duplicates :

{(x ^ 2) | x in (0 .. 10)}  list<integer>{size(x.slots) | x in class}

For example, we have the traditional average_salary method :

average_salary(s:set[man]) : float      -> (sum(list{m.sal | m in s}) / size(s))

Last, two usual constructions are offered in CLAIRE to check a boolean expression universally (forall) or existentially (exists). A member of a set that satisfies a condition can be extracted (a non-deterministic choice) using the some construct: some(x in a | f(x)). For instance, we can write :

exists(x in (1 .. 10) | x > 2) // returns true  some(x in (1 .. 10) | x > 2) // returns 3 in most implementations  exists(x in class | length(x.ancestors) > 10)

The difference between exists and some is that the first always returns a boolean, whereas the second returns one of the objects that satisfy the condition (if there exists one) and unknown otherwise. It is very often used in conjunction with when, as in the following example :

when x := some(x in man | rich?(x))  in (borrow_from(x,1000), ...)  else printf("There is no one from whom to borrow!")

Conversely, the boolean expression forall(x in a | f(x)) returns true if and only if f(x) is true for all members of the set a. The two following examples returns false (because of 1):

forall(x in (1 .. 10) | x > 2)  forall(x in (1 .. n) | exists(y in (1 .. x) | y * y > x))

A read-only (untyped) list can also be thought as tuples of values. For upward compatibility reasons, the expression tuple(a1,...,an) is equivalent to list(a1,...,an) :

tuple(1,2,3), tuple(1,2.0,"this is heterogeneous")

Since it is a read-only list, a tuple cannot be changed once it is created, neither through addition of a new member (using the method add) or through the exchange of a given member (using the nth= method). CLAIRE offers an associated data type. For instance, the following expressions are true :

tuple(1,2,3) % tuple(integer,integer,integer)  tuple(1,2,3) % tuple(0 .. 1, 0 .. 10, 0 .. 100)  tuple(1,2.0,"this is heterogeneous") % tuple(any,any,any)

Typed tuples are used to return multiple values from a method. Because a tuple is a bag, it supports membership, iteration and indexed access operations. However, there is yet another data structure in CLAIRE for homogeneous arrays of fixed length, called arrays. Arrays are similar to lists but their size is fixed once they are created and they must be assigned a subtype (a type for the members of the array) that cannot change. Because of these strong constraints, CLAIRE can provide an implementation that is more efficient (memory usage and access time) than the implementation of bags. However, the use of arrays is considered an advanced feature of CLAIRE since everything that is done with an array may also be done with a list.

/+(x:bag, y:bag) -> list

x /+ y returns a new list that is the concatenation of the two bag contents.

/+(l1:list, l2:list) -> list

l1 /+ l2 returns a new list that is the concatenation of the two lists.

<<(l:list, n:integer) -> list

(l << n) left-shifts the list l by n units, which means that the n first members of the list are removed. This is a method with a side-effect since the returned value is the original list, which has been modified.

^(s1:set, s2:set) -> set

(s1 ^ s2) returns the intersection of the two sets s1 and s2 that is the set of entities that belong to both s1 and s2. Other internal restrictions of the property ^ exist, where ^ denotes the intersection (it is used for the type lattice).

^(l:list, y:integer) -> list

(l ^ y) skips the y first members of the list l. If the integer y is bigger than the length of the list l, the result is the empty list, otherwise it is the sublist starting at the y + 1 position in l (up to the end).

add(l:list, x:any) -> list

add(s,x) adds x to the list l. The returned value is the list obtained by appending (x) to l.

add(s:set, x:any) -> set

add(s,x) adds x to the set s. The returned value is the set s U {x}. This method may modify the set s but not necessarily.

add*(l1:list, l2:list) -> list

add*(l1,l2) returns the concatenated list l1 . l2, but it is destructive: it uses l1 as the data structure on which to perform the concatenation. Hence, the original l1 is no longer available after the method add* has been called

car(self:list) -> any

Classical LISP methods that return the head of the list (e.g. l[1]).

car(list(1,2,3)) -> 1  car(list(3,2,1)) -> 3

cast!(s:bag, t:type) -> bag

cast!(s, t) sets the member type of bag s to t. This method should be used carefully since their is no verification made to assert that all elements from the list actually belongs to the supplied type.

cast!(list(1,2,3), integer) -> list<integer>(1,2,3)

cdr(l:list) -> type[l]

Classical LISP methods that return the tail of the list (e.g. the list l starting at its second element ).

cdr(list(1,2,3)) -> (2, 3)  cdr(list(3,2,1)) -> (2, 1)

cons(x:any, l:list) -> list

This traditional method appends x at the beginning of l and returns the constructed list.

cons(1, list(2,3)) -> (1,2,3)

copy(s:bag) -> bag

The copy of a bag (a set or a list) returns a fresh set or list with the same elements

delete(s:bag, x:any) -> bag

delete(p, x, y) is equivalent to p(x) :delete y. This is a destructive method in the sense that it modifies its input argument unless the result is nil (There is only one empty list). The proper way to use delete, therefore, is either destructive (l :delete x) or non-destructive (delete(copy(l), x)).

difference(self:set, x:set) -> set

difference(s, t) returns the difference set s - t, that is the set of all elements of s which are not elements of t.

get(l:list, x:any) -> integer

get(l, x) returns the lowest i such that l[i] = x (if no such i exists, 0 is returned).

hash(l:list, x:any) -> integer

hash(l, x) returns an integer between 1 and length(l) that is obtained through generic hashing. To obtain the best dispersion, one may use a list of size 2i-3. This function can be used to implement hash tables in CLAIRE; it is the basis of the table implementation.

last(self:list) -> type[member(self)]

last(l) returns l[length(l)]

length(self:bag) -> integer

returns the length of a list. The length of a list is not its size !

list!(s:set) -> type[list[member(s)]]

list!(s) transforms s into a list. The order of the elements in the list can be anything.

make_list(t:type, n:integer) -> list

returns an empty list with type member t. n gives the size of the allocated content (i.e. adding n element won't cause further allocation).

make_list(n:integer, x:any) -> type[list[list<any>(x),list({})]]

returns a list of length n filled with x (e.g., make_list(3, 0) = list(0, 0, 0)).

max(f:method, self:bag) -> type[member(self)]

max(f,self) return the element of self that has the greatest value according to the ordering method f. For instance :

max(< @ integer, list(1,2,3,2,1)) -> 3

min(f:method, self:bag) -> type[member(self)]

min(f,self) return the element of self that has the lowest value according to the ordering method f. For instance :

min(< @ integer, list(1,2,3,2,1)) -> 1

nil :: Id(nil)

nil is the empty list instance.

nth :: property(open = 3)

nth can be redefined on user class domain meant to have indexed access. The reader converts the x[y] notation into a call to nth(x,y) that at evaluation will call the redefined restriction :

hash_table <: ephemeral_object(data:list[any])  nth(x:hash_table, x:any) : any ->      x.data[hash_value(x) and \xFFF]

nth(l:bag, i:integer) -> any

nth(l,i) return the i^thelement of the bag l. nth(l,i) is equivalent to l[i].

nth+(l:list, i:integer, x:any) -> bag

nth+(l,i,x) inserts element x at the i^thposition in the bag l. By extension, i may be length(l) + 1, in which case x is inserted at the end of l.

nth-(l:list, i:integer) -> bag

nth-(l,i) removes the i^thelement of the bag l. By extension, i may be length(l) + 1, in which case x is inserted at the end of l.

nth=(self:list, x:integer, y:any) -> any

nth=(l,i,x) replace the i^thelement of the bag l by x. nth(l,i,x) is equivalent to l[i] := x.

nth= :: property(open = 3)

nth= can be redefined on user class domain meant to have indexed access. The reader converts the x[y] := z notation into a call to nth(x,y,z) that at evaluation will call the redefined restriction :

hash_table <: ephemeral_object(data:list[any])  nth=(x:hash_table, x:any, y:any) : void ->      x.data[hash_value(x) and \xFFF] := y

rmlast(self:list) -> list

removes the last element of the list self.

shrink(l:list, n:integer) -> list

The method shrink truncates the list l so that its length becomes n. This is a true side-effect and the value returned is always the same as the input. As a consequence, shrink(l, 0) returns an empty list that is different from the canonical empty list nil.

let l := list<integer>(1,2,3)  in (shrink(l, 2),      assert(length(l) = 2))

sort(f:method, self:list) -> list

this method sorts the list self according to the ordering method f

tuple!(x:list) -> tuple

makes a tuple from a list