Path to enlightenment. if you haven’t seen this meme before. Click here Random Wednesday afternoon, my good friend drops some lines in a Telegram group we share with and really excited about his new realization: “Have you seen the y-combinator in ES6? f*cking beautiful!” — he wrote, and shared this snippet: Daniel Rodríguez Adrián Obelmejias Roberto von Schoettler, 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 of JavaScript and I’ll be sharing our naive discoveries today. I will assume you have some experience with ES2015 and because, well, sure you do, functional JavaScript is lately. fantasy land functional programming concepts hot as hell y-combinator Before that Wednesday, the startup incubator behind was the only “y-combinator” I knew about, so I had to go and ; I quickly grasped the idea and my answer to Daniel’s snippet was nothing more than another snippet: Hacker News read about y-combinator functions 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 , 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 yourselves: function declarations Anonymous Immediately Invoked Function Expression The is a proof by 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. y-combinator function Haskell Curry I won’t be explaining the y-combinator implementation in detail, you can read great explanations and instead, but I can expose it in a less cryptic syntax so you can keep reading this article: here here Tail Call Optimization I was really excited about this discovery, but I couldn’t avoid to be bothered about my poorly improvised function, I knew there was something while using that classic so I started to rework the function to call itself only once: fib growing exponentially fib() + fib() Great! The new function grows linearly so for , is called times, while using the original code it was being invoked around for the same , 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 : n=30 fib 31 one million times n concept […] a 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 , which is a special case of recursion. tail call tail-recursive The last action of the original function is an , a sum of numbers, whereas the new one’s is a function call, meaning it is written in form. Alongside the time complexity difference already shown, it also benefits from introduced in which basically transforms the recursion under the hood, skipping the creation of new layers in the , going from linear space complexity to constant space complexity, allowing to eventually return (due to JavaScript’s number ) without throwing “Maximum call stack size exceeded” error — better late and wrong than never, huh? fib arithmetic operation tail-recursive Tail Call Optimization ES2015 into a while-loop Function Call Stack O(n) O(1) fib([Number.MAX_SAFE_INTEGER](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER)) Infinity limitations 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 is the only engine that has . Thankfully, there’s a technique called 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. JavaScriptCore implemented TCO trampolining The implementation above takes a function and returns a new function (the “trampolined” version) that, when called, will invoke passing its arguments. 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. trampoline fn fn fn Notice that the function has been slightly modified to return a thunk instead of the value of calling itself, since always returns either a value or a thunk, its stack frame is discarded and its recursive invocation happens outside of , in the context of the trampolined function, preventing functions to pile up in the call stack. The thunks’ closures hold the necessary information for their internal fib invocations to work, will eventually hit for to return a value, breaking the while loop and chaining the result out of the trampolined function. fib fib fib fib n 0 fib 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 and none intended to boost performance but to workaround JavaScript engines’ limitations, thus TCO support is still quite desired. many trampoline implementations out there Making JavaScript look like Lisp, one parenthesis at a time. — , 2017 Adrián Obelmejias 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 to actually calculate big numbers in the Fibonacci series without hitting : big-integer 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 is very expensive. Destructing Assignment Seriously, stick to iterative procedures if performance is important. My from that random Wednesday if you’re curious. original notes Not clear about function composition? . Check this Must read: . automatic memoization using y-combinator
