One of the most profound ideas in lambda calculus, is the Y-operator.
I’ve learned the Y-operator at least three times, and every time, I found
it extremely hard to understand. This blog is therefore an example of a
quixotic undertaking: I want to see whether it is possible for me to
explain the Y-operator so that you, gentle reader, can understand it
with minimal background. In this case, “minimal background” means
at least a few years of college level mathematics.
Background: Why Y?
The Y-operator is part of lambda calculus, a field of logic that
appeals to people who just couldn’t get enough of solving equations in
high-school mathematics. Lambda calculus is named after the “lambda”
operator, which stands for an “anonymous function”. It can be used to
syntactically (that is, mechanically) transform expressions. A short
example: “(lambda (x) (* x x))” is a method that takes one
argument (called x) and returns the square of the argument.
Here is how you use it:
((lambda (x) (* x x)) 8) ;; apply the abovementioned function to 8 => (* 8 8) ;; MECHANICALLY substiture 8 for x => 64 ;; Whee!
The Y-operator is used to create recursive functions
using lambdas. That is, functions that call themselves. That is
its purpose. Y is defined as follows:
(Y F) = (F (Y F))
For this to work, F better be a function. Read it as follows:
“Y of a function F equals F applied to Y of F”.
An example: Factorial
As I said: This allows us to define recursive stuff using just
lambdas. To demonstrate, I will need a volunteer recursive function.
You over there: Factorial! could you step over here, please?
The factorial function is defined thus: The factorial of a number
n is the product of all natural numbers up to n. A way of
writing this in a fairly conventional syntax is:
fact(n) = (n == 1) ? 1 : (n * fact(n - 1)). Now, lets
do it without function definitions. Lets say we want to
find the factorial of 8. In lambda calculus we can write:
((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) 8)
Holy lambda, Batman! That didn’t help much, did it? Well: here’s
the good thing: You don’t have to understand it. Using
what we learned about lambda, we can just blindly calculate it.
Lets see how it works.
Doing the math
Calculating the factorial for 8 will be a really long
exercise, so let’s settle for 2 instead. Here we go:
((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) 2)
Substitute the definition of (Y F) = (F (Y F)):
(((lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x)))))) (Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x)))))))) 2)
Whoa, those parenteses are dizzying. Well, we can substitute for the
f in the first lambda:
((lambda (x) (if (= x 1) 1 (* x ((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) (-1 x))))) 2)
Keep substituting for the outer lambda at all times. This time x = 2 (only for the outer lambda)
(if (= 2 1) 1 (* 2 ((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) (-1 2))))
We now know the answer to the if (and I’ll expand (-1 2) => 1 as well):
(* 2 ((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) 1))
We need to do another of those crazy Y expansions. It is not hard, just exchange the f
(I’ll skip one step this time):
(* 2 ((lambda (x) (if (= x 1) 1 (* x ((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) (-1 x))))) 1))
Substitute the 1 for x in the outermost lambda:
(* 2 (if (= 1 1) 1 (* 1 ((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) (-1 x)))))
If we had started with a larger number, we would’ve gotten a string of
(* 4 (* 3 (* 2.... built up from these transformations. But we’re
almost done: The if is true this time, so we can substitute:
(* 2 1)
The whole Y and lambda mess just evaporated. w00t! And the answer is
of course 2 which is correct.
What the magic (Y F) = (F (Y F)) does is to let us embed a
function within itself an inifinitely number of times. So, for factorial:
(Y fact) = (fact (fact (fact (fact (fact (Y fact))))))
In this case fact is defined as (pay attention now): A function that
takes a function as an argument and returns another function. The returned
function takes a natural number as an argument, and if the number is one, it
returns it, otherwise: it calls the function that was given as argument to the
first function. Y keeps injecting fact into itself, so it can always go
deeper in the recursive call. But as soon as the number reaches 1, we don’t
have to go any further, and the “final” (Y fact) collapses into
Y generates as many function applications as we need, so it will let us
create recursiveness, without naming a single function. (Y F) is then
the value of F when F is applied to itself an infinitely number of times.
This is called the fixed point for the function F.
Conclusion: Why Y?
The Y operator lets us use purely syntactic (mechanical) steps
to evaluate recursive functions. It gives the mathematical construct of
lambda calculus as much computing power as a programming language, without
needing to define names for functions. It is a mathematical marvel.
Can it be used for anything? I don’t really think so. But just as
Y expands a lambda expression, it can expand your mind. I hope that
you feel a little smarter going away from this blog than entering it.
You can read more about the Y-operator at wikipedia.
And if you want to go for the whole nine yards, check out the Structure and Interpretation of Computer Programs online video
lectures! 20 hours of Lisp!
Did you manage to read through the whole article? Did you understand it?
Let me know what you think: Write a comment, or send me an