Continuations in Common Lisp
An introductory guide, using the continuation-passing macros of Paul Graham’s On Lisp
Continuations are a difficult concept, but one that has certain value in certain applications. In this guide, I will try to explain the concepts and how to implement continuations within Common Lisp, hopefully it helps in your understanding of this topic. I suspect you will have to read a few different explanations from different sources and hopefully one of them will click. Hopefully you find the below guide useful.
Part 1 (this page) will give a conceptual overview of Continuations, while Part 2 (to come shortly) will detail a possible implementation in Common Lisp (based on Paul Graham’s continuation-passing macros in On Lisp).
What are Continuations?
A continuation can be considered a program that is frozen in action. You can save this object for as long as you like, and when you call it, it will restart the computation taking place when it was created.
I like to think of a continuation as a bookmark within a program. Consider the following expression:
> (+ 1 (+ 2 (+ 3 (+ 4 5))))
;; Which may be easier to read as follows:> (+ 1
(+ 2
(+ 3
(+ 4 5))))
We could rewrite this program as:
- Add 4 and 5 to give 9
- Add 3 to the output of step 1 (9) to give 12
- Add 2 to the output of step 2 (12) to give 14
- Add 1 to the output of step 3 (14) to give 15
Say we took a continuation after step 2, and saved this within an object called *cont*. This continuation would represent the remainder of the above program, namely steps 3 and 4.
Let’s work with pseudocode for a bit. Assume we can call this continuation and pass in a value, say 7, with the following:
> (*cont* 7)The continuation *cont* is a functional object and here will restart the remainder of the program (steps 3 and 4 in the above), but using the value supplied (7) and not the original value at the end of step 2 (12). Thus the above expression will return 10:
> (*cont* 7)10;; The above is equivalent to (+ 1 (+ 2 7)), where the 7 is the value supplied to the continuation
Continuations from another perspective
Let’s revisit the above, but from a different perspective. When our Common Lisp interpreter evaluates the earlier expression, it evaluates each term from left to right. This has an effect of going down the call stack (in theory — I don’t am not sure if call stacks are actually created for the simple example below, but you can imagine the same process for functions calling other functions and so on).
Once the evaluator reaches the bottom of the stack, it starts returning the values upwards to the top. The above four steps capture this return process. Thus, Lisp will evaluate the forms from left to right and downwards, and then once all the forms are evaluated, it will return values upwards.
To help understand continuations, it helps to visualise that Lisp evaluates forms downwards and returns forms upwards.
Let us know visualise our continuation from above with the below. If you carefully step through our example, you will hopefully see that the continuation refers actually to the top part of the expression and not the bottom part. Thus, while a continuation refers to the remainder of a program, once we realise that returns values are returned upwards, we realise the remainder of the program is all the forms above the point we take a continuation, and not below it. For me this was a pretty important point, so hopefully you appreciate it too.
So again, for repetition, evaluate downwards, but return upwards. The last parts of a program are the ones at the top, i.e. last in first out, or alternatively, first in last out :)
A natural question then would be, what is the bottom part of the above program, namely
> (+ 3 (+ 4 5))This is just a normal function call. We don’t need any special mechanisms to “save” it or re-run it — its just a simple form that we need to run. One could very easily store these function calls in a variable and recall them later, with something like the following:
> (defvar *saved-form*)> (let ((next-steps (lambda (a)
(+ 3 (+ 4 a)))))
(setf *saved-form* next-steps)
(funcall next-steps 5))12> *saved-form*#<FUNCTION (LAMBDA (A)) {52C670EB}>> (funcall *saved-form* 5)12
So what’s your point?
To cut a long story short, it is very easy to know what is happening next, i.e. the forms we are about to evaluate (such as within the let above). It is a lot harder to know what’s happened before, because that would require going back up the call stack all the way up to the top level, something that can be done, but something that is not readily apparent from the code block that you are currently looking at.
For example, how could we represent the above continuation? Perhaps we could do
> (defun *cont* (a)
(+ 1 (+ 2 a)))This doesn’t seem too bad. But imagine if we had many levels to our call stack, with recursions as well. As I understand, it is not an easy task.
Conceptually, in functional programming, we write downwards (as per the above diagrams). So it is relatively easy to keep track of what is next, but we tend to lose track of what happened before.
Imperative vs. Declarative Programming
I guess the central concept in all of this is the differences between imperative & declarative programming. Courtesy of Stack Overflow:
- An imperative language uses a sequence of statements to determine how to reach a certain goal. These statements are said to change the state of the program as each one is executed in turn.
- On the other hand, functional programming is a form of declarative programming. Declarative programming is a non-imperative style of programming in which programs describe their desired results without explicitly listing commands or steps that must be performed.
In our example, imperative programming would be the four steps we outlined at the start, step by step commands on how to execute a program from start to finish. In such styles of programming, it is relatively easy to keep track of the next steps, after all it is a step by step process.
On the other hand, the functional example we gave you was declarative. At the first step we said, give us the sum of 1 and (+ 2 …). The latter object was not yet calculated, we just said we want it. It is only in subsequent steps that we worked downwards and evaluated each part of this form and calculated the value to be added to 1.
One may think the return of values upwards as the imperative calculation done by the interpreter to calculate the final outcome, after evaluating each part, i.e.:
- A form is an expression of what we want
- Evaluating the elements of the form → Determining what we want
- Returning the values → Giving us what we want
In functional programming, it is easy to ask for what we want (i.e. a form is an expression of what we want), but it is harder to express the steps to get it. For this reason, continuations, which are the remainder of steps in a program at a particular point in the program, are harder to express manually in functional programming, as the style of the functional paradigm obscures this part (the “how”) in favour for the “what”.
Returning back to our earlier discussion, it is relatively easy to ask for the bottom part (+ 3 (+ 4 5)) as that is simply asking for what we want; its a bit harder to ask for the top part, because that is remainder of steps in a calculation, and our language style explicitly obscures the steps of calculation (the “how”) from the steps of evaluation (asking for “what’ we want).
Continuations are thus an important mechanism to bridge this gap, to make it easier to get the remaining steps of a program. I am no expert, but based on the above, I would assume continuations hold far less importance in imperative languages because the remaining steps of a program are very obvious in those languages.
And as a final concluding thought to Part 1 of this guide, I hope the above elaboration highlights the importance of understanding and using continuations in functional programming, as they represent a key facet of the limitations of the language itself (limitations may not be the best word, but rather this deficiency is simply an outcome of functional programming focusing on what we want and not how).
Continuations in Common Lisp (Part 2) — Sneak Peak
Let’s now move on and learn how to implement continuations in Common Lisp. Below are the macros we need. Yikes! We will cover these in Part 2 of the guide, to come out shortly.
(defvar *actual-cont* #'identity)(define-symbol-macro *cont* *actual-cont*)(defmacro =defun (name parameters &body body)
(let ((f (intern (concatenate 'string
"="
(symbol-name name)))))
`(progn
(defmacro ,name ,parameters
`(,',f *cont* ,,@parameters))
(defun ,f (*cont* ,@parameters)
,@body))))(defmacro =bind (parameters expression &body body)
`(let ((*cont* #'(lambda ,parameters ,@body)))
,expression))(defmacro =values (&rest return-values)
`(funcall *cont* ,@return-values))(defmacro =funcall (fn &rest arguments)
`(funcall ,fn *cont* ,@arguments))(defmacro =apply (fn &rest arguments)
`(apply ,fn *cont* ,@arguments))(defmacro =lambda (parameters &body body)
`#'(lambda (*cont* ,@parameters)
,@body))
