Ruby » Ruby master

Feature #6602

Updated by nobu (Nobuyoshi Nakada) over 12 years ago

=begin 
 Hi, 

 Some hours ago, Matz proposed turning on "tail call optimization" by default from Ruby 2.0. 

 What do you think about it? 


 = Background 

 Tail call: Method invocation at last of method body. 

 Tail call optimization: Eliminating the new stack frame creation when method invocation is "tail call". 


 For exmaple, the method bar() is located at last of method foo(), so bar() is "tail call". 

   def foo() 
     ... 
     bar() 
   end 

 In this case, after invocation of method bar(), foo()'s method frame information (which contains local variables, program counter, stack pointer and so on) is no longer needed because method foo() doesn't work after that (correctly, method foo() only does "return"). 

 Next example, a simple recursion code by foo().    Of course, foo() is "tail call". 

   def foo() 
     ... 
     foo() 
   end 

 Current Ruby causes stack overflow error because such recursion consumes the (VM) stack.    However, using tail call optimization, VM doesn't consume stack frame any more. 

 Such recursion can be converted to simple loop: 

   def foo 
     while true 
       foo() 
     end 
   end 

 Someone calls tail-call opt as "tail recursion optimization" because recursion is famous use-case (*1). 

 *1: Generally, tail-recursion optimization includes another optimization technique - "call" to "jump" translation.    In my opinion, it is difficult to apply this optimization because recognizing "recursion" is difficult in Ruby's world. 

 Next example.    fact() method invocation in "else" clause is *not* a "tail call". 

   def fact(n) 
     if n < 2 
       1 
     else 
       n * fact(n-1) 
     end 
   end 

 If you want to use tail-call optimization on fact() method, you need to change fact() method as follows (continuation passing style). 

   def fact(n, r) 
     if n < 2 
       r 
     else 
       fact(n-1, n*r) 
     end 
   end 

 In this case, fact() is tail-call (and a bit difficult to read/write). 

 Of course, the following code is easy to understand and short. 

   (1..n).inject(:*) 

 Last examples.    Recognizing tail-call is a bit difficult.   

   def foo 
     begin 
       bar2()    # not a tail-call 
     rescue 
       bar3()    # not a tail-call 
     rescue 
       bar4()    # not a tail-call 
     ensure 
       bar5()    # tail-call! 
     end 
   end 

   def foo 
     while true 
       return bar("break") # tail-call? (current CRuby can't handle "break" in eval(). 
     end 
   end 

 CRuby 1.9 has a code tail-call optimization (not tested yet.    maybe there are several bugs).    However, it is off by default because of several problems described in next section. 


 = Problems: 

 * (1) backtrace: Eliminating method frame means eliminating backtrace. 
 * (2) set_trace_func(): It is difficult to probe "return" event for tail-call methods. 
 * (3) semantics: It is difficult to define tail-call in document (half is joking,    but half is serious) 

 References: 
 * [ruby-core:20273] 
 * [ruby-core:20307] 
 * [ruby-core:22736] 
 * [ruby-core:22790]  

 Maybe (1) has big impact for ordinal users. 

 For example: 

   def foo 
     bar() 
   end 
  
   def bar 
     baz() 
   end 
  
   def baz 
     raise("somethig error") 
   end 

 In this case, backtrace information only include "baz", because bar() in foo and baz() in bar are "tail-call".    Users can't see eliminated frame information in backtrace. 

 This is why we don't introduce them by default to Ruby 1.9. 


 = Discussion 

 Many people ask us that "why don't you introduce tail-call optimization?    it is very easy technique."    I wrote reasons above. 

 Matz said "it seems small impact enough.    Go ahead". (I doubt it ;P ) 

 Yusuke Endo proposed that introducing special form (for example, send_tail(:foo, ...)) to declare tail call.    Users only use this special form when the backtrace information can be eliminated (*2). 

 (*2) Special form "goto foo()" is nice joking feature :)    I like it but I believe Matz will reject it. 

 Akira Tanaka introduced that special backtrace notation like: 

   baz 
   ... (eliminated by tail call optimization) 
   main 

 to represent eliminating method invocation information.    We can know they were eliminated (good) but we can't know what method frames were eliminated (bad). 


 = Conclusion 

 Matz wanted to introduce it.    However it has several problems.    Should we turn on this optimization by default? 

 Sorry for long (and poor English) article.    Comments and proposals are welcome (with short English, long Ruby codes ;p). 


 Thanks, 
 Koichi 
 =end

Back