I’d recommend reading Lambda Calculus in JavaScript before continuing!The Y Combinator is a fixed-point higher order function which is used to implement recursion in any programming language which does not support it natively.
It has been introduced by the mathematician and logician Haskell Curry in 1940’s and is considered to be one of the most beautiful ideas in programming and logic.
We’ll see how to implement that amazing piece of code in 6 programming languages:JavaScriptHaskellJavaRacketPythonCOriginal Y Combinator in Lambda CalculusWe’ve just expressed one of the most powerful concepts in computer science in less than 30 characters.
As you may have guessed, we just wrote down the Y Abstraction.
What’s its actual application?Let’s use the classical factorial example.
The factorial of a number n is the sum of all the positive integers between 0 and n.
We can easily use recursion in order to find the factorial of any positive integer (in pseudocode):So let’s pretend we have to compute the factorial of 3; adopting the solution above, we’ll be executing our function the following way:So as you can see, we’re calling the factorial function inside the factorial function itself.
This is a simple example about how recursion works, and not every language supports that style of programming!Here comes the Y Combinator.
Let’s start by implementing it in JavaScript:It’s actually pretty easy!.As you can see, that is pretty close to the code we wrote above using the Lamba Calculus notation!Now, we need to implement our function which will calculate the factorial of a given integer:Great!.As you can see, we’re not taking an integer as first argument, but we’re taking a function that returns an anonymous function which takes an integer as its only argument.
That way, we parametrized the f call, which will be used inside our Y implementation.
Now let’s call the factorial function using the Y Combinator we just wrote above and here we are:We can now call any kind of recursive function inside our Y Combinator avoiding runtime memory exceptions!Y Combinator in HaskellAs you can see, writing the Y Combinator Abstraction in Haskell is pretty easy when you’re coming from the Lambda Calculus notation!By the way, this code won’t compile because of (x x) which requires an infinite type.
For that reason, we have to choose if we want to adopt an Unsafe Coercion and make it work, or change the approach:Using Unsafe Coercion (unsafe):Adopting a non-recursive solution (safe):https://stackoverflow.
com/questions/4273413/y-combinator-in-haskell/5885270#5885270Just to keep it simple, we’re gonna use the unsafe version, which is easier to show and explain.
Let’s implement the factorial function in Haskell!We can now call the factorial function using the previously defined Y Combinator:It’s actually pretty cool!.But I find it to be more “conceptual” to implement that kind of solution in Haskell, which already has an amazing support for recursion.
Y Combinator in JavaI have to admit it: I am not a Java expert and that is actually the most complex piece of code I ever wrote… but it works!.And it shows you an alternative to the classical Imperative/Object Oriented approach in Java.
I am not saying that you should use this kind of approach everytime you have to solve a problem using recursion in Java: instead, I strongly believe that the example above shows you how Lambda Calculus can actually be as complete as the Turing Machine, which is the foundation of imperative and Object Oriented languages such as Java!Y Combinator in RacketRacket implementation is basically the same as the Lambda Calculus one!.They’re actually pretty similar and that language shows how close it is to the Lambda Calculus notation, which is the foundation of any LISP programming language!Y Combinator in PythonY Combinator in Python is actually easy to implement, but a little “messy” because of its lambda syntax.
By the way, the way it works is extremely clear and developer working with Python will certainly understand how the Y Combinator works under the hood!Y Combinator in CThat has probably been the worst idea in my life, but its pretty satisfying to see how a language which is basically 100% based on the Turing Machine, can still implement such an abstract concept derived from Lambda Calculus!Pure C solution is not even close to the Lambda Calculus definition, but does the exact same job with outstanding performances!ConclusionAs we’ve seen in both Java and C examples, Lambda Calculus concepts can still be expressed in languages which were born with a totally different approach their core.
Lambda Calculus is an amazing topic and is totally worth to spend some time studying it.
It’s actually mind-changing!My website: https://www.
micheleriva.
itMy GitHub: https://github.
com/michelerivaMy LinkedIn: https://linkedin.
com/in/micheleriva95/My Instagram: http://instagram.
com/mitch_sleva.