call/cc is a powerful tool for implementing custom control forms operators. However, call/cc can be pretty unwieldy, so people tend to use delimited, composable continuations with operators like reset and shift. But what if I told you that these operators can be implemented using just call/cc?

In this post, we’ll implement delimited continuations, composable continuations, dynamic-wind, and parameters all from just call/cc. I will assume a solid familiarity with continuations and Racket. If you aren’t very familiar, then feel free to check out my continuations post to get some background. But even having read that, you sould play around with them a lot to get familiar, because this post is pretty heavy on continuation weirdness!

1  Delimited and Composable Continuations

Without delimiters, continuations created with call/cc capture the entire program. Also, the continuations created with call/cc "jump" when you call them and they never return, so you can’t use the result of calling a continuation. This is why they’re called non-composable continuations. These two facts make call/cc confusing and difficult to use, so people usually use delimited, composable continuations with operators like reset and shift. But these can actually be implemented in terms of call/cc! So if you’re working in a language with just call/cc and want delimited, composable continuations, you can implement them yourself.

Before we get into any implementation, I need to give credit where credit is due. Most of the code in this post is based on code found on Oleg Kiselyov’s blog. This post puts some of those pieces together, expands on them, and explains them in more detail.

Let’s think about what delimited continuations are. When we wrap code in a reset, continuations created inside only capture up to the reset. In other words, calling a delimited continuation returns the result of "filling the continuation’s hole" and running the rest of the reset’s body. Calling an undelimited continuation fills in the hole and runs the rest of the whole program.

Another property of continuations is composability. Non-composable continuations are like jumps. They are functions that never return, so you can’t use the result. Composable continuations actually do return their results. In my continuations post, I called these aborting and non-aborting continuations respectively. This has nothing to do with whether a continuation is delimited. However, composable continuations only make sense when the continuations are delimited. If a composable continuation captures the whole rest of the program, it also captures the part of the program that exits the process! So the composable continuation is saying "ok I’m going to run the code from this continuation and then I’ll come back to you", but then while it’s doing that, the world ends, so it never gets back to you.

Side note: If you use call-with-composable-continuation from the repl, the continuations will actually return. But if you create a Racket program that just evaluates that expression, when run the program, you’ll see that the continuation doesn’t return. This is because the repl pretty much wraps top-level expression in a reset and modules don’t.

Our task is to limit how much is captured by a continuation and allow us to use the results of continuations.

Now, without further ado, let’s get coding!

In case you haven’t seen it, (let/cc k body ...) is equivalent to (call/cc (lamdba (k) body ...)). It’s just easier to write.

To start, we implement something like a scheduler, or trampolining, in top*. go is a (non-composable) continuation that takes in a zero-argument function (a thunk), and ends up jumping here to the "scheduler". This effectively throws away the context of the program as far as the runtime is concerned. We’ll see why we do this soon.

go is set to a continuation that saves its argument to thnk, runs it, stores the result in v, pops the next saved continuation off the stack, and calls it with the result of the thunk. We’ll see who pushes continuations to the stack soon.

Normally, we’d just put the body of top* at the beginning of the program. But since we’re going to be running code in a repl, which delimits our continuations, we need to wrap our expressions with top to establish the context of the scheduler every time. Pretend that instead of (program-thunk), we just had the entire rest of the program right there.

In reset, we push the current continuation onto pstack and jump to the scheduler with the body as a thunk. Remember, the scheduler runs the body, saves the result, pops a continuation off the stack, and calls that continuation with the result. Pushing a continuation onto the stack before jumping to the scheduler ends up causing the scheduler to jump back to that continuation with the result of running the thunk.

Let’s think about a simple example, (top (list (reset 1))). When we reach the reset, the current continuation wraps its argument in a list and exits. We push this continuation onto the stack and jump to the scheduler with the thunk (lambda () 1). This sets v to 1, pops that continuation from the stack, and then calls it with 1, resulting in exiting with '(1). So if there’s no funny business in the reset, it’s like it’s not even there.

In call-with-composable-continuation, we grab the current continuation k. But we don’t supply it to f directly. Instead, we give f a wrapped function that grabs cont, the current continuation at the time of applying k, and push that onto the stack before jumping to k. Since the reset ends up at the scheduler, k does too. k runs the body of the reset with the argument passed to it replacing the call-with-composable-continuation, but then since we pushed cont onto the stack, we return to the body of the call-with-composable-continuation instead of the reset! Don’t worry if that doesn’t fully make sense yet. We’ll go step by step through an example in a moment.

By the way, the reason we’re doing call-with-composable-continuation instead of shift for now because shift is basically call-with-composable-continuation with an abort. call-with-composable-continuation keeps it simple and minimizes the numer of things we have to keep in our head at once.

Now let’s step through that example from the code.

But before we talk about how it works under our implementation, let’s make sure we understand how it works in regular Racket. The continuation k should essentially be the function add1 since that’s the only thing between the reset and the call-with-composable-continuation. I wrapped the whole reset in a list to make sure that we’re only capturing up to the reset. When we do (k 1), we should get back 2. Then, we multiply that by 5, getting 10, and return that from the call-with-composable-continuation, which adds 1 to it and wraps it in a list.

Now how does our implementation work? I’ll put the code here again so we can follow it:

First, we establish the scheduler with top. Next, we call list, so when reset is called, the current continuation wraps its argument in a list and exits. reset pushes this continuation onto the stack and it’s the only continuation in it for now. Then, it jumps to the scheduler, discarding the context. At this point, we’re at that (when thnk ...) expression in top*. Then, we call the thunk, which is the body of the reset.

The first thing it does is call add1. Inside the add1, the current continuation, which we’ll get as k in a moment, adds 1 to its argument, sets that to v in the scheduler, pops a continuation off the stack, and calls it with v. We call call-with-composable-continuation, which gives us access to this continuation, but with a wrapper that pushes the current continuation cont at the time of calling k onto the stack. What happens when we call k?

We push the current continuation cont onto the stack and call k with 1. What does k do? It adds 1, sets that to v in the scheduler, pops cont off the stack, and calls it with the result. Now, we’re back in the body of the call-with-composable-continuation! And we resumed with 2, which was the result of calling k. This is exactly what we want! Then, we just multiply that 2 by 5 and return to the reset body, which adds 1, giving us 11.

Then, we return from the reset, which returns to the scheduler, which pops a continuation off the stack. What continuation is on the stack? Remember, we originally pushed the reset’s continuation onto the stack, then pushed cont onto the stack, then popped it to jump back to the call site of k. At this point, the next continuation is the reset’s, so we call it with the result of running the body of the reset, 11, which wraps that result in a list and exits. And we’re done!

The big idea is that reset saves the current continuation and jumps to the scheduler, telling it to run the body. Since the body runs in the scheduler’s context, continuations captured in the body will capture the end of the scheduler, which pops the next continuation off the stack and calls it, which jumps. This is how we avoid capturing the whole rest of the program, which includes the exit. By mutating the stack of continuations, we can control where we’ll end up next time we return to the scheduler.

Before we call a composable continuation k, we push the current continuation cont onto the stack. That way, we’ll run k, which will end at the scheduler, which will pop and resume at cont with the result of running the rest of the reset body with the argument we suppled to k. Pushing the current continuation onto the stack causes control to return to this point when we hit the end of the scheduler. That’s how we "trick" non-composable continuations into "returning a value". It’s really just two jumps with some weird stuff in between, but as far as the user’s concerned, it just looks like the continuation returned a value!

This is all very subtle and hard to follow. There are a lot of nonlocal jumps and there is mutation happening while we’re jumping all over the place. I encourage you to run through some more examples in your head and play around until you’re comfortable. This is very tricky stuff.

Now, let’s implement shift. Like I said before, shift is basically call-with-composable-continuation with an abort. Once we understand how reset and call-with-composable-continuation work, shift isn’t too much of a leap:

It’s the same as call-with-composable-continuation, but we wrap the body in a go, which jumps to the scheduler. Unlike reset, we don’t save the continuation before we jump. This has the effect of using whatever happens to be on the top of the stack, which is usually the reset’s continuation.

For example, let’s run through

We establish the scheduler and push the reset’s continuation onto the stack, which wraps its argument in a list and exits. When we end up at the shift, we jump to the scheduler with a thunk that returns 0. So we end up passing 0 to that continuation, resulting in '(0). When we jumped to the scheduler from the shift, we discarded the context that included the add1. The only thing that remembered that context was k, which we ignored.

So shift ends up replacing the entire reset with the result of the shift’s body. And it’s no different if we call k in the shift. k is basically a function as far as the user is concerned. It just happens to run the body of the reset that we aborted from.

And there we have it! Using undelimited, non-composable continuations, we implemented delimited and composable continuations.

Now what about dynamic-wind and parameters?

2  Dynamic Wind

Let’s say you’re working with files. You have the functions (open path) which opens a file at the path and returns a value representing the file, and (close file) which closes the file. We’re well-behaved programmers, so we will make sure that we always close our files when we’re done with them.

To make sure we never forget, let’s make an abstraction that closes the file for us when we’re done:

Very nice. But what if we do this?

We leave the body of with-file without closing it!

Alright, that’s unfortunate, but it’s not a huge deal. When the process ends, the operating system cleans up after us anyway.

But here is another example:

If we use saved-k to re-enter the body of with-file, at this point, the file is already closed! This would cause the body to fail. This would be a problem even if the continuation was composable.

In general, there are a lot of situations where you want to run code under some context that includes setup and cleanup, and continuations don’t play nice with that since they cause us to jump all over the place. What we want is an operation that allows us to run some body of code where every time we enter the body, we run some setup, and every time we leave the body, we run some cleanup, regardless of whether we naturally enter/exit or if it was because of a continuation jumping in or out. This operation is called dynamic-wind.

Let’s look at some examples:

Without dynamic-wind, the cleanup doesn’t run when we abort. Let’s look at another example:

Without dynamic-wind, we don’t get the setup when we re-enter.

Alright, how do we implement this thing?

When I was trying to learn how to implement it, the first implementation I found kept track of the thunks that were pending execution. We keep track of a stack of pairs of thunks. Each pair has a setup and a cleanup thunk. We maintain the invariant that a pair is in the stack if and only if the setup has been run and the cleanup hasn’t yet been run in the current dynamic context.

When we call a continuation, we are jumping from one dynamic context to another. When we create a continuation, we remember the continuation’s dynamic context by associating it with the current value of the stack of thunk pairs at the time of creation. When we call a continuation, we compare the current value of the stack with the continuation’s and run the thunks as appropriate. But as we go, we have to carefully and incrementally change the value of the stack to maintain the invariant. And we also have to be careful about which thunks to run and the order that we run them.

This implementation is very hard to understand and reason about. There is a lot of intricate book-keeping, there is global mutable state, and we’re jumping all over the place because of call/cc.

This implementation works fine with call/cc, but it was very difficult to try to generalize it to delimited continuations. To learn more about this strategy and see my failed attempt to generalize it to delimited continuations, you can look at my implementation.

As usual, all roads lead back to Oleg Kiselyov. His post Delimited continuations do dynamic-wind has an implementation in terms of delimited continuations. This implementation is much simpler and doesn’t need to be generalized to delimited continuations! This is the implementation we’ll discuss in this post. I only bothered mentioning the other implementation because it’s the original and it’s the first thing you’ll find if you’re looking around.

Before we get coding, I want to clarify that this implementation of dynamic-wind has nothing to do with the code we’ve just been writing for implementing delimited continuations. We’re going to start out with Racket’s built-in reset and shift operators, not the ones we made. We’ll connect everything at the end.

Now let’s start coding:

We define a new operator called yield, which shifts a record containing the value yielded and the continuation of the yield. Yield is sort of like an exception we can resume from. The expectation is that we are in the context of some handler that will decide what to do with the yield record.

For example, we can use yield to implement generators:

Here, for-generator is the "handler" for yield. We run the generator body in a reset and look at the result. If we yielded from the body, the result would be a yield record. In that case, we run the loop-body with the yielded value and recur, resuming the body. If the body ended on its own, we’d reach the other branch, in which case we’d return void and stop recurring.

How should dynamic-wind interact with yield? If we yield from inside of a dynamic-wind, then we should run the cleanup since we’re leaving the body. And when we resume from the yield, we should run the setup. And the yield should go right through the dynamic-wind to the handler outside of it. For example:

We should print setup cleanup 1 setup cleanup 2. First, we naturally run the setup on the way in. Then The yield exits the generator body, hence the first cleanup. In the handler, we print the yielded value, 1. Then, we resume, which re-enters the body, hence the second setup. Next, we naturally run the cleanup on the way out. Finally, the next yield just results in 2 getting printed with no dynamic-wind business.

Now, we’re ready to implement dynamic-wind:

The structure is similar to the generator. dynamic-wind is a handler for yields. We initialize our recursive loop with a (reset (thunk)), but we don’t run it right away because we haven’t run the setup yet. Instead, we wrap it in a thunk and call it th so we can run it later. Next, we run setup-thunk. Only after that do we run th, which runs the main thunk. Then we run the cleanup thunk, regardless of whether we finished naturally or yielded. This is because in either case, we want to run the cleanup.

Like in the generator, if we get a yield record, that means we yielded out of the main thunk. Since we want yields to go right through the dynamic-wind on the way out, we re-yield v to let the outer handler handle it. It’s like re-throwing an exception. But we also need the yield to go right through on the way back in, so we save the value that the outer handler resumes with to reenter and we resume the body by calling k with that value. But we don’t resume right away. We do it in a thunk that we recur on so we end up calling the setup before we re-enter the body. And since this is in a loop, the whole thing happens for future yields until the body finishes, in which case we return the value of the body.

This is very nice, but we don’t want to use yield. We want reset and shift! Luckily, we can implement reset and shift in terms of yield such that they play nice with dynamic-wind. But we also use reset and shift in our implementation of dynamic-wind. To avoid confusion, let’s make it clear whether we’re using the built-in operators or our operators that we’re making. We can do this with a qualified import:

To start, let’s think about how reset and shift should interact with dynamic-wind. For example:

Remember, shift aborts to the reset. That’s why we get the first cleanup. And when we call the continuation inside the shift, we re-enter the body, which is why we get the second setup. After we re-enter, we print "after the shift". Although the (k 1) is lexically inside of the dynamic-wind, it executes from outside of its dynamic extent because the shift aborts before we run it. Next, we exit naturally, which runs the cleanup.

Let’s look at another example:

The first setup comes naturally. The first cleanup is from the shift aborting. When we call saved-k, we get a setup from re-entering the dynamic-wind, we print "after the shift", and we exit naturally, running the cleanup. It’s really the same thing as last example, but instead of immediately resuming, we do it in the next repl prompt. But it’s interesting that the continuation "remembers" the dynamic-wind.

Alright, how do we implement this? Let’s try using the built-in reset and shift and see what happens:

Notice that we used our dynamic-wind, but racket’s reset and shift. We’re missing the inner setup and cleanup! We only get the natural ones, not the ones from jumping out and in. This is because the shift aborts right past the dynamic-wind to the reset, which means jumping past the code that runs the cleanup. And we resume right at the point of the shift instead of getting stopped going back through the dynamic-wind, skipping the setup on re-entry.

yield is the only thing that plays nice with dynamic-wind, so we’ll implement shift using it:

Similar to how we made yield in terms of shift, we make a struct representing the shift operation and yield that struct.

If we’re yielding, we’ll need a handler. Where should the shift get handled? Well, shift aborts out the reset, so it’s the perfect place to handle it! This means that shifts without a reset will just abort the program with a shift record, but that’s not a big deal. Theoretically, we could wrap the entire program in a reset and everything would work fine.

Like all the yield handlers we’ve written, we run the body in a reset. But we use the real Racket version, not the one we’re making. We inherit the delimiting behavior from the real version and add the yield handling on top of it. Anyway, if the body yields a shift record, we run the shift body with k, but wrapped in a reset. And this is our reset, not the built-in, real version. This recursive call is just like the looping that we used in our other handlers, but instead of a let loop, we just do a recursive call directly because it’s easier.

If something other than a shift record got yielded, we error. We do this because users aren’t going to be using yield, only reset and shift, which yield shift records. So we assume that any other kind of yield is from a mistake in our implementation.

You might be wondering why we bothered going through yield at all. If we want shift, why not just implement dynamic-wind in terms of shift instead of yield?

You could try to do that, but it’s much more straightforward with yield. With yield, the handler is what drives the control flow. After all, yield doesn’t give the caller access to a continuation! Only the handler gets access. And dynamic-wind is essentially a handler, so it fits in perfectly. The flow of the yield nicely captures the essence of jumping out of and into a dynamic extent.

With shift, the body drives the control flow, and there is no handler, which makes it harder to detect and handle exit and re-entry. We’d have to manipulate the body and the continuation or something. It’d be much trickier to figure out.

Now that we have reset and shift, let’s implement call-with-composable-continuation and call/cc:

call-with-composable-continuation is nothing surprising. It’s just shift, but we resume with the result of the body.

call/cc is a little weirder. It’s similar, but we wrap the continuation such that it shifts when you call it. This gives us the aborting behavior.

This is how you would normally implement these two operators in terms of shift. However, this implementation doesn’t play nice with dynamic-wind:

In our implementation, it looks like call/cc leaves the dynamic extent for some reason. This is because we use shift! Even though we’re resuming right away, we’re still going out of and into the body.

We can fix this with a little hack. We’ll add a tag to some yields that tells dynamic-wind to let it pass right on through without triggering cleanup and setup, trusting that the handler will resume right away. This will allow us to pretend like we never left.

We made a sub-struct of yield-record that we check for in dynamic-wind. If the yield record is an instance of this struct, we skip the cleanup and setup. There’s a little bit of book-keeping here, but it’s not too crazy. The only weird part is that when the continuation resumes for the first time, we need to avoid triggering the setup, but if we use the continuation from outside later like what we usually do with saved-k, we need it to trigger the setup. This all gets handled by the skip? flag since it is only ever true on that first shift that should pass through.

Anyway, let’s rewrite call-with-composable-continuation and call/cc to use these operators:

Nice!

2.1  Parameters

One very useful feature you can create with dynamic-wind is parameters, which implement dynamic binding.

For example, let’s say you want to run some function that prints stuff, but instead of it printing to standard out, you want to redirect its output to a file. One way to do this is to have it take in an output port and make it use the one passed to it instead of hard-coding standard out. But then you’d have to pass this output port around everywhere. And what if the function is part of some library and you can’t re-write it? Do we expect all libraries that might print stuff to take in output ports everywhere?

Well, a very hacky solution would be to have a global, mutable variable for the current output port, and expect everyone to follow a convention of using that global mutable variable. If we want to redirect some output, we could set! the variable to something else, run the code, and then set! it back to its old value. Sounds like a job for dynamic-wind!

The body can freely use and mutate current-output-port, and any code outside of the body doesn’t see the effects of this mutation. We do (set! new-output-port current-output-port) in case the body locally mutates the current output port, jumps out, and then jumps back in. When the body resumes, we want the variable to be exactly how it was before. This is called dynamic binding because the scope of the variable is the dynamic extent of the body, nothing to do with lexical scope. Nice! This is starting to sound less like some gross hack and more like a reasonable feature.

To avoid confusion between dynamically scoped variables and regular old lexically scoped variables, we’ll make a special abstraction called parameters:

Parameters are very useful. They are a powerful mechanism for allowing code to be dynamically configured without having to pass a configuration around everywhere.

3  Putting it All Together

At the beginning of this post, I told you that we could get all of this from just call/cc, but we implemented dynamic-wind in terms of reset and shift. Well, remember how we implemented reset and shift in terms of call/cc? That’s right, if we start out with just call/cc, we can implement reset and shift on top of that, implement yield and dynamic-wind in terms of that reset and shift, and then implement reset, shift, call/cc, and call-with-composable-continuation that play nice with dynamic-wind in terms of yield. If you want to see it all put together in one module, here it is. I’m not going to go through writing it here because there is nothing interesting and new. It’s just some layering and connecting pieces together in the obvious way.

4  Conclusion

From just the humble, confusing call/cc, we implemented all our favorite control operators and even added dynamic-wind to be able to set up and clean up context in the face of continuations. This is by no means the best way to implement these operators, it’s just what I found to be the easiest to understand. But if you’re stranded on an island with just duct tape and call/cc, you aren’t going to be stuck with nasty, undelimited, non-composable continuations!