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 RAA20001; Tue, 21 May 2002 17:12:26 +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 RAA19956 for ; Tue, 21 May 2002 17:12:25 +0200 (MET DST) Received: from sunny.pacific.net.au (sunny.pacific.net.au [203.25.148.40]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g4LFCNL12547 for ; Tue, 21 May 2002 17:12:24 +0200 (MET DST) Received: from wisma.pacific.net.au (wisma.pacific.net.au [210.23.129.72]) by sunny.pacific.net.au with ESMTP id g4LFCKXt013136 for ; Wed, 22 May 2002 01:12:20 +1000 (EST) Received: from ozemail.com.au (ppp70.dyn17.pacific.net.au [61.8.17.70]) by wisma.pacific.net.au with ESMTP id BAA24924 for ; Wed, 22 May 2002 01:12:18 +1000 (EST) Message-ID: <3CEA63D1.5020607@ozemail.com.au> Date: Wed, 22 May 2002 01:12:17 +1000 From: John Max Skaller User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.2.1) Gecko/20010901 X-Accept-Language: en-us MIME-Version: 1.0 To: caml-list@inria.fr Subject: Re: [Caml-list] Tail recursion detection References: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Alain Frisch wrote: >>My question is: how smart is the Ocaml tail call detector? >> > >As far as I can tell, the detection is quite easy > >Does this answer your question ? > Well, I was hoping for a definitive answer: Perhaps I'm confused, but .. The problem isn't replacing calls with jumps, but identifying which closure to reuse. In general, that is impossible without dataflow analysis. For example (ignore impossible typing here please) let rec f g x = g g x in f f x Obviously, the call 'g g x' is at the tail, but to do a tail call, one must avoid construction a new closure of f with its argument, and just store the argument in the slot used by the previous one. To do that, you have to know that the function being applied is actually f. Clearly this is impossible in this example until you see the 'f f x' after the 'in' keyword. In Felix, this problem is nasty. Consider recursive procedure calls. Naturally, to avoid an infinite recursion, such a call is going to be one branch of a conditional. My problem is the recommended technique for doing this is like: proc f(x:int) { if x == 0 then { print "end"; } else { f(x-1); } endif; } which is equivalent to proc f(x:int) { proc z() { print "end"; } proc nz() { f(x-1); } val g = if x ==0 then z else nz endif; g (); } and now you see it it is not at all obvious without dataflow analysis how to make this all work with only one storage location for 'x'. The f called in 'nz' cannot be tail called without analysing all of f, since just examining nz will not tell you if, after it returns, the old x is still required. On the other hand, g() can't be tail called either, without looking inside z and nz, which itself requires determining the how the value of g arose. -- John Max Skaller, mailto:skaller@ozemail.com.au snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia. voice:61-2-9660-0850 ------------------- 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