kestas.kuliukas.com

The Y Combinator explained with JavaScript

	var y = function(le) {
		return function(f) { 
			return f(f); 
		}(function(f) {
			return le(
				function(x) { return (f(f))(x); }
			);
		});
	};

The Y combinator is an interesting function which only works with functional languages, showing how recursion can still be done even without any variable or function declarations, only functions and parameters.
Unfortunately it's hard to figure out what it does exactly because of what it is; variable and function declarations are what make computer code understandable, and the Y combinator is all about trying to work without them.

I got the Y combinator in its JavaScript form above, and an awareness of it and challenge to understand it, from the third of Douglas Crockford's excellent lectures on JavaScript.

The approach I found the most helpful for learning how it works, which I'll use below, is to try and build the Y combinator using an easy example; the factorial function. (fact(4) = 4*3*2*1 = 24)

	var fact = function(n) {
		if( n < 2 ) return 1;
		else return n*fact(n-1);
	};

There it is, a very simple recursive function. If n is 1 return 1, otherwise multiply n by fact(n-1).
In order to make the Y combinator though we need to remove all declarations. The fact() function refers to fact() within itself. But how can we recursively call the factorial function without creating a reference to the factorial function?
We can do it by passing the factorial function as a parameter, and having a function which returns the factorial function rather than declare it.

	var makeFact = function(givenFact) {
		var fact=function(n) {
			if( n < 2 ) return 1;
			else return n * givenFact(n-1);
		}
		return fact;
	};

The problem is that without a "givenFact" function we can't call makeFact. It seems like we can't use this approach because we can't use makeFact to make a factorial function without already having a factorial function!
It turns out that it is possible though, because the fact function which makeFact makes doesn't always call givenFact. Instead of passing in a pre-made givenFact we can make givenFact itself use makeFact, until makeFact makes a fact call which doesn't need to call givenFact.

	var makeRealFact = function(makeFact) {
		var tryFact=function(n) {
			var nextTryFact = makeFact(tryFact);
			return nextTryFact(n);
		};
		return makeFact(tryFact);
	};

We create a new function makeRealFact (our Y function) which uses makeFact to make the actual factorial function.
The tryFact function is passed to makeFact to be used as its givenFact function. If makeFact needs to use givenFact it will call tryFact again, which will make another tryFact using makeFact and try again.
Eventually makeFact will be able to return a factorial function which doesn't use givenFact, which can then be used to find a givenFact, and that used to find another givenFact, and so on.

This approach is like using makeFact to keep working on the tryFact function, assuming makeFact will always need a simpler tryFact function until it finds a way to makeFact without needing tryFact. It's still simple recursion, but in an indirect way.

"return nextTryFact(n)" will recursively call tryFact(n)-nextTryFact(n)-tryFact(n-1)-nextTryFact(n-1)-etc until nextTryFact(1) is reached, returning a value without needing to use givenFact.

There is still a problem though; tryFact references itself ("var nextTryFact = makeFact(tryFact);"), so it doesn't solve the problem of getting rid of variable/function declarations.
Another function needs to be created to keep on cycling through tryFact-nextTryFact, without tryFact having to reference itself.
The getNextTryFact function will return the next tryFact function to tryFact, so it doesn't have to refer to itself.

	var makeRealFact = function(makeFact) {
		var getNextTryFact=function() {
			var tryFact = function(n) {
				var nextTryFact = getNextTryFact();
				var result = nextTryFact(n);
				return result;
			};
			var nextTryFact = makeFact(tryFact);
			return nextTryFact;
		};
		return getNextTryFact();
	};

Instead of tryFact passing itself to makeFact until it isn't needed it calls getNextTryFact, which passes tryFact to makeFact for it.

But now getNextTryFact needs to refer to itself, so we need a way to refer to getNextTryFact without declaring it.
This is done by passing getNextTryFact to itself as a parameter, and is the final adjustment needed to remove all self-referencing functions.

	var makeRealFact = function(makeFact) {
		var getNextTryFact=function(getNextTryFactRef) {
			var tryFact = function(n) {
				var nextTryFact = getNextTryFactRef(getNextTryFactRef);
				var result = nextTryFact(n);
				return result;
			};
			var nextTryFact = makeFact(tryFact);
			return nextTryFact;
		};
		return getNextTryFact(getNextTryFact);
	};

Now we have a function which can make a factorial function using the makeFact function recursively, without ever needing to refer to its own variables/functions via labels; everything can be accessed via parameters. (getNextTryFactRef is a reference to the getNextTryFact function, maintained using parameters rather than a variable declaration.)

Obviously declarations are still used though, but now we can start to factor them out to end up with a function which only uses parameters. From here on the function gets much less readable, but we show that it truly doesn't need variable declarations, and thus show how it is equivalent to the Y function above.

First the tryFact function is passed directly to makeFact, without being declared.

	var makeRealFact = function(makeFact) {
		var getNextTryFact=function(getNextTryFactRef) {
			var nextTryFact = makeFact(
				function(n) {
					var nextTryFact = getNextTryFactRef(getNextTryFactRef);
					var result = nextTryFact(n);
					return result;
				}
			);
			return nextTryFact;
		};
		return getNextTryFact(getNextTryFact);
	};

Next the inner-most nextTryFact function is used to generate a result without being declared.

	var makeRealFact = function(makeFact) {
		var getNextTryFact=function(getNextTryFactRef) {
			var nextTryFact = makeFact(
				function(n) {
					// Already it's becoming cryptic
					var result = (getNextTryFactRef(getNextTryFactRef))(n);
					return result;
				}
			);
			return nextTryFact;
		};
		return getNextTryFact(getNextTryFact);
	};

Next the result is returned without being declared.

	var makeRealFact = function(makeFact) {
		var getNextTryFact=function(getNextTryFactRef) {
			var nextTryFact = makeFact(
				function(n) {
					return (getNextTryFactRef(getNextTryFactRef))(n);
				}
			);
			return nextTryFact;
		}
		return getNextTryFact(getNextTryFact);
	};

Next the outer nextTryFact function is returned directly without being declared.

	var makeRealFact = function(makeFact) {
		var getNextTryFact=function(getNextTryFactRef) {
			return makeFact(
				function(n) {
					return (getNextTryFactRef(getNextTryFactRef))(n);
				}
			);
		};
		return getNextTryFact(getNextTryFact);
	};

Because getNextTryFact is used twice on the same line a label is needed to refer to the same thing twice. This has to be done by passing it to a function as a parameter, so the parameter can be used as a label to refer to the same thing twice.

	var makeRealFact = function(makeFact) {
		var getNextTryFact=function(getNextTryFactRef) {
			return makeFact(
				function(n) {
					return (getNextTryFactRef(getNextTryFactRef))(n);
				}
			);
		};
		return function(getNextTryFactRef) { 
			return getNextTryFactRef(getNextTryFactRef); 
		}(getNextTryFact);
	};

Finally the getNextTryFact function is passed directly to the nameless function which calls getNextTryFact on itself to start the recursion going.

	var makeRealFact = function(makeFact) {
		return function(getNextTryFactRef) {
			return getNextTryFactRef(getNextTryFactRef);
		}(
			function(getNextTryFactRef) {
				return makeFact(
					function(n) {
						return (getNextTryFactRef(getNextTryFactRef))(n);
					}
				);
			}
		);
	};

We've got rid of the declarations of tryFact, nextTryFact, result, and getNextTryFact, leaving a function which has no declarations, only parameters.
All that is needed now is to rename makeFact "le" (don't know why), getNextTryFactRef "f", the n parameter "x", and makeRealFact "y", get rid of some white-space, and we have the Y combinator function as it was given above.

	var y = function(le) {
		return function(f) { 
			return f(f); 
		}(function(f) {
			return le(
				function(x) { return (f(f))(x); }
			);
		});
	};
	// Even when written from scratch this form is baffling

Although we made it for the factorial function the Y combinator can be used for any recursive function, showing that recursion can be done without variables and thus without any side-effects. Below the same y combinator function is used to make a factorial function and a fibbonaci function.

	var makeFact = function(givenFact) {
		return function(n) {
			if( n < 2 ) return 1;
			else return n * givenFact(n-1);
		}
	};
	var fact=y(makeFact);
	alert(fact(5)); // Outputs 120
	
	var makeFib = function(givenFib) {
		return function(n) {
			if( n<=2 ) return 1;
			else return givenFib(n-1) + givenFib(n-2);
		}
	};
	var fibbonaci=y(makeFib);
	alert(fibbonaci(5)); // Outputs 5

Or, if you want to get rid of all declarations completely:

	(function(y) {
		alert(y(
			function(givenFact) {
				return function(n) {
					if( n < 2 ) return 1;
					else return n * givenFact(n-1);
				}
			}
		)(5)); // Outputs 120 
		
		alert(y(
			function(givenFib) {
				return function(n) {
					if( n<=2 ) return 1;
					else return givenFib(n-1) + givenFib(n-2);
				}
			}
		)(5)); // Outputs 5
		
	})(
		function(le) {
			return (function(f) { 
				return f(f); 
			})(function(f) {
				return le(
					function(x) { return (f(f))(x); }
				);
			});
		}
	);

Not a var in sight.

It's inefficient and it's ugly, but it's clever, it proves something interesting about functional languages, and toy problems like this should help in recognizing when anonymous functions are genuinely useful for real problems and using them appropriately.


Since PHP 5.3 PHP has had anonymous functions, allowing the sort of function passing that makes things like the Y combinator possible.
However PHP can't do "($f($f))($x)", it has to do "$g=$f($f); $g($x);". This makes a callonself function necessary and prevents a true Y combinator implementation. Something that does the equivalent thing is given below, for those who know better PHP than JavaScript.

function callonself($f) {
	return $f($f);
};
function y($le) {
	return callonself(function($f) use($le) {
		return $le(function($x) use ($f) {
			$g=callonself($f);
			return $g($x);
		});
	});
}

$makeFact=function($givenFact) {
	return function($n) use($givenFact) {
		return $n <= 2 ? $n : $n*$givenFact($n-1);
	};
};
$fact=y($makeFact);

print $fact(5)."
"; // Outputs 120 $makeFib=function($givenFib) { return function($n) use($givenFib) { return $n <= 2 ? 1 : $givenFib($n-1) + $givenFib($n-2); }; }; $fibbonaci=y($makeFib); print $fibbonaci(5); // Outputs 5