Howto:Continuation-passing style programming in Nasal

This article is a stub. You can help the wiki by expanding it.

In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a so called "continuation", i.e. a function callback that is to be invoked by the called function once it has completed. This means: functions are never allowed to return to their caller- ever!

First class continuations can be used to implement exceptions, coroutines, threads, generator functions and many other constructs. There are particular advantages when implementing concurrent algorithms and code.

In functional programming, this technique is facilitated by using so called "tail calls", which are optimized into jumps/gotos internally, so that they don't cause a stack overflow. Nasal supports first class functions, closures, tail calls and also continuations.

So, functions written in CPS also do not require a call stack: they effectively create one manually, by using lambda expressions ("func" in Nasal) to build new continuations on top of old ones.

Any conventional function or function call can be rewritten in CPS, so it is possible to throw away stack use completely and only use continuations. This might actually make the implementation simpler, because two operations, call and return, are replaced by "goto with parameters".

Instead of "returning" values as in the more familiar direct style, a function written in continuation-passing style takes an explicit "continuation" argument, i.e. a function which is meant to receive the result of the computation performed within the original function.

For example, consider the following conventional style:

var multiply = func(x,y) return x*y;
print( multiply(10,25) );

As you know by now, in CPS style, each procedure takes an extra argument representing what should be done with the result the function is calculating. Here's the same code in CPS style:

var multiply = func (x,y,callback) callback(x*y);
multiply(10,25,print);

Note, how the explicit call to print has become an argument to the multiply function, so that it is invoked by the called function itself, rather than its caller.

CPS programming also makes it easy to express unusual control structures, like catch/throw or other non-local transfers of control.

The key to CPS is to remember that (a) every function takes an extra argument, its continuation, and (b) every argument in a function call must be either a variable or a lambda expression, i.e. a func expression in Nasal (not a more complex expression).

Similarly, when a subroutine is invoked within a CPS function, the calling function is required to supply a procedure to be invoked with the subroutine's "return" value.

Expressing code in this form makes a number of things explicit which are implicit in direct style. These include: procedure returns, which become apparent as calls to a continuation; intermediate values, which are all given names; order of argument evaluation, which is made explicit; and tail calls, which simply is calling a procedure with the same continuation that was passed to the caller, unmodified.

CPS has the effect of turning expressions "inside-out" because the innermost parts of the expression must be evaluated first, so CPS explicates the order of evaluation as well as the control flow.

Obviously, in order to call a procedure written in CPS from a procedure written in direct style, it is necessary to provide a continuation that will receive the result computed by the CPS procedure, i.e. a Nasal helper function that serves as a continuation callback:

var multiply = func (x,y,callback) callback(x*y);
var get_result = func(result) return result; # helper function to serve as a continuation proxy
print( multiply(10,25,get_result) );

Note how Nasal's built-in "print" function is invoked on a CPS function by using a dummy function (get_result) to return the result of the computation to the caller.

Links

• http://en.wikipedia.org/wiki/Continuation-passing_style
• http://c2.com/cgi/wiki?ContinuationPassingStyle
• http://matt.might.net/articles/by-example-continuation-passing-style/
• http://marijnhaverbeke.nl/cps/