Tail Call Optimisation in Elixir & Ruby

Surviving without looping.

I'm learning Elixir for fun and frolics^[1]. Elixir is a pure functional language; my go-to language for ages has been Ruby which also has functional language elements so there is a lot of cross-over. What I didn't expect at first glance (though it makes sense at second glance) is the complete absence of looping constructs. That's right: there's no for and no while (although there is an each on enumerations).

Core to Elixir is lots and lots of recursion, enabled by really powerful pattern matching.

I'm assuming you understand the difference between the stack the heap^[2]. Each time you call a method, a new stack frame is created and pushed onto the stack. When the method finishes, the frame is popped off and its memory released.

def method_one
  method_two
end

def method_two
  puts 'Hello World!' # <<--
end

method_one

So when we are executing the puts on line 6, the stack looks a bit like this...

1. puts
2. method_two
3. method_one

So let's imagine we have a huge queue of work to do. In ruby, we might loop over it like this...

# assuming queue is an array
until queue.empty?
  queue.shift
end

In elixir, we might recurse like this...

defmodule Q
  def dequeue([hd | tl]), do: dequeue(tl)
  def dequeue([]), do: []
end

Fine and dandy but anything that can be expressed as a loop can be expressed using recursion so we could re-write the ruby to be...

def dequeue(arr)
  arr.shift
  dequeue(arr) unless arr.empty?
end

So what happens to the stack? In ruby dequeue([1,2,3]) looks like this:

1. dequeue([])
2. dequeue([3])
3. dequeue([2,3])
4. dequeue([1,2,3])

Elixir's stack looks like this:

1. Q.dequeue(...)

Huh? Well, recursing in ruby is just like a normal method call: it adds a new frame to the stack. In Elixir, and other functional languages, recursing as the last thing the method does, reuses the existing frame. This is called Tail Call Optimisation (TCO).

This means that if we ask ruby to recurse too much, we're going to get the dreaded SystemStackError: stack level too deep.

Well, it turns out that you can enable TCO in ruby. This instruction tells the VM to enable it for any code it subsequently compiles:

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

And then you can tail-recurse as much as you like.