1

Y = λf.(λx.f (x x)) (λx.f (x x))

From here.

Note:

1. “(x x)”[the latter one] means “apply ‘x’ to ‘x’”, we can use “A1” to represent the result;

2. “(λx.f (x x))”[the latter one] means “apply ‘A1’ to ‘λx.f’”, we can use “B1” to represent the result;

3. “(x x)”[the former one] means “apply ‘x’ to ‘x’”, we can use “A2” to represent the result;

4. “(λx.f (x x))”[the former one] means “apply ‘A2’ to ‘λx.f’”, we can use “B2” to represent the result;

5. “λf.(λx.f (x x)) (λx.f (x x))” means apply “B1” to “λf.B2”.

From here(1), here(2) and here(3) and here(4).

Here is the JavaScript version.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

function y(le) {
    return (function (f) {
        return f(f);
    }(function (v) {
        return le(function (x) {    // function_1
            return v(v)(x);
        });
    }));
}

function F(factorial) {
    return function (n) {    // function_2
        return n <= 2
            ? n
            : n * factorial(n - 1);
    };
}

var factorial = y(F);

var number120 = factorial(5);

Notes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1. "return function (f) { return f(f); }" creates a function which invokes the
 input parameter, a function, by passing the function itself as the input, and
 the function is returned as the result of "y(le)". This function defines the
 recursion.

2. The "(function (v) {/* not include the inside content. */})" is the
 implementation of the function "f" defined in step 1. The "v" in this
 function is the argument "f" and the function "f" in step 1.

3. The "return le(function (x) { return v(v)(x); });" part means an enhanced
 version of "le(some_function)" function is returned. The implementation of
 the enhanced "le" function is: apply the recursion invocation defined in "f",
 by putting "v" as the parameter of "v" function to a "lower level". Note the
 returned value of "le(...)" is "function_2" returned by a implementation of
 "le", such as "F", while "function_2" in the implementation as "F" will
 invoke a lower level of "function_1" as it's the input parameter of "le",
 until the recursion is ended.

“y/function_1” is Yin, “F/function_2” is Yang. Imagine the “太极图(taijitu)“: the Yin head eats the Yang tail while the Yin tail is eaten by the Yang head.

Some more interesting points about Yin/Yang:

1. Yin is the source of everything, including Yang.

2. Yin is difficult to observe or understand, while Yang is not.

3. Yin can produce Yang and Yang can produce Yin, Yin can consume Yang and Yang can also consume Yin.

In functional programming, the Y combinator can be used to formally define recursive functions in a programming language that does not support recursion.

From here.

“无中生有”, which means creating something(or maybe everything) from nothing, that is “Y combinator“.