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 TAA25782; Wed, 9 Apr 2003 19:24:04 +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 TAA25776 for ; Wed, 9 Apr 2003 19:24:03 +0200 (MET DST) Received: from pacific-carrier-annex.mit.edu (PACIFIC-CARRIER-ANNEX.MIT.EDU [18.7.21.83]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h39HO2909404 for ; Wed, 9 Apr 2003 19:24:02 +0200 (MET DST) Received: from grand-central-station.mit.edu (GRAND-CENTRAL-STATION.MIT.EDU [18.7.21.82]) by pacific-carrier-annex.mit.edu (8.12.4/8.9.2) with ESMTP id h39HO1Q1005737; Wed, 9 Apr 2003 13:24:01 -0400 (EDT) Received: from melbourne-city-street.mit.edu (MELBOURNE-CITY-STREET.MIT.EDU [18.7.21.86]) by grand-central-station.mit.edu (8.12.4/8.9.2) with ESMTP id h39HO09l000297; Wed, 9 Apr 2003 13:24:01 -0400 (EDT) Received: from mit.edu (MFLIN.MIT.EDU [18.194.0.116]) ) by melbourne-city-street.mit.edu (8.12.4/8.12.4) with ESMTP id h39HNxU8000016; Wed, 9 Apr 2003 13:24:00 -0400 (EDT) Date: Wed, 9 Apr 2003 13:23:59 -0400 Subject: Re: CPS folds (was Re: [Caml-list] stack overflow) Content-Type: text/plain; charset=US-ASCII; format=flowed Mime-Version: 1.0 (Apple Message framework v551) Cc: "caml-list@inria.fr" To: Neel Krishnaswami From: Mike Lin In-Reply-To: Message-Id: <0CFED0CA-6AB0-11D7-AC6E-000393AE4242@mit.edu> Content-Transfer-Encoding: 7bit X-Mailer: Apple Mail (2.551) X-Spam: no; 0.00; mikelin:01 caml-list:01 yaxpo:01 -mike:01 brogoff:01 neel:01 krishnaswami:01 shouxun:01 passing:01 closures:01 bug:01 faq:01 beginner's:01 beginners:01 bin:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk If y'all want to see a real example, Yaxpo is a whole XML parser structured in CPS. One of the things it has to do is, of course, to build up a DOM tree. http://mikelin.mit.edu/yaxpo -Mike On Wednesday, April 9, 2003, at 12:54 PM, brogoff@speakeasy.net wrote: > 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 ------------------- 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