Does Ruby perform Tail Call Optimization?

Question

Functional languages lead to use of recursion to solve a lot of problems, and therefore many of them perform Tail Call Optimization (TCO). TCO causes calls to a function from another function (or itself, in which case this feature is also known as Tail Recursion Elimination, which is a subset of TCO), as the last step of that function, to not need a new stack frame, which decreases overhead and memory usage.

Ruby obviously has "borrowed" a number of concepts from functional languages (lambdas, functions like map and so forth, etc.), which makes me curious: Does Ruby perform tail call optimization?

Answer 1

No, Ruby doesn't perform TCO. However, it also doesn't not perform TCO.

The Ruby Language Specification doesn't say anything about TCO. It doesn't say you have to do it, but it also doesn't say you can't do it. You just can't rely on it.

This is unlike Scheme, where the Language Specification requires that all Implementations must perform TCO. But it is also unlike Python, where Guido van Rossum has made it very clear on multiple occasions (the last time just a couple of days ago) that Python Implementations should not perform TCO.

Yukihiro Matsumoto is sympathetic to TCO, he just doesn't want to force all Implementations to support it. Unfortunately, this means that you cannot rely on TCO, or if you do, your code will no longer be portable to other Ruby Implementations.

So, some Ruby Implementations perform TCO, but most don't. YARV, for example, supports TCO, although (for the moment) you have to explicitly uncomment a line in the source code and recompile the VM, to activate TCO – in future versions it is going to be on by default, after the implementation proves stable. The Parrot Virtual Machine supports TCO natively, therefore Cardinal could quite easily support it, too. The CLR has some support for TCO, which means that IronRuby and Ruby.NET could probably do it. Rubinius could probably do it, too.

But JRuby and XRuby don't support TCO, and they probably won't, unless the JVM itself gains support for TCO. The problem is this: if you want to have a fast implementation, and fast and seamless integration with Java, then you should be stack-compatible with Java and use the JVM's stack as much as possible. You can quite easily implement TCO with trampolines or explicit continuation-passing style, but then you are no longer using the JVM stack, which means that everytime you want to call into Java or call from Java into Ruby, you have to perform some kind of conversion, which is slow. So, XRuby and JRuby chose to go with speed and Java integration over TCO and continuations (which basically have the same problem).

This applies to all implementations of Ruby that want to tightly integrate with some host platform that doesn't support TCO natively. For example, I guess MacRuby is going to have the same problem.

Answer 2

Update: Here's nice explanation of TCO in Ruby: http://nithinbekal.com/posts/ruby-tco/

Update: You might want also check out the tco_method gem: http://blog.tdg5.com/introducing-the-tco_method-gem/

In Ruby MRI (1.9, 2.0 and 2.1) you can turn TCO on with:

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

There was a proposal to turn TCO on by default in Ruby 2.0. It also explains some issues that come with that: Tail call optimization: enable by default?.

Short excerpt from the link:

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

Answer 3

It can have but is not guaranteed to:

https://bugs.ruby-lang.org/issues/1256

Answer 4

TCO can also be compiled in by tweaking a couple variables in vm_opts.h before compiling: https://github.com/ruby/ruby/blob/trunk/vm_opts.h#L21

// vm_opts.h
#define OPT_TRACE_INSTRUCTION        0    // default 1
#define OPT_TAILCALL_OPTIMIZATION    1    // default 0

Answer 5

This builds on Jörg's and Ernest's answers. Basically it depends on implementation.

I couldn't get Ernest's answer to work on MRI, but it is doable. I found this example that works for MRI 1.9 to 2.1. This should print a very large number. If you don't set TCO option to true, you should get the "stack too deep" error.

source = <<-SOURCE
def fact n, acc = 1
  if n.zero?
    acc
  else
    fact n - 1, acc * n
  end
end

fact 10000
SOURCE

i_seq = RubyVM::InstructionSequence.new source, nil, nil, nil,
  tailcall_optimization: true, trace_instruction: false

#puts i_seq.disasm

begin
  value = i_seq.eval

  p value
rescue SystemStackError => e
  p e
end