Not too many programming languages have the concept of first-class continuations built into them. Scheme is one that does1, so it will be our vehicle for today's adventure. Now what really is a continuation? In order to get an idea, consider the following simple expression:

(+ 5 4)

Remember that Scheme uses prefix notation2, where the first item in a parenthesised list is the operator, that is applied to the list of arguments, which is the rest of the list. + is the sum-operator, so the above expression evaluates to 9. So far, so good. How does this help with continuations? Well, a continuation is a way of bundling up “what's left to do” with respect to an arbitrary sub-expression within a program.

Imagine the perspective of the literal 5 in the expression above. If you are this five, look around you and try to come up with a function, that would represent the rest of the computation after you are done evaluating3. So in the expression above, after 5 evaluates to five, what is left to be done in order to finally evaluate to 9? Here's a suggestion:

(define (kont v)
  (+ v 4))

Indeed, after evaluating the 5 literal, the rest of the expression can be represented as a function, that takes one value and adds 4 to it. And if you stick the value of 5 into that function, it will return 9, like it must.

Once you realise that you need to take the perspective of a part of an expression in order to figure out what the continuation does, it is not hard to figure out these functions for arbitrarily complex expressions. It just takes a little bit of practice. But thus far, this is just a theoretical idea. How would you work with continuations? How to you get to them?

In Scheme (and also Standard ML), there is an operator called call/cc, which is short for call-with-current-continuation. Its purpose is to capture the continuation at a certain point in a program and make it available to the programmer. The name call-with-* suggests, that the operator needs something that it can call. That would be a function. This function has to take one argument and call/cc will call that function with the continuation it captured as the function's only argument. This function parameter is the only argument that call/cc expects and the return value of the call/cc invocation is the value of the the supplied function applied to the captured continuation. Here are simple examples, that use call/cc:

(call/cc (lambda (k) 5)) → 5
(+ (call/cc (lambda (k) 5)) 4) → 9

Since these don't use the continuation at all, it is straight forward to tell the values these expressions evaluate to. Now for something more interesting: Since Scheme allows us to mutate memory4, we can just store the continuation in a parameter for later use:

(define kont #f)

(+ (call/cc (lambda (k)
              ;; Store the continuation k in the global
              ;; parameter kont, that we defined before.
              (set! kont k)
              ;; Ignore the continuation otherwise, and
              ;; just return 5; so this expression boils
              ;; down to (+ 5 4); though we used call/cc
              ;; to extract the continuation from the
              ;; perspective of our value 5.
              5))
   4) → 9

;; Take a look at ‘kont’ — this is how Racket pretty prints it.
kont → #<continuation>

(kont 10) → 14

Remember when we defined a function called kont earlier? We figured out that the continuation right after evaluating the 5 is a function that adds 4 to its one and only argument. Now applying the continuation (stored in kont) to a value of 10 results in: 14 — just as we predicted.

The captured continuation has a special property, that sets it apart from being a simple function: When it is invoked, it resurrects its execution context entirely and abandons the current one, no matter where the program went in the meantime. This property can be used to implement all sorts of useful high-level control flow facilities. A simple, easily understood one is “early exit”. Consider this:

(fold * (*) '(1 2 3 4 0 6 7 8 9 10)) → 0

This is an expression that computes the product of all values in the list, that is the last argument to fold5. Since any integer being multiplied by zero results in zero, the computation could stop at the fifth element of the input list. However, fold has no concept of exiting early. Since we have call/cc, we can easily add that:

(call/cc (lambda (return)
            (fold (lambda (x acc)
                    (if (zero? x)
                      (return 0)
                      (* x acc)))
                  (*)
                  '(1 2 3 4 0 6 7 8 9 10)))) → 0

It's the same expression as before, but it's executed inside the function, that is passed to call/cc. That way, we have access to the surrounding continuation. In the call to fold we pass a function that's more complex than the direct reference to multiplication function. fold will hand the current element of the list as the first argument of its function argument and the current value of its accumulator as the second one. What we need to do is straight-forward: Check if the current argument is zero, and if that is the case, just invoke the surrounding continuation with 0 as its argument. As mentioned earlier, this resurrects the continuations execution context and abandons the current one.

Now in order to see if you understood continuations, at this point in other texts on the subject, you get confronted with mind-benders like the following, which is from TSPL page 646:

(((call/cc identity) identity) "Hey!")

If you evaluate this at a Scheme prompt, it will return the string "Hey!". This might be guessable, but the question is: Why? Let's analyse the expression's form first: At its most primitive, this expression can be summarised like this:

(operator operand)

The operand has the value "Hey!", trivilly. And since we know the result of the final evaluation is that same value, we can (barring side effects) reason that operator has to be the identity function7. Since that function appears twice in the original expression, it feels like we are on the right track! A guess would be, that the second incarnation of identity somehow gets transposed into the operator spot. Maybe we can just replace it with something else, like string-upcase. But if you try, you will notice that things are not quite as easy is they seemed8:

(((call/cc identity) string-upcase) "Hey!")
→ string-upcase: contract violation
    expected: string?
    given: #<procedure:string-upcase>

…and not "HEY!" like one might have guessed. Time to take a look at the expression, that is our operand:

((call/cc identity) identity)

With our previous strategy we need to look at (op identity), put ourselves in the perspective of op and ask: What function represents the rest of the computation after I am done evaluating myself? And you can follow that strategy pretty mechanically:

(define (k v)
  (v identity))

This is what gets handed in as the argument to identity in (call/cc identity). And since it is identity, all it does is return the continuation it is handed. That is all it does. Which means, we end up with this:

((lambda (op) (op identity)) identity)
;; Which can be reduced to:
(identity identity)
;; Which can be further reduced to:
identity

Let's come back to our guess-work from earlier, where we naïvely used string-upcase instead of identity: It would reduce to this: (string-upcase string-upcase). And now all of the sudden the error message makes sense too: It says string-upcase expected a string argument, but instead got a procedure; and not any procedure but string-upcase itself.

To summarise the above: The call/cc uses its identity argument to feed the right identity into itself, ultimately returning itself. So (((call/cc identity) identity) "Hey!") reduces to (identity "Hey!") which evaluates to "Hey!".

It's a fair bit mind-bendy if you think it all through, but managable if you follow the strategy that was presented earlier. What remains to examine is what continuations are useful for beyond clever puzzles. Well, they are a primitive that allows the implementation of a lot of high-level control structures such as early-exit (as we have seen earlier), exceptions, co-routines, generators, and more. In a language with first-class continuations all these features can be implemented in a library without further language support.

Finally, let's not overlook that there are problems with full, unbounded continuations as well: For details on that, see [Kis12]. To alleviate most of these concerns, we might take a look at delimited continuations. That is, however, a story for another day.

Footnotes

1 See [R4RS] p.28f
2 See [SICP] p.8f
3 Number literals evaluate to themselves — but in general, the subexpression that would be picked could be arbitrarily complex.
4 I know, I know.
5 The * symbol evaluates to the multiplication function and (*) evaluates to the identity element of multiplication, namely 1.
6 According to the author it is “probably the most confusing Scheme program of its size”, a Confusion Desity Maximum, if you will.
7 (lambda (x) x)
8 As we will see later, this intuition is not completely wrong, but there is a twist!

References

[SICP] Harold Abelson and Gerald J. Sussman. Structure and Interpretation of Computer Programs. 2nd ed. The MIT Press, 1996. isbn: 0262011530.

[R4RS] William Clinger, Jonathan Rees, et al. R4RS, The revised4 report on the algorithmic language Scheme. New York, NY, USA: ACM Lisp Pointers, 1991, pp. 1–55.

[TSPL] R. Kent Dybvig. The Scheme Programming Language. 4th ed. MIT Press, 2009, pp. I–XII, 1–491. isbn: 978-0-262-51298-5.

[Kis12] Oleg Kiselyov. An argument against call/cc. 2012. url: http://okmij.org/ftp/continuations/against-callcc.html.

Posted Tue 01 Oct 2019 22:23:24 CEST Tags: