Re: [Caml-list] Tail recursion detection

[Benedikt Grundmann <bgrundmann@gmx.net>]

At 09:46 21.05.02 +0200, Alain Frisch wrote:
>On Mon, 20 May 2002, John Max Skaller wrote:

Maybe you want to have a look at scheme's r5rs (revised ... revised report 
... scheme).   After reading the section on tail calls it's obvious that 
they can be detected by simple pattern matching on the syntax.


Good luck,

Bene

> > I'm in the process of writing a tail recursion detector for
> > Felix, and many of the routines are tail recursive (heh!).
> > However, in a few places, there are multi-way branches
> > each of which terminate in identical tail calls:
> >
> > let rec f x y = match .. with
> >    | .. ->
> >       if .. then
> >       if .. then
> >       if .. then
> >       f x' y'
> >       else f x' y'
> >       else f x' y'
> >       else f x' y'
> > ..
>
>
>These would be tail calls even with different x' and y' ...
>
> > My question is: how smart is the Ocaml tail call detector?
>
>As far as I can tell, the detection is quite easy: just replace
>during (some kind of intermediate) code generation any call followed
>by a return with a tail call (after replacing any jump to a return
>with the return). This is enough to detect tail call in your example.
>Have a look at the OCaml bytecode generator, it is easy enough to get the
>idea.
>
>
>Does this answer your question ?
>
>-- Alain
>
>-------------------
>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


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