From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 4283DBB81 for ; Mon, 13 Feb 2006 04:23:53 +0100 (CET) Received: from smtp1.adl2.internode.on.net (smtp1.adl2.internode.on.net [203.16.214.181]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k1D3NpKL024388 for ; Mon, 13 Feb 2006 04:23:52 +0100 Received: from rosella (ppp21-250.lns2.syd7.internode.on.net [59.167.21.250]) by smtp1.adl2.internode.on.net (8.13.5/8.13.5) with ESMTP id k1D3Nkhc095974; Mon, 13 Feb 2006 13:53:46 +1030 (CST) (envelope-from skaller@users.sourceforge.net) Subject: Re: [Caml-list] HOFs, recursion, and being tail-rec... From: skaller To: Jonathan Roewen Cc: caml-list@yquem.inria.fr In-Reply-To: References: <20060213.085348.126575598.garrigue@math.nagoya-u.ac.jp> <1139796314.8591.79.camel@rosella.wigram> Content-Type: text/plain Date: Mon, 13 Feb 2006 14:23:45 +1100 Message-Id: <1139801025.8591.137.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.4.1 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 43EFFBC7.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 hofs:01 recursion:01 hofs:01 compiler:01 ocaml:01 stack:01 rec:01 associative:01 ocaml:01 curried:01 optimise:01 recursive:01 recursive:01 compiler:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 On Mon, 2006-02-13 at 15:47 +1300, Jonathan Roewen wrote: > > So it isn't a well formed sentence to say depth first > > search cannot be tail-rec, it is easy to construct a > > depth first search in any FPL that is. > > > > However, no matter what you do, you will indeed need > > memory linear in the tree depth (unless it is 1-ary tree as > > pointed out). > > Yes, but tail-rec would mean the function call trace does not use > memory linear in the tree depth, which would be a positive > optimisation. I do not think you can assume that without measuring it, either by an actual speed test, or examining the generated machine code. > BTW: the memory linear to the tree depth is used in the > list passed to search, 'visited'. Yes. > I'm just wondering if using List.exists and HOFs prevents the compiler > from generating tail-rec code (I presume that List.exists is already > tail-rec). I am not an expert on Ocaml optimisation -- but I would guess your code does indeed cause the machine stack to be pushed with the return address of 'search': let rec search visited position = if position = goal then true else List.exists (search (position::visited)) (positions position edges (position::visited)) Here 'search' is called to calculate an argument to List.exists, which is the last call, and the one in tail position. Well, actually this is not correct! The function in tail position *in theory* is actually (List.exists (search (position::visited))) since application is left associative. However Ocaml is smart and I believe it knows how to make curried calls of explicitly named functions without closure construction. In other words, if possible, it calls let f x y = .. in f a b (* f is NOT in tail position *) as if you had written let f (x,y) = .. in f (x,y) (* f IS in tail position *) This just shows that 'tail-rec' is a muddled idea. It is a purely syntactic property, when what you're interested in is performance. The correlation is implementation dependent. In any case, 'search' call in your code is NOT in tail position within the function search any way you look at it. I'd be surprised if Ocaml could optimise the code above to eliminate recursive calls. There IS a way to do this in some cases that I know about, which I hope to implement in Felix one day: a significant class of non-tail recursive functions can in fact be implemented without subroutine calling. I think your code is an example of this. > As it wouldn't be hard to make it tail-rec I'd imagine.. Generally KISS is a good idea for two reasons which are the same reason: (a) you can reason about your code more easily (b) the compiler optimiser can reason about your code more easily In the case of a balanced tree there is no reason to worry about recursion. The formula for the size of the tree is exponential in the tree depth, so a couple of recursions on a linear memory stack is irrelevent compared to the disk paging you'd get thrashing about trying to search a tree of any significant depth. As a counter example, I think it was Jacques who actually found Felix lexer was scanning a list of tokens non-tail recursively, which had a significant impact on Felix performance -- causing stack overflow lexing larger files. That's the degenerate case of an 1-ary tree :) -- John Skaller Felix, successor to C++: http://felix.sf.net