Re: [Caml-list] Tail recursion detection

[John Max Skaller <skaller@ozemail.com.au>]

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