[ruby-core:20312] Re: Tail recursion?

Comments in line.

On Thu, Dec 4, 2008 at 8:39 AM, Yusuke ENDOH <[e-mail]> wrote:
..
> YARV itself implements tail call optimization, but the feature is currently
> disabled by default.  I guess this is because, if it is enabled,
> - stack trace will change (and become harder to read), and
> - set_trace_func cannot hook an event of method return.

In the long run, I don't see the lack of set_trace_func hook for
intermediate returns or stack_trace reading being an insurmountable
reason for not doing tail-recursion elimination.

First let's discuss the set_trace_func hook.  Generally those programs
which register a callback for a return event also register an callback
for a call event, and it's the caller that knows when tail recursion
is possible.

So as long as the call event has a flag that indicates it won't return
here and as long as there is one return event registered, a program
capturing both calls and returns can know what's going on and could
report exactly what locations are skipped and how many levels will be
popped (by remembering this when the call takes place) .

Similar reasoning applies to a program showing a stack trace. Again
what's key here is just that the call stack have a flag indicating
tail recursion is taking place which is known at the time of the call.
However the recording this fact probably needs to be done in the
*caller's* frame. If you don't capture information on the calls, you
will lose exactly the intermediary locations where you would have
returned to. However I don't think this is hard for a programmer to
figure out, and perhaps it might not even be of much interest much of
the time.

Before leaving this topic, let me mention that in Ruby 1.8 where there
is no tail recursion, ruby-debug records extra information on calls.
It does this partially to make up for the lack of the ability to get
parameter names and information from the internal call stack
structure; this has been noted recently in this list and discussed at
great length. Yes, the fact that ruby-debug has to do this does slows
down execution, but Kent Sibilev wisely engineered a way to turn the
extra tracking on or off with great flexibility that we don't get
complaints about the slowness.

>
> But I also want tail call optimization in some cases.  I think a new method
> call syntax or feature may be needed to declare that the call is tail call
> and should be optimized.  For example, how about Method#tail_call:
>
>  def foo
>    ...
>    method(:foo).tail_call
>  end

Given the above, I don't think this is necessary. Just as ruby-debug
does with its "Debugger.start; ...; Debugger.stop" or Debugger.start
{} one could have a way to register with the VM, turnning on or off
recording extra information about tail recursion

>
> --
> Yusuke ENDOH <[e-mail]>
>
>