From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id AAA20477; Wed, 25 Aug 2004 00:18:11 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id AAA19938 for ; Wed, 25 Aug 2004 00:18:10 +0200 (MET DST) Received: from mproxy.gmail.com (rproxy.gmail.com [64.233.170.195]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i7OMI9GS019216 for ; Wed, 25 Aug 2004 00:18:10 +0200 Received: by mproxy.gmail.com with SMTP id 77so114597rnl for ; Tue, 24 Aug 2004 15:18:09 -0700 (PDT) Received: by 10.38.83.11 with SMTP id g11mr695945rnb; Tue, 24 Aug 2004 15:18:09 -0700 (PDT) Received: by 10.38.83.55 with HTTP; Tue, 24 Aug 2004 15:18:09 -0700 (PDT) Message-ID: Date: Tue, 24 Aug 2004 15:18:09 -0700 From: Nathaniel Gray Reply-To: Nathaniel Gray To: skaller@users.sourceforge.net Subject: Re: [Caml-list] Continuations Cc: "Sébastien Hinderer" , caml-list@pauillac.inria.fr In-Reply-To: <1093330050.15255.417.camel@pelican.wigram> Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit References: <20040813212722.GA1158@galois> <1093330050.15255.417.camel@pelican.wigram> X-Miltered: at nez-perce with ID 412BBEA1.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 2004:99 sourceforge:01 2004:99 32,:01 python:01 python:01 obtuse:01 closures:01 swept:99 closures:01 anyhow:01 inefficient:01 ocaml:01 closure:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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: > > 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