Coroutines

With picoLisp-3.0.3, the 64-bit version of PicoLisp has support for coroutines. This article tries to show their basic usage.

Assume we need all Pythagorean triples (i.e. all numbers A, B and C, such that A^2 + B^2 = C^2) with elements between 1 and N. A straightforward way to print them is:
   (de pythag (N)
      (for A N
         (for B (range A N)
            (for C (range B N)
               (when (= (+ (* A A) (* B B)) (* C C))
                  (println (list A B C)) ) ) ) ) )
We get:
   : (pythag 20)
   (3 4 5)
   (5 12 13)
   (6 8 10)
   (8 15 17)
   (9 12 15)
   (12 16 20)
However, just printing the triples is not very useful if they were needed in various situations for further processing. The lispy way for a general tool is passing a function to pythag and decide later what to do with the data:
   (de pythag (N Fun)
      (for A N
         (for B (range A N)
            (for C (range B N)
               (when (= (+ (* A A) (* B B)) (* C C))
                  (Fun (list A B C)) ) ) ) ) )
(note that for a truly general tool, we would write Fun and the local variables as transient symbols to avoid conflicts)

Now we can print them again
   : (pythag 20 println)
   (3 4 5)
   (5 12 13)
   (6 8 10)
   (8 15 17)
   (9 12 15)
   (12 16 20)
collect them into a list if we like
   : (make (pythag 20 link))
   -> ((3 4 5) (5 12 13) (6 8 10) (8 15 17) (9 12 15) (12 16 20))
or do with them whatever we like.

Still, this method has its limits. What if we need to pass a very large number for N, and we want to access the values one by one, perhaps in the course of some other involved calculation? Pre-generating the list of all values might not be feasible.

Using a Generator

One way to solve this problem is a generator. This function returns the next value each time it is called:
   (de pythag (N)
      (job '((A . 1) (B . 1) (C . 0))
         (loop
            (when (> (inc 'C) N)
               (when (> (inc 'B) N)
                  (setq B (inc 'A)) )
               (setq C B) )
            (T (> A N))
            (T (= (+ (* A A) (* B B)) (* C C))
               (list A B C) ) ) ) )

   : (pythag 20)
   -> (3 4 5)
   : (pythag 20)
   -> (5 12 13)
   : (pythag 20)
   -> (6 8 10)
   ...
Now we can call it whenever we need a new value. The function encapsulates the state of its local variables in a job environment.

A major disadvantage, however, is that it does not reflect the flow of control. The three nested for loops above had to be unfolded and programmed manually. This is hard to read, even for this simple case, and may be difficult or impossible to program in more complicated cases.

Using a Coroutine

A coroutine preserves the local environment, as well as the state of control of a function. It may have multiple exit points, and continue execution where it left off the last time.

This is done via two new functions: co and yield.
   (de pythag (N)
      (co 'pythag
         (for A N
            (for B (range A N)
               (for C (range B N)
                  (when (= (+ (* A A) (* B B)) (* C C))
                     (yield (list A B C)) ) ) ) ) ) )

   : (pythag 20)
   -> (3 4 5)
   : (pythag 20)
   -> (5 12 13)
   : (pythag 20)
   -> (6 8 10)
   ...
So this is a generator equivalent to the one above, but with cleanly nested for loops.

The function co is called with a tag argument, and an executable body (a prg), similar to catch. When called the first time, a new coroutine for that tag is created, and the body gets executed. If called again later, and an existing coroutine for that tag is found, execution will continue at the point where it left off last time with yield.

yield stops executing the coroutine's body, and immediately returns to the caller (or to some other coroutine if desired). When a coroutine is resumed with co, it will continue at the point of the last call to yield. If it is resumed by a call to yield in another coroutine, the return value of the first yield is the value given as an argument to the second yield.

Efficiency

In terms of memory usage, coroutines are rather expensive, because each of them requires its own stack segment. By default, the main segment will be restricted to 64 kB, and each coroutine to 64 kB. These values may increased with stack.

To my surprise, however, coroutines are quite efficient in terms of runtime overhead. Measuring the context switch to and from an empty coroutine (an endless loop with just a (yield))
   : (bench (do 1000000 (co 'bench (loop (yield)))))
   0.380 sec
   -> NIL
shows that it needs just 0.38 / 2 = 0.19 microseconds per switch operation.

This is in the same order of magnitude of a normal function call:
   : (bench (do 1000000 ((quote (X Y) (+ X Y)) 3 4)))
   0.162 sec
   -> 7
Comparing the implementations of pythag above - as a generator using job and a coroutine - shows that the coroutine version is about 10 percent faster.

Inspecting and Stopping Coroutines

The function stack can be used to see which coroutines are currently running (in addition to its primary task of setting or returning the current stack segment size).

Let's say we called pythag like in the example above, and then started two more coroutines as
   : (co "routine1" (yield 1))
   -> 1
   : (co "routine2" (yield 2))
   -> 2
Now there must be three coroutines running. stack returns them:
   : (stack)
   -> ("routine2" "routine1" pythag . 64)


When co is called with only a tag, but without a body, the corresponding coroutine is stopped.
   : (co "routine1")
   -> T
   : (co "routine2")
   -> T
   : (co 'pythag)
   -> T
   : (stack)
   -> 64
Now all coroutines are gone, and stack returns only the remaining segment size (in kilobytes).

A Tree Example

A typical example of a situation where a coroutine can simplify things a lot, is a recursive algorithm.

For testing, let's generate a balanced binary tree:
   (balance '*Tree (range 1 15))
As you may know, you can display it with the view function
   : (view *Tree T)
            15
         14
            13
      12
            11
         10
            9
   8
            7
         6
            5
      4
            3
         2
            1
It is easy to traverse such a tree, e.g. to print its nodes:
   : (de printNodes (Tree)
      (when Tree
         (printNodes (cadr Tree))
         (println (car Tree))
         (printNodes (cddr Tree)) ) )
   -> printNodes

   : (printNodes *Tree)
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
But what if you want to get the nodes returned, one by one, as in a generator function? For example, to compare the nodes of two trees and see of they are equal? If you think about it, you'll see that it is not trivial.

With a coroutine, it is straightforward. We can write a function that returns another node upon each call:
   (de nextLeaf (Rt Tree)
      (co Rt
         (recur (Tree)
            (when Tree
               (recurse (cadr Tree))
               (yield (car Tree))
               (recurse (cddr Tree)) ) ) ) )
With that, we can write a function to compare two trees
   (de cmpTrees (Tree1 Tree2)
      (prog1
         (use (Node1 Node2)
            (loop
               (setq
                  Node1 (nextLeaf "rt1" Tree1)
                  Node2 (nextLeaf "rt2" Tree2) )
               (T (nor Node1 Node2) T)
               (NIL (= Node1 Node2)) ) )
         (co "rt1")
         (co "rt2") ) )
The last two calls to co stop the two coroutines, independent of the result.

https://picolisp.com/wiki/?coroutines

21sep14   abu