Path to enlightenment. Click here if you haven’t seen this meme before.
Random Wednesday afternoon, my good friend Daniel Rodríguez drops some lines in a Telegram group we share with Adrián Obelmejias and Roberto von Schoettler, really excited about his new realization: “Have you seen the y-combinator in ES6? f*cking beautiful!” — he wrote, and shared this snippet:
Before that Wednesday, the startup incubator behind Hacker News was the only “y-combinator” I knew about, so I had to go and read about y-combinator functions; I quickly grasped the idea and my answer to Daniel’s snippet was nothing more than another snippet:
You’re probably familiar with recursion, that’s it, a self-calling function, which is very functional and cool, right? Not exactly: lambda calculus doesn’t welcome function declarations, it allows anonymous function expressions and function arguments only, that means one cannot bind functions to identifiers, so it is impossible to refer a function definition inside its own function body. It is easier to understand this limitation if you try to write a recursive Fibonacci function as an Anonymous Immediately Invoked Function Expression yourselves:
I won’t be explaining the y-combinator implementation in detail, you can read great explanations here and here instead, but I can expose it in a less cryptic syntax so you can keep reading this article:
I was really excited about this discovery, but I couldn’t avoid to be bothered about my poorly improvised
fib function, I knew there was something growing exponentially while using that classic
fib() + fib() so I started to rework the function to call itself only once:
Great! The new function grows linearly so for
fib is called
31 times, while using the original code it was being invoked around for the same
n, making your machine choke in the process. And this wasn’t the only improvement I introduced; almost without noticing it, I was touching ground at another very functional concept:
[…] a tail call is a subroutine call performed as the final action of a procedure. If a tail call might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive, which is a special case of recursion.
The last action of the original
fib function is an arithmetic operation, a sum of numbers, whereas the new one’s is a function call, meaning it is written in tail-recursive form. Alongside the time complexity difference already shown, it also benefits from Tail Call Optimization introduced in ES2015 which basically transforms the recursion into a while-loop under the hood, skipping the creation of new layers in the Function Call Stack, going from O(n) linear space complexity to O(1) constant space complexity, allowing
trampoline implementation above takes a function
fn and returns a new function (the “trampolined” version) that, when called, will invoke
fn passing its arguments.
fn must either return a result or a “thunk”; a thunk is a function that returns either a result or another thunk; these thunks are going to be invoked until a result comes out.
Notice that the
fib function has been slightly modified to return a thunk instead of the value of calling itself, since
fib always returns either a value or a thunk, its stack frame is discarded and its recursive invocation happens outside of
fib, in the context of the trampolined function, preventing
fib functions to pile up in the call stack. The thunks’ closures hold the necessary information for their internal fib invocations to work,
n will eventually hit
fib to return a value, breaking the while loop and chaining the result out of the trampolined function.
Applying everything explained today plus some currying and function composition, we can write something very functional like this:
That’s quite hard to read, here’s a simpler version:
And here the same snippet but using big-integer to actually calculate big numbers in the Fibonacci series without hitting
And finally, some benchmarks: