Introduction
I remember trying to learn Continuation Passing Style and having difficulty trying to grasp this concept. I think the problem I had was not understanding the motivation. I did not understand why this was important, what problem was it trying to solve. This article tries to shed some light on the subject.
Motivation
Stack based machines have the concept of call-and-return: at any time, a program can call a number of instructions (e.g. a function), and then return to the point of call. This enables a hierarchical composition of abstractions that are represented by blocks of code (e.g. functions). On these machines, blocks of code may communicate using the stack, for example the parameters of a function are, usually, passed through a stack. Higher level languages abstract the communication between blocks of code that uses stacks, expressing them as parameters or as the return value.
Register machines, however, have no stack. In these machines continuation passing style is a more natural way to program. Because there is no stack to control where to go after a code block ends, if you want to simulate a call-and-return, then, when you call a code block, you have to pass where to return to as well. The code block being called must cooperate with the caller, it must explicitly call the code block to execute when it itself is finished. Continuation passing style, is therefore a convention.
An example
Consider a simple assembly language (defined in BNF) that targets a register based machine, where you can group instructions into code bocks, delimited by curly braces, and identify them with a certain name:
<program> ::= <program> <code-block>
| <code-block>
<code-block> ::= <identifier> "{" <intructions> "}"
| <identifier> "{" "}"
<instructions> ::= <instructions> <instruction> | <instruction>
<instruction> ::= <register> ":=" <value>
| <register> ":=" <register> <binop> <value>
| print <value>
| if <register> = <value> jump <value>
| if <register> != <value> jump <value>
| jump <value>
<value> ::= <number> | <register> | <identifier>
Comments start with ";"
This is an example of a simple program that places the value 5 in register r1, increments it to 6 and prints it on the screen:
main {
r1 := 5
r1 := r1 + r1
print r1
}
Now we split this program into three blocks of code, placing each step into a block of code:
main {
r1 := 5
jump inc
}
inc {
r1 := r1 + r1
print r1
jump finish
}
finish {
print r1
}
Because of this restructuration, after a step is finished we jump to the next block of code (i.e. step). Now, if we want to reuse the block of code inc, we must abstract the label of the next block of code. Let us abstract it in the register r2:
main {
r1 := 5
r2 := finish
jump r1
}
inc {
r1 := r1 + r1
jump r2
}
finish {
print r1 -- will output '6'
}
The block of code inc now expects that a label is provided in the second register, which will be used to jump to after its computation finishes.
Another example: the factorial
Consider an implementation of the factorial function:
fact {
r3 := 1
jump fact_aux
}
fact_aux {
if r1 = 0 jump fact_finish
if r1 = 1 jump fact_finish
r3 := r3 * r1
r1 := r1 - 1
jump fact_aux
}
fact_finish {
r3 := r1
jump r2
}
The block of code fact_aux expects three registers, the first must hold the actual parameter of the factorial function, the second must hold the continuation label, and the third must hold the result of the last call. In the first two instructions we verify if we are in the base of the recursion; if so, then we jump to fact_finish, where we move the result into register r1 and then jump to the continuation held in register r2. If we are in an intermediate step, then we update the value of the result, decrement the value of the factorial, and, finally, jump to fact_aux.
Conclusion
Continuation passing style is ackward to reason about. Our brain is more used to divide and conquer. There are, however, examples of successful projects that use this notion as the foundation of its framework (like Python's Twisted). Continuation passing style and tail recursion enable the definition of stackless machines, making functional languages very efficient. Once the cornerstone is grasped (i.e. there is no return), continuation passing style is easy to master.
