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 <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net