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 DAA10731; Sat, 1 Feb 2003 03:30:58 +0100 (MET) 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 DAA10549 for ; Sat, 1 Feb 2003 03:30:57 +0100 (MET) 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 h112UtP05354 for ; Sat, 1 Feb 2003 03:30:56 +0100 (MET) Received: (qmail 28558 invoked by uid 36130); 1 Feb 2003 02:30:54 -0000 Received: from localhost (sendmail-bs@127.0.0.1) by localhost with SMTP; 1 Feb 2003 02:30:54 -0000 Date: Fri, 31 Jan 2003 18:30:54 -0800 (PST) From: brogoff@speakeasy.net To: "caml-list@inria.fr" Subject: Re: [Caml-list] @, List.append, and tail recursion In-Reply-To: <20030131191806.GA28910@juvenileinstructor.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, 31 Jan 2003, Russ Ross wrote: > Tail recursion is a powerful and efficient construct, but it still > requires care on the part of the programmer to make sure that the > calls are proper tail calls. I think there are many recursive > functions which cannot be transformed easily into tail calls, but > there is a large class of functions that can be mechanically > transformed using techniques discussed here and elsewhere. I would > be interested personally if anyone could point to papers or other > resources about this topic. Right now I think there is some > low-hanging fruit to be plucked--recognizing and transforming a few > simple patterns (code that looks like List.map) would make a big > difference in a lot of code. Handling more complex cases is > undoubtedly harder, but I think the potential benefits are > considerable. For the particular case being discussed, there is a bit of theory, and if you read Minamide's paper you'll see that he comments that six functions from the SML Basis can take advantage of the hole abstraction to be written in tail recursive form: append, take, map, mapPartial, filter, and tabulate. For OCaml's list, we I think it's pretty clear that fold_right can't be written this way, since it doesn't necessarily construct lists. I think it's also clear that we can write map2, flatten, split, and combine with setcdr (I like replace_tl as a name for this :) in tail recursive form, since map2, split, and combine are all tweaks of map, likewise flatten is a tweak of append. I just hacked up tail recursive versions of all of these functions (including the SML ones Minamide mentioned) using setcdr, so it is doable. PS: As you may know, you can certainly make functions like fold_right tail recursive using a trick called the CPS transformation, like so, from let rec fold_right f l accu = match l with [] -> accu | a::l -> f a (fold_right f l accu) to let rec fold_rightk f l accu k = match l with [] -> k accu | a::l -> fold_rightk f l accu (fun x -> k (f a x)) let fold_right f l accu = fold_rightk f l accu (fun x -> x) but as you can see that doesn't help so much, because we create lots of closures. So just making things tail recursive isn't really enough, since we can make anything tail recursive. This hole abstraction stuff Minamide discusses is a bit more, and touches on such areas as linear types. I think "destination passing style" will give you a few good hits on Google, if you're looking for more refs, but the Minamide paper cited earlier is a good start. -- 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