On Mon, 2006-02-13 at 08:53 +0900, Jacques Garrigue wrote:
> From: Jonathan Roewen <jonathan.roewen@gmail.com>
> > 
> > I have a simple implementation of depth-first-search, and was
> > wondering if my approach would qualify as tail-rec (whether from the
> > code it is/isn't, and whether ocaml can optimise it so it is).
> 
> By definition a depth-first-search cannot be tail-recursive: you need
> a stack to implement the backtracking.

There is a need for a stack, but it doesn't have to be
a machine (control) stack. A basic principle of duality
seems to be that control and data can always be transformed
into each other (proof: Turing only has conditional goto). 
In this case CPS provides the transform.

There is category error in Jacques claim: depth-first search
is an algorithm, it is a matter of *semantics*.

Tail-rec is merely a *syntactic* property, which has
semantic implications only for a particular implementation.

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).

BTW: considering control/data duality you will find that most compilers
miss very interesting optimisations. Ackermann's function
can be implemented using only 2 words (for the arguments)
per stack frame. No compilers I know of do this optimisation --
and I have not seen any reference to it in the literature.


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net