Thu Aug 20 09:27:08 CEST 2009

Delimited Continuations

In contrast with the previous PF implementation, which was mostly an
indirect threaded Forth, the current VM has a direct representation of
continuations.  Partial continuations are not so difficult to
construct on top of this: they simply splice the current K upto a

I prefer to use shift/reset, so let's implement that first.

Seems to work:

(shift 1 2 3) reset
<1> [{'1 '2 '3}]
<3> 1 2 3

The first paper about delimited continuations seems to be this
one[1].  In the introduction it mentions that the crucial idea is to
represent continuations as functions that can be composed.
In contrast, traditional continuations cannot be composed, as they do
not return a value to the calling context (it is discarded).

On page 7, on changing the CEK machine: ``One solution is changing
(CEK7) so that the invoked continuation is concatenated to the current
one: ...''  Apparently this is problematic for the denotational
semantics (continuations being opaque?) but I see no problems on the
implementation side.

Essentially, in PF this concatenation could be made ``lazy'' (just
like SEQ SUBroutines) by allowing K to be a tree instead of a list.
That way the interpreter can unpack branches one cell at a time.
Otoh, it seems simpler to place the burdon in `run' as it is now.

There are some other problems with the current implementation though:
the `prompt-tag' and `undip' functions are special, but can occur in
lists that are representing a continuation.  Therefore it is probably
best to represent the continuations abstractly to prevent programs
from destructing them.  In any case, it could be left as is now.  Just
keep in mind: a list of code can be converted to a continuation, but
vise versa isn't really sound.

[1] http://www.ccs.neu.edu/scheme/pubs/felleisen-beyond.pdf