Teach Yourself Scheme: 13.4 Coroutines (idea)

Prev Up Next

The generators used above are interesting generalizations of the procedure concept. Each time the generator is called, it resumes its computation, and when it has a result for its caller returns it, but only after storing its continuation in an internal variable so the generator can resumed again. We can generalize generators further, so that they can mutually resume each other, sending results back and forth amongst themselves. Such procedures are called coroutines.

We will view a coroutine as a unary procedure, whose body can contain resume calls. resume is a two-argument procedure used by a coroutine to resume another coroutine with a transfer value.

A coroutine (let's call it A) has an internal variable called local-control-state that stores, at any point, the remaining computation of the coroutine. Initially this is the entire coroutine computation. When resume is called -- ie, invoking another coroutine B -- the current coroutine will update its local-control-state value to the rest of itself, stop itself, and then jump to the resumed coroutine B. When coroutine A is itself resumed at some later point, its computation will proceed from the continuation stored in its local-control-state.

(define-macro coroutine
  (lambda (x . body)
    `(letrec ((local-control-state
               (lambda (,x) ,@body))
              (resume
               (lambda (c v)
                 (call/cc
                  (lambda (k)
                    (set! local-control-state k)
                    (c v))))))
       (lambda (v)
         (local-control-state v)))))

13.4.1  Tree-matching with coroutines

Tree-matching is further simplified using coroutines. The matching process is coded as a coroutine that depends on two other coroutines to supply the leaves of the respective trees:

(define make-matcher-coroutine
  (lambda (tree-cor-1 tree-cor-2)
    (coroutine dont-need-an-init-arg
      (let loop ()
        (let ((leaf1 (resume tree-cor-1 'get-a-leaf))
              (leaf2 (resume tree-cor-2 'get-a-leaf)))
          (if (eqv? leaf1 leaf2)
              (if (null? leaf1) #t (loop))
              #f))))))

The leaf-generator coroutines remember who to send their leaves to:

(define make-leaf-gen-coroutine
  (lambda (tree matcher-cor)
    (coroutine dont-need-an-init-arg
      (let loop ((tree tree))
        (cond ((null? tree) 'skip)
              ((pair? tree)
               (loop (car tree))
               (loop (cdr tree)))
              (else
               (resume matcher-cor tree))))
      (resume matcher-cor '()))))

The same-fringe? procedure can now almost be written as

(define same-fringe?
  (lambda (tree1 tree2)
    (letrec ((tree-cor-1
              (make-leaf-gen-coroutine
               tree1
               matcher-cor))
             (tree-cor-2
              (make-leaf-gen-coroutine
               tree2
               matcher-cor))
             (matcher-cor
              (make-matcher-coroutine
               tree-cor-1
               tree-cor-2)))
      (matcher-cor 'start-ball-rolling))))

Unfortunately, Scheme's letrec can resolve mutually recursive references amongst the lexical variables it introduces only if such variable references are wrapped inside a lambda. And so we write:

(define same-fringe?
  (lambda (tree1 tree2)
    (letrec ((tree-cor-1
              (make-leaf-gen-coroutine
               tree1
               (lambda (v) (matcher-cor v))))
             (tree-cor-2
              (make-leaf-gen-coroutine
               tree2
               (lambda (v) (matcher-cor v))))
             (matcher-cor
              (make-matcher-coroutine
               (lambda (v) (tree-cor-1 v))
               (lambda (v) (tree-cor-2 v)))))
      (matcher-cor 'start-ball-rolling))))

Note that call/cc is not called directly at all in this rewrite of same-fringe?. All the continuation manipulation is handled for us by the coroutine macro.

Prev Up Next