Iterations

We just saw that CLAIRE will produce in-line substitution for some methods. This is especially powerful when combined with parametric function calls (using call(...)) taking advantage of the fact that CLAIRE is a functional language. There is another form of code substitution supported by CLAIRE that is also extremely useful, namely the iteration of set data structure.

Any object s that understands the set! method can be iterated over. That means that the construction for x in s e(x) can be used. The actual iteration over the set represented by s is done by constructing explicitly the set extension. However, there often exists a way to iterate the set structure without constructing the set extension. The simplest example is the integer interval structure that is iterated with a while loop and a counter.

It is possible to define iteration in CLAIRE through code substitution. This is done by defining a new inline restriction of the property iterate, with signature (x:X,v:Variable,e:any). The principle is that CLAIRE will replace any occurrence of (for v in x e) by the body of the inline method as soon as the type of the expression x matches with X (v is assumed to be a free variable in the expression e). For instance, here is the definition of iterate over integer intervals :

iterate(x:interval[min:integer,max:integer],v:Variable,e:any) =>      let v := min(x), %max := max(x)      in (while (v <= %max) (e, v :+ 1))

Here is a more interesting example. We can define hash tables as follows. A table is defined with a list (of size 2n - 3, which is the largest size for which a chunk of size 2n is allocated), which is full of "unknown" except for these objects that belong to the set. Each object is inserted at the next available place in the table, starting at a point given by the hashing function (a generic hashing function provided by CLAIRE: hash) :

htable <: object(count:integer = 0,                  index:integer = 4,                  arg:list<any> = list<any>())  set!(x:htable) : set -> {y in x.arg | known?(y)}  insert(x:htable, y:any) ->      let l := x.arg      in (if (x.count >= length(l) / 2)          (x.arg := make_list(^2(x.index - 3), unknown),          x.index :+ 1, x.count := 0,          for z in {y in l | known?(y)} insert(x,z),              insert(x,y))      else let i := hash(l,y)          in (until (l[i] = unknown | l[i] = y)                  (if (i = length(l)) i := 1 else i :+ 1),                  if (l[i] = unknown)                      (x.count :+ 1, l[i] := y)))

Note that CLAIRE provides a few other functions for hashing that would allow an even simpler, though less self-contained, solution. To iterate over such hash tables without computing set!(x) we define :

iterate(s:htable, v:Variable, e:any)      => (for v in s.arg (if known?(v) e))

Thus, CLAIRE will replace :

let s:htable := ... in sum(s)

by :

let s:htable := ... in      (let x := 0      in (for v in s.arg          (if known?(v) x :+ v),          x))

The use of iterate will only be taken into account in the compiled code unless one uses oload, which calls the optimizer for each new method. iterate is a convenient way to extend the set of CLAIRE data structure that represent sets with the optimal efficiency. Notice that, for a compiled program, we could have defined set! as follows (this definition would be valid for any new type of set) :

set!(s:htable) -> {x | x in s}

When defining a restriction of iterate, one must not forget the handling of values returned by a break statement. In most cases, the code produce by iterate is itself a loop (a for or a while), thus this handling is implicit. However, there may be multiples loops, or the final value may be distinct from the loop itself, in which case an explicit handling is necessary. Here is an example taken from class iteration :

iterate(x:class, v:Variable, e:any) : any      => (for %v_1 in x.descendents          let %v_2 := (for v in %v_1.instances e) // catch inner break          in (if %v_2 break(%v_2)))  // transmit the value

Notice that it is always possible to introduce a loop to handle breaks if none are present; we may replace the expression e by :

while true (e, break(nil))

Last, we need to address the issue of parametric polymorphism, or how to define new kinds of type sets. The previous example of hash-sets is incomplete, because it only describes generic hash-sets that may contain any element. If we want to introduce typed hash-sets, we need to follow these three steps. First we add a type parameter to the htable class :

htable[of] <: object(of:type = any, count:integer = 0, ...)

Second, we use a parametric signature to use the type parameter appropriately :

insert(x:htable<X>, y:X) -> ...

Last, we need to tell the compiler that an instance from htable[X] only contains objects from X. This is accomplished by extending the member function which is used by the compiler to find a valid type for all members of a given set. If x is a type, member(x) is a valid type for any y that will belong to a set s of type x. If T is a new type of sets, we may introduce a method member(x :T, t :type) that tells how to compute member(t) if t is included in T. For instance, here is a valid definition for our htable example :

member(x:htable,t:type) -> member(t @ of)

This last part may be difficult to grasp (do not worry, this is an advanced feature). First, recall that if t is a type and p a property, (t @ p) is a valid type for x.p when x is of type t. Suppose that we now have an expression e, with type t1, that represents a htable (thus t1 <= htable). When the compiler calls member(t1), the previous method is invoked (x is bound to a system-dependent value that should not be used and t is bound to t1). The first step is to compute (t1 @ of), which is a type that contains all possible values for y.of, where y is a possible result of evaluating e. Thus, member(t1 @ of) is a type that contains all possible values of y, since they must belong to y.of by construction. This type is, therefore, used by the compiler as the type of the element variable v inside the loop generated by iterate.