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:
At that point, I had no idea what a y-combinator was or how that piece of code worked; it was the beginning of a spontaneous quest for better answers in the fantasy land of JavaScript and I’ll be sharing our naive discoveries today. I will assume you have some experience with ES2015 and functional programming concepts because, well, sure you do, functional JavaScript is hot as hell lately.
y-combinator
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:
The y-combinator function is a proof by Haskell Curry that recursion can be expressed as a set of rewrite rules when explicit recursion is impossible, as in lambda calculus. It might not be very useful for every-day development, but it is very interesting that you can achieve a fully-capable purely-functional programming style in JavaScript.
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:
Tail Call Optimization
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 n=30, fib is called 31 times, while using the original code it was being invoked around one million times 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 fib([Number.MAX_SAFE_INTEGER](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER)) to eventually return Infinity (due to JavaScript’s number limitations) without throwing “Maximum call stack size exceeded” error — better late and wrong than never, huh?
trampoline
We got a fairly performant recursive Fibonacci function that may call itself some 9 quintillion times without overflowing the call stack, nice, right? Well, not that nice since, at the time of writing, Safari’s JavaScriptCore is the only engine that has implemented TCO. Thankfully, there’s a technique called trampolining to overcome the Function Call Stack limitation on platforms that lack TCO by taking the result of each function invocation out of its stack frame.
The 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 0 for fib to return a value, breaking the while loop and chaining the result out of the trampolined function.
Be aware that a trampolined function with its thunks doubles the total amount of function calls and will be outperformed by its more primitive recursive version. There are many trampoline implementations out there and none intended to boost performance but to workaround JavaScript engines’ limitations, thus TCO support is still quite desired.
Making JavaScript look like Lisp, one parenthesis at a time. — Adrián Obelmejias, 2017
Wrapping up
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 Infinity:
And finally, some benchmarks:
Conclusions and further reading
- Functional programming might be a bit difficult to understand, but might also be addictive once you get into it.
- Function calls are expensive, use them wisely if you care.
- Variable swapping with Destructing Assignment is very expensive.
- Seriously, stick to iterative procedures if performance is important.
- My original notes from that random Wednesday if you’re curious.
- Not clear about function composition? Check this.
- Must read: automatic memoization using y-combinator.