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 SAA24744; Wed, 9 Apr 2003 18:54:16 +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 SAA24843 for ; Wed, 9 Apr 2003 18:54:15 +0200 (MET DST) Received: from grace.speakeasy.org (grace.speakeasy.org [216.254.0.2]) by nez-perce.inria.fr (8.11.1/8.11.1) with SMTP id h39GsD908494 for ; Wed, 9 Apr 2003 18:54:13 +0200 (MET DST) Received: (qmail 5448 invoked by uid 36130); 9 Apr 2003 16:54:11 -0000 Received: from localhost (sendmail-bs@127.0.0.1) by localhost with SMTP; 9 Apr 2003 16:54:11 -0000 Date: Wed, 9 Apr 2003 09:54:11 -0700 (PDT) From: brogoff@speakeasy.net To: Neel Krishnaswami cc: "caml-list@inria.fr" Subject: Re: CPS folds (was Re: [Caml-list] stack overflow) In-Reply-To: <16020.10973.162317.709095@h00045a4799d6.ne.client2.attbi.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Spam: no; 0.00; brogoff:01 caml-list:01 neel:01 krishnaswami:01 shouxun:01 passing:01 closures:01 recompile:01 speakeasy:01 closure:01 bytecode:01 writes:01 overflow:02 continuation:02 mottl:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Wed, 9 Apr 2003, Neel Krishnaswami wrote: > Yang Shouxun writes: > > On Wednesday 09 April 2003 16:14, Markus Mottl wrote: > > > > > > The trick is to use continuation passing style (CPS): you pass a > > > function closure (continuation) containing everything that's > > > needed in subsequent computations. Instead of returning a result, > > > the sub-function calls the continuation with the result, which > > > makes the functions tail-recursive. > > > > I've learned this style in Scheme. Yet I feel paralyzed when trying > > to write in it to build trees. The problems are that unless the next > > call returns, the tree is not complete yet and it may have several > > calls on itself. Before going any further, see if you can recompile the program in bytecode, and detect the error location using stack tracing. CPS is not that helpful in cases where you can't find some clever defunctionalization of the CPS function into accumulator passing style or something else. All those closures that get allocated so that you don't hit the stack have a cost, too. Measure before using. That said, all of this CPS stuff is fascinating, and well worth learning for any computing professional with an interest in functional programming. If you know Scheme, buy yourself a copy of "Essentials of Programming Languages". There are some really great chapters on CPS in that book. -- Brian ------------------- 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