Tutorial on writing 'yield' [Was: Re: [plt-scheme] question about continuation example in "t-y-scheme in fixnum days"]

On Mon, 3 Apr 2006, nusret wrote:

> I'm learning Scheme and got a little bit confused after reading the tree
> traversal example on Ch 13, "Jumps" of Teach yourself scheme in fixnum
> days. (page 53 in the pdf file).


Hi nusret,


[Note: most of this comes from The Little Schemer; you might want to take
a look at that book sometime: it covers this more comprehensively.

This post is a bit long; apologies!]



Perhaps it might help if we simplify the example to something slightly
simpler: let's say that we'd like to write a generator to march through a
list of items.  That is, let's say that we'd like some function called
LIST->GENERATOR that behaves like this:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> (define elt-generator
    (list->generator '(hello world) (lambda () 'done)))
> (elt-generator)
'hello
> (elt-generator)
'world
> (elt-generator)
'done
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



How can we go about doing this?  Here's one approach:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(module generator-example mzscheme
  (provide list->generator)
  (require (lib "list.ss"))

  ;; list->generator: (listof X) (-> Y) -> (union X Y)
  ;; returns a generator function that, when called, returns successive
  ;; elements of the list.  When the list is exhausted, returns the
  ;; results of applying finished-thunk.
  (define (list->generator list finished-thunk)
    (letrec ([entry-point
              (lambda ()
                (cond
                  [(restoring-from-save?) (continue-from-restore-point!)]
                  [else (do-work list)]))]
             [saved-point (void)]
             [restoring-from-save? (lambda () (not (void? saved-point)))]
             [continue-from-restore-point! (lambda () (saved-point))]
             [save-point! (lambda (f) (set! saved-point f))]
             [do-work
              (lambda (list)
                (cond
                  [(empty? list) (finished-thunk)]
                  [else
                   (save-point! (lambda () (do-work (rest list))))
                   (first list)]))])
      entry-point)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


We're not really using continuations yet, although we'll start to
introduce it soon.  *grin*

But I hope the rest of the code is clear: we're iterating across the list,
and right before we return elements back, we record what we need to do
next, so that when we call the generator back, the entry-point can pick up
where it left off.

Let's try it out:

;;;;;;
> (define elts (list->generator '(hello world) (lambda () 'done)))
> (list (elts) (elts) (elts))
(hello world done)
;;;;;;


Ok, so it works.  But now let's slowly introduce elements of continuations
into the system and see how far we can take this.


First, let's use what we already know about "escaping" continuations and
modify the entry point slightly, so that results that we compute are
explicitely thrown up to the caller:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (define (list->generator list finished-thunk)
    (letrec ([entry-point
              (lambda ()
                (call/cc (lambda (k)
                           (set! caller k)
                           (cond
                             [(restoring-from-save?)
                              (continue-from-restore-point!)]
                             [else (do-work list)]))))]
             [caller (void)]
             [saved-point (void)]
             [restoring-from-save? (lambda () (not (void? saved-point)))]
             [continue-from-restore-point! (lambda () (saved-point))]
             [save-point! (lambda (f) (set! saved-point f))]
             [do-work
              (lambda (list)
                (cond
                  [(empty? list) (caller (finished-thunk))]
                  [else
                   (save-point! (lambda () (do-work (rest list))))
                   (caller (first list))]))])
      entry-point))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Here, we've made changes to ENTRY-POINT and DO-WORK, but this should still
have the same effect as before.  do-work uses CALLER to throw values back,
but otherwise, this shouldn't be too inescapable.  *grin*


Next, let's look at DO-WORK:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
             [do-work
              (lambda (list)
                (cond
                  [(empty? list) (caller (finished-thunk))]
                  [else
                   (save-point! (lambda () (do-work (rest list))))
                   (caller (first list))]
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


This almost looks like a simple list traversal using what we understand
about structural recursion, except for the funky call to SAVE-POINT, where
we're explicitely building a lambda that tells the system what to do next.


Wouldn't it be nice if we didn't have to explicitely code that

    (lambda () (do-work (rest list)))

part?  It turns out that we can, if we take advantage of call/cc:

             [do-work
              (lambda (lst)
                (cond
                  [(empty? lst) (caller (finished-thunk))]
                  [else
                   (call/cc (lambda (k)
                              (save-point! k)
                              (caller (first lst))))
                   (do-work (rest lst))]))]

If we use call/cc, the bound 'k' here has a similar effect to the one we
explicitely built up in the last code snippet.  call/cc builds a functions
that captures the "rest-of-the-computation" as 'k', and in this body of
the ELSE here, 'k' has the effect of:

    (lambda (continuation-arg) (do-work (rest lst)))

which is what we want.

If we make this change, though, we do have to update
CONTINUE-FROM-SAVE-POINT! to pass in some sentinel value, since all
continuations have to take in an argument.


Let's show what list->generator looks like now.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (define (list->generator list finished-thunk)
    (letrec ([entry-point
              (lambda ()
                (call/cc (lambda (k)
                           (set! caller k)
                           (cond
                             [(restoring-from-save?)
                              (continue-from-restore-point!)]
                             [else (do-work list)]))))]
             [caller (void)]
             [saved-point (void)]
             [restoring-from-save? (lambda () (not (void? saved-point)))]
             [continue-from-restore-point! (lambda () (saved-point 'resume))]
             [save-point! (lambda (f) (set! saved-point f))]
             [do-work
              (lambda (lst)
                (cond
                  [(empty? lst) (caller (finished-thunk))]
                  [else
                   (call/cc (lambda (k)
                              (save-point! k)
                              (caller (first lst))))
                   (do-work (rest lst))]))])
      entry-point))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


Note here that CONTINUE-FROM-RESTORE-POINT! is just passing the 'resume
symbol as a sentinel just to keep things going: that value isn't really
used otherwise here.  (Other applications of continuations do make use of
passing values, like the CALLER continuation that we've seen, so it's just
our SAVED-POINT that doesn't care.)


Does this make sense so far?  Please feel free to ask questions about
this, because it took me a few readings too to get this right.  *grin*



There's actually a few more cute things we can do here.  One thing is that
we can refactor out the subexpression:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
                   (call/cc (lambda (k)
                              (save-point! k)
                              (caller (first lst))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


and give it a good name, say, YIELD:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
                   (let ((yield
                          (lambda (v)
                            (call/cc (lambda (k)
                                       (save-point! k)
                                       (caller v)))))
                     (yield (first lst)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


Let's see what things look like now:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (define (list->generator lst finished-thunk)
    (let
        ([caller (void)]
         [saved-point (void)])
      (letrec ([entry-point
                (lambda ()
                  (call/cc (lambda (k)
                             (set! caller k)
                             (cond
                               [(restoring-from-save?)
                                (continue-from-restore-point!)]
                               [else (do-work lst)]))))]
               [restoring-from-save?
                (lambda () (not (void? saved-point)))]
               [continue-from-restore-point!
                (lambda ()
                  (saved-point 'resume))]
               [save-point!
                (lambda (f) (set! saved-point f))]
               [yield
                (lambda (v)
                  (call/cc (lambda (k)
                             (save-point! k)
                             (caller v))))]
               [do-work
                (lambda (lst)
                  (cond
                    [(empty? lst)
                     (let forever () (yield (finished-thunk)) (forever))]
                    [else
                     (yield (first lst))
                     (do-work (rest lst))]))])
        entry-point)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


(I made some cosmetic changes: I lifted out the LETs for CALLER and
SAVED-POINT since they're not really functions and don't need to be
LETRECed.  I also modified the empty case to continue throwing the
finished-thunk, just in case the caller is silly enough to try pulling
more elements off.)


But we can actually go a little further: notice that the only free
variable in DO-WORK is YIELD, so we can do something like:

              (let ([do-work (lambda (yield) (lambda (lst) ...))]) ...)

and have DO-WORK take in the yield as an argument.



If we make this change, we might as well lift the whole thing up a bit...

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(module generator-example mzscheme
  (provide list->generator)
  (provide make-generator)
  (require (lib "list.ss"))

  (define (list->generator lst finished-thunk)
    (letrec ([f (lambda (yield)
                  (let loop ([lst lst])
                    (cond
                      [(empty? lst)
                       (let forever ()
                         (yield (finished-thunk)) (forever))]
                      [else
                       (yield (first lst))
                       (loop (rest lst))])))])
      (make-generator f)))

  (define (make-generator seed-function)
    (let
        ([caller (void)]
         [saved-point (void)])
      (letrec ([entry-point
                (lambda ()
                  (call/cc (lambda (k)
                             (set! caller k)
                             (cond
                               [(restoring-from-save?)
                                (continue-from-restore-point!)]
                               [else (do-work)]))))]
               [restoring-from-save?
                (lambda () (not (void? saved-point)))]
               [continue-from-restore-point!
                (lambda ()
                  (saved-point 'resume))]
               [save-point!
                (lambda (f) (set! saved-point f))]
               [yield
                (lambda (v)
                  (call/cc (lambda (k)
                             (save-point! k)
                             (caller v))))]
               [do-work (lambda () (seed-function yield))])
        entry-point))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



Not only is list->generator a little cleaner, but we now have a general
generator-making function called MAKE-GENERATOR:

;;;;;;
> (define ints
    (make-generator
     (lambda (yield)
       (let loop ((n 0))
         (yield n)
         (loop (add1 n))))))
> (ints)
0
> (ints)
1
> (ints)
2
;;;;;;



Anyway, hope this helps!