Generators are useful constructions for producing values without having to bundle
up all the values in a list and returning the list. The generator idiom has been
added to ruby and python by adding the `yield' keyword, but these languages do not
allow you to derive the generator form yourself. It is widely known that generators
can be built using delimited continuations but a naive implementation can have subtle
problems.

First an example of using a generator:

 (define counter
   (generator
     (let loop ([current 0])
       (yield current)
       (loop (add1 current)))))

  > (counter)
  0
  > (counter)
  1
  > (counter)
  2
  
Here is the same thing in ruby and python:

Ruby:
  def counter
    current = 0
    while true
      yield current
      current += 1
    end
  end

Python:
  def counter():
    current = 0
    while True:
      yield current
      current += 1

Delimited continuations, rather than full continuations, are necessary for implementing
generators because ... Here is a naive implementation using the shift/reset control
operators:

(define-syntax-rule (generator-no-tag body0 body ...)
  (define yielder
    (let ([yield (lambda (value) (shift k (set! cont k) value))])
      yield))
  (splicing-syntax-parameterize ([yield (make-rename-transformer #'yielder)])
    (define (cont)
      (reset
	(let ([retval (begin body0 body ...)])
	  ;; normal return:
	  (set! cont (lambda () retval))
	  retval))))
  (define (generator) (cont))
  generator)

What it is doing is returning a function that when called will execute the body passed
to the macro. Whenever the user code calls `yield' the current continuation will be
captured by `shift' and set the `cont' variable to it and finally returning the value
pass to `yield' to whoever called the generator in the first place. Here is an
illustration of the generator at runtime.

(generator
  ;; <-- executing (cont) starts here
  (let loop ([counter 0])
    (yield counter)
    (loop (add1 counter))))

When the yield statement is hit `cont' changes

(generator
  (let loop ([counter 0])
    (yield counter)
    ;; <-- (cont) is now here
    (loop (add1 counter))))

So when the generator is called again it will start from the new `cont', loop once,
and then counter will be 1 instead of 0. This is fine and seems to work but things
start breaking when generators are nested.

(generator
  (let ([y1 yield])
    (let ([g2 (generator
		(let ([y2 yield])
		  (for ([i (in-range 0 num)])
		       (y1 i))))])
      (g2))))

Repeatedly calling this generator produces 0 when it should produce the sequence
of values from 0 to `num'. The reason for this can be seen by following `cont'.
At the start:

(generator
  ;; <-- (cont) is here
  (let ([y1 yield])
    (let ([g2 (generator
		(let ([y2 yield])
		  (for ([i (in-range 0 num)])
		       (y1 i))))])
      (g2))))


One step:

(generator
  ;; <-- (cont) is here
  (let ([y1 yield])
    (let ([g2 (generator
		(let ([y2 yield])
		  (for ([i (in-range 0 num)])
		       (y1 i))))])
      (g2))))

After (y1 i) is invoked cont the outer cont moves to the inside generator

(generator
  (let ([y1 yield])
    (let ([g2 (generator
		(let ([y2 yield])
		  (for ([i (in-range 0 num)])
		       (y1 i))
		       ;; <-- (cont) is here
		       ))])
      (g2))))

`y1' is really a call to `shift' which moves control to the closest delimited
continuation but instead of choosing the outer delimited continuation, the inner
one gets chosen instead. Essentially our problem looks like this

(reset
  (let ([y1 (shift ...)])
    (reset
      (let ([y2 (shift ...)])
	(y1)))
    ... ;; rest
    ))

Invoking y1 inside two resets only jumps out of one of them, the inner one. After
invoking y1 we now have

(reset
  (let ([y1 (shift ...)])
    ... ;; rest
    ))

So invoking y1 does not return values for the outer generator as one might expect.
Invoking y1 does set the outer `cont', though, so isn't the position within the
generator correct? Well yes in fact after y1, cont is pointing at the right place.
Invoking the generator again should start from that cont and produce the value 1. In
our current version it still produces 0 though. This is because after y1 is called the
the rest of the body of the outer generator is executed. When the body finishes `cont'
is set to the end of the body so that the last result is always returned. Recall the
macro looks like this

(define (cont)
  (reset
    (let ([retval (begin body0 body ...)])
      ;; normal return:
      (set! cont (lambda () retval))
      retval)))

Whatever the last value of the generator body is, that will be the value produced by
the generator after the generator has run out of body expressions. If we didn't reset
`cont' after the main body had finished then we could re-execute the body after the
last yield statement which is not what we want. For example, if we took out the set!
inside the macro so we have

(define (cont)
  (reset
    (let ([retval (begin body0 body ...)])
      retval)))

And try this generator

(generator
  (yield 1)
  (yield 2)
  (printf "i am done\n")
  0)

We see this output

>
 1
 2
 i am done
 0
 i am done
 0

"i am done" is printed twice because the last yield, (yield 2), sets cont such that
everything after the yield is executed. This isn't what you want, but even if you did
things are still broken. If we try our generator macro (without tags and set!) and try
to write a generator that invokes two generators we won't get the expected output.

(generator
  (let ([y1 yield])
    (let ([g1 (generator
		(let ([y2 yield])
		  (for ([i (in-range 0 4)])
		       (y1 i))))]
	  [g2 (generator
		(let ([y2 yield])
		  (for ([i (in-range 0 4)])
		       (y1 i))))])
      (printf "x1\n")
      (g1)
      (printf "x2\n")
      (g2)))))

Invoking this generator a few times

>
 x1
 x2
 0
 1
 2
 3

We should have seen some numbers from the (g2) call after x1 is printed but we didn't.
The body of the outer generator is executed in its entirety because the yield inside
the inner generator is caught by the reset of the inner generator.

The solution to this is to use identifiers that reset and shift respond to so that a
shift to identifier `k' will return control to the reset that also uses identifier `k'.
In other words, this code will do what we want

(reset-at k1
  (let ([y1 (shift-at k1 ...)])
    (reset-at k2
      (let ([y2 (shift-at k2 ...)])
	(y1 ...)))))

A simple change to our macro gives us this:

(define-syntax-rule (generator body0 body ...)
  (let ([tag (make-continuation-prompt-tag)])
    (define yielder
      (let ([yield (lambda (value) (shift-at tag k (set! cont k) value))])
	yield))
    (splicing-syntax-parameterize ([yield (make-rename-transformer #'yielder)])
      (define (cont)
	(reset-at tag
		  (let ([retval (begin body0 body ...)])
		    ;; normal return:
		    (set! cont (lambda () retval))
		    retval))))
    (define (generator) (cont))
    generator))

Now our nested generator works properly

(generator
  (let ([y1 yield])
    (let ([g2 (generator
		(let ([y2 yield])
		  (for ([i (in-range 0 num)])
		       (y1 i))))])
      (g2)))))

And invoking the inner generator twice also works properly

(generator
  (let ([y1 yield])
    (let ([g1 (generator
		(let ([y2 yield])
		  (for ([i (in-range 0 4)])
		       (y1 i))))]
	  [g2 (generator
		(let ([y2 yield])
		  (for ([i (in-range 0 4)])
		       (y1 i))))])
      (printf "x1\n")
      (g1)
      (printf "x2\n")
      (g2))))

>
 x1
 0
 1
 2
 3
 x2
 0
 1
 2
 3