Reporting on sucess/failure of tail recursion

Reporting on sucess/failure of tail recursion

[Erik de Castro Lopo]

Hi all,

Say I have a file containing a number if Ocaml functions. 

We all know the advantages of tail recursive functions over non-tail
recursive ones and some of us know if a simple function is tail
recursice just by looking at it. However, for more complex functions
it would be really nice if there was a compiler mode that could print 
which recursive functions in a file were tail recursive and which were 
not.

Is there a way to do this? Does anyone else think this would be a useful
feature?

Cheers,
Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo
+-----------------------------------------------------------+
"I saw `cout' being shifted "Hello world" times to the left 
and stopped right there." -- Steve Gonedes

Re: [Caml-list] Reporting on sucess/failure of tail recursion

[Jonathan Roewen]

> Is there a way to do this? Does anyone else think this would be a useful
> feature?

I would love this feature! I was thinking about mentioning some
two-three days ago myself ;-)

Even cooler would be if a tool could suggest an alternative
implementation that is tail-rec if can be made so.

Jonathan

Re: [Caml-list] Reporting on sucess/failure of tail recursion

[Erik de Castro Lopo]

Jonathan Roewen wrote:

> I would love this feature! I was thinking about mentioning some
> two-three days ago myself ;-)

I've been wanting this for at least the last 6 months.

> Even cooler would be if a tool could suggest an alternative
> implementation that is tail-rec if can be made so.

That might be asking a bit much :-).

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo
+-----------------------------------------------------------+
"Or here's an even simpler indicator of how much C++ sucks: Print out
the C++ Public Review Document. Have someone hold it about three feet
above your head and then drop it. Thus you will be enlightened."
 -- Thant Tessman

Re: [Caml-list] Reporting on sucess/failure of tail recursion

[basile]

> Say I have a file containing a number of Ocaml functions.

> We all know the advantages of tail recursive functions over non-tail
> recursive ones and some of us know if a simple function is tail
> recursice just by looking at it. However, for more complex functions
> it would be really nice if there was a compiler mode that could print
> which recursive functions in a file were tail recursive and which were
> not.

Functions are not tail-recursive, but function *calls* are (or not)
tail-recursive. I mean that a given function may have both tail
[-recursive]
and non-tail [-recursive] calls.

Maybe what you are dreaming of is an extension of the -dtypes flag (to
ocamlc) which not only computes the type of each expression,
but also flags each function *call* as a tail (or not a tail) call. I do
agree it would be quite useful (but my knowledge of ocaml internals make
me think that it is in principle easy, but in practice would require a lot
of changes within the compiler, since tail-rec detection is done in passes
near the backend, after the typing.).

We could even dream of a let tailrec language construct which behaves like
let rec but checks that each recursive call to the function is in fact a
tail-recursion.

All this is in principle easy to do, but I understand that it might
require a significant amount of work which is not the priority of INRIA
Cristal team (which is a team of researchers, not of engineers).

Regards.


-- 
Basile Starynkevitch http://starynkevitch.net/Basile

PS: I've currently got ADSL problems so have difficulties to read my emails.

Re: [Caml-list] Reporting on sucess/failure of tail recursion

[Erik de Castro Lopo]

basile@starynkevitch.net wrote:

> Functions are not tail-recursive, but function *calls* are (or not)
> tail-recursive. I mean that a given function may have both tail
> [-recursive]
> and non-tail [-recursive] calls.

Ok, so many recursive functions are actually written like:

    let fact n =
        let rec sub_fact curr acc =
            if curr > n then acc
            else sub_fact (curr + 1) (curr * acc)
        in
        sub_fact 1 1

with a no-recursive outer function and a tail recursive inner function.
It would still be nice to know if the inner function is tail recursive.
	
> Maybe what you are dreaming of is an extension of the -dtypes flag (to
> ocamlc)

Ooo, I didn't know about -dtypes. That might be useful. Thanks.

Yes, something like -dtypes.

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo
+-----------------------------------------------------------+
"That being done, all you have to do next is call free() slightly 
less often than malloc(). You may want to examine the Solaris 
system libraries for a particularly ambitious implementation of 
this technique."
-- Eric O'Dell (comp.lang.dylan)

Re: [Caml-list] Reporting on sucess/failure of tail recursion

[Jean-Christophe Filliatre]

Erik de Castro Lopo writes:
 > with a no-recursive outer function and a tail recursive inner function.
 > It would still be nice to know if the inner function is tail recursive.

As  already explained by  Basile, the  right notion  is that  of "tail
call"  not of "tail  recursive function"  (you can  define it  as "all
recursive  calls  are tail  calls",  but  it  is less  precise).   For
instance, the following function
 
   let rec fold f s accu =
      match s with
        Empty -> accu
      | Node(l, v, r, _) -> fold f r (f v (fold f l accu))

has two recursive calls, one which is  not a tail call (fold f l accu)
and one which is (fold f r ...)

Being warned of non-tail calls may be useful in some situations, but I
guess the  issue is often the call  to a library function  that is not
tail recursive. That's  why you need the documentation  to be explicit
about that...

-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)

Re: [Caml-list] Reporting on sucess/failure of tail recursion

[skaller]

On Fri, 2005-12-02 at 16:17 +0100, Jean-Christophe Filliatre wrote:
> Erik de Castro Lopo writes:
>  > with a no-recursive outer function and a tail recursive inner function.
>  > It would still be nice to know if the inner function is tail recursive.

> As  already explained by  Basile, the  right notion  is that  of "tail
> call"  not of "tail  recursive function" 

> Being warned of non-tail calls may be useful in some situations, but I
> guess the  issue is often the call  to a library function  that is not
> tail recursive. 
 ***************

Hehe .. committing the same error yourself.

> That's  why you need the documentation  to be explicit
> about that...

No, it is meaningless: the idea only applies to a definition.
The only visible part of a Library function is its interface.
Furthermore, it is very unlikely a call to a library function
would be recursive, whether it is in tail position or not.

What needs to be documented for a library function is its
complexity (time/space etc). In this sense the documentation
of the C++ Standard Library should be taken as an examplar.

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

Re: [Caml-list] Reporting on sucess/failure of tail recursion

[David MENTRE]

Hello,

2005/12/2, basile@starynkevitch.net <basile@starynkevitch.net>:
> agree it would be quite useful

So do I. I've just submited it as feature request:
  http://caml.inria.fr/mantis/view.php?id=3905

> (but my knowledge of ocaml internals make
> me think that it is in principle easy, but in practice would require a lot
> of changes within the compiler, since tail-rec detection is done in passes
> near the backend, after the typing.).

I arrived to the same conclusion. I wanted to implement that feature
but when I discovered the same facts as you, I ditched the project
(ok, I could have try a little harder but it wasn't the week-end
project I expected :-).

Yours,
d.

Re: [Caml-list] Reporting on sucess/failure of tail recursion

[David Thomas]

Particularly with respect to list operations,
"non-tail-recursive" usually implies stack space used
is O(n) to the length of the list, whereas "tail
recursive" implies O(1).  I, for one, would love to
see these figures explicitly, instead.

--- skaller <skaller@users.sourceforge.net> wrote:

> What needs to be documented for a library function
is its 
> complexity (time/space etc). In this sense the
documentation
> of the C++ Standard Library should be taken as an
examplar.



		
__________________________________ 
Start your day with Yahoo! - Make it your home page! 
http://www.yahoo.com/r/hs

Re: [Caml-list] Reporting on sucess/failure of tail recursion

[Andres Varon]

While exploring the (undocumented) options of ocamlopt I discovered  
once that -dlinear explicitly says if a function is a tailcall or  
not. It has worked consistently for me whenever I needed to check  
this afterwards.

Andres

On Dec 2, 2005, at 7:28 PM, David Thomas wrote:

> Particularly with respect to list operations,
> "non-tail-recursive" usually implies stack space used
> is O(n) to the length of the list, whereas "tail
> recursive" implies O(1).  I, for one, would love to
> see these figures explicitly, instead.
>
> --- skaller <skaller@users.sourceforge.net> wrote:
>
>> What needs to be documented for a library function
> is its
>> complexity (time/space etc). In this sense the
> documentation
>> of the C++ Standard Library should be taken as an
> examplar.
>
>
>
> 		
> __________________________________
> Start your day with Yahoo! - Make it your home page!
> http://www.yahoo.com/r/hs
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs