I gave an introductory talk on R7RS Scheme in 2013 that included some neat examples using closures, continuations and macros. This article expands on that, intended for anyone curious about those concepts.
If your programming language supports continuations, you can implement any control flow construct in native source code form. That means you can import things like
I'll give simple examples on how all of the above can be implemented using closures, continuations and macros, using plain R7RS Scheme.
NOTE: This post is a work in progress that I'm posting early. The later examples doesn't include explanations, and some are outright missing. Also, if I get anything wrong, please let me know in the comments at the bottom.
You can run the examples using Chibi Scheme.
To get started, we need a function
println that simply prints all of its
arguments. We'll create a variadic function that simply calls
display on all
its arguments, and put it in a library called
Here's a test program
Running it produces
There are many ways to explain what continuations are, but I will offer two mental models that are very useful, with minor trade-offs in exactness.
A continuation represents the rest of the computation. A good way to think about this is that whenever you capture a continuation, you essentially set a label in the code that you can later jump back to. So it's almost like a GOTO or JUMP instruction, with the additional benefit of being able to pass along new values that will replace the value at the location where it jumps to. (Moreover, when you jump, the code will continue running from that location, returning to the correct functions that were active when you first captured the continuation.)
So, if you have a function that computes some mathematical expression, you can surround one of the variables with such a label. Later on, you can back jump to this label, but with a new value for that variable.
set_label will insert the current code location into the
label and return its input argument
age immediately. After that,
goto_label will jump back to the location pointed to by
label and continue
execution there, but now with the value of 500.
Running the program should print
Notice that after jumping to the label location, the program will continue
running at the
set_label(age) location. At this point in time, the value of
500 will be returned to the
print_person itself has to return, and the return
location this time around will be right after the
If we translate the previous example to Scheme, we can implement
To implement the final two functions, we'll use
call/cc. It has a special
Your code goes into
<body>, and from there we have access to a variable
continuation. It's actually a special function that lets you exit from
(call/cc ...)-block with a return value. If you do
(continuation 123), the program will jump back to the location of the
call/cc and continue running from there as if
123. And you can do that as many times as you want.
Now, the definition of
set-label uses the above form:
The code above will (1) capture the current continuation and put it inside the
continuation, (2) store the continuation in the global variable
labeland (3) return the value
Remember that our goal is to be able to jump back to where the
is used, but with new values.
label will eventually contain a continuation, the implementation
goto-label is straight-forward:
The final program can be run in Chibi Scheme. Put the following in a
Executing it gives:
Now I'll suggest a few mental models that can be used to understand how continuations work. After that, we'll revisit this example, but wrap everything up in a neat little library, so that we can write
in our Scheme programs.
Knowing a little bit about implementation strategies for continuations is of great help in understanding them.
Many Schemes use continuation passing style, but I think it's much easier to think of it in terms of copying and reinstating the call stack.
Recall that a call stack is a collection of stack frames. Each frame contains a return address, function arguments and perhaps also a placeholder for a return value.
In the program above, imagine that the program is a tree. At the root node, the
program first has a branch out to the definition of println, whose internal
definitions branch out from there. Next, it has a branch for the definition for
make-label, and so on:
The vertical line going from root and downwards — the trunk, so to speak — is what we call the top-level in Scheme.
call/cc does, in some implementations, is to take a copy of the
entire call stack from the top-level up to the current position.
So we copy a chunk of the call stack and put it in memory. This is what we mean when we say we "take a continuation".
When we want to invoke a continuation, we want to continue running at the same location that the continuation was taken. To do this, we just reinstate the call stack: Chop off the current call stack from the top-level up to the current position, and replace it with the one we have stored. Finally, we have a value to pass on, so we place that in the correct location at the very top of the stack where there is a place for the return-value. Then we continue running from there.
I'm doing some hand-waving here, of course. There are many other details that you'd have to do, but the point is to understand the general strategy.
Recall the goto example given earlier. It used a global variable
hold the continuation. This is a problem if we want to make a general
goto-library, because it means you can only ever jump to one location.
So we should take an extra argument to
goto-label. But Scheme
passes arguments by value and cannot — in general — mutate their "outer"
values: A function taking an argument can only modify it locally.
There are two ways to solve this: With or without macros.
Without macros, we could use label names instead of variable, but that requires a bit of house-keeping code. Let's use macros instead. We're going to need them for more advanced examples anyway.
A macro will expand its body and embed it at the location in the code where it's used. Think of it as a copy-and-paste operation that substitutes variables. The general form is:
syntax-rules tells which macro system to use. Yes, there are several
available. The one we use is pattern-based. The next empty
() is a list of
literals we don't want to substitute. In our case it's empty.
As a simple example, consider the
unless function, which will execute some
code if its first boolean value is false:
Or in pseudo-code:
The above definitions have a serious problem. Because they take values, which
means that they will always be evaluated. Imagine a
wipe-root function that
deletes everything on your drive and returns the number of important files you
lost. What would happen below?
Well, it will actually execute
(wipe-root) before passing on its return
unless. To work around that, we could wrap
wipe-root in a closure:
But that doesn't look anything like the ordinary if-statement. Another solution
would be to take a function by value,
(unless #f wipe-root), but that
wouldn't be very useful.
Nay, the elegant solution is to use macros to control evaluation:
Running the above code in Chibi will not call
therefore not print anything.
Note that some people dislike macros, because it can obscure the exact behaviour of your program. For example, things that look like functions may actually be macros, meaning you don't really know when — or if — your arguments are evaluated, and that makes it hard to reason about your program. I think they're great if used with care.
What we want is to be able to write
and with value-passing:
We'll use the same strategy as before, except that
can be invoked using a label and value, or only a label.
goto-label function uses
case-lambda, which patterns matches on its
invocation form. The first line matches calls to
(goto-label <label>), while
the second matches
(goto-label <label> <value>).
set-label macro also matches on the same two patterns. Here we use a
single underscore instead of typing out the full name of the macro.
Put that in a file called
goto.sld, and you should be able to run the above
Using the call stack model of explanation explained earlier, it means that taking a continuation copies the entire call stack down to the second-to-last frame of the top-level. This prevents us from having endless loops whenever we reinstate a continuation. It's a detail, don't worry.
Now, the big deal about continuations is that you can use them to implement any other control flow construct, from simple gotos to exception mechanisms, coroutines, cooperative threads, non-deterministic programming and so on.
But it turns out that undelimited continuations cannot do this without storing
one additional piece of state. That is also somewhat of a detail, but as you'll
see in the later examples. we always have to keep tabs on different
continuations. The more general continuation systems are delimited. They are
truly functional, and do not require explicitly storing continuations in
variables. Many Schemes provide these through constructs such as
prompt-abort. I won't go into those, but the main idea is
that instead of copying the call stack, you can put a marker somewhere and only
copy a part of it. That means that your continuations will be true
Anyway, undelimited continuations are unfortunately not part of the official
R7RS specification, so I will focus on
Anyway, let's dive right into the examples. Let's say we want to implement a
simple exception system. We can do that using
call/cc and then users can
have exception handling with a simple import statement of pure Scheme code.
To make our exception library useful, we'll wrap the functionality in macros.
The basic idea is to have a global
throw function that we pass the
continuation on to.
Running the above program,
When you catch an exception, wouldn't it be cool to fix the error and then have the program continue as if nothing happened? Here's one way of doing that.
Any language with closures can implement lazy evaluation, but if you have a macro system, you can change the user interface so that it feels like a natural part of the language.
I forgot to say this, but macro expansions happens at compile time. That's very important to remember. That means we should be able to provide our own comment system to Scheme. Our system will allow for nested comments as well, as in you can comment some code, but add an uncomment directive outside of that to make it run again.
If we later on want to enable that part of the code, we can do
The comments library:
Imagine you have a unit-testing framework where you test some code. If it fails, you want to print the expected result, the actual result but also the source code that gave you the error.
This can be done in languages like C using their
#define-macros, but it is a
bit limited and will not always let you define local variables and so on.
Here's a simple library that does that in Scheme.
(I think I wrote this. I'll find out and give credit where due.)
Probably the most boring thing to do, since you've probably done it yourself, but here it is anyway.
We also need the measure-time library:
Object orientation as a library: Bryan's Object System (actually the guy who wrote "Real World Haskell", I think).
Non-deterministic programming: http://c2.com/cgi/wiki?AmbSpecialForm Also: http://matt.might.net/articles/programming-with-continuations--exceptions-backtracking-search-threads-generators-coroutines/
Green threads: https://en.wikipedia.org/wiki/Continuation
It doesn't have anaphoric macros, but most systems give you defmacro anyway. It's just not standardized. However, the macro system in RnRS Scheme is hygienic, which is a good thing.
It doesn't have delimited continuations, but again, most Schemes actually provide them, it's just that there isn't a standardized interface.
What about Common Lisp? It probably has all of the above, either in the language itself or in libraries. Also, Common Lisp compilers are supposedly really good at delivering optimized binaries.
What other cool stuff can you implement with continuations? Take a look at what the Scala people are using them for. One cool usage that was made in Scheme was a web server that could serialize continuations and send them across processes. If I recall correctly, they used continuations to plug the stateless hole you have when doing the server-client-server round dance, so that you could program as if the user was there all the time, as in:
The above program serves a complete HTML page to the user, asking his name.
If he chooses to answer — and after any amount of time — the program will
extract his reply, put it in the
name variable and continue running as if
nothing had happened in between. In other words, we plug the statelessness hole
of HTTP using continuations, and can write programs that look like any other,
even though they go through an endless server-client round dance.