continuations and call/cc

You are on a desert island. There are ravenous lions and the bomb is about to go off. Your life now depends on teaching a complete ass fuck idiot what continuations are and how/when/where to use call/cc. Go!


The current status of /prog/ is such that I can post a dumb thread like this and actually improve the overall quality of the board, so no, I will not go back to /g/.

I'll give it my best dummies explanation, but I will probably fail.

A continuation is basically the work left to do when we have the result of an expression. If we have an expression (+ 3 (+ 2 1)), then when we are evaluating the subexpression (+ 2 1) we still have to add 3 to get the result. call/cc makes the continuation of the current expression available to us as a function.

Example.

(+ 3 (call/cc (lambda (k) (+ 2 1))))

At this point, the continuation k, is equivalent to a function (lambda (k) (+ 3 k)) and if k is called at any point in the body of the lambda, it will return immediately. If it is not called in the body of the lambda, it is implicitly called at the end. Thus the above expression is equivalent to

(+ 3 (call/cc (lambda (k) (k (+ 2 1)))))

With scheme, continuations are first class so you could pass them into/out of functions, store them away, use them in data structures, etc. I've seen several interesting uses of continuations, but one of the nicest was non-blind backtracking. Other uses are documented in the paper 'call with current continuation patterns'

Two further examples.
Say we wanted to multiply all the numbers of the list, but if the list contained a negative number we wanted to return that instead. We could do
(define (multiply listofnums)
  (call/cc (lambda (escape)
             (foldl (lambda (x y)
                      (if  (negative? x)
                           (escape x)
                           (* x y)))
                    1
                    listofnums))))
>(multiply '(1 2 3 4 5 6))
720
>(multiply '(1 2 -4 4 5 6))
-4
Another example is to use it for backtracking, the following is not efficient and you should really use iterators instead.

(define (fail msg)
  (error msg))

(define (in-range start end)
  (call/cc (lambda (top)
             (let ((f fail))
               (let loop ((s start))
                 (if (< end s)
                     (f)
                     (begin (call/cc (lambda (loopcont)
                                       (set! fail loopcont)
                                       (top s)))
                            (loop (+ s 1)))))))))

(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")))