From: Rocky Bernstein Date: 2008-12-05T23:28:50+09:00 Subject: [ruby-core:20371] Re: Tail recursion? On Fri, Dec 5, 2008 at 7:45 AM, Yusuke ENDOH wrote: > Hi, > > 2008/12/5 Rocky Bernstein : >> 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) . > > Sorry I don't understand very well. Not a problem. I don't explain very well. > Do you mean we should give up to > hook a return event when tail call occured? I was saying that in the site of the caller, say at method "a", which knows that a tail recursion is about to happen, a note that a tail-recursive is happening is set a's parent frame (the one which gets returned to which could be itself). In the "call" event, a flag of this condition should be indicated so that programs registering call/return events can track can keep their own record. As for the the return, I don't think anything more needs to be done. "return" already raises an event. If it gets transformed into a jump inside the same method, the jump might register a "return" event followed by a clear of the "tail recursion removal flag" after return event is called. If this information is set, caller() the would to look for this status in the frames it reports. > > If so, I guess it has two problems, (1) serious compatibility problem, > and (2) trace_func that is used dynamically like this: > > def at_return > set_trace_func(proc do|*r| > if r[0] == "return" && r[3] == :foo > set_trace_func(nil) > yield > end > end) > end > > def foo > puts "foo start" > at_return { puts "return from foo" } > puts "foo end" > end > > foo #=> foo start, foo end, return from foo > > I'm sorry but I don't understand you now. If this is still relevant in light of what I wrote above, I'd appreciate further explanation. >> 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. > > I think it was just a change of what enlarges. Sure. Probably we agree here. It is not that tail recursion shouldn't be done, but to show what has occurred in a stack trace, a little bit of care in the implementation may help. Similarly a program which is registering returns (and probably calls) events also may want to make use of this extra bit of status as well. > The record you said > will lengthen instead of call stack, won't it? No. The record is a single boolean. It doesn't indicate the number of eliminated returns although I suppose it could by turning it into an number which by default is 0 and having each tail-recursive call increment that. Programs that register trace events may want to save their own information which they can do on this on the call event. > I wonder if tail call > elimination still make sense. The sense I get from the community is that it does. > > In addition, making stack trace inexact is too drastic change for Ruby > to be unacceptable. That's just my personal opinion, though. > > I still think it's better to declare tail-call explicitly by special > syntax or method. > > -- > Yusuke ENDOH > >