Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Continuations
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-08-24 (22:18)
From: Nathaniel Gray <n8gray@g...>
Subject: Re: [Caml-list] Continuations
On 24 Aug 2004 16:47:31 +1000, skaller <> 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:
> >
> >
> > 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?


>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- -->

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: