Feature #12543
explicit tail call syntax: foo() then return
Description
How about introducing a new syntax for tail call?
def foo() foo() end foo() #=> stack level too deep
def bar() bar() then return end bar() #=> infinite loop
- no new keyword (cf.
goto foo()
) - no conflict with any existing syntax
- an experimental patch is available (attached)
- no shift/reduce nor reduce/reduce conflict in parse.y
--
Yusuke Endoh mame@ruby-lang.org
Files
Related issues
Updated by mame (Yusuke Endoh) over 4 years ago
- Subject changed from explicit tal call syntax: foo() then return to explicit tail call syntax: foo() then return
Updated by mame (Yusuke Endoh) over 4 years ago
- Related to Feature #6602: Tail call optimization: enable by default? added
Updated by ko1 (Koichi Sasada) over 4 years ago
mame-san:
Do you have use-cases?
Updated by matz (Yukihiro Matsumoto) over 4 years ago
- Status changed from Open to Closed
I am not positive. This may not work under tracing. I am for adding tail-call optimization, but Koichi do not love the idea either.
Matz.
Updated by ko1 (Koichi Sasada) over 1 year ago
- Status changed from Closed to Assigned
Another idea: tailcall return foo()
- Background:
return
is void expression and anymethod(return)
is not prohibited on current compiler. So nobody use it == no-incompatibility. Any keywords are acceptable (example:goto return foo()
).
I like Endoh-san's original idea, tailcall explicitly. It is similar to goto, and programmer should understand there is no backtrace.
I heard that someone want to use taicall with pattern matching which will be introduced into Ruby 2.7.
Updated by duerst (Martin Dürst) over 1 year ago
I don't think tail call optimization should be a feature that is switched on or off by the programmer at each location. I think it should be an option used on execution, and it should be ON by default.
We want programs to be fast, and tail call optimization makes them faster. In #6602, there was the opinion that tail calls are rare in Ruby, but that may also have to do with the fact that they are not optimized. So to some extent, it's a chicken and egg problem.
What usually happens is that users write programs and run them. If they run faster, that's good. That's why I think tail call optimization should be on by default. What happens next is that occasionally, there's a bug. That bug may produce a stack trace. The stack trace should include a hint as to where tail call optimization was in effect. The programmer will read the stack trace, and if they suspect that the bug is somewhere near the tail call, they can run the program with tail calls switched off by using an option.
For me, having tail calls off by default, or having syntax to switch them on per calling location seems to put the chart before the horse. I hope this can be avoided.
Updated by mame (Yusuke Endoh) over 1 year ago
I'm strongly against "ON by default". It makes the backtrace difficult to understand. Consider the following program:
1: def foo 2: raise 3: end 4: 5: def bar 6: foo 7: end 8: 9: bar
If tail-call optimization is used by default, it will print:
Traceback (most recent call last): 1: from test.rb:9:in `<main>' test.rb:2:in `foo': unhandled exception
The frame of bar
is removed due to tail-call optimization, so the debugger must guess how it reached at Line 2 from Line 9.
This issue would be incredibly difficult when multiple frames are omitted. It would be not so rare on practical programs. I believe that "easy to debug" is one of the most important properties in Ruby.
Updated by duerst (Martin Dürst) over 1 year ago
mame (Yusuke Endoh) wrote:
I'm strongly against "ON by default". It makes the backtrace difficult to understand. Consider the following program:
If tail-call optimization is used by default, it will print:
Traceback (most recent call last): 1: from test.rb:9:in `<main>' test.rb:2:in `foo': unhandled exception
This should be changed to something like:
Traceback (most recent call last): 1: from test.rb:9:in `<main>' [some frames omitted due to tail call optimization, use --tail-call-optimization-off for more details] test.rb:2:in `foo': unhandled exception
Of course, the exact name of the exception and the wording of the message can still be improved. Implementation should be easy, just set a flag on the stack frame above the one that is eliminated by the tail call optimization.
The frame of
bar
is removed due to tail-call optimization, so the debugger must guess how it reached at Line 2 from Line 9.
Guessing is of course not prohibited, but better use the option to get the full trace.
This issue would be incredibly difficult when multiple frames are omitted. It would be not so rare on practical programs. I believe that "easy to debug" is one of the most important properties in Ruby.
I agree that "easy to debug" is important for Ruby. But I don't think my proposal makes debugging very difficult.
Updated by mame (Yusuke Endoh) over 1 year ago
I don't like --tail-call-optimization-off
. I will not specify the option, see an omitted backtrace, and then I must re-run my code with the option. It is not an easy-to-debug language for me.
And I have another concern. If tail call optimization is on by default, some people will strongly depend on it. For example, someone may write:
def main_loop socket = server_socket.accept ... main_loop end
This code will break when --tail-call-optimization-off
is specified.
So, I think it should be off by default, and it would be good to allow to write:
def main_loop socket = server_socket.accept ... return and main_loop # explicit tail call end
Updated by Dan0042 (Daniel DeLorme) over 1 year ago
Questions:
- Is it possible to use "partial" tail-call optimization, where the backtrace is kept but all other frame state is discarded?
- Is it possible to detect tail-recursion and turn on optimization just for that?
Updated by shyouhei (Shyouhei Urabe) over 1 year ago
Dan0042 (Daniel DeLorme) wrote:
Questions:
- Is it possible to use "partial" tail-call optimization, where the backtrace is kept but all other frame state is discarded?
That's heavier than a normal method call; we don't "keep" a Thread::Backtrace::Location now. Instances of that class are constructed on-the-fly when necessary. However if we do a "partial" optimization like you say we have to explicitly keep them, which adds extra overhead every time when you call something -- not only when backtraces are needed.
- Is it possible to detect tail-recursion and turn on optimization just for that?
That's what's requested in this request. "Turn optimization just for this return
" is what's called then return
here.
Updated by Eregon (Benoit Daloze) over 1 year ago
duerst (Martin Dürst) wrote:
We want programs to be fast, and tail call optimization makes them faster.
That's not true in general.
It might make recursive methods faster, but it makes normal methods calls that happen at the end of a method body slower with a JIT, because the TCO call is a loop calling two different methods, instead of straight line code from inlining the method call which happens to be in tail position.
Is it possible to use "partial" tail-call optimization, where the backtrace is kept but all other frame state is discarded?
I think not in general, because then we'd need a stack for the backtrace and TCO no longer removes the need for stack space (it might be feasible to, e.g., keep a counter if it's a self-recursive call but not in general).
I strongly agree that if we add TCO, it should be explicit in the code, otherwise it breaks backtraces/tracing/debugging and it slows downs JIT-ed execution.
Maybe it could be implicit if it's restricted to self-recursive calls (e.g.; def bar; ...; bar; end).
In that case, there is not much information in the backtrace to be lost, and the performance of JIT-ed execution is likely similar, while allowing the self-recursive style (instead of a loop).
I'm not sure how useful the self-recursive style is in Ruby though.
I am thinking the example above with main_loop is more readable and easier to understand what it actually does with a while socket = server_socket.accept
loop.
Do we have motivating examples for this feature?
Updated by nobu (Nobuyoshi Nakada) 7 months ago
- Has duplicate Feature #16945: Enable TCO by use of special form added
Updated by dsisnero (Dominic Sisneros) 7 months ago
+1 for tail call optimization - either explicit or automatic