Chapter 19. Continuation-Passing Style

One can approach the notion of continuation from many different angles. I would like to start with asynchronous function calls in Javascript (JS), which are often employed for the purpose of eliminating potential blocking due to inputs or resources needed for execution being yet to be made available.

Let us use do_async1 and do_async2 to refer to two functions such that calls made to them are supposed to be executed asynchronously (so as to avoid potential blocking of entire program execution):

In the body of the following function do_async12, a call to do_async1 is followed by another call to do_async2: Calling do_async1 returns immediately after the actual work to be done is scheduled. And the same can be said about calling do_async2. There is in general no guarantee that the work scheduled for calling do_async1 is done ahead of the work scheduled for calling do_async2 or vice versa. What needs to be done if we want to enforce such an order? One solution is to provide a variant of do_async1 of the following interface: The argument passed to do_async1_cont is a thunk (that is, a nullary closure-function), which is supposed to be called immediately after the work scheduled for do_async1 is done. And this thunk is often given the name continuation, referring to the work that needs to be continued. In the following presentatin, cont0() may also be used as a shorthand for cfun(void). With do_async1_cont, the function do_async1() can be given the following implementation: which simply means that no more work is needed after the work scheduled for calling do_async1 is done. As for the function do_async12(), the following implementation can be given: where a call to do_async2 is to be made only after the work scheduled for do_async1 is finished. In fact, we can require that each function take a continuation argument if it ever schedules work to be done asynchronously. For instance, we can have the following variant of do_async12: where the interface for do_async2_cont is just like that for do_async1_cont. And this style of coding is often referred to as continuation-passing style (CPS).

In the following presentation, I would like to present a few more examples that contrast the direct style with the CPS-style. Let cont1 be declared as follows:

The functions fact and k_fact given below are implemented in the direct style and the CPS-style, respectively: Given an integer n and a continuation k, k_fact(n, k) basically means to pass fact(n) to the continuation k. Please note that the continuation argument passed to the recursive call in the body of k_fact is a newly built closure-function that multiplies by n whatever integer passed to it and then passes the product to the original continuation.

The next example is slightly more involved. The functions fibo and k_fibo given below are implemented in the direct style and the CPS-style, respectively:

Given an integer n and a continuation k, k_fibo(n, k) basically means to pass fibo(n) to the continuation k. There are two recursive calls in the body of fibo; they are translated into two recurisve calls in the body of k_fibo, where the second one appears in the continuation passed to the first one.

Going from fact to k_fact and fibo to k_fibo is often referred to as CPS-translation. Note that the recursive calls in the bodies of k_fact and k_fibo are all tail-calls. In general, each recursive call in an implementation written in the direct style should be translated into a tail-recursive one in the corresponding implementation written in the CPS-style. If a recursive call in the direct style happens to be tail-recursive, then the corresponding tail-recursive call in the CPS-style is passed the same continuation as the one passed to its caller. For instance, the following example shows a tail-recursive function (fact2) in the direct style being translated into one (k_fact2) in the CPS-style:

As yet another example, let us see list0_map of the direct style contrasted with list0_kmap of the CPS-style:

Note that the argument f0 (for list0_kmap) takes a continuation as its second argument, which makes f0 a second-order function. Therefore, list0_kmap is itself a third-order function.

The last example in this chapter is the following stream-processing function written in CPS-style:

Given a stream and a function, stream_kforeach processes an element in the given stream by applying the given function to it; if the function returns true, then stream_kforeach repeats to process the next element (if it exists); if the function returns false, then stream_kforeach stops processing the rest of the elements and terminates. Of course, what is described here is actually done in CPS-style. Please click here to see a demo of stream_kforeach being called to display the (infinite) stream of prime numbers: 2, 3, 5, 7, 11, etc. For the source code of demo, please see Sieve.dats.

Please find on-line the entirety of the code used in this chapter. The mentioned URL link(s) can be found as follows:

• https://ats-lang.github.io/DOCUMENT/ATS2FUNCRASH/LECTURE/12/CODE/Sieve.html

• https://github.com/ats-lang/ats-lang.github.io/blob/master/DOCUMENT/ATS2FUNCRASH/LECTURE/12/CODE/Sieve.dats