Continuation kata

If you have a little Scheme under your belt, just plunge into the challenge right now:

We want to find three integers, x y and z such that both are in the range [2,9] and that they are the lengths of the sides of a right triangle (x^2 = y^2 + z^2). The challenge is to write two procedures, in-range and fail such that the solution to the problem looks like this:

(let ((x (in-range 2 9))
      (y (in-range 2 9))
      (z (in-range 2 9)))
  (if (= (* x x) (+ (* y y) (* z z)))
      (list x y z)
      (fail "no solution")))

In other words, we are after an elegant way of implementing search backtracking: the possible values of the (x, y, z) triplets must be checked in turn, until a solution is found or we exhaust the search space. This is the kind of problem that declarative languages like Prolog solve in a breeze. Scheme does not fare bad, either: the right solution is just a screenful long. Keep on reading if you feel like getting some hints.

I’ve stolen this little exercise from an excellent talk by Marc Feeley on writing a Scheme to C compiler. The example pops up when Marc is discussing what makes such a compiler tricky (that is, what Scheme features are missing in C): tail calls, garbage collection, closures and first class continuations. So here goes the first hint: the solution uses call/cc.

Continuations 101

I couldn’t put a finger on it, but there’s something pesky about continuations: in my experience, they’re hard to grasp at first. And yet, the concept is quite simple: whenever you are evaluating an expression E, there’s someone waiting to do something with the value of E; for instance, in the process of evaluating:

(+ 3 (* 5 4))

if you take E to be (* 5 4), the interpreter is waiting for your result to add 3… this thing to be done to the result of evaluating a (sub)expression can be, quite naturally, represented by a procedure that takes a single argument; in our example, this procedure could be:

(lambda (v) (+ 3 v))

or, if you are evaluating the whole thing on a REPL toplevel that will print the result, maybe something roughly equivalent to:

(lambda (v) (print (+ 3 v)))

It is this (usually invisible) procedure what we call the current continuation. Every expression has a continuation, but in many languages it is only implicit. Scheme gives you the possibility of accessing it. If you write:

(+ 3 (call/cc (lambda (cont) (* 5 4))))

that could be translated as

(+ 3
   (let ((cont (lambda (v) (+ 3 v)))
      (* 5 4)))

Of course, things get only interesting when you use cont; for instance, it is hopefully clear that

(+ 3 (call/cc (lambda (cont) (* 5 4) (cont 18))))

evaluates to 21. Besides writing silly examples and bore your readers to tears, you can put this stuff to good use in a variety of ways. The most immediate is to early scape from a long computation. This procedure multiplies all the elements in a given list:

(define (mult lon)
  (cond ((null? lon) 1)
        ((zero? (car lon)) 0)
        (else (* (car lon) (mult (cdr lon))))))

but it will do a lot of useless work when lon contains a 0. First class continuations allow a better way:

(define (mult-k lon cont)
  (cond ((null? lon) 1)
        ((zero? (car lon)) (cont 0))
        (else (* (car lon) (mult-k (cdr lon) cont)))))

(define (mult lon) (call/cc (lambda (cont) (mult-k lon cont))))

If you understand why this is better than the previous version, you’re on your way to understanding continuations as non-local exits. And if by now you’re thinking that continuations are not, after all, a big deal, quick tell me what

(((call/cc (lambda (k) k)) (lambda (x) x)) "HEY!")

evaluates to, and why. By the way, this nice micro-kata is from TSPL’s section on continuations, which provides a nice, if brief, introduction to call/cc, including a description of another typical use case: the implementation of threading via coroutines. A more extended (but still not too long) discussion of the very same issues can be found in Dann Friedman’s beautiful paper Applications of Continuations.

Finally, if you have a little time in your hands, read through this interesting ll1 mail thread, where guys like Mathias Felleisen, Avi Bryant or Paul Graham have their say on continuations and their uses.

Backtracking

Since coroutines are not needed to solve our original kata, let me gloss over them and jump to the next typical use of continuations: backtracking. A key thing to remember about call/cc is that the continuation passed to the lambda form is a first class value. Among other things, that means that you can store it and use it in a totally unrelated context. Or, in other words, Scheme introduces time-travel in your toolset, with its associated wonders (as in Schelog, a Prolog implemented in Scheme) and headaches.

Let’s see how backtracking can be implemented with the aid of persistent continuations using an example adapted from Jacques Chazarain’s book Programmer avec Scheme (which, by the way, makes for an excellent second book on Scheme, provided you read French). Writing a procedure that looks for the first occurrence of an element in a list that satisfies a given predicate is a piece of cake:

(define (search lst p?)
  (cond ((null? lst) #f)
        ((pair? lst) (or (search (car lst) p?)
                         (search (cdr lst) p?)))
        ((p? lst) lst)
        (else #f)))

where we accept list of lists too. But what if i want to get all findings one by one? I’d like to have a solution generator that returns a procedure returning, in successive calls, each of the occurrences of a solution in the given list. That is, we want to be able to write code like this one:

(define solutions
  (search-generator '(0 ((1 a) 2) b (b c) (((6)))) number?)
(solutions) => 0
(solutions) => 1
(solutions) => 2
(solutions) => 6
(solutions) => 'done

Persistent continuations allow a very clean implementation of search-generator. The strategy is to start the search, and each time we find an element in the list satisfying the predicate store the current continuation (which will keep on searching for more solutions) for later invocations. We then return a procedure that calls the continuation and stores a new one which will resume the search with the rest of the list. You can have a little fun trying to find the solution before reading it below. Or, if you get stuck, to read Ferguson and Duego’s excellent Call with Current Continuation Patterns, where you’ll find examples of call/cc in action.
Got your answer? Well, let’s compare:

(define (search-generator lst p?)
  (let ((success '?)) ;; placeholder for the current continuation
    (letrec ((cont-success ;; next continuation
              (lambda (x) (search lst)))
             (search
              (lambda (elem)
                (cond ((null? elem) 'done)
                      ((pair? elem) (search (car elem))
                                    (search (cdr elem)))
                      ((p? elem) (call/cc
                               (lambda (k) ;; next search will continue from here
                                 (set! cont-success k)
                                 (success elem))))
                      (else 'done)))))
      (lambda () (call/cc (lambda (k)
                       (set! success k)
                       (cont-success 'done)))))))

Once you grasp how this works, you have all the ingredients to solve our original kata.

Not only Scheme

There are other languages with support for first class continuations, SML/NJ and Ruby being the most salient cases. Besides, Seaside implements them for our beloved Smalltalk.

You don’t need call/cc to play some of the tricks discussed above. For instance, one can implement backtracking in Python (the linked article contains also an intro to continuations) or Standard SML (ditto, also with examples in Pascal, and, of course, SML), using a technique known as Continuation Passing Style, or CPS, that consist on passing explicitly the continuation to each of your functions. Explaining CPS would take another article, so, for now, i will let you explore it by yourself, but i’ll mention that armed with CPS you can, essentially, play all the call/cc tricks. A few years ago, type theorist extraordinaire Benjamin C. Pierce asked in the Caml mailing list about cool CPS usages, and took the time to summarize the responses he got. It contains pointers to many mind-bending readings.

The solution

I almost forgot: if you give up finding our kata’s solution or want to check it out, you’ll find it in Marc Feeley’s talk for the Montreal Scheme/Lisp Users Group. As i’ve mentioned, it deals with the implementation of a Scheme to C compiler (Marc is the lead developer of Gambit-C), which is based on CPS. The site contains links to the talk slides and videos, and a beautiful pure-scheme implementation of the compiler. Enjoy.

Tags: , , , ,

12 Responses to “Continuation kata”

  1. PDI^2 :: Continuation kata :: February :: 2006 Says:

    [...] Sono sempre più fan di Programming Musings , l’ultimo post: Continuation Kata sembra decisamente gustoso. Per ora mi sono ferameto al primo paragrafo perché devo dormire, ma direi che una soluzione forse potrebbe essere: [...]

  2. asdf Says:

    Does this count? It is only 15 lines, not a page.

    (define fail (lambda (x) x))
    (define (in-range a b)
      (call-with-current-continuation
       (lambda (k)
         (let ((i a)
    	   (fk fail))
           (call-with-current-continuation
    	(lambda (try)
    	  (set! fail
    		(lambda (result)
    		  (set! i (+ i 1))
    		  (if (> i b)
    		      (fk result)
    		      (try i))))
    	  (k i)))))))
    
  3. jao Says:

    Back at reddit, i’ve found this Haskell one liner:

    [(x,y,x) | x

    Beautiful (but then, see what katas are about).

  4. Jim Says:

    Your original search function doesn’t work–here’s a working version.

    (define (search lst p?)
      (cond ((null? lst) #f)
            ((pair? lst) (or (search (car lst) pred?)
                             (search (cdr lst) pred?)))
            ((pred? lst) lst)
            (else #f)))
    
  5. jao Says:

    Jim,

    oops, of course you’re right. I’ve corrected it in the post. Thanks for pointing it out.

  6. Jim Ursetto Says:

    Here is another solution to search-generator. Below, the call to yield and the outermost call/cc could actually be removed without affecting the result. Let’s assume we do so. As in the original search, the body of the (pred? …) clause will return L as the result of (search (car L)), which short-circuits the OR and exits the function immediately with that value. When resumed, #f is returned to the OR clause and the search resumes with (search (cdr L)). This is a special case which relies on the fact that we are not using recursion, and can short-circuit with OR; in general you can’t omit the yield.

    (define (search-generator L pred?)
      (let ((resume #f))
       (lambda ()
         (call/cc
          (lambda (yield)
            (if resume
                (resume #f)
                (let search ((L L))
                  (cond ((null? L) #f)
                        ((pair? L) (or (search (car L))
                                       (search (cdr L))))
                        ((pred? L)
                         (call/cc (lambda (k)
                                    (set! resume k)
                                    (yield L))))
                        (else #f)))))))))
    
  7. matthias Says:

    1. The Haskell one-liner is also available in PLT Scheme (DrScheme/Full Swindle):

    (list-of (list x y z)
        (x  i high) (generate i) (loop (+ i 1))))
        (fail)))
    
    (define *fail* (list (lambda (_) (error 'fail "no solution"))))
    
    (define (fail) [(begin0 (car *fail*) (set! *fail* (cdr *fail*))) 'continue])
    
  8. matthias Says:

    The Haskell one-liner is not a solution. Why?
    It is available in PLT Scheme (drscheme) and I bet other Scheme preludes, too.
    Here is a solution that is different from Marc’s but uses a bit more Scheme than he’d want for his talk:

    (define (in-range x low high)
      (let/ec esc
        (define (generate i)
          (let/cc k (set! *fail* (cons k *fail*)) (esc i)))
        (let loop ((i low))
          (unless (> i high) (generate i) (loop (+ i 1))))
        (fail)))
    
    (define *fail* (list (lambda (_) (error 'fail "no solution"))))
    
    (define (fail) [(begin0 (car *fail*) (set! *fail* (cdr *fail*))) 'continue])
    
  9. Kevin Greer Says:

    Below is my solution:

    (define fail '())
    (call/cc (lambda (k) (set! fail k)))
    
    (define (in-range-or-else s e else)
      (if (> s e)
          (begin (set! fail else) (else))
          (call/cc (lambda (k)
                 (set! fail (lambda () (k (in-range-or-else (+ s 1) e else))))
                 s))))
    
    (define (in-range s e) (in-range-or-else s e fail))
    

    I used an internal function in my solution but because I thought it might be useful on its own, I’ve exposed it. It is called in-range-or-else and it lets you provide the function to call on failure. The in-range function just calls this with ‘fail’.

    Here’s a similiar function called “in-list”:

    (define (in-list-or-else l else)
      (if (null? l)
          (begin (set! fail else) (else))
          (call/cc (lambda (k)
                 (set! fail (lambda () (k (in-list-or-else (cdr l) else))))
                 (car l)))))
    
    (define (in-list l) (in-list-or-else l fail))
    
  10. Peter Says:

    I apologize in advance for this not formatting correctly, but I have never left a comment before.

    While working on my solution I noticed that if the solution succeeds then some record of possible backtraking continuation is left, and thus if you try to run the program again it will produce strange results. One solution I thought of was a success function that wraps the correct result, however if you define a macro (called with-fail in my solution) that wraps the call you can get this effect, as well as be able to next backtracking functions.

    My macro is:

    (define-syntax with-fail
    (syntax-rules()
    ((with-fail body …)
    (fluid-let ((fail (lambda (x) x)))
    body …))))

    and the rest of the definitions are:

    (define fail (lambda (x) x))

    (define in-range
    (lambda (low high)
    (call/cc
    (lambda (outer)
    (if (

  11. Peter Says:

    apparently the lessthan is an error

    (define inrange
    (lambda (low high)
    (call/cc
    (lambda (outer)
    (if (lessthan low high)
    (begin
    (call/cc
    (lambda (inner)
    (let ((old fail)) (set! fail (lambda (x) (set! fail old) (inner))))
    (outer low)))
    (inrange (+ 1 low) high))
    high)))))


Leave a Reply

Gravatar
WordPress.com Logo

Please log in to WordPress.com to post a comment to your blog.

Twitter picture

You are commenting using your Twitter account. (Log Out)

Facebook photo

You are commenting using your Facebook account. (Log Out)

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 25 other followers