Delimited Continuations

If you’ve programmed in an imperative language, chances are you’ve used a guard clause to return early from a method or function in certain cases, like the following Ruby code that approximates following someone on Twitter:

Early returns can be confusing if we use them all over the place, but they can be useful to describe requirements for the main method body to execute. Normally in Clojure, we’d need to write something like this:

This kind of nesting isn’t out of the ordinary in Clojure, but it’s not really an early return. In the previous example, detecting whether a user is blocked or not doesn’t really look like a precondition for the function—it looks much more like a peer to the rest of the function body.

It turns out that we can simulate early returns in Clojure by using delimited continuations. A good way to think about continuations is that they let you pause the execution of your code, capture its environment, and save a reference to that environment to use later. Again, they let you capture the environment: things like local variables and even the current state of the call stack!

If you haven’t seen continuations before, this probably sounds insane. It still kind of does sound that way to me. Oleg Kiselyov, who’s done some staggering research^[29] in both quantity and quality, has some good arguments against undelimited continuations like Scheme’s call/cc,^[30] but the delimited variety are less problematic.

The delimc^[31] library provides delimited continuations as macros, so if you add [delimc "0.1.0"] to your project.clj, you can try this out in your sample project:

shift captures the current continuation, delimited by the containing reset. This continuation (which the shift binds to the name k) can be called just like a function, and when we do that, execution resumes from the point where the shift occurred in the code. So when we call (k :ok), we’re saying: insert the value :ok where the shift occurred in the code. And if we don’t invoke k, we don’t insert any value in place of the shift, and in fact the reset is complete at that point!

If this seems a bit confusing, you’re not alone: continuations are a tricky concept to wrap your mind around. The purpose of these examples is to show what’s possible, not to master the shift/reset programming model.

We’ve needed to add another level of nesting in the delimc version, but now the guard condition stands on its own, independently of the rest of the function body. We can go a step further and extract the guard clause to clean things up:

So within the context of the reset, every shift expression is able to decide whether or not to continue executing the body of the reset. What’s more, the shift could even decide to continue the execution multiple times! We can use this trick to implement even more interesting control flow operations, like the nondeterministic choice operator. Here nondeterminism doesn’t imply anything about randomness: it’s a term for a programming paradigm where an expression may have more than one possible value. We’ll see more of the implications of this idea in Chapter 8, ​Implement New Language Features​, when we look at logic programming. But for now, here’s what nondeterministic programming looks like with delimited continuations:

Notice that with choice, we’re actually calling the continuation multiple times, instead of just choosing between 0 and 1 time as we did with the early return example. And we prune the search space with insist, which does basically the same job as our guard clause from earlier, but only stops one branch at a time of the search, rather than the whole execution.

So how does all this shift/reset magic work? Clearly no function could warp the flow of control so deeply. And as you’d expect, there’s a macro under the hood allowing these things to happen. delimc uses a technique called continuation-passing style (CPS) to rewrite reset’s input expressions into ones that implement these semantics we’ve been seeing.

We don’t have nearly enough room to dig into all the details, but suffice to say that the reset macro is our entry point, kicking things off by setting up some context and calling a function that transforms its expression sequence into continuation-passing style:

There’s a decent amount of complexity omitted here, but as you can see, shift is just a thin wrapper around shift*, which will always throw an exception. What gives? shift* is purely a marker for the expr-sequence->cps transformations to use, and transform is one of the key ones. We’ll look at other examples of code walking like this in more detail in the last chapter, but first let’s see some examples of shift/reset macroexpansion:

In the first example, (reset 1), we call the identity function with 1 as an argument. Not bad at all. (reset 1 2) gets more complicated: we construct an anonymous function that calls the identity function with 2 as an argument (ignoring its argument, which is 1). In the third example, (reset (shift k (k 1))), we capture the continuation k inside an anonymous function and call it with 1 as an argument. In this small case, the continuation k is just the identity function.

You probably noticed that the clojure.core/identity function is injected directly into the macroexpansion rather than being quoted. This trick might be surprising at first, because it’s not obvious that this is a legal thing to do. It turns out the Clojure compiler handles this case for us, but in general it’s nicer to refer to names in macros than to emit functions directly into them. This is one of the least mind-bending parts of the code, though. These transformations become much more complicated as more complex expressions are passed into them, especially as soon as we give shift something to actually capture:

As you can see, things get complicated very quickly once the CPS transformations need to track the pending state of the computation. This is a bad way to compute (+ 1 1), but as you saw earlier, all this complexity pays off when you decide to call the continuation 0 times, or many times.

What’s perhaps most interesting about this library is that all the code required for this syntax transformation is only a couple hundred lines long. The functions underneath the reset macro, the ones that expr-sequence->cps uses, have a big job to do, and they don’t handle every scenario. reset is what’s known as a code-walking macro, because it walks its input expressions, transforming them into a form that jives with delimc’s worldview. The second thing to know about code-walking macros (after what they can do) is that they are hard to get right. In order to do its job as users might expect, delimc would have to be able not only to transform simple expressions like those you’ve seen, but also to handle local variable bindings, anonymous functions, conditionals, and who knows what else! It works very well with many inputs, but as of this writing, some input expressions can’t yet be handled, such as loop.

If you’re interested in digging more into delimited continuations, the delimc README^[32] lists a number of papers that go into much more detail about this programming model and its implementation details.

Control Flow: A Special Case of Language Features

In this chapter, you’ve seen some amazing control flow mechanisms that macros give you the power to create. Now that you’ve seen one specific way of extending the language in ways you can’t do in other languages, we’ll look at the more general case. In the next chapter, you’ll learn how to implement other language features as macros.