People call Y the "applicative-order fixed-point operator for functionals." Let's take a closer look at what this means in the factorial example.
Suppose M is the true mathematical factorial function, possibly in Plato's heaven. Let F denote the function:
F = (lambda (h) (lambda (n) (if (< n 2) 1 (* n (h (- n 1))))))
Then:
((F M) n) = (M n).
That is, M is a fixed point of F: F maps (in some sense) M onto M. Y satisfies the property:
((F (Y F)) X) = ((Y F) X)
This property of Y is very important. Another important property is that the least defined fixed point for functionals is unique; therefore, (Y F) and M are in some sense the same.
Applicative-order Y is not the same as classical Y, which is a combinator. Some texts refer to Y as Z.
To derive Y, I will start with a recursive function example, factorial. In the derivation I will use three techniques:
- The first one passes an additional argument to avoid using any self-reference primitives from Scheme.
- The second technique converts multiple-parameter functions to nested single-parameter functions to separate manipulations of the self-reference and ordinary parameters.
- The third technique introduces functions through abstraction.
All code examples will use the variables n and m to refer to integers, the variable x to refer to an unknown but undistinguished argument, and the variables f, g, h, q, and r to refer to functions.
The basic form of the factorial function is:
(lambda (n) (if (< n 2) 1 (* n (h (- n1)))))
The h variable should refer to the function we wish to invoke when a recursive call is made, which is the factorial function itself. Since we have no way to make h refer directly to the correct function, let's pass it in as an argument:
(lambda (h n) (if (< n 2) 1 (* n (h h (- n 1)))))
In the recursive call to h, the first argument will also be h because we want to pass on the correct function to use in the recursive situation for later invocations of the function.
Therefore, to compute 10! we would write:
(let ((g (lambda (h n) (if (< n 2) 1 (* n (h h (- n 1))))))) (g g 10) )
During the evaluation of the body of g, h's value is the same as the value of g established by let; that is, during execution of g, h refers to the executing function. When the function call (h h (- n 1)) happens, the same value is passed along as an argument to h; h passes itself to itself.
We want to split the management of the function's self-reference fr om the management of other arguments. In this particular case, we want to separate the management of h from that of n. A technique called "currying" is the standard way to handle this separation. Before we curry this example, let's look at another example of currying. Here is a program that also computes 10!, but in a slightly more clever way:
(letrec ((f (lambda (n m) (if (< n 2) m (f (- n 1) (* m n)))))) (f 10 1))
The trick is to use an accumulator, m, to compute the result. Let's curry the definition of f:
(letrec ((f (lambda (n) (lambda (m) (if (< n 2) m ((f (- n 1)) (* m n ))))))) ((f 10) 1))
The idea of currying is that every function has one argument. Passing multiple arguments is accomplished with nested function application: the first application returns a function that takes the second argument and completes the computation of the value. In the previous piece of code, the recursive call:
((f (- n 1)) (* m n))
has two steps: the proper function to apply is computed and applied to the right argument.
We can use this idea to curry the other factorial program:
(let ((g (lambda (h) (lambda (n) (if (< n 2) 1 (* n ((h h) (- n 1)))) ))) ((g g) 10))
In this piece of code, the recursive call also computes and applies the proper function. But that proper function is computed by applying a function to itself.
Applying a function to itself is the process by which we get the basic functionality of a self-reference. The self-application (g g) in the last line of the program calls g with g itself as an argument. This returns a closure in which the variable h is bound to the outside g. This closure takes a number and does the basic factorial comput ation. If the computation needs to perform a recursive call, it invokes the closed-over h with the closed-over has an argument, but all the hs are bound to the function g as defined by the let.
To summarize this technique, suppose we have a self-referential function using letrec as in the following code skeleton:
(letrec ((f (lambda (x) ... f ...))) ... f ...)
This skeleton can be turned into a self-referential function that uses let where r is a fresh identifier:
(let ((f (lambda (r) (lambda (x) ... (r r) ...)))) ... (f f)
