This post provides a very simple step-by-step implementation of the Y-combinator in JavaScript. You should be able to implement the Y-combinator in your language of choice after reading this post; as you’ll see – it’s that easy.

**What is a combinator?**

According to wikipedia,

A combinator is a particular type of higher-order function that may be used in defining functions

without using variables. The combinators may be combined to direct values to their correct places in the expression without ever naming them as variables.

The emphasized text highlights the most interesting part of the definition – combinators allow functions to be defined without variables. Imperative programming relies heavily on variables and trying to eschew variables can be a mind-stretching exercise.

**Show me the code!**

The following code snippet is a Y-combinator example of the factorial function in JavaScript.

var yCombFact = function (number) { return (function (fn) { return fn(fn, number); })(function(f, n) { if(n <= 1) { return 1; } else { return n * f(f, (n - 1)); } }); }; yCombFact(5); //120Looks abstruse right? No worries – lets break it down.

Two major thingsThere are two major concepts that help drive home the understanding of the Y-combinator:

- No variables allowed – this implies we have to find a way to write the factorial function without using variables.
- Invoking the no-variable-function defined in 1 without using variables again.

Part 1: Rewriting the factorial function without variablesHere is the factorial function definition. Can you spot the variable usage in it?

var factorial = function(n) { if(n <= 1) { return 1; } else { return n * factorial(n - 1); } } factorial(5); //120The expression

onlyn * factorial(n – 1)succeeds because it can find the variablein scope; without it, thefactorialfunction would not be recursive. But remember, we are trying to do away withfactorialallvariables.The workaround is to pass in the variable reference as a function parameter. In the factorial example, recursion can then be achieved by using the placeholder parameter as the reference. The no-variable-factorial function looks like the following:

var noVarFactorial = function(fn, n) { if(n <= 1) { return 1; } else { return n * fn(fn, (n - 1)); } } noVarFactorial(noVarFactorial, 5); //120The new definition works exactly like the old one but without the internal dependency on the

variable. Rather, recursion succeeds by relying on the ‘factorialinjected’parameter and the computer is none the wiser.

Part 2: Invoking the no-variable function without variablesWe have rewritten the factorial function to avoid variables however we still need to store the

function in a variable before invoking itfactorialvar factorial = ...; factorial(factorial, 5);The trick? Functions to the rescue again! Let’s create a

function that uses thefactorialCalculatordefinition above.noVariableFactorialfunction factorialCalculator(n) { //as defined earlier var noVarFactorial = ...; return noVarFactorial(noVarFactorial, n); } factorialCalculator(5); //120The noVarFactorial name has to go since we want to avoid variables. And how do we achieve this? Yes, functions once more. So lets create a wrapper function inside the

that invokesfactorialCalculatornoVariableFactorial.function factorialCalculator(n) { var wrapper = function (noVarFact) { return noVarFact(noVarFact, n); } return wrapper(noVarFactorial); } factorialCalculator(5); //120Unfortunately, the wrapper function has led created another

variable and this has to be eliminated too. For a complete implementation, the two variables (wrapper) have to go.wrapper and noVarFactIt’s now time to leverage language specific idioms to achieve this. JavaScript has the IIFE idiom which allows you to immediately invoke a function (read about it here). Using it, we can eliminate the need for the

variable as thus:wrapperfunction factorialCalculator(n) { return (function (noVarFact) { return noVarFact(noVarFact, n); })(noVarFactorial); } factorialCalculator(5); //120

Combining all the piecesThe last thing is to insert the

definition so that it is no longer a global variable in the scope. Just as we do in Mathematics, we can justnoVarFact‘substitute’the value in. The final piece is then:function factorialCalculator(n) { return (function (noVarFact) { return noVarFact(noVarFact, n); })(function(fn, n) { if(n <= 1) { return 1; } else { return n * fn(fn, (n - 1)); } }); } factorialCalculator(5); //120And that, my friends, is the yCombinator in all its glory. I have decide to leave the variables as they are to make it all clear but here is the standard format so you know it when you see it

function factorialCalculator(n) { return (function (fn) { return fn(fn, n); })(function(fn, n) { if(n <= 1) { return 1; } else { return n * fn(fn, (n - 1)); } }); } factorialCalculator(5);

ConclusionThe Y-combinator is quite easy to understand – it requires understanding function invocation patterns, variable substitution by parameters and higher level functions. As an exercise, can you try implementing the fibonacci using the Y-combinator approach? Better still, why not create a Y-combinator function that accepts function that match the fn(fn, n) signature?

Related Posts

Leave a Reply