Sat Jan 2 11:08:07 CET 2010
Experiments - trying to understand defunctionalized continuations
So, let's have a look at this from a more cocrete point of view: using
a trampoline VM loop, how to implement `if'?
* In the final implementation, the continuation represented as
nested frames needs to support continuation marks. So it might be
best to stick close to the current representation. However, the
tags that identify continuation frame constructors can be
implemented by primitive functions directly. However, this
modification can probably be made later.
* Represent environments and continuation stacks as efficiently as
possible (i.e. use vectors).
* Avoid creating garbage in the VM. Continuation frames themselves
are the main point. Make sure that this is limited to an absolute
minimum, i.e. the place where the current value is stored (passed
to the current continuation) should not be a fresh cell.
A place where a lot of garbage gets created in the original VM is
function argument evaluation: instead of simply pushing in-place onto
a stack, each evalated argument replaces the current continuation
frame. Note that when continuations can be captured, in-place update
is not allowed.
So how to fix this? VMs i've seen before keep the current value rib
stored in a register, and save the rib whenever a new frame gets
entered. Actually, this isn't much different except that it saves the
creation of frames for primitive function evaluations.
The question is now: once converted to CPS where the order of
evaluation is clear, does this need special support? I'm still mixing
up several ways of looking at the problem..
CPS-converted code names all intermediates explicitly, so they are
added to the current environment. Also, all primitive invocations are
values. The same goes for ANF.
At the VM level this needs just apply, and no sequencing of
So which one is simplest? ANF or CPS? Since continuations need to be
implemented as data structures in the current VM approach (due to
access to the continuation marks), ANF might be simplest.
However, this only side-steps the problem: sequencing still needs to
be encoded somewhere.
I wonder, is it possible to use `let*' (or a single-variable `let1') as
a primitive form, explicitly sequencing the calculations at compile
ANF does require the argument value to be stored in the environment
multiple times: once when evaluated, and once when applied. I.e.:
(let ((fn ...)
(apply fn arg1 arg2))
The `apply' extend the environment of `fn' with values from the
environment of the body of the let expression.
Can this be optimized? I.e. something like this: first evaluated fn,
get its environment, and extend that environment directly.
This then gets into trouble with vararg functions.
Alternatively: only one argument functions? This makes the
continuations simpler, moves sequencing to the compiler, but produces
Is this so?
However, single-argument abstractions seem simpler to implement.
What about this: single-argument abstractions, and primitive
invocations in terms of variable references using De Bruijn indices.
So.. looks like ANF isn't necessary: creating separate continuation
frames for all the instructions seems to be simplest.
The idea behind ANF is then really that the only point where any
continuation frames are created is for the body of a let form. All
the other forms take values directly.
Maybe this is simpler indeed...