A "real" continuation example
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
[Sam, takes up the Continuation Python Challenge] Thanks, Sam! I think this is very helpful.
... It's the only way to do it - every example I've seen of using call/cc looks just like it.
Same here -- alas <0.5 wink>.
I reworked your Scheme a bit. IMHO letrec is for compilers, not for people. The following should be equivalent:
I confess I stopped paying attention to Scheme after R4RS, and largely because the std decreed that *so* many forms were optional. Your rework is certainly nicer, but internal defines and named let are two that R4RS refused to require, so I always avoided them. BTW, I *am* a compiler, so that never bothered me <wink>.
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.
Fully understood. It's also really hard to implement the feature without knowing how someone who wants it would like it to behave. But I don't think anyone is getting graded on this, so let's have fun <wink>. Ack! I have to sleep. Will study the code in detail later, but first impression was it looked good! Especially nice that it appears possible to package up most of the funky call_cc magic in a base class, so that non-wizards could reuse it by following a simple protocol. great-fun-to-come-up-with-one-of-these-but-i'd-hate-to-have-to-redo- from-scratch-every-time-ly y'rs - tim
Sam> I reworked your Scheme a bit. IMHO letrec is for compilers, not for Sam> people. Sam, you are aware of course that the timbot *is* a compiler, right? ;-) >> So what would this look like in Continuation Python? Sam> Here's my first hack at it. Most likely wrong. It is REALLY HARD to Sam> do this without having the feature to play with. The thought that it's unlikely one could arrive at a reasonable approximation of a correct solution for such a small problem without the ability to "play with" it is sort of scary. Skip Montanaro | Mojam: "Uniting the World of Music" http://www.mojam.com/ skip@mojam.com | Musi-Cal: http://www.musi-cal.com/ 518-372-5583
[Tim]
So what would this look like in Continuation Python?
[Sam]
Here's my first hack at it. Most likely wrong. It is REALLY HARD to do this without having the feature to play with.
[Skip]
The thought that it's unlikely one could arrive at a reasonable approximation of a correct solution for such a small problem without the ability to "play with" it is sort of scary.
Yes it is. But while the problem is small, it's not easy, and only the Icon solution wrote itself (not a surprise -- Icon was designed for expressing this kind of algorithm, and the entire language is actually warped towards it). My first stab at the Python stack-fiddling solution had bugs too, but I conveniently didn't post that <wink>. After studying Sam's code, I expect it *would* work as written, so it's a decent bet that it's a reasonable approximation to a correct solution as-is. A different Python approach using threads can be built using Demo/threads/Generator.py from the source distribution. To make that a fair comparison, I would have to post the supporting machinery from Generator.py too -- and we can ask Guido whether Generator.py worked right the first time he tried it <wink>. The continuation solution is subtle, requiring real expertise; but the threads solution doesn't fare any better on that count (building the support machinery with threads is also a baffler if you don't have thread expertise). If we threw Python metaclasses into the pot too, they'd be a third kind of nightmare for the non-expert. So, if you're faced with this kind of task, there's simply no easy way to get it done. Thread- and (it appears) continuation- based machinery can be crafted once by an expert, then packaged into an easy-to-use protocol for non-experts. All in all, I view continuations as a feature most people should actively avoid! I think it has that status in Scheme too (e.g., the famed Schemer's SICP textbook doesn't even mention call/cc). Its real value (if any <wink>) is as a Big Invisible Hammer for certified wizards. Where call_cc leaks into the user's view of the world I'd try to hide it; e.g., where Sam has 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) I'd do def walk(self, x): if type(x) == type([]): for item in x: self.walk(item) else: self.put(x) where "put" is inherited from the base class (part of the protocol) and hides the call_cc business. Do enough of this, and we'll rediscover why Scheme demands that tail calls not push a new stack frame <0.9 wink>. the-tradeoffs-are-murky-ly y'rs - tim
participants (3)
-
rushing＠nightmare.com -
Skip Montanaro -
Tim Peters