Re: [Caml-list] Continuations

[skaller <skaller@users.sourceforge.net>]

On Tue, 2004-08-24 at 08:32, Nathaniel Gray wrote:

> I wrote a "simple" tutorial on continuations that you might try
> reading.  You can find it here:
>    http://mojave.caltech.edu/papers/cont-tut.ps
> 
> Let me know if there is anything that you think could be improved in
> terms of clarity.

This is a nice article to read if you know Python.
However I'm left a bit confused about what happens
to the call stack in an essentially recursive function.

CPS doesn't eliminate the call chain, because clearly
that's impossible -- so where does it go? The answer
is that the continuation is a closure which encapsulates
the local variables of the caller -- at least the ones needed
by the 'rest of the function' after the call point, including
the arguments -- which thus includes some other continuation.
Hence the continuations link these frames in a 'stack' 
in such cases anyhow -- the *machine* stack is eliminated
and replaced by a list of heap allocated objects.

This is likely to be inefficient in cases where the
machine stack *could* have been used effectively.
So I'm left wondering how to modify the CPS algorithm
to only transform 'essential' function calls.

In Felix, there is rule which determines whether this
is possible. The machine stack must be empty when
an explicit 'yield' operation is executed (yield
works by returning the point in the code to resume
plus its context)

So in some cases it is easy to determine (meaning --
without data flow analysis) that a call can safely
use the more efficient machine stack.

In particular, procedures can yield but
functions cannot -- so functional code always uses
the machine stack.

My guess is the modified CPS algorithm would first
apply the standard one then do a simplified kind
of data flow analysis to eliminate some non-essential
heap closures and put the information back on the stack.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners