Contents

Co-expressions

Introduction

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

The first and most significant difference to mention is that co-expressions in Object Icon 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. Co-expressions in Object Icon are also fast. Creating a co-expression takes about the same time as creating an empty list, and invoking a co-expression is about 30% faster than invoking a procedure.

The implementation of co-expressions in 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 non-recursive design of the interpreter loop in Object Icon means that no context-switch is required to implement co-expressions, and the implementation is written entirely in standard C.

Co-expressions and local variables

In contrast to conventional Icon, 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

cocopy() is a builtin function which 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.

To illustrate how this might be useful, consider 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.

Using cocopy() provides a solution to the problem :-

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).

Another way to solve the problem, which doesn’t use cocopy(), 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.

The coact() function

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

It transmits value to ce, optionally setting ce’s activator. 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.

A related function, cofail(ce, activator), can be used to transmit failure to ce.

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 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

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)
   e := ^e
   suspend |@e
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:-

  1. main creates a co-expression (call it #1) and invokes it.
  2. p creates another co-expression (#2) and invokes it.
  3. black_hole transmits 100 to its &source, ie #1.
  4. 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.
  5. black_hole is resumed and fails. Failure is transmitted to &source, which is now #1.
  6. Since p has already returned, #1 fails to #2.
  7. Since black_hole has already failed, #2 fails to #1.
  8. 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)

ipl.pdco.Seq is a procedure that 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

A PDCO (“Programmer-Defined Control Operation”) is a procedure, whose parameters are intended to be co-expressions, which expresses some kind of control-structure like activity.

The terminology comes from Icon; see for example page 8 of https://www2.cs.arizona.edu/icon/analyst/backiss/IA22.pdf.

For example, here is Dijkstra’s non-deterministic “do..od” loop structure, which can be found in the ipl.pdco package here.

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 two numbers using the above.

Download domult.icn

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 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()
   }
   if \thrown then {
      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. After try returns, the caller can then check the global variable exception.thrown to see whether an exception was raised.

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

More information about exception handling can be found on this page.

Handling runtime errors

In a similar vein to the handling of exceptions, it is possible to handle runtime errors too. However, this facility is built into the implementation, since that is where runtime errors are generated.

To set a runtime error handler, an assignment to the keyword variable &handler is made. The value must be either &null (which turns handling off), or a co-expression, which is activated when a runtime error occurs. When that happens, the keywords &errornumber, &errortext, &errorvalue and &errorcoexpr will be set to give detail about the runtime error. Note that &errorvalue will not be set if no value was associated with the error (evaluating it will fail) and &errornumber will not be set if the error is not one of the standard numbered ones. &errortext is always set to the error message, and &errorcoexpr is always set to the value of &current when the error occurred.

Here is an example program which handles a runtime error caused by attempting to add 1 to the null value :-

Download runerr.icn

import io, lang

procedure main()
   local e
   e := create {
      write("okay")
      1 + &null
      write("shouldn't get here")
   }

   &handler := &current
   errorclear()
   if @e then
      write("Evaluation succeeded")
   else {
      if &errortext then {
         write("Evaluation caused runtime error")
         write("\t&errornumber=",image(&errornumber))
         write("\t&errortext=",image(&errortext))
         write("\t&errorvalue=",image(&errorvalue) | "<none>")
         write("\t&errorcoexpr=",image(&errorcoexpr))
         Coexpression.traceback(&errorcoexpr)
      } else
         write("Evaluation failed")
   }
   &handler := &null
end

The output is :-

okay
Evaluation caused runtime error
        &errornumber=102
        &errortext="numeric expected"
        &errorvalue=&null
        &errorcoexpr=co-expression#2(0)
Traceback:
co-expression#2 activated by co-expression#1
   main()
   at line 7 in eg.icn

Note that attempting to resume the co-expression which caused the runtime error for another value will produce a runtime error. This particular runtime error is in the “fatal” category, meaning it cannot be handled and always causes immediate termination.

Non-blocking I/O and background tasks

Co-expressions are a very useful tool when used to perform I/O on multiple streams at the same time, in a non-blocking fashion. They provide an alternative to the conventional rather clumsy techniques of callbacks and state-machines.

The co-expression technique uses a scheduler class and several worker co-expressions, each of which performs non-blocking I/O. The worker co-expressions are created by the main client program, but activated by the scheduler. A worker then runs until it wishes to do some I/O, and before it does so it re-activates the scheduler. The scheduler notes the streams which each worker wants to read from or write to, and uses the poll() function to determine which of them are ready. The appropriate workers are then re-activated so that they can read or write data and continue their execution until the next piece of I/O, or they exit. In either case, control returns again to the scheduler.

An implementation of a scheduler along these lines can be found in the io package. The scheduler is called io.Scheduler. The worker co-expressions are wrapped in instances of a class called io.Task. This class has methods to let the task sleep for a time, or to poll streams. Both these methods activate the scheduler rather than blocking the program. The most important method in Scheduler is work(), which does a slice of work on a ready Task, if one is ready.

As an example consider the following program which uses the http.HttpClient class, which provides a way to retrieve data over HTTP. It has a retrieve() method which creates a io.SocketStream to communicate with the server and tries to retrieve a page of data, using conventional synchronous logic. However, it has an option to use a Task, which tells it to use the Task’s poll method, rather than the normal poll method in DescStream. With no further alteration to the logic of the class, it can now be used asynchronously.

Download nonblock.icn

import io, http, net

global sched

procedure download(x, t)
   local cl, req, resp, s
   s := RamStream()
   cl := HttpClient().
      set_task(t).
      set_timeout(10000)
   req := HttpRequest().
      set_url(URL(x)).
      set_output_stream(s)
   if resp := cl.retrieve(req) then
      write("Retrieved ", *s.str(), " bytes from ", x)
   else
      write("Failed to retrieve ", x, ": ", &why)
   s.close()
   cl.close()
   t.revert()
end

procedure new_task(s)
   local t
   t := Task(sched, create download(s, t))
   t.start()
end

procedure main()
   # Use a 50ms delay in the Scheduler's call to poll.
   sched := Scheduler(50)
   new_task("http://www.google.com")
   new_task("http://www.yahoo.com")
   new_task("http://news.bbc.co.uk")
   new_task("http://www.telegraph.co.uk")
   new_task("http://www.herald.co.zw/")
   new_task("http://www.dailymail.co.uk")
   new_task("http://www.independent.co.uk/")
   new_task("http://www.guardian.co.uk/")
   new_task("http://www.thesun.co.uk/")
   new_task("http://www.express.co.uk/")

   until sched.empty() do {
      sched.work()
      # Could do some extra work between polls.
   }
   write("Exiting")
end

The main method creates an Scheduler and adds ten Tasks which each download some data. Then it repeatedly calls work, until there is nothing left to do. Example output is as follows :-

Retrieved 73010 bytes from http://www.telegraph.co.uk
Retrieved 190705 bytes from http://www.guardian.co.uk/
Retrieved 150044 bytes from http://www.independent.co.uk/
Retrieved 9558 bytes from http://www.google.com
Retrieved 102355 bytes from http://news.bbc.co.uk
Retrieved 153377 bytes from http://www.yahoo.com
Retrieved 56454 bytes from http://www.herald.co.zw/
Retrieved 131933 bytes from http://www.thesun.co.uk/
Retrieved 154414 bytes from http://www.express.co.uk/
Retrieved 203773 bytes from http://www.dailymail.co.uk
Exiting

As a further example, here is a simple server that can handle several clients simultaneously. One task listens for incoming connections, each of which is serviced by a new task created in the handle procedure. These tasks make use of a useful utility class called io.TaskStream which simply wraps another Stream (in this case a SocketStream). The implementation of TaskStream defines the in and out methods so that they call the task’s poll method, and hence re-activate the scheduler before performing the I/O on the underlying Stream. Thus the read and write methods used in the handle procedure do not block the program, but allow other tasks to be scheduled instead.

Download server.icn

import io

global sched, x_flag

procedure handle(a)
   local t, s
   t := Task(sched, create {
      # Service the client with a 30s timeout
      a := TaskStream(a, t, 30000) 
      write("\tHandling...")
      repeat {
         s := a.read() | {
            write("\tRead failed ", &why)
            break
         }
         # An input of "x" shuts down the server
         if s == "x" then {
            x_flag := 1
            break
         }
         # An input of "q" ends this client's session
         if s == "q" then 
            break
         a.write(map(s))
      } 
      write("\tEnd of handling.")
      a.close()
      t.revert()
   })
   t.start()
end

procedure main()
   local f, x
   # Use a 50ms delay in the Scheduler's call to poll.
   sched := Scheduler(50)

   x := Task(sched, create {
      f := SocketStream(ProtocolFormat.INET, SocketType.STREAM) | stop(&why)
      f.bind("inet:*:7000") | stop(&why)
      f.listen(5)  | stop(&why)
      write("Listening...")
      repeat {
         x.poll([f, Poll.IN]) | stop(&why)
         handle(f.accept())
      }
   })
   x.start()

   until \x_flag do {
      sched.work()
      # Could do some extra work between polls.
   }

   f.close()
   write("Exiting")
end

The scheduler class is also used by the gui library. Rather than performing I/O, these tasks typically perform background updates of the user interface. For example the logic to make the cursor flash in a textfield is encapsulated in a Task. The task sleeps for a while, then updates the cursor, and repeats the process indefinitely until the task is stopped when the textfield is disposed of.

Contents