[Python-Dev] A "real" continuation example

[rushing at nightmare.com]

Tim Peters writes:
 > The Scheme solution was the hardest to write, but is a largely
 > mechanical transformation of a recursive fringe-lister that
 > constructs the entire fringe in one shot.  Continuations are used
 > twice: to enable the recursive routine to resume itself where it
 > left off, and to get each leaf value back to the caller.  Getting
 > that to work required rebinding non-local identifiers in delicate
 > ways.  I doubt the intent would be clear to an average Scheme
 > programmer.

It's the only way to do it - every example I've seen of using call/cc
looks just like it.

I reworked your Scheme a bit.  IMHO letrec is for compilers, not for
people.  The following should be equivalent:

(define (list->generator x)
  (let ((produce-value #f))

    (define (looper x)
      (cond ((null? x) 'nada)
	    ((list? x)
	     (looper (car x))
	     (looper (cdr x)))
	    (else
	     (call/cc
	      (lambda (here)
		(set! getnext (lambda () (here 'keep-going)))
		(produce-value x))))))

    (define (getnext)
      (looper x)
      (produce-value #f))

    (lambda ()
      (call/cc
       (lambda (k)
	 (set! produce-value k)
	 (getnext))))))

(define (display-fringe x)
  (let ((g (list->generator x)))
    (let loop ((elt (g)))
      (if elt
	  (begin
             (display elt)
             (display " ")
             (loop (g)))))))

(define test-case '((1 ((2 3))) (4) () (((5)) 6)))
(display-fringe test-case)

 > So what would this look like in Continuation Python?

Here's my first hack at it.  Most likely wrong.  It is REALLY HARD to
do this without having the feature to play with.  This presumes a
function "call_cc" that behaves like Scheme's.  I believe the extra
level of indirection is necessary. (i.e., call_cc takes a function as
an argument that takes a continuation function)

class list_generator:

    def __init__ (x):
        self.x = x
        self.k_suspend = None
        self.k_produce = None

    def walk (self, x):
        if type(x) == type([]):
            for item in x:
                self.walk (item)
        else:
            self.item = x
            # call self.suspend() with a continuation
            # that will continue walking the tree
            call_cc (self.suspend)

    def __call__ (self):
        # call self.resume() with a continuation
        # that will return the next fringe element
        return call_cc (self.resume)

    def resume (self, k_produce):
        self.k_produce = k_produce
        if self.k_suspend:
            # resume the suspended walk
            self.k_suspend (None)
        else:
            self.walk (self.x)

    def suspend (self, k_suspend):
        self.k_suspend = k_suspend
        # return a value for __call__
        self.k_produce (self.item)

Variables hold continuations have a 'k_' prefix.  In real life it
might be possible to put the suspend/call/resume machinery in a base
class (Generator?), and override 'walk' as you please.

-Sam