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