Recently I thought I'd take a jab at functional languages just to try out a different paradigm of thinking, and I decided to pick up Elixir
since it's so syntatically similar to Ruby
. While I was learning, I found something.
TLDR:
- Elixir has no loops
- Recursion makes an additional call to call stack (which is why your stack overflows if you forget your base case)
- Tail Call Optimizations is a compiler feature that optimizes recursions (if the last thing it does is call itself)!
There is no concept of loop in Elixir.
Yes, none of your for
loops or .each
. It's a bit of a strange concept at first, but let's see what's the alternative.
If you can't use an iterative approach to iterate a loop, how do you traverse a list? Recursion.
Brief recap: Recursion is when a function calls itself, like this
A Ruby Example:
def traverse(tail)
head = tail.shift # shift takes out the first element
puts "Element: #{head}"
return if tail.empty?
traverse(tail)
end
An Elixir Example:
defmodule Recursion do
def traverse([]), do: IO.puts "Done"
def traverse([head | tail]) do
IO.puts "Element: #{head}"
traverse(tail)
end
end
Pretty interesting to traverse recursively instead of the iteratively aye?
LARGE NUMBERS!
Next, let's see what happens when it comes to a large number!
Ruby:
large_array = Array.new(500_000).fill { |i| i + 1 }
traverse(large_array)
# Element: 1
# Element: ...
# Element: ...
# Element: 10918
#=> stack level too deep (SystemStackError)
It crashes with a SystemStackError
! Wow, does that mean recursion
is bad? does that mean recursion
is bad? does the mean recursion
is bad? does that mean recursion
is ... Okay, before we go crazy, let's take a look at how Elixir deals with it.
Elixir:
start = 1
increment = 1
length = 500000
list = Stream.iterate(start, &(&1 + increment)) |> Enum.take(length)
Recursion.traverse(list)
# Element: 1
# Element: ...
# Element: ...
# Element: 500000
# Done
#=> :ok
You can see that Elixir effortlessly handles all five hundred thousands recursion. But why does it work in Elixir
but not Ruby
?
Because of Tail Call Optimization
!
What is Tail Call Optimization?
Tail Call Optimization (TCO) is a compiler feature in which the compiler automatically optimizes the stack, if the last thing that a function does is call itself.
But what is the stack? and what do you mean by 'optimizes the stack'?
Stack is a data structure that employs the LIFO mindset (Last-In-First-Out), think of it as a fixed array but you can only insert from one end and take out from the same end. What we're specifically talking about here is the call stack.
To understand this better, we need to first understand how call stacks work.
When you call a function, it gets added to the call stack, and when it finish executing, it gets popped off the stack, like so:
And when you have a recursive function call, it's basically adding itself to the call stack every single time. If you forget your base case/have too big of a call stack, it throws a stack overflow error! (what we saw earlier), like this.
All TCO means is that, when the compiler sees the last call of the function is calling itself, instead of adding the function call to the call stack, it does a goto
instead, and basically restarts the same function call, requiring O(1) instead of O(n) space (we will prove this later).
Now this is what it looks like when it's TCO-ed:
Do we have that in Ruby?
We do indeed! However TCO is not enabled by default, so you have to pass in the compile option during runtime, and you can do it like so:
RubyVM::InstructionSequence.compile_option = {
tailcall_optimization: true,
trace_instruction: false
}
require './tail_recursion.rb'
large_array = Array.new(500_000).fill { |i| i + 1 }
traverse(large_array)
# Element: 1
# Element: ...
# Element: ...
#=> Element: 500000
Not very useful if you have to enable it with a flag, but it's there if you need it!
Proof?
Got your back! In RubyLand, We can inspect the current call stack with a call to Kernel#caller
. Lets .count
!
Change our code like so:
def traverse(tail)
head = list.shift
puts "Element: #{head}, Stack Count: #{caller.count}" #=> new line
return if tail.empty?
traverse(tail)
end
# Normal ruby
traverse(large_array)
# Element: 1, Stack Count: 1
# Element: ..., Stack Count: ...
# Element: ..., Stack Count: ...
# Element: 10918, Stack Count: 10918
# => stack level too deep (SystemStackError)
# TCO-enabled
traverse(large_array)
# Element: 1, Stack Count: 1
# Element: ..., Stack Count: 1
# Element: ..., Stack Count: 1
# Element: 500000, Stack Count: 1
Conclusion
Alright so that's it for today! Thought it's pretty cool that I'm trying to learn Elixir but end up learning something about compiler instead!
Check out my previous articles too:
Top comments (15)
Didn't know there's a flag.
Why isn't it enabled by default?
Seems like a no-brainer optimization to do when the conditions allow it.
Also, it works in all explicit/implicit return positions, right? Not just at the end of the function?
What about mutual recursion with both functions calling each other in tail position?
There are implicit trade-off, such as losing the stack trace which could make things harder to debug.
I think you have to keep in mind though, software is about tradeoffs - just because the condition allow it does not mean the tradeoff is worth it.
One of the most popular use case is recursion, but we don't really do recursions in Ruby, so is it really worth the tradeoff then?
It's also Python's reasoning (Guido). You can read more about his blog posts here explaining his rationale, it's a pretty good read.
1) neopythonic.blogspot.com/2009/04/t...
2) neopythonic.blogspot.com/2009/04/f...
You can also read about the progress on Ruby's official issue tracker - bugs.ruby-lang.org/issues/6602
Yes it doesn't have to literally be on the last line, but just the last executed statement.
Not sure what you mean about mutual calling, I don't think that's really possible (I could be wrong) - Yes, you can mutual call each other at tail call position, but that does not instantly make it possible for tail call optimization; TCO is when a compiler recognizes it's calling itself (as stated in the gifs). TCO also eliminates the stackframe (can read in the issue tracker). I don't think compilers can recognize a mutual calling tail call and optimize that
ES6 spec mandated TCO for mutually recursive functions as well that both call each other in tail call position.
Only Apple browsers have it implemented at the moment, Chrome implemented it but later removed it.
One notable part of the spec was that
would not get optimized, because there is an implicit
return undefined
after the last line.I understand how that limitation came about, but I don't really see why they couldn't add a single "void" to the stack and then merrily recurse as if it's this:
since the return value of the inner a is never used.
The tradeoffs for Ruby specifically sound like something that is more relevant in development than production, almost like something that should be a flag... Oh. That's what they did. Okay.
(I'd still suggest it be the default, until someone needs to pass
--debug
, but I get the idea)Very interesting explanation. I've been using Elixir for a while now, and even though I knew that the BEAM provides tail call optimization, I did not know how it worked behind scenes, it is a
goto
!Glad you liked it man! Yeah it's always interesting to see how things work behind the scene!
Just want to mention that tail call optimization is not always the best solution. Sometimes, it consumes more memory and runs slower than body recursion.
Interesting, can you elaborate on that?
P.S: And welcome to dev.to :D
After Erlang/OTP R12B, a body-recursive function generally uses the same amount of memory as a tail-recursive function and generally hard to predict whether the tail-recursive or the body-recursive version will be faster.
With around 10, 000 elements, a body-reclusive function is about 10% faster. But with larger lists (like 10, 000, 000 elements), a body-reclusive function is about 97% lower and it is about as faster as the standard library map.
references:
Myth: Tail-Recursive Functions are Much Faster Than Recursive Functions
erlang.org/doc/efficiency_guide/my...
TAIL CALL OPTIMIZATION IN ELIXIR & ERLANG – NOT AS EFFICIENT AND IMPORTANT AS YOU PROBABLY THINK
pragtob.wordpress.com/2016/06/16/t...
Wow that is interesting indeed, thanks for sharing!
Why is the Elixir example considered a use of TCO? It uses a Stream for lazy evaluation but is it using TCO under the hood?
That was just a quick way for me to generate large numbers
Ah okay I get it now, thanks!
May I mark it with the triple unicorn? ) Thanks a lot!
That means a lot man, thanks! :D
Just share it to three other friend who'll unicorn it hahaha