Experimenting with Lisp variants eventually led me to the programming construct of continuations as popular with the Scheme programming language. In case you’re not familiar with the construct, it’s a control construct (like the if statement or exception dispatch) that works a little like this:
Say you’re in the kitchen in front of the refrigerator, thinking about a sandwitch. You take a continuation right there and stick it in your pocket. Then you get some turkey and bread out of the refrigerator and make yourself a sandwitch, which is now sitting on the counter. You invoke the continuation in your pocket, and you find yourself standing in front of the refrigerator again, thinking about a sandwitch. But fortunately, there’s a sandwitch on the counter, and all the materials used to make it are gone. So you eat it. 🙂
A discussion on LtU goes on a bit longer, but that’s not the whole of it. Exceptions can be modeled as escaping continuations; co-routines and threads as mutually invoking continuations. Continuations are a powerful tool, that can be difficult to understand. This was my effort to understand them.
My exercise for this is implementing generators — called iterators/enumerators in C#, input iterators in C++ — using continuations in Scheme. The contract for my generators will be C++ iterator-like. An iterator value is a function; invoked with ‘get is like dereferncing, and will return the current element; invoked with ‘next will return the next iterator value or #f false.
Some code to illustrate my goal:
(it 'get) ; get current element (set! it (it 'next)) ; move forward (when (not it) (done)) ; detecting end of iteration
And some pseudo code, C# iterator style:
(define (gen3) (let loop ((x 1)) (yield x) (unless (= x 3) (loop (+ x 1)))))
The advantage of this interface design, the C++ iterator concept, is that code can be made to function with multi-pass iterators, iterators that can be saved for resuming iteration or refer to a particular storage location in a container.
First try
(define (writeln x) (display x) (newline)) (define call/cc call-with-current-continuation) ; generate 1 2 3 as a sequence using special iterators ; broken: only works from repl because returning to the previous (define (gen3a) (call/cc (lambda (exit) (let loop ((x 1)) (call/cc (lambda (resume) (exit (lambda (msg) (cond ((eqv? msg 'get) x) ((eqv? msg 'next) (resume '())) (#t (raise-error))))))) (unless (= x 3) (loop (+ x 1)))) (exit #f)))) ; and try out this generator (writeln "gen3a") (let continue ((it (gen3a))) (when it (writeln (it 'get)) (continue (it 'next))))
Paste this into the Scheme REPL and it runs, printing 1 2 3. But does it work? I first tried this code out thinking I was halfway there, to see how far it would get. I was rather surprised when it printed the right answer.
So what’s really happening here? The first call/cc sets up a fast-path for returning from the function — this is an escaping continuation. Calling ‘exit’ will now return immediatetly from the gen3 call.
The let begins the loop, just as it did in the earlier pseudo-code. The next call/cc with resume forms the pseudo-code yield, exiting with a lambda function. The magic in this lambda is the resume parameter. It lets us pick back up again right in the middle of the loop!
It seems like everything is ready to go. The returned lambda becomes the iterator object, and when you invoke with ‘next, it picks back up in the middle of the loop. So what’s the problem?
The REPL Bug
The issue is really subtle, so don’t blink. Exit is never modified, right? So what happens when we exit the second time through the loop? Well, we resume into the earlier iteration through. Luckily for the REPL case, that earlier iteration is the same as the current one, but this might not always be the case. To see this, you first need something that can see the difference:
(let continue ((it (gen3a)) (ix 1)) (when it (begin (writeln (list ix (it 'get))) (continue (it 'next) (+ ix 1)))))
In this loop, each call to (it ‘get) should be in a different context for the ix integer. As a result, this prints (1 1) (1 2) (1 3) — the same value for ix each iteration. The second call returns to the wrong place! Even “weirder” things can happen too, all due to using that exit continuation more than once.
The Fix
One potential fix is to replace the exit routine, each iteration, with a new continuation to return to the current caller instead of the initial one. When we do this, this iterator and its use snap into place, working as intended:
(define (gen3b) (call/cc (lambda (exit) (let loop ((x 1)) (set! exit (call/cc (lambda (resume) (exit (lambda (msg) (cond ((eqv? msg 'get) x) ((eqv? msg 'next) (call/cc (lambda (new-exit) (resume new-exit)))) (#t (raise-error)))))))) (unless (= x 3) (loop (+ x 1)))) (exit #f))))(let continue ((it (gen3b)) (ix 1)) (when it (begin (writeln (list ix (it 'get))) (continue (it 'next) (+ ix 1)))))
Unfortunately, we’ve introduced side-effects, cementing the iterator as an input iterator, non-restartable. On a positive note though, the previous loop now works.
This is a bit ugly at this point — three calls to the mystifying call-with-current-continuation — but it was interesting to me, and offered . This code isn’t complete, I feel like a bull in a china shop, or maybe a bull writing cobol. Opinions and one-up-manship welcome. Some ideas:
- Use fewer call/cc operations to do the same thing. Three definitely feels overkill.
- Finish the goal with some nice define-syntax to make this iterator feel like part of the language, or at least language-extension-esq (ala C# 2.0 iterator syntax)
- This iterator was written side-effect free up until the set! exit, breaking restart. Rewrite this generator to be restartable, or in C++ iterator terminology, fulfilling forward iterator requirements.
Note: examples here run under PLT Scheme. YMMV.