Updated Dec 21, 2009 by r.parlett

Coexpressions

Co-expressions

Introduction

Co-expressions and local variables
The cocopy() function
The coact() function
Refreshing
The ! operator
Co-expression "black holes"
Uses of co-expressions

As an expression type
Co-routines
PDCOs
Exception handling

Introduction

The implementation and semantics of co-expressions is rather different in V2 of Object Icon, compared to V1, and indeed to traditional Icon.

The first and most significant difference to mention is that co-expressions in V2 are cheap. Each co-expression has an interpreter stack, but it grows and shrinks dynamically in chunks called "frames", with one frame corresponding to each procedure call. Each frame is quite small, typically about 100 bytes. This is in sharp contrast to the traditional Icon interpreter's allocation for a co-expression - a fixed size region sufficient for the predicted maximum required for both C and interpreter stack.

The implementation of co-expressions in V2 of Object Icon is also highly portable. The conventional Icon implementation requires a low-level context switch to swap between C stacks. This is inherently non-portable, and raises a number of other issues. The new non-recursive design of the interpreter loop in V2 of Object Icon means that no context-switch is required to implement co-expressions, and the new implementation is written entirely in standard C.

Co-expressions and local variables

In contrast to conventional Icon, V2 of Object Icon implements co-expressions in such a way that they share the local variables of the procedure in which they were created (in Icon each co-expression gets a copy of the local variables).

For example, the following program

import io

procedure main()
   local i, e
   i := 1
   e := create i := 2
   write(i)
   @e
   write(i)
end

outputs

1
2

whereas in Icon the result would be

1
1

Refreshing a co-expression creates a new co-expression, which also shares the same local variables. Thus the program

import io

procedure main()
   local i, e
   i := 1
   e := create i +:= 1
   write(i)
   @e
   write(i)
   e := ^e
   @e
   write(i)
end

outputs

1
2
3

The cocopy() function

Sometimes the way co-expressions share local variables is awkward.

Consider for example the problem of creating a list of ten co-expressions, each of which will generate a squared integer; 1 for the first, 4 for the second, 9 for the third and so on. The following obvious attempt (which would work in Icon), unfortunately doesn't work in Object Icon :-

import io

procedure main()
   local x, i, e

   x := []
   every i := 1 to 10 do
      put(x, create i * i)

   every e := !x do
      write(@e)
end

The problem with this is that each create i * i references the same i, which eventually reaches the value 10. So the output is ten 100s.

One way to solve this problem is to use a procedure to create the co-expressions :-

import io

procedure p(i)
   return create i * i
end

procedure main()
   local x, i, e

   x := []
   every i := 1 to 10 do
      put(x, p(i))

   every e := !x do
      write(@e)
end

Now each co-expression has its own copy of i, since each of the 10 calls to p creates its own set of local variables for that procedure.

This is rather clumsy however, and to provide a tidier solution, a builtin function cocopy is provided. This does exactly the same as the refresh operator ^, but instead of returning a new co-expression which also shares the local variables, a new set of local variables is allocated with values copied from the original. Here is another version of the above program :-

import io

procedure main()
   local x, i, e

   x := []
   every i := 1 to 10 do
      put(x, cocopy{i * i})

   every e := !x do
      write(@e)
end

Note we have used cocopy{i * i}, which is just syntactic shorthand for cocopy(create i * i).

The coact() function

This builtin function is like the @ operator, but more flexible. It takes four parameters as follows: coact(value, ce, activator, failto)

It transmits value to ce, optionally setting ce's activator. If failto is not &null, value is ignored, and failure is transmitted to ce instead. If activator is &null, then the activator of ce is left unchanged.

Note that coact(val, ce, &current) has the same effect as val@ce.

The default of ce is &source, so coact(val) is like val@&source, with the important difference that the activator of &source is unchanged. This use of coact is helpful in avoiding co-expression "black holes", described below.

Refreshing

In Icon, refreshing a co-expression reset the local variables to their values when the co-expression was created. This doesn't happen in the V2 Object Icon implementation of co-expressions. Refreshing a co-expression simply creates a new co-expression which shares the local variables of the co-expression being refreshed. cocopy does the same, but creates copies of the local variables instead.

The ! operator

V2 of Object Icon lets the unary ! operator be applied to co-expressions. The effect is to generate the sequence of results from a refreshed copy of the given co-expression. In other words, the result sequence of !e is the same as for p(e), if p were defined as the following procedure :-

procedure p(e)
   local t
   e := ^e
   while t := @e do
      suspend t
end

Note that evaluating !e does not affect e, nor generate any results from it.

Co-expression "black holes"

Consider the following program :-

import io

procedure black_hole()
   100@&source
end

procedure p()
   local e2
   e2 := create black_hole()
   return @e2
end

procedure main()
   local e1
   e1 := create p()
   write(@e1)
end

One would expect this program to simply write "100" as output; in fact it doesn't output anything, and enters an infinite loop. To understand why, here is the sequence of events which take place when it is run:-

main creates a co-expression (call it #1) and invokes it.
p creates another co-expression (#2) and invokes it.
black_hole transmits 100 to its &source, ie #1.
p now returns 100. This has the effect of resuming &source, which is now #2, since #2 just activated #1 by transmitting 100 to it.
black_hole is resumed and fails. Failure is transmitted to &source, which is now #1.
Since p has already returned, #1 fails to #2.
Since black_hole has already failed, #2 fails to #1.
The above two steps repeat forever.

The infinite loop is caused by the fact that the two co-expressions end up having each other as activators, whereas we want #1 to be the activator of #2, but &main to remain the activator of #1. The solution is to use the coact function in the black_hole procedure, replacing 100@&source with coact(100). In this simple example, we could also have just returned 100 from black_hole; however this wouldn't have helped if black_hole had been a deeply nested procedure.

Uses of co-expressions

As an expression type

The ! operator, together with a co-expression's ability to alter local variables lets us conveniently use co-expressions as a way of replaying an arbitrary expression almost as though it were a macro. For example :-

import io

procedure main()
   local e, i
   e := create i +:= 1
   i := 1
   !e
   !e
   !e
   write(i)
end

Outputs 4.

As another example, the following program prints the hexadecimal numbers in the range 0000 to FFFF:-

import io

procedure main()
   local e
   e := create !&digits | !"ABCDEF"
   every write(!e || !e || !e || !e)
end

This use of co-expressions is inspired by the following paper.

http://www.cs.arizona.edu/icon/ftp/doc/tr86_20.pdf

Co-routines

Co-expressions provide a complete co-routine capability. One particularly useful feature of co-routines is to generate the elements of a deeply nested structure. For example, consider the following binary tree class :-

class Node()
   public const data
   private l, r

   public insert(val)
      if val < data then
         (/l := Node(val)) | l.insert(val)
      else
         (/r := Node(val)) | r.insert(val)
   end

   public traverse()
      (\l).traverse()
      coact(self)
      (\r).traverse()
   end

   public new(i)
      self.data := i
      return
   end
end

The following main procedure populates a tree with random data and then uses the traverse method to print all the elements:-

import io

procedure main()
   local root, e, r
   r := create |?1000
   root := Node(@r)
   every 1 to 15 do
      root.insert(@r)
   e := create root.traverse()
   while write((@e).data)
end

Instead of using a while loop to print the elements we could also use an every loop as follows :-

   e := create root.traverse()
   every write((!e).data)

or, even more concisely

   every write(Seq{root.traverse()}.data)

Seq is a procedure which can be found in the ipl.pdco package. It simply takes a co-expression as a parameter and suspends each of its results. Note that Seq{root.traverse()} is just syntactic shorthand for Seq(create root.traverse()).

PDCOs

These are control structures whose elements are expressed as co-expressions. For example, here is Dijkstra's non-deterministic "do..od" loop structure, which can be found in the ipl.pdco package.

procedure Do(a[])
   local x, i
   repeat {
      x := []
      every i := 1 to *a by 2 do
         if @^a[i] then 
            put(x, i)

      if *x = 0 then
         break

      @^a[?x + 1]
   }
end

Here is a program to multiply using two number using the above.

import io, ipl.pdco

procedure main(a)
   local e, p, q, r

   e := create integer(pop(a)) | stop("Integer expected")
   p := !e
   q := !e

   writes(p, " * ", q, " = ")
   r := 0
   Do {
      q < 0, {
         q := -q
         p := -p
      },

      q > 0 & q % 2 = 0, {
         q /:= 2
         p *:= 2
      },

      q > 0 & q % 2 = 1, {
         q -:= 1
         r +:= p
      }
   }
   write(r)
end

Note that the Do { ... } construct above is actually just an ordinary procedure call with six parameters, since

P{ e1, e2, ..., en }

is just syntactic shorthand for

P(create e1, create e2, ... create en)

The ability of V2 co-expressions to refer to local variables (rather than copies of them) is a big advantage here. In conventional Icon, the above code would require that p, q and r be global or static variables in order that their values could be changed by the co-expressions.

Another nice example of the use of PDCOs is the function List in the package ipl.pdco, which is as follows :-

procedure List(e)
   local t
   t := []
   while put(t, @e)
   return t
end

Using List together with mutual evaluation gives a feature very similar to Python's list comprehensions. For example :-

List{(e := 0 to 9, e * e)}

gives the list [0, 1, 4, 9, 16, 25, 36, 49, 64, 81].

List can also be used to perform mapping and filtering on a list. For example, given one list x, the following produces another list with just the even elements of x :-

List{(e := !x, if e%2 = 0 then e)}

Exception handling

Since co-expressions provide a way of doing what amounts to a non-local goto, they can easily be used for exception handling. The package exception contains procedures try and throw, which are used as follows :-

import io, lang, exception

procedure p2()
   throw("something")
end

procedure p1()
   p2()
end

procedure main()
   try {
      p1()
   } | {
      write("Caught:", image(thrown))
      Coexpression.traceback(thrower)
   }
end

This outputs :-

Caught:"something"
Traceback:
co-expression#2 activated by co-expression#1
   main()
   p1() from line 13 in test9.icn
   p2() from line 8 in test9.icn
   exception.throw("something") from line 4 in test9.icn
   at line 9 in exception.icn

The try procedure works as a PDCO. It runs its body (p1() in this case) in a separate co-expression, but before doing so sets a global variable, exception.throw_handler to &current, ie the co-expression to re-activate on a throw. In fact, all the procedure throw does is store its parameter in the global variable exception.thrown, &current in the global variable exception.thrower, and activates exception.throw_handler. Having been activated again, try then simply succeeds or fails depending on whether or not it was activated by a throw.

Note that this way of handling exceptions does not "unwind" any stack. The stack of exception.thrower remains fully intact, and can be printed.