CSC 324 Tutorial Week 7
=======================

Generators
==========
Some languages (e.g. python, C#) provide generators: procedures that
 can return and be resumed. Prolog's main flow of control is a
 generalization of this, so it's worth looking at generators simply
 to warm up to Prolog. (We'll do Prolog in a few weeks.)

Goal
----
The goal is to write:

  (define (p)
    (yield 'hello)
    (yield 'there)
    (yield 'world))

 and have the following happen:

  (p) => 'hello
  (p) => 'there
  (p) => 'world

Preliminaries
-------------
Recall that call-with-current-continuation (call/cc) needs a procedure
 to call. To avoid typing lambda... all the time,
 Let's define a convenient shorthand:

  (define-syntax let/cc
    (syntax-rules ()
      ((let/cc name body ...)
       (call/cc (lambda (name) body ...)))))

(let/cc name body ...) evaluates body ... with name bound to the
 continuation of the entire expression.
In body ..., evaluating (name v) now means:

  - come back to this let/cc
  - *don't* evaluate body ... to get the result
  - use v as the result instead

First attempt at yielding
-------------------------
(define (p)
  (let/cc yield
    (yield 'hello)
    (yield 'there)
    (yield 'world)))

(p) => 'hello
(p) => 'hello
etc.

We need to save the point in execution where we returned from.
 Let's store the continuation right as we call yield, so we can
 resume at this point.

Second attempt
--------------
(define p
  (let ((resume #f)) ; lives between calls to p
    (lambda ()
      (let/cc yield           ; note continuation to return from this call of p
        (if resume (resume)   ; after first call, resume is non-#f, so call resume to
                              ;  jump back to middle of first call, with no value
          (begin              ; gets here only during first call, afterwards blocked by resume
            (let/cc k         ; set resume to continuation for result of first statement in begin
              (set! resume k) ; second call will use it to come back and skip the first statement
              (yield 'hello)) ; jump to yield of first call: not what we want
            (let/cc k
              (set! resume k)
              (yield 'there))
            (let/cc k
              (set! resume k)
              (yield 'world))))))))

(begin (display (p)) (display "Returned from first call to p"))

  => 'hello ; also displays "Returned from first call to p"

(p)

  => 'there ; also displays "Returned from first call to p"

(begin (display (p)) (display "Returned from third call to p"))

  => 'world ; also displays "Returned from first call to p"

Problem: yield in the body returns to our original continuation, stored 
 when p was first called. We need to update yield each time p is called.

Third attempt
-------------
(define p
  (let ((resume #f)
        (yield 'uninitialized)) ; same variable seen by all calls to p
    (lambda ()
      (let/cc k
        (set! yield k) ; change yield on every call
        (if resume (resume)
          (begin
            (let/cc k
              (set! resume k)
              (yield 'hello))
            (let/cc k
              (set! resume k)
              (yield 'there))
            (let/cc k
              (set! resume k)
              (yield 'world))))))))

Works! A little syntax might make it clearer:

  (define-syntax set/cc!
    (syntax-rules ()
      ((set/cc! name body ...)
       (let/cc k (set! name k) body ...))))

(define p
  (let ((resume #f)
        (yield 'uninitialized))
    (lambda ()
      (set/cc! yield
        (if resume (resume)
          (begin
            (set/cc! resume
              (yield 'hello))
            (set/cc! resume
              (yield 'there))
            (set/cc! resume
              (yield 'world))))))))

Fourth attempt: cleaning it up
------------------------------
Let's make yield a procedure to do the set and yield.

(define p
  (let ((resume #f)
        (return 'uninitialized))
    (lambda ()
      (set/cc! return
        (if resume (resume)
          (let ((yield
                  (lambda (result)
                    (set/cc! resume
                    (return result)))))
            (yield 'hello)
            (yield 'there)
            (yield 'world)))))))

Fifth attempt: making it into a syntax
--------------------------------------
Now we can make a syntax.

In the syntax-rules system, the user of the syntax must supply
 the name to use for the yield procedure.

(define-syntax generator
  (syntax-rules ()
    ((generator yield-name body ...)
     (let ((resume #f)
           (return 'uninitialized))
       (lambda ()
         (set/cc! return
           (if resume (resume)
             (let ((yield-name
                     (lambda (result)
                       (set/cc! resume
                         (return result)))))
               (begin body ...)
               (set/cc! resume)
               (return)))))))))

(define p
  (generator yield
    (yield 'hello)
    (yield 'there)
    (yield 'world)))