call/cc and other fantastic tales

A.S. The part about continuations begins at about half the post, where the code blocks are. You can skip to that, if you’re not interested in my ramblings.

I don’t remember when exactly I decided to take up programming. I probably never did; after some exposition to shells, open sources and compilers (and compiler errors), I subconsciously decided that I had absorbed enough to take the next step.

And so, I started reading those Zed A. Shaw books, Learn <language> the hard way. I didn’t want to be a bad programmer, and “the hard way” certainly sounded better than whatever method the code monkeys writing Java for those big, grey and soul-less corporations had used to learn.

Turns out doing things “the hard way” roughly translates to throwing things at a wall repeatedly, hoping that something sticks, at least according to Zed A. Shaw. Those books didn’t help much. Don’t read them.

Disheartened from all the crap-throwing, I figured I’d do what anybody else would do in this situation and downloaded Structure and Interpretation of Computer Programs.

I sat down and started reading it with the intent of making it to the end. Reading (and understanding) some parts wasn’t exactly a walk in the park, but I kept going on diligently, trying not to skim or skip over the parts that I couldn’t wrap my head around immediately. I did all the exercises, too. Then the exercises started getting more and more difficult.

I never finished SICP.

I had heard the rumors claiming that reading SICP would turn you into a CS wizard, but while I did feel an improvement, I didn’t believe it until I went back to Ruby. Suddenly, I could understand what I was doing! Sure, it took me a long while to actually do anything useful with it, but reading part of that book and learning Scheme really helped me.

Scheme is a very simple and elegant language. It is so simple that people who have never programmed before can learn it, in the case of MIT’s old introductory programming class 6.001, over the course of one lecture. The entire specification of the language fits in a 73-page document; 88 if you include the list of base keywords, macros and standard library functions. I often use it as reference while programming in Scheme.

Obligatory xkcd.

Now, if you’ve ever heard a talk by Rich Hickey, you’ll know that simple != easy. And indeed, Scheme and the other Lisps are incredibly powerful languages, despite being so simple.

I’ve never really dealt well with hard things, as you can see from my early abandonment of SICP, and while my first concern when coming up with Solutions to Make The World A Better Place is simplicity, if that simplicity is not complemented with ease of use and understanding I don’t feel like I accomplished what I set out to do.

I really dislike how simple concepts can be made hard through obscure wording and complex explanations. Lots of programmers, particularly those who are versed in some functional language, are often guilty of this. I’m not saying we should write everything with Cleartext, just that reveling in buzzwords and obscure terms without ever explaining them leads to confusion.

A Monad is just a monoid in the category of endofunctors, what’s the big deal?

I think the easiest way to convey an unfamiliar concept is by showing how it works concretely. An abstract explanation, no matter how simple it is, will require you to:

• Understand what exactly the example is trying to achieve, and how to translate it to code.
• Recognize the pattern this feature is trying to solve in an already existing design, and understand how to integrate it by yourself.

Conversely, by taking a common design that is close to what you already know and applying the new concept to it, you cut out many layers of mental abstractions and therefore reduce the complexity of the explanation, making it way easier to understand.

Take continuations. Sure, you might find explanations telling you what it is theoretically and maybe even that example with the fridge and the sandwich. That’s cool and all, but what the hell are they? How do I use one?

Let’s imagine a program where you’re never allowed to return anything from functions. You might wonder why and how would something like that ever happen, so let’s take javascript as an example.

When javascript encounters an expensive and/or long operation, such as an AJAX request or a read/write, it runs it in parallel with the rest of the script, so as not to block the whole page while it’s crunching data or waiting for a response from a server.

The problem with these asynchronous functions is that you cannot explicitly return something from them as you would with normal synchronous, blocking functions.

function readFile(file_obj) {
    var reader = new FileReader;
    return reader.readAsBinaryString(file_obj);
}
var a = readFile(document.getElementById("file-picker").files[0]);
=> undefined
a
=> undefined

Thankfully in javascript functions are first-class citizens, which means that they are a data structure like any other and you can assign them to variables and pass them as arguments to other functions, just like you would with strings or arrays.

So you define a function to call back when the asynchronous function is done.

function readFile(file_obj) {
    var reader = new FileReader;
    reader.onload = function(e) {
        /* do stuff with the file */ };
    reader.readAsBinaryString(file_obj);
}
var file = document.getElementById("file-picker").files[0];
readFile(file);

This, however, is not very portable. We don’t know what we’re gonna need to do with this binary string, so instead of reusing that bit of code and changing the anonymous function for each operation, we can use continuations.

function doStuff(binary_string) {
    /* stuff */
}
function doOtherStuff(binary_string) {
    /* you get the idea */
}
function readFile(file_obj, continuation) {
    var reader = new FileReader;
    reader.onload = function(e) {
        continuation(e.target.result); };
    reader.readAsBinaryString(file_obj);
}
var file = document.getElementById("file-picker").files[0];
readFile(file, doStuff);
readFile(file, doOtherStuff);

This is called CPS (continuation-passing style): in this style, you’re not allowed to return values, so you have to pass the function that you’re gonna call on the result as an argument to the current function, and you keep doing this until the process is over.

In other words, you continue the process by feeding to the current function the next step of the process, i.e. its continuation.

In this particular case, the continuation can be represented by a function, but that’s not always correct. A continuation is actually the entire “context” of any given point in the execution of a program. It includes:

• The variables currently in scope.
• The current position in the program.
• What it needs to do next.

If function A calls function B as the last thing it does, function B can be called function A’s continuation; the function call itself represents the current position, it includes everything it needs to do next (the body of function B), and all the variables it can access, not counting globals (its arguments).

(If you didn’t understand, here’s a better explanation by Ian Bicking.)

Continuations are the data structures a compiler builds at each step to know where it is and what’s the next step. You can think of them as a “place” in the program execution.

Normally, continuations are only available to the compiler. This is not the case for Scheme, which happily gives you first-class access to continuation through the construct call-with-current-continuation, aka call/cc.

call/cc is a function that takes another function with one parameter, and assigns this parameter to the continuation where call/cc was called. I don’t know about you, but I couldn’t figure out half of it when I first read this, so let’s see how exactly it works.

(define (return-one cc) (cc 1))
(call/cc return-one)

The compiler detects that call/cc is called, so it saves the current point of execution (the current continuation). Then, it calls return-one with the current continuation as an argument. In the body of the function, the current continuation represented by cc is thrown 1, which makes 1 the next step of the program. And sure enough, the expression above evaluates to 1.

This can be used to emulate a return statement, which is missing from Scheme.

(display
  (call/cc (lambda (return)
    (display "One ")
    (return "Two ")
    (display "Three"))))
One Two

You can also save the continuation for later use:

(define reset #f)
(define counter #f)
((lambda ()
   (call/cc (lambda (cc) (set! reset cc)))
   (set! counter 1)))
> counter
1
> (set! counter (+ 1 counter))
> counter
2
> (reset)
> counter
1

Here we defined and evaluated a function that saves the current continuation in reset and sets counter to 1. We can now set the counter to whatever we want, but when we call reset, the program will jump to the point where the continuation was saved (right before evaluating call/cc) and continue the execution of the function from there, in this case resetting the counter to 1.

Let’s go over the sandwich example.

Say you’re in the kitchen in front of the refrigerator, thinking about a sandwich. You take a continuation right there and stick it in your pocket.

(define pocket #f)
(define sandwich #f)
(define (eat-sandwich)
  (let ((mouth ‘()))
    (call/cc (lambda (current-continuation)
               (set! pocket current-continuation)))
    (if sandwich
      (begin (cons sandwich mouth)
             (display “Ate the sandwich!\n”))
      (error “No sandwich”))))

The sandwich has not yet been prepared, so if we call eat-sandwich, it will fail.

> (eat-sandwich)
ERROR: No sandwich

Then you get some turkey and bread out of the refrigerator and make yourself a sandwich, which is now sitting on the counter.

> (set! sandwich (cons ‘bread ‘turkey))

You invoke the continuation in your pocket, and you find yourself standing in front of the refrigerator again, thinking about a sandwich. But fortunately, there’s a sandwich on the counter, and all the materials used to make it are gone. So you eat it. :-)

> (pocket)
Ate the sandwich!

Only Scheme and a handful of languages (including Ruby!) let you manipulate continuations this way, but you should be using this very sparingly anyway. I don’t think anybody would be happy to find something like this in production code.

I wrote this because when I was standing on a mountain thinking about continuations, I didn’t find any clear enough explanation on the counter. This is my sandwich for those who will come next. Buon appetito!

P.S. I still have much to learn, and I’m writing this primarily to understand it myself. Please feel free to correct me if you find any mistakes or inconsistencies.