Continuation-Passing Style in TypeScript

Tail recursion, resumable exceptions, and more

Continuation-passing style (CPS) is an occasionally very useful technique which is fairly niche for developers outside of functional programming languages. Many JavaScript developers are familiar with a similar technique in which callbacks are used to handle asynchronous operations in pre-promise-era node.js code, but CPS itself is more general. This post will introduce CPS and show how it can flexibly solve problems which require unusual and non-local control flow.

There’s a large number of introductions to CPS online already but I wanted one which focused on its applicability to TypeScript, skipping over topics like compilation and the continuation monad. If such things interest you there will be links to further reading at the end.

This post assumes some familiarity with tail call elimination/proper tail calls. If you aren’t familiar with them then I recommend Axel Rauschmayer’s tail call optimization post for an overview in JavaScript. The V8 and SpiderMonkey JavaScript engines do not support proper tail calls, so most of the code in this post will not be stack safe in Firefox, node.js, or Chromium-based browsers. The examples which rely on tail calls can be run on large inputs using the JavaScriptCore runtime that powers Safari and bun due to its proper tail call support when running in strict mode.

CPS: the basic idea #

When writing code in continuation-passing style, every function receives one or more “continuation” functions as arguments. When a function completes whatever processing it was doing it must pass its result to one of its continuations, rather than returning the result directly.

To start with a very basic example, consider a function which adds two numbers:

function add(n: number, m: number): number {
  return n + m;
}

Here’s what this function looks like using CPS:

function addCPS<T>(n: number, m: number, k: (sum: number) => T): T {
  return k(n + m);
}

Our continuation here is called k, as is idiomatic for code using CPS. addCPS adds two numbers as before but its return type is not number. Instead, addCPS is polymorphic, and has its return type decided by the continuation that it is provided. Here’s some examples of how we might use addCPS in a program written using CPS:

console.log(addCPS(1, 2, sum => sum * sum)); // 9
console.log(addCPS(1, 2, sum => `The sum is: ${sum}`)); // The sum is: 3
console.log(addCPS(1, 2, (sum) => addCPS(sum, 3, x => x))); // 6

In these examples we use addCPS to produce a value and then pass in a function which performs further processing. We can view each line as a series of operations: add two numbers and then square them, add two numbers and then convert the result to a string, add two numbers and a third number and then return the result unchanged. Given a series of steps in a CPS-sequenced computation, a continuation expresses the remainder of the computation after the current operation. Calling k allows the computation to “continue”, running until it reaches its conclusion.

If you’ve done callback-based programming in JavaScript before it’s important to note that this is not generally the same thing. Specifically, asynchronicity is not part of the story and code in CPS does return a value when it runs. The return value is specified by the continuation rather than by the addCPS function itself.

This style of programming may seem obscure. It is, especially at first, but it also has immense practical benefits in the right contexts.

Summing the contents of binary trees #

Consider this data type for binary trees:

type BinaryTree<T> = {
  contents: T,
  left: BinaryTree<T> | null,
  right: BinaryTree<T> | null
}

Say that, given a binary tree of numbers, we wanted to calculate the sum of all nodes. Here’s one way we could do so:

function sumTree(tree: BinaryTree<number> | null): number {
    if (!tree) return 0;
    return sumTree(tree.left) + sumTree(tree.right) + tree.contents;
}

I think this function is very straightforward. To calculate the sum of a tree we first calculate the sum of its subtrees, and then add them to the root node’s contents. The implementation has a problem though: it is possible for this function to overflow the stack and throw an exception on large inputs.

A stack overflow may or may not be a practical concern; it depends on the problem being solved. This function builds up one stack frame per depth of the tree. On my machine running node.js version 22, this occurs at a depth between 9000 and 10000. In a fully unbalanced tree this isn’t a very large number of nodes but it is also hard to think of cases where we’d encounter such a data structure in practice. A filesystem usually has a limit to its depth, it would be bizarre for a source code file to have that level of nesting, etc. On the other hand, if the tree is fully balanced, the stack unsafety is almost certainly not a problem. A fully balanced binary tree has as many nodes as 2 to the power of its depth. For a depth of 9000 this is an astronomically large number, with a decimal representation thousands of digits long.

All that said, it is still troublesome to have to consider potential stack sizes when choosing an ergonomic representation of a problem. Abstracting away such concerns is preferable when possible.

One way we could avoid growing the size of the call stack would be to convert our algorithm to be iterative. Here’s how that looks, using a textbook approach to iterative tree traversal:

function sumTreeIterative(tree: BinaryTree<number>): number {
    const stack: Array<BinaryTree<number>> = [tree];
    let total = 0;

    while (stack.length) {
        const node = stack.pop()!;
        total += node.contents;

        if (node.left) {
            stack.push(node.left);
        }

        if (node.right) {
            stack.push(node.right);
        }
    }

    return total;
}

While this does compute the sum, the intention of the algorithm is buried. It takes four times as many logical lines to perform the work of our previous two-line function, relies on mutation, and brings in the use of a stack, whose specification is completely unnecessary in the recursive implementation. The use of the stack isn’t arbitrary: the iterative algorithm is explicitly simulating the JavaScript call stack! If you break down the executions for identical inputs you’ll be able to see that calls in the recursive algorithm correspond to pushes in the iterative algorithm, and returns in the recursive version correspond to pops in the iterative one. When traversing our binary trees you absolutely have to remember your place in the tree, because you need to know what the next step of the algorithm is.

Next step. That’s exactly what continuations are about. It turns out that CPS allows us to have a tail recursive implementation without resorting to mutable stack management. Here’s the implementation:

function sumTreeCPS<K>(tree: BinaryTree<number> | null, k: (n: number) => K): K {
    if (!tree) return k(0);
    
    return sumTreeCPS(tree.left, (leftSum) =>
        sumTreeCPS(tree.right, (rightSum) =>
            k(leftSum + tree.contents + rightSum)));
}

(This implementation is based off of the Racket implementation in Kristopher Micinski’s lecture here.)

We can call the function like this:

const sum = sumTreeCPS(someTree, x => x); // sum has type `number`

The first thing to note about this implementation is that it makes three calls, all of which are in the tail position. Indeed, if we run this code in bun in strict mode with a tree that’s a million levels deep, we don’t get a stack overflow. The second thing to note is that the logic here is almost identical to the logic in our original recursive algorithm: to compute the sum of a tree, compute the sum of its left subtree, then the sum of the right subtree, and then add both of them to the contents of the tree. The use of k adds a little noise, and it’s less convenient to call the function, but I vastly prefer the CPS implementation to the iterative one. The CPS version is explicitly focused on the logic of the algorithm rather than on imperative, mechanical concerns.

As before, we have to track the path through the tree somewhere, and so some data structure needs to grow with the depth of the tree. In this case that structure is the continuation itself. As we traverse the tree, the function we’re passing around will grow with references to more functions. Like the iterative solution these references are stored on the heap, preventing overflows. Like the recursive solution this data structure is managed for us by the language’s built-in abstraction capabilities, rather than requiring manual programmer management. If we’re running in an environment with proper tail call support then I consider the CPS solution to be the best of both worlds.

Adding non-local returns #

The motivating example in this section is directly borrowed from Ziyang Liu’s blog post on CPS which demonstrates this technique in Haskell.

Say that we wanted to add a new requirement to our tree summation function: if the tree contains the number 42 anywhere, we must exit early and return the value 1000 as the tree’s “sum”.

Our recursive algorithm becomes significantly less elegant in this case, as we now have to plumb the fact that we’re in an “early exit” state through the layers of recursion:

function sumTreeRec42(tree: BinaryTree<number>): number {
    function sumTreeInner(tree: BinaryTree<number> | null): [number, boolean] {
        if (!tree) return [0, false];

        if (tree.contents === 42) return [1000, true];

        const [leftSum, leftReturnedEarly] = sumTreeInner(tree.left);
        if (leftReturnedEarly) return [1000, true];

        const [rightSum, rightReturnedEarly] = sumTreeInner(tree.right);
        if (rightReturnedEarly) return [1000, true];

        return [leftSum + rightSum + tree.contents, false];
    }

    return sumTreeInner(tree)[0];
}

The details are up to taste. We could have used a tagged union for more explicitness with significantly more lines of code but I elected to use a boolean to indicate that we’re in the process of an early return. In any case, we’ve had to completely rewrite our logic in order to account for the new requirement.

In contrast, the iterative algorithm from before adapts to the new requirement pretty well:

function sumTreeIter42(tree: BinaryTree<number>): number {
    const stack: Array<BinaryTree<number>> = [tree];
    let total = 0;

    while (stack.length) {
        const node = stack.pop()!;

        // This new line is the only change
        if (node.contents === 42) return 1000;

        total += node.contents;

        if (node.left) {
            stack.push(node.left);
        }

        if (node.right) {
            stack.push(node.right);
        }
    }

    return total;
}

As much as I still dislike the manual stack management from before, adding this new requirement meant adding only one additional line of code, without modifications to any others.

Thinking operationally, we could rephrase our early return requirement as “Traverse a tree, building up stack frames. When you encounter the magic value, jump to the top of the stack, discarding intermediate frames, and return a constant value.” From this perspective it’s clear why the iterative solution is a more natural fit for this requirement change. JavaScript only provides one primitive for built-in stack manipulation (throwing exceptions) and TypeScript does not/cannot apply type safety to its use. (We could have implemented the recursive algorithm with throw, but doing so in the general case opens a can of worms.) As discussed earlier though, the iterative algorithm is still using a call stack: the stack variable. Because the stack is being managed explicitly by userland code we can do whatever we want with it. Discard it, reorder it, whatever.

As it so happens, CPS is very good at this as well. The key insight is that CPS requires us to call a continuation in order to exit our computation. If we take multiple continuations, then we can choose where we exit to!

function sumTreeCPS42<K>(tree: BinaryTree<number>, kOuter: (n: number) => K): K {
    function sumTreeInner<K>(
        tree: BinaryTree<number> | null,
        exit: (n: number) => K,
        k: (n: number) => K
    ) {
        if (!tree) return k(0);
        if (tree.contents === 42) return exit(1000);

    return sumTreeInner(tree.left, exit, (leftSum) =>
        sumTreeInner(tree.right, exit, (rightSum) =>
            k(leftSum + tree.contents + rightSum)));
    }

    return sumTreeInner(tree, kOuter, kOuter);
}

We’ve added a wrapper function to make the external interface cleaner like we did with the naive recursive implementation, and we have to thread the additional exit argument through our calls. Aside from that, the actual logical change to the inner recursive function is the addition of a single line, just like with the iterative solution.

Going back to the operational mindset, when we redefine our continuations they build up a “call stack” of work which will be performed. Like with the iterative solution our call stack is now a first-class value. The difference here is that the only things we can do with our call stack are to either execute or discard it; we don’t have the ability to arbitrarily modify a “call stack” array, but we also don’t have to, and we definitely don’t want to. That way lies chaos.

Referring to the continuation as a “call stack” may seem like slight of hand, but consider what’s going on in the machine when tail call elimination is present. In this case JavaScriptCore’s built-in call stack does not grow in the face of tail calls, and rather swaps out the top stack frame every time a tail call occurs. We literally are storing a data structure of stack frames and choosing which ones get put on the built-in call stack to be executed. We’ve reified control flow into something which we can manipulate by hand.

The example code shows two continuations, k and exit. We never redefine exit throughout the inner computation, so the call stack it encodes never changes. In the case where we call it we discard k’s call stack and exit early to the stack held by exit. That stack is kOuter, whatever it is that our tree summation function’s caller is doing. We’ve just defined a longjump, allowing ourselves to traverse the stack to labelled points. This is equivalent to a type-safe try/catch!

Resumable exceptions via CPS #

Contrived examples are fun, so let’s add some more. Here’s some new requirements for the sum function:

1. Add all the numbers in the tree via a left-to-right preorder traversal.
2. If we hit a node with the value 42, instead return the value 1000.
3. If we hit a node with the value 1337, look up the tree. If there is a value above us with the value 25565, return 1337 as the value of the closest 25565’s entire subtree. Otherwise, continue to sum as normal.

We’ve already covered that point 2 is asking us to implement exceptions, which JS can already do reasonably well. Point 3 is asking us to implement resumable exceptions, which JS cannot do at all. An exception is resumable if we can catch it, perform some logic, and then continue execution at the point at which the exception was created. Further, we are installing two separate exception handlers here: One at the top level, which should catch our “early return” exceptions, and one at intermediate levels, which should catch our “1337” exceptions. Some languages like Java provide facilities for using different handlers for different kinds of exceptions, but JS does not.

This is a verbose set of requirements, so it’s going to have a verbose solution. That said I believe that CPS is the best tool for approaching this problem in TS. Here’s what it looks like:

function sumTreeCPS1337<K>(tree: BinaryTree<number>, kOuter: (n: number) => K): K {
    type Exceptions = {
        exit: (n: number) => K,
        throw1337: (resume: () => K) => K,
    }

    function sumTreeInner(
        tree: BinaryTree<number> | null,
        { exit, throw1337 }: Exceptions,
        k: (n: number) => K
    ) {
        if (!tree) return k(0);
        if (tree.contents === 42) return exit(1000);

        // If this node contains 25565 then we want to re-bind the point
        // in the call stack that "throw1337" points to. Make a new throw 
        // function which, when called, exits directly to this subtree's
        // continuation with a constant value.
        const exceptions: Exceptions = {
            exit,
            throw1337: tree.contents === 25565 ?
                (resume) => k(1337) :
                throw1337
        }

        const next: () => K =
            () => sumTreeInner(tree.left, exceptions, (leftSum) =>
                sumTreeInner(tree.right, exceptions, (rightSum) =>
                    k(leftSum + tree.contents + rightSum)));

        if (tree.contents === 1337) {
            // Go back to the stack where `throw1337` was defined. If the handler
            // there wants to resume execution, it will call `next`, and we'll
            // keep going with the same logic as though nothing had happened.
            // If the handler there does *not* want to resume execution, then
            // our current call stack (`k`) will be dropped and we'll switch to
            // the call stack set up by throw1337.
            return throw1337(next);
        }

        // Nothing weird happened so we continue as normal
        return next();
    }

    return sumTreeInner(tree, {
        exit: kOuter,
        throw1337: (resume) => resume(),
    }, kOuter);
}

Since we’ve added a new continuation we’ve had to change our signatures to plumb it through. In this case I’ve packed both of the non-local continuations into an object with an explicit type for readability.

throw1337 is something new: a higher-order continuation. When we “throw” a resumable exception, we include the call stack to return to in case we want to perform an resumption. This is why we’ve taken the normal return value of our sum function and put it into the next variable. throw1337 is a handler that was defined somewhere previously in the program’s execution. When we call it we hand control flow back to wherever it was defined; then, that definition point can choose to allow the computation to continue (by handing control back to resume) or it can drop the remainder of execution and instead do something else.

Inside of sumTreeInner we provide a new handler for this “exception”, which discards resume and returns a constant, but at the top level of sumTreeCPS1337 we install a handler which calls the resumption. This way, if there are no intermediate handlers, computation will continue as normal.

This implementation is type safe. TypeScript, like many statically typed languages, has more powerful type checking than it has type inference. The explicit type annotation on next is necessary because its type cannot be inferred, but it is still checked and providing the wrong type in the annotation will cause the TypeScript compiler to report an error.

Readers who are familiar with resumable exceptions may know that they can form the basis of algebraic effect handlers. I believe that this is the case here, and that CPS can be used to implement classic algebraic effects like coroutines and nondeterminism, but I do not yet fully understand the details¹. This is far beyond the scope of this blog post and I hope to write more about it in the future.

I’ve tried to approach this problem using a recursive, non-CPS implementation. Here’s the best I was able to come up with:

function sumTreeRec1337(tree: BinaryTree<number>): number {
    type RecursiveResult = {
        tag: "Exiting42"
    } | {
        tag: "Throwing1337"
    } | {
        tag: "Sum",
        sum: number
    }

    function sumTreeInner(
        tree: BinaryTree<number> | null,
        has25565Ancestor: boolean): RecursiveResult {

        if (!tree) return {
            tag: "Sum",
            sum: 0
        }

        if (tree.contents === 42) return {
            tag: "Exiting42"
        }

        if (has25565Ancestor && tree.contents === 1337) return {
            tag: "Throwing1337"
        }

        const leftResults = sumTreeInner(
            tree.left,
            has25565Ancestor || tree.contents === 25565);

        if (leftResults.tag === "Exiting42") return leftResults;
        if (leftResults.tag === "Throwing1337" && tree.contents === 25565) return {
            tag: "Sum",
            sum: 1337,
        }
        if (leftResults.tag === "Throwing1337") return leftResults;

        const rightResults = sumTreeInner(
            tree.right,
            has25565Ancestor || tree.contents === 25565);

        if (rightResults.tag === "Exiting42") return rightResults;
        if (rightResults.tag === "Throwing1337" && tree.contents === 25565) return {
            tag: "Sum",
            sum: 1337,
        }
        if (rightResults.tag === "Throwing1337") return rightResults;

        return {
            tag: "Sum",
            sum: leftResults.sum + rightResults.sum + tree.contents,
        }
    }

    const result = sumTreeInner(tree, false);

    if (result.tag === "Exiting42") return 1000;
    if (result.tag === "Throwing1337") throw new Error("TILT: this is impossible");
    return result.sum;
}

While this makes less use of higher-order functions than our CPS implementation, I still prefer the CPS approach. I actually found the CPS approach much easier to implement correctly; it took some back-and-forth with the type checker to get things right, but once it typechecked it passed test cases on the first try. The recursive implementation was easy to write without type errors but my first two implementations were subtly wrong and mishandled interactions between the different types of exceptions when they were both present². Even if I had nailed the recursive implementation on my first attempt I would still find CPS to be a better approach to this series of problems. The next two sections will explore why.

I didn’t even try to come up with an iterative solution to this problem. I don’t expect it would be easy.

Control-based problems benefit from control-based solutions #

In a real-world project, every time our implementation can successfully adapt to a requirements change without a massive overhaul it increases our confidence that we’ll be able to reasonably adapt to future changes as well, assuming that the changes are not radically different in kind than what we’ve already experienced. The aesthetic impression left by a snapshot of our system is only a small part of maintainability; what’s more important is the system’s ability to flex and gradually change as we need it to over time. Once a simple and elegant solution has weathered a few requirements changes it will usually appear less simple and less elegant, while being more reliable.

I will be the first to admit that CPS code is often aesthetically displeasing. Manipulating control flow can be hairy, and before I started doing research for this blog post I found CPS code hard to read in general. (I still find it hard to read in languages that I’m not well-practiced with.) That said, for the kinds of problems shown in this post, the CPS approach adapted far better than either the iterative or the plain recursive ones. CPS allowed us to start with a simple solution to a simple problem and gradually evolve it as the problem’s requirements grew increasingly bizarre. The plain recursive approach had to be completely rewritten every time the requirements changed. The iterative approach handled one change well but was unsalvageable once resumable exceptions entered the picture. If this blog post were a real world project, the CPS approach is the only one which would have avoided the maintenance burden of repeated rewrites. I have a reasonable amount of confidence that more strange requirements changes could be handled reasonably: laziness, nondeterminism, and generally anything involving specifications around control flow or evaluation order.

Of course this is no accident; I’m writing a blog post on CPS so I chose the kinds of problems that CPS handles well as examples. I’m calling these problems “control-based” as a vague shorthand, as I do not know of a proper term or precise categorization for them. Hopefully if you’ve read this far you’ve developed a gut feeling for what they might look like. I argue in my post Recursive Problems Benefit from Recursive Solutions that implementations are more maintainable when they closely reflect the specification of problems which they solve. I believe this holds true here.

As some additional food for thought: in the resumable exception problem I specified an execution model for the solution, leading to a situation where the order in which 42 and 1337 were hit was meaningful. In this case their meanings become enmeshed and the problem can’t be easily decomposed into two separate passes over a tree. If I were to change some of the details of the execution order (such as saying that it should be post-order rather than pre-order) the CPS implementation could easily adapt. If I were to instead say that the presence of 42 anywhere in the tree should cause the result 1000, regardless of whether 1337 appears anywhere, then I’d be changing not just the details of execution but also the entire specification paradigm. This would be moving from an operational mindset (giving requirements in terms of specific steps) to a denotational one (giving requirements in terms of the composition of simpler behaviors). In such a case the CPS solution would lose some of its edge and a two-pass approach would become necessary.

When 42 and 1337 are mutually interlinked like this we could say that the problem is complected. Complected requirements usually lead to uglier and more brittle solutions and so I find it especially interesting that the opposite is true here. When looked at from a certain angle the CPS code has an elegance to it which only improves as the problem gets more tangled.

My experience is that control-based problems are probably relatively rare in everyday development and that this may be a good reason for most projects to avoid CPS. Programmers are often tasked with solving hard problems, but a much larger portion of most of our jobs is finding a way to define problems such that they’re no longer hard. Complectedness frequently has negative impacts on both the authoring and the usability of software and this means that developers have good reason to coax their problem definitions away from the areas where CPS is most effective. On the other hand, if you need to solve these sorts of messy problems and you can’t change to a language with better support for advanced control flow (such as a functional language with monadic “do” notation, algebraic effects, or delimited continuations as a first-class language feature) then CPS might be the most reasonable answer.

Conclusion #

I think that CPS is a great tool for developers to have in their toolbox. It’s not one that will be used every day (or month, or year) but it provides an intoxicatingly powerful way of looking at and manipulating control flow. This is especially true in functional languages which have better syntax and runtime support for it, but it applies to TypeScript as well.

There is a ton of research on CPS in other languages but I don’t know that I’ve ever seen its use discussed in TypeScript. I think this is a shame. One reason for this may be V8’s lack of support for proper tail calls. CPS code is inherently fragile on large input sizes in node.js; most of the CPS binary tree examples in this post can only handle a few thousand nodes before causing node’s stack to overflow. This fragility makes the technique much less general and is good cause for node developers to use it exceedingly sparingly. This cuts off a whole avenue of exploration in our ecosystem. I say that CPS is niche, but this is the perspective of a single developer who has only used it in toy examples. There are millions of JavaScript developers in the world and I am absolutely certain that some of them could find ways to use CPS that I would not expect, if only the tool was put into their hands. We should all cheer for the exploration of new ways to program and I really hope that one day these techniques will become more accessible.

Acknowledgements #

Thank you to PolyWolf and Abhinav Sarkar for providing me with resources on CPS, which I used as the basis for this post.

Further reading #

Videos:

• Brandon Wu has an introductory lecture on CPS, and another one on regular expressions which uses CPS in its implementation.
• The previously-mentioned lecture by Kristopher Micinski introduces CPS in Racket and covers automatic compilation to CPS form.

Blog posts:

• Li-yao Xia has blog posts on the use of the continuation monad in Haskell and the use of first-class language-supported continuations to implement algebraic effects.
• Dmitry Kandalov has a post on using call/cc to perform non-local control flow with CPS in Scheme.
• The previously-referenced blog post by Ziyang Liu covers CPS, the continuation monad, and call/cc in Haskell.
• Matt Might has a blog post on CPS in JavaScript.

Research papers:

• Oleg Kiselyov has published a breathtaking amount of research on continuations as a first class language feature. I think that attempting to translate some of these results to TypeScript using CPS could open up exciting possibilities.

Unknowns/possible future work #

• Is there an iterative implementation for the resumable exceptions problem which is at all comprehensible?

• What would it look like to implement coroutines via CPS? Would it be at all usable, and would there be any benefits? (I expect it would allow you to “clone” a generator, resuming its execution multiple times from multiple places. Could this be useful?)

• CPS can be abstracted into a continuation monad in Haskell. Call/CC is available on this monad. Can we take this backwards? What does call/CC look like in TypeScript while using CPS?

• Are there cases where CPS is being actively used in the TS ecosystem now? (Other than the general sense of callbacks for asynchronous code.)

• Is there a practical and mechanical way to transform CPS code into something stack safe in TypeScript?

• Is there anything that those of us outside of the major browser vendors can do to promote implementation of tail calls (whether “proper” or “syntactic”) in JavaScript engines other than JavaScriptCore?

If you know the answer to any of these questions please let me know!

All code samples shown in this post are released into the public domain under a CC0 license. Full example code and license text may be found here.