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