Re: Abstracting continuations

[address@hidden]

Michael St. Hippolyte wrote:
> [...] I understand how to define a continuation by taking a snapshot of
> the relevant program state at a particular point in the running of the
> program. What I'm curious about is whether there are any languages that
> let you define a continuation without actually having to run the program
> to that point first.

There are probably many ways to interpret what you mean by defining a
continuation.

One possible answer to your question might be a language that has eval.
Eval allows you to construct (or define) a program fragment and then
evaluate it.

Eval ordinarily returns to the caller, but one could imagine a different
primitive, say (replace-continuation k v), that would take a continuation
and a value and would ditch the current continuation and start executing
the specified continuation (k v). Actually, this is pretty much exactly
what the bash builtin command exec does.

A third idea comes from my spare time hobby. I have been designing a
functional higher-order programming language, which I call Order, on top
of the C preprocessor macro mechanism. The current implementation of the
Order interpreter is based on an abstract machine called the continuation
machine. The purpose of the continuation machine is to make it possible to
compute recursive functions on the C preprocessor. (If you know the C
preprocessor, you should know that C preprocessor macros can not be
recursive nor is there any builtin mechanism for any kind of recursion,
iteration or repetition.) The continuation machine essentially takes as a
parameter a delayed macro call to execute:

   (macro, param1, param2, param3, ...)

The continuation machine then expands the macro

   CM_##macro(param1, param2, param3, ...)

The macro must either expand to a new delayed macro call, or expand to a
special sequence of tokens that stops the machine. For example, an
instruction that would diverge, could look like this:

#define CM_DIVERGE(...) (DIVERGE,__VA_ARGS__)

The continuation machine keeps expanding the result of the macro expansion
until it expands the special stop token sequence. (The continuation
machine essentially computes a fixed point.)

In order to be able to compute arbitrary functions using the continuation
machine, one needs to write the functions in CPS (continuation passing
style). For example, a pair of instructions that performs list reversal
could look like this:

#define CM_REVERSE(l,...) \
  (REVERSE_2,,l,__VA_ARGS__)
#define CM_REVERSE_2(r,l,K,...)                   \
  IF(IS_CONS(l),                                  \
     (REVERSE_2,(CAR(l),r),CDR(l),K,__VA_ARGS__), \
     (K,r,__VA_ARGS__))

Note the K parameter and how the alternative of the IF-expression
essentially passes the result, r, of list reversal to K.

(Actually, instruction definitions are somewhat more complicated due to
efficiency considerations, but the above could be made to work.)

The continuation machine essentially makes no restrictions on how any
particular instruction computes the next delayed macro call. This
means that an instruction can essentially replace the continuation with
anything that it likes. One instruction that is used in the implementation
of the Order interpreter is called REPLACE_C and essentially replaces
the continuation with its parameters. (The REPLACE_C instruction is
actually used in the implementation of the bind_cc(<pattern>,<expr>)
special form of the Order language. Yes, the interpreter has first class
continuations.)

Regards,
  Vesa Karvonen