Warning on not-tail recursive functions

Warning on not-tail recursive functions

[tmp123]

Hello,

Please, knows someone if "ocamlopt" can print a warning message when a 
recursive function is not tail recursive, and code with the "jmp" 
optimization has not been generated?.

In this case, probably I can correct the function implementation to 
write a better one. Without it, I must always look at the generated 
assembler to check it.

Thanks a lot.

Re: [Caml-list] Warning on not-tail recursive functions

[Brian Hurt]

On Sat, 4 Aug 2007, tmp123@menta.net wrote:

> Hello,
>
> Please, knows someone if "ocamlopt" can print a warning message when a 
> recursive function is not tail recursive, and code with the "jmp" 
> optimization has not been generated?.

The problem is that I often write recursive functions which are not tail 
recursive, and that's OK.  As an example, take a look at the join (or 
filter) functions I wrote in priority queue implementation in my previous 
email (subject line: "Sorted list").  They're not tail recursive, but 
since they only go O(log N) deep, that's not a problem.

The rules for what is or is not tail recursive are pretty simple.  Boiled 
down, they are:
1) The tail call must not be within a try expression
2) You can not do anything except return, uninspected and unmodified, the 
returned value from the call.

Given that the rules are simple and local, I can generally just tell, by 
looking at the call, wether it's a tail call or not.

Brian

Re: [Caml-list] Warning on not-tail recursive functions

[Oliver Bandel]

Zitat von Brian Hurt <bhurt@spnz.org>:

>
>
> On Sat, 4 Aug 2007, tmp123@menta.net wrote:
>
> > Hello,
> >
> > Please, knows someone if "ocamlopt" can print a warning message when a
> > recursive function is not tail recursive, and code with the "jmp"
> > optimization has not been generated?.
>
> The problem is that I often write recursive functions which are not tail
> recursive, and that's OK.


Well, during I've learned on tail-recursion I have habituized to always
write functions tailrecursive, so that when I want to try a non-tailrec
function, I really have to think a log about it...

...really!

It's only a way of what one is used to do very often.
If you get accustomed to tailrec function writing,
then it's "natural".

Before I knew how to write tailrec code, it was the other way around
and I had to tjink a lot about how to get it tailrec.



[...]
>
> The rules for what is or is not tail recursive are pretty simple.  Boiled
> down, they are:
> 1) The tail call must not be within a try expression
> 2) You can not do anything except return, uninspected and unmodified, the
> returned value from the call.


What ist with a

  ...
   ignore (maybe_tailcall())
  ...



???

Does ignore REALLY ignore the values (does not generate them), so that
this call is like a true tail-call, or will the maybe_tailcall
generate and give back results to the ignore-call and then
ignore throws away the stuff (then it would be NO tailcall).


Ciao,
   Oliver

Re: [Caml-list] Warning on not-tail recursive functions

[Julien Moutinho]

On Sat, Aug 04, 2007 at 02:34:21PM +0200, Oliver Bandel wrote:
> Zitat von Brian Hurt <bhurt@spnz.org>:
> > On Sat, 4 Aug 2007, tmp123@menta.net wrote:
> > > Please, knows someone if "ocamlopt" can print a warning message when a
> > > recursive function is not tail recursive, and code with the "jmp"
> > > optimization has not been generated?.
> >
> > The problem is that I often write recursive functions which are not tail
> > recursive, and that's OK.
Ibid.

> > The rules for what is or is not tail recursive are pretty simple.  Boiled
> > down, they are:
> > 1) The tail call must not be within a try expression
> > 2) You can not do anything except return, uninspected and unmodified, the
> > returned value from the call.
I agree Mr.Hurt.

> Does ignore REALLY ignore the values (does not generate them), so that
> this call is like a true tail-call,
No, [ignore] is not a macro, so it always triggers the calculation of its argument.
Think about ignore as if it would be [let ignore _ = ()]
Note however that it is not truly the case, and that [ignore == ignore] is false,
since [ignore] is actually defined as an external value
[external ignore : 'a -> unit = "%ignore"]

> or will the maybe_tailcall
> generate and give back results to the ignore-call and then
> ignore throws away the stuff (then it would be NO tailcall).
Yes, AFAICS with the -S option, neither [ignore] nor [let _ = your_rec_fun in ()]
are segregated from the other functions to produce jumps.
And I perfectly understand that the Inrians work on more important
optimizations than those.

Re: [Caml-list] Warning on not-tail recursive functions

[Brian Hurt]

On Sat, 4 Aug 2007, Oliver Bandel wrote:

> What ist with a
>
>  ...
>   ignore (maybe_tailcall())
>  ...
>

That is not a tail call.  You're using the value it returns.

Brian

> Does ignore REALLY ignore the values (does not generate them), so that
> this call is like a true tail-call, or will the maybe_tailcall
> generate and give back results to the ignore-call and then
> ignore throws away the stuff (then it would be NO tailcall).

Throwing away the result is using the result.

Brian

Re: [Caml-list] Warning on not-tail recursive functions

[Oliver Bandel]

Zitat von Brian Hurt <bhurt@spnz.org>:

>
>
> On Sat, 4 Aug 2007, Oliver Bandel wrote:
>
> > What ist with a
> >
> >  ...
> >   ignore (maybe_tailcall())
> >  ...
> >
>
> That is not a tail call.  You're using the value it returns.

Yes, but ignore ignores the value,
and my question was regarded to THIS CERTAIn aspect:
if it INTERNALLY would mean that the arguments will not be created,
then nothing must be given back and if no further commands are
following (read the "..." under the ignore-call as the next
pattern of a pattern match, not as a command that follows the ignore(..)).




>
> Brian
>
> > Does ignore REALLY ignore the values (does not generate them), so that
> > this call is like a true tail-call, or will the maybe_tailcall
> > generate and give back results to the ignore-call and then
> > ignore throws away the stuff (then it would be NO tailcall).
>
> Throwing away the result is using the result.


Ignoring a result in a way that it will never be created, would mean
to have no result => this would be tailcall-equivalent.

And that was my question! Would ignore throw away the
created results, or would it suppress creating results?!

Now some answers wer: results will be treated and thrown away afterwards.

Then a next question could arise: could it be implemented in a way, that
creating the results would be blocked from the beginning on (so that nothing
must be thrown away, because nothing would be created)?

This is not really an urgent question, only something,
that during the last two days sometimes came to my mind.


Ciao,
   Oliver