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 RAA03146; Mon, 1 Oct 2001 17:53:27 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA03244 for caml-list@pauillac.inria.fr; Mon, 1 Oct 2001 17:53:27 +0200 (MET DST) 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 RAA02714 for ; Mon, 1 Oct 2001 17:42:23 +0200 (MET DST) Received: from tcsnpop1.tcsn.uswest.net (tcsnpop1.tcsn.uswest.net [207.108.112.1]) by nez-perce.inria.fr (8.11.1/8.10.0) with SMTP id f91FgLr00940 for ; Mon, 1 Oct 2001 17:42:21 +0200 (MET DST) Received: (qmail 57880 invoked by uid 50); 1 Oct 2001 15:42:15 -0000 Delivered-To: fixup-caml-list@inria.fr@fixme Received: (qmail 57688 invoked by uid 0); 1 Oct 2001 15:42:13 -0000 Received: from adslppp180.tcsn.uswest.net (HELO dylan) (216.161.144.180) by tcsnpop1.tcsn.uswest.net with SMTP; 1 Oct 2001 15:42:13 -0000 Message-ID: <001a01c14a8f$e63e5cf0$210148bf@dylan> From: "David McClain" To: References: <004401c1483d$8d1bd160$210148bf@dylan> <20011001161757.A29127@cs.uu.nl> Subject: Re: [Caml-list] Error Reporting Date: Mon, 1 Oct 2001 08:44:01 -0700 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.00.2919.6600 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2919.6600 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Ah yes! I remember that Flanagan paper. Now maybe I can really try to understand it. I really appreciate all your feedback and the pointer to the surrounding context papers. I am compiling to OCaml closures. And for the most part the translation is direct. However, I found that the compilation of match clauses benefited greatly from CPS style. I actually did one version of the compiler that used CPS throughout and I found that I could almost do that except for the management of the OCaml exception frames. But I also found that the code tended to run about 30% slower (test programs took 1.3 times longer to run). The bulk of the code was not measured, but your papers indicate that CPS is a bit of a memory hog. Many thanks to all who responded! - DM ----- Original Message ----- From: "Frank Atanassow" To: "David McClain" Cc: Sent: Monday, October 01, 2001 7:17 AM Subject: Re: [Caml-list] Error Reporting > David McClain wrote (on 28-09-01 09:49 -0700): > > > There must be a past history, or otherwise you would not be able to implement > > > function application. > > > > I must confess that I don't understand this statement... > [..] > > But I suppose you are hinting that the compiler knows that all three of > > these closures are contained in the outermost one and so some record of > > activation history could be maintained by the compiler secretly plating > > static linkage information into each sub-closure. Not a bad idea! It > > certainly beats runtime computation of dynamic linkage and storing all that > > in a history queue. > > Something like that. John Prevost gave a nice example. > > In the CPS transform, in the case for application, you pass the continuation > of the application term to the operator, because the result of the application > has to be returned to the context of the call. That continuation is your past > history, since it tells you where you were before the function body was > evaluated. > > In the case for a tail call, you don't return to the calling context; that is, > you discard the current continuation. Instead, (I think) you just pass the > function to itself, since so it serves as its own continuation. > > So, for example, in > > let rec f x = if x=0 then 1 + g x else f (x-1) > > you translate g x as > > [g x] = fun k -> [g] (fun g' -> [x] (fun x' -> g' k x')) > > but f (x-1) as > > [f (x-1)] = fun _ -> [f] (fun f' -> [x-1] (fun x' -> f' f' x')) > > Err... approximately at least. :) You will have to double-check this, but the > point is that distinction between these two cases gets obliterated in the > image of the translation, because no function _ever_ returns (as you > said). > > Therefore, you have to add the error-handling information before you do the > transform, for example by turning continuations into an abstract datatype like > John did. Indeed, this is what you have to do anyway when you use CPS to > compile to machine code, since machines don't understand lambda-calculus, but > I assume you are compiling to Ocaml source. > > Anyway, you might want to read this paper: > > The Essence of Compiling with Continuations > Flanagan, Sabry, Duba, Felleisen > http://citeseer.nj.nec.com/174731.html > > which shows why CPS transformation is redundant, and it is better to do a > source-to-source transformation anyway. If you are really serious about this, > then you may also wish to check the Context (papers which reference this > paper) to see extensions of this idea. > > -- > Frank Atanassow, Information & Computing Sciences, Utrecht University > Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands > Tel +31 (030) 253-3261 Fax +31 (030) 251-379 > ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr