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.
The same effect could obviously also be implemented using an anonymous lambda/func callback:
var multiply = func (x,y,callback) callback(x*y);
print( multiply(10,25,func (x) {x;} ) );
A more complex use case: threaded geodinfo() calls
The following experimental snippet of code illustrates how geodinfo calls can be run in a worker thread to query the terrain at a given position, and then execute a callback (named 'process' in this case) to process the collected data, note that there isn't any sort of synchronization taking place, rather anonymous/temporary functors and data structures are passed to the worker thread for gathering the data:
var lat = getprop("/position/latitude-deg");
var lon = getprop("/position/longitude-deg");
var step=0.01;
var results = {};
results.new = func return {parents:[results], store:[] };
var is_vec = func(v) typeof(v)=='vector';
var get_alt = func(vec) {
if ( is_vec(vec) ) vec[0] or nil;
}
# dummy processing routine
var process = func(vec,i) print('Thread #',i,':', size(vec));
var run_query = func(target, i,callback=process) {
for (var i=0;i<1;i+=step){
for (var j=0;j<1;j+=step) {
var p=get_alt( geodinfo(lat+i,lon+j) );
append(target,p) # save
}
}
# finished, do something with the data:
callback(target,i);
}
var profile = func(code,i='none') {
var (start,end) = ( systime(), 0 );
end=systime();
code(i);
print('Timing info:', end-start);
}
# some helper functions
var test = func(i) profile ( func run_query(results.new().store, i));
var thread_test = func(i) thread.newthread( func test(i) );
# test('main loop');
thread_test(1);
thread_test(2);
thread_test(3);