CSP or Continuation-Passing Style is a style of programming in which
functions return results via callbacks.
+ operator is a function that takes two numbers and
returns their sum. In CSP
+ operator becomes a function that takes
three arguments, two terms and a callback, usually called a continuation in
the context of CSP.
In Java we can express this as:
Because functions’ results are always returned via callback calls, CSP is forcing us to name the returned values by naming callback parameters. In addition CSP makes the order of evaluation of an expression explicit. For example, a simple Java program in imperative style:
Can be expressed in CSP as follows:
While transforming imperative programs into CSP form we may encounter
problems with handling procedures (methods returning
void in Java).
A lot of functional programming languages do not support procedures,
instead they define a special type called
Unit, that has only
a single value and use that type to signify that function does
not return any meaningful data.
Unit type is often identified with the empty tuple
In Java we do not have
Unit, but we may use
Void type with its only
null to simulate it.
While looking at our last example we may notice that in CSP form,
function arguments can be in one of three forms:
a constant, a variable or a lambda expression.
There is no rule preventing us from passing two or more
callbacks to a single function.
Indeed this is necessary to translate
if statement to CSP counterpart:
Cont<Boolean> we could use here
Cont<Void> as well.
To get a better feel for CSP we will look at three more examples. We will start with a simple (naive) program for computing sum of all numbers between given two numbers:
The transformation to CSP will become easier
if we first replace
for loop with recursion:
This version can be easily translated into CSP:
gt is the CSP counterpart of
Next we will transform factorial computing function. This time we will start with a recursive definition that is easier to translate:
CSP version of factorial looks like this:
As the last example we will transform a function that computes Fibonacci sequence:
In CSP it looks like this:
Now we should have, at least intuitive feel, how the
transformation to CSP works. In fact any program can be
transformed to CSP. The last point is quite interesting,
especially if we pass
() -> exit(0) or some other not-returning function
as the last continuation. Why? Because in that case we will
never return from any of the called functions.
Let’s see how this works on a simple example:
The entire idea of having a call stack is about providing a way for
the called functions to return the control to the callers.
But if we are never returning, then we don’t need a call stack, right?
Not so fast, some of you may say - what about passing arguments to
the called functions,
call stack is used for that too. Yes, the arguments are also stored on
the call stack but with CSP we capture
the values of arguments using closures.
Of course JVM does not know that our programs are in CSP form or that they
would do fine without having a call stack at all.
Instead we get a new call stack frame every time we call something,
this results in
StackOverflowError quickly when we call
factorial(3000, r -> ...).
StackOverflowErrors we may use a technique called trampolining.
Trampolining in connection with CSP
could reduce the required call stack space to a constant number
The idea of trampolining is very simple, we split computation into
parts and then we compute only the first part and return a
continuation (called thunk) that is responsible for computing the rest.
The returned continuation captures the result of the first computation in
its closure so we don’t have to recompute it.
Let’s see how a trampolined
+ operator would looks like:
Notice that trampolined
+ operator splits its computation
into two parts: computing the sum and calling the continuation.
The called continuation will again split it’s work and so on and on.
add3 function illustrates two key points.
One is that the logical flow of the program stays the same, we just
call the passed continuations like in a pure CSP program.
The other is, that to introduce trampolining we only need to modify
primitives provided by our programming language (operators and statements).
The program code stays the same.
Of course because Java is a statically-typed language we need to change
functions return type from
Thunk, but this is
a simple mechanical change that would not be necessary in
a dynamically-typed language.
Next example illustrates how trampolined
if statement and
factorial looks like. Notice that factorial code did not change,
not counting the return type:
Because we are now performing computation “in parts”, we need a procedure that will be continually invoking returned thunks, thus ensuring that out computation is making progress. A procedure like this is called a trampoline:
We are also providing a new primitive operator
can be used to mark the last part of the computation.
trampoline we may now compute
without any troubles:
As a side effect, we may now use trampoline to mix CSP and imperative code in the same program.
CSP and trampolining are not mere theoretical concepts, there where and are still used to implement e.g. LISP interpreters. Continuations can also be used to simplify backtracking algorithms. Source code for this blog post can be found here.