[Caml-list] HOFs, recursion, and being tail-rec...

[Caml-list] HOFs, recursion, and being tail-rec...

[Jonathan Roewen]

Hi,

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

val positions : 'a -> ('a * 'a) list -> 'a list -> 'a list
(* I think that's right type: returns positions we can traverse to,
omitting nodes we've previously visited *)

(* val dfs: 'a -> 'a -> ('a * 'a) list -> bool *)
let dfs start goal edges =
    let rec search visited position =
      if position = goal then true
      else List.exists (search (position::visited)) (positions
position edges (position::visited))
    in search [] start;;

Jonathan

Re: [Caml-list] HOFs, recursion, and being tail-rec...

[Jacques Garrigue]

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 degenerate case where all nodes are non-branching
(i.e. there is only one path), which in theory could be made
tail-recursive. But it would not be the case with your code, as
List.exists has no special case for the last element of the list (not
that it would make a lot of sense in general.)

> val positions : 'a -> ('a * 'a) list -> 'a list -> 'a list
> (* I think that's right type: returns positions we can traverse to,
> omitting nodes we've previously visited *)
> 
> (* val dfs: 'a -> 'a -> ('a * 'a) list -> bool *)
> let dfs start goal edges =
>     let rec search visited position =
>       if position = goal then true
>       else List.exists (search (position::visited)) (positions
> position edges (position::visited))
>     in search [] start;;

Re: [Caml-list] HOFs, recursion, and being tail-rec...

[skaller]

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

Re: [Caml-list] HOFs, recursion, and being tail-rec...

[Jonathan Roewen]

> 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. BTW: the memory linear to the tree depth is used in the
list passed to search, 'visited'.

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). As it wouldn't be hard to make it tail-rec I'd imagine..

Jonathan

Re: [Caml-list] HOFs, recursion, and being tail-rec...

[skaller]

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