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 IAA14124; Tue, 24 Aug 2004 08:47:48 +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 IAA13702 for ; Tue, 24 Aug 2004 08:47:47 +0200 (MET DST) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i7O6limL001228 for ; Tue, 24 Aug 2004 08:47:45 +0200 Received: from [192.168.1.200] (ppp212-216.lns2.syd3.internode.on.net [203.122.212.216]) by smtp3.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id i7O6lVHY035555; Tue, 24 Aug 2004 16:17:32 +0930 (CST) Subject: Re: [Caml-list] Continuations From: skaller Reply-To: skaller@users.sourceforge.net To: Nathaniel Gray Cc: =?ISO-8859-1?Q?S=E9bastien?= Hinderer , caml-list@pauillac.inria.fr In-Reply-To: References: <20040813212722.GA1158@galois> Content-Type: text/plain Message-Id: <1093330050.15255.417.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 24 Aug 2004 16:47:31 +1000 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 412AE490.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 sourceforge:01 2004:99 32,:01 python:01 closures:01 9660:01 glebe:01 anyhow:01 inefficient:01 closure:01 nsw:01 caltech:01 snail:02 continuation:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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