are our runtime continuations real continuations?
Erick Tryzelaar
instead of using the c stack. Is this correct? I'm trying to decide
how to go about implementing the runtime support for nonlocal gotos.
According to some exception paper by the c-- folks, there are
essentially 4 techniques for implementing exceptional flow control:
http://cminusminus.org/download/c--exn.pdf
1. stack cutting, where you just reset the frame pointer and program
counter to the landing pad. Stack cutting is cheap, but you always pay
for creating the landing pad.
2. stack unwinding, where you step through each frame down to the
landing pad. As long as there's no exception there's no cost, but
walking the stack can be expensive.
3. Native unwinding, where the caller and callee have a table of
return locations.
4. Continuation passing scheme, where you just use tail calls and heap
allocated stack frames. Calls can be pretty expensive unless you can
use a fast GC.
Assuming we do need full continuations, doing CPS would be the simplest.
john skaller
On 18/09/2009, at 9:38 AM, Erick Tryzelaar wrote:
>
> As far as I can tell, we're essentially doing CPS to manage our stack,
> instead of using the c stack. Is this correct?
More or less. Technically procedures use the method of "resumptions".
Felix (C++ version) uses an object which contains a program counter,
and represents a "stack frame". These are heap allocated.
> I'm trying to decide
> how to go about implementing the runtime support for nonlocal gotos.
Felix unwinds the procedure stack because otherwise you can
end up with pointer cycles. If you then point at a variable in a
frame the whole cycle is reachable. Unwinding zeros out the
link causing the cycles.
Felix unwinds the machine stack by throwing a C++ exception.
> Assuming we do need full continuations, doing CPS would be the
> simplest.
Alway read stuff from function programming people with grains of
salt and battery acid .. :)
CPS in a functional language is quite different to a procedural
language,
and don't forget fthreads.
However "expensive" for the "naive" implementation ignores the fact
that the optimiser removes most of these overheads, mainly by
inlining but also by using machine stack when possible instead of
heap frames.
Technically CPS passes continuations into a function which it
tail calls. Felix does not pass continuations: its stack frames
ARE continuations. The driver holds a pointer to the top
(active) frame, and receives a new one to resume when the
procedure returns, Felix doesn't really "pass* continuations
to a procedure: they're passed to the driver.
--
john skaller
ska...@users.sourceforge.net