Re: [Caml-list] Continuations

[Nathaniel Gray <n8gray@gmail.com>]

On 24 Aug 2004 16:47:31 +1000, skaller <skaller@users.sourceforge.net> wrote:
> 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.

The intention was that that wouldn't matter.  :-)  Let me know if my
Python was too obtuse.

> 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.

Yes.  I was mainly trying to communicate the way that the CPS
transformation changes the control flow of a program and I wanted to
avoid discussing closures since they're also hard for people to
understand.  As you and several others have pointed out, I may have
swept too much under the rug.

> 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.

I suppose you could put any non-recursive (or tail-recursive)
sub-computation on the stack.  That would preclude the use of CPS to
support microthreading, however.  Doesn't OCaml use some kind of
hybrid stack/CPS system?

Cheers,
-n8

-- 
>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- http://mojave.cs.caltech.edu -->

-------------------
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