Lambda Calculus via C# (7) Fixed Point Combinator and Recursion

[FP & LINQ via C# series]#

[Lambda Calculus via C# series]#

p is the fixed point (aka invariant point) of function f if and only if:

1
p
2
≡ f p

Take function Math.Sqrt as example, it has 2 fix point, 0 and 1, so that 0 ≡ Math.Sqrt(0) and 1 ≡ Math.Sqrt(1).

The above fixed point definition also leads to infinite substitution:

1
p
2
≡ f p
3
≡ f (f p)
4
≡ f (f (f p))
5
≡ ...
6
≡ f (f (f ... (f p) ...))

Similarly, the fixed point combinator Y is defined as if Y f is the fixed point of f:

1
(Y f)
2
≡ f (Y f)

Normal order fixed point combinator (Y combinator) and recursion#

The following Y combinator is an implementation of fixed point combinator, discovered by Haskell Curry:

1
Y := λf.(λg.f (g g)) (λg.f (g g))

It is called the normal order fixed point combinator:

1
Y f
2
≡ (λf.(λg.f (g g)) (λg.f (g g))) f
3
≡ (λg.f (g g)) (λg.f (g g))
4
≡ f ((λg.f (g g)) (λg.f (g g)))
5
≡ f (Y f)

The following is Y implemented in SKI:

1
Y := S (K (S I I)) (S (S (K S) K) (K (S I I)))

And just in SK:

1
Y := S S K (S (K (S S (S (S S K)))) K)

When Y f can also be substituted infinitely:

1
(Y f)
2
≡ f (Y f)
3
≡ f (f (Y f))
4
≡ f (f (f (Y f)))
5
≡ ...
6
≡ f (f (f ... (f (Y f)) ...))

So Y can be used to implement recursion. As fore mentioned, in lambda calculus, a function cannot directly apply it self in its body. Take the factorial function as example, the factorial of n is defined recursively:

If n is greater than 0, then factorial of n is the multiplication of n and factorial of n – 1
if n is 0, then factorial of n is 1

So naturally:

1
Factorial := λn.If (n == 0) (λx.1) (λx.n * (Factorial (n - 1)))

However, in lambda calculus the above definition is illegal, because the self reference does not work anonymously:

1
λn.If (n == 0) (λx.1) (λx.n * (? (n - 1)))

Now with the power of Y combinator, the recursion can be implemented, but still in the anonymous way. First, in above definition, just pass the reference of itself as an variable/argument:

1
λf.λn.If (n == 0) (λx.1) (λx.n * (f (n - 1)))

If the above function is called FactorialHelper, then the Factorial function can be implemented as:

1
FactorialHelper := λf.λn.If (n == 0) (λx.1) (λx.n * (f (n - 1)))
2
Factorial := Y FactorialHelper

So the recursive Factorial is implemented anonymously:

1
Factorial
2
≡ Y FactorialHelper
3
≡ (λf.(λg.f (g g)) (λg.f (g g))) FactorialHelper
4
≡ (λf.(λg.f (g g)) (λg.f (g g))) (λf.λn.If (n == 0) (λx.1) (λx.n * (f (n - 1))))

When Factorial is applied, according to the definition of Factorial and Y:

1
Factorial 3
2
≡ Y FactorialHelper 3
3
≡ FactorialHelper (Y FactorialHelper) 3

Here (Y FactorialHelper) can be substituted by Factorial, according to the definition. So FactorialHelper is called with Factorial and n, exactly as expected.

The normal order Y combinator does not work with applicative order reduction. In applicative order, here FactorialHelper is applied with (Y FactorialHelper), so the right most argument Y FactorialHelper should be reduced first, which leads to infinite reduction:

1
FactorialHelper (Y FactorialHelper) 3
2
≡ FactorialHelper (FactorialHelper (Y FactorialHelper)) 3
3
≡ FactorialHelper (FactorialHelper (FactorialHelper (Y FactorialHelper))) 3
4
≡ ...

The normal order Y combinator only works with normal order. In normal order, here FactorialHelper is applied with (Y FactorialHelper), so the left most function FactorialHelper should be reduced first:

1
FactorialHelper (Y FactorialHelper) 3
2
≡ (λf.λn.If (n == 0) (λx.1) (λx.n * (f (n - 1)))) (Y FactorialHelper) 3
3
≡ (λn.If (n == 0) (λx.1) (λx.n * (Y FactorialHelper (n - 1)))) 3
4
≡ If (3 == 0) (λx.1) (λx.3 * (Y FactorialHelper (3 - 1)))
5
≡ If (False) (λx.1) (λx.3 * (Y FactorialHelper (3 - 1))
6
≡ 3 * (Y FactorialHelper (3 - 1))
7
≡ 3 * (FactorialHelper (Y FactorialHelper) (3 - 1))
8
≡ 3 * ((λf.λn.If (n == 0) (λx.1) (λx.n * (f (n - 1)))) (Y FactorialHelper) (3 - 1))
9
≡ 3 * ((λn.If (n == 0) (λx.1) (λx.n * (Y FactorialHelper (n - 1)))) (3 - 1))
10
≡ 3 * (If ((3 - 1) == 0) (λx.1) (λx.(3 - 1) * (Y FactorialHelper ((3 - 1) - 1))))
11
≡ 3 * ((3 - 1) * (Y FactorialHelper ((3 - 1) - 1)))
12
≡ 3 * (2 * (Y FactorialHelper ((3 - 1) - 1)))
13
≡ 3 * (2 * (FactorialHelper (Y FactorialHelper) ((3 - 1) - 1)))
14
≡ 3 * (2 * ((λf.λn.If (n == 0) (λx.1) (λx.n * (f (n - 1)))) (Y FactorialHelper) ((3 - 1) - 1)))
15
≡ 3 * (2 * ((λn.If (n == 0) (λx.1) (λx.n * (Y FactorialHelper (n - 1)))) ((3 - 1) - 1)))
16
≡ 3 * (2 * (If (((3 - 1) - 1) == 0) (λx.1) (λx.((3 - 1) - 1) * (Y FactorialHelper (((3 - 1) - 1) - 1)))))
17
≡ 3 * (2 * (((3 - 1) - 1) * (Y FactorialHelper (((3 - 1) - 1) - 1))))
18
≡ 3 * (2 * (1 * (Y FactorialHelper (((3 - 1) - 1) - 1))))
19
≡ 3 * (2 * (1 * (FactorialHelper (Y FactorialHelper) (((3 - 1) - 1) - 1))))
20
≡ 3 * (2 * (1 * ((f.λn.If (n == 0) (λx.1) (λx.n * (f (n - 1)))) (Y FactorialHelper) (((3 - 1) - 1) - 1))))
21
≡ 3 * (2 * (1 * ((n.If (n == 0) (λx.1) (λx.n * (Y FactorialHelper (n - 1)))) (((3 - 1) - 1) - 1))))
22
≡ 3 * (2 * (1 * (If ((((3 - 1) - 1) - 1) == 0) (λx.1) (λx.(((3 - 1) - 1) - 1) * (Y FactorialHelper ((((3 - 1) - 1) - 1) - 1))))))
23
≡ 3 * (2 * (1 * 1))

So the Y f infinite reduction is blocked in in normal order reduction. First, Y f is reduced to f (Y f), then the next reduction is to reduce leftmost expression f, not the the rightmost (Y f). In the above example Y FactorialHelper n:

If n is greater than 0, Y Factorial n is reduced to n * (Y Factorial (n - 1)), where Y Factorial can be further reduced, so the recursion continues.
If n is 0, Y Factorial n is reduced to 1. The reduction ends, so the recursion terminates.

Y combinator is easy to implement in C#. Generally, for a recursive function f of type T -> TResult, its helper function accepts the T -> TResult function and a T value, then return TResult, so its helper function is of type (T -> TResult) –> T -> TResult. Y can be viewed as accepting helper function and returns f. so Y is of type ((T -> TResult) –> T -> TResult) -> (T -> TResult). So:

1
public static partial class FixedPointCombinators<T, TResult>
2
{
3
    // Y = (g => f(g(g)))(g => f(g(g)))
4
    public static readonly Func<Func<Func<T, TResult>, Func<T, TResult>>, Func<T, TResult>>
5
        Y = f => new SelfApplicableFunc<Func<T, TResult>>(g => f(g(g)))(g => f(g(g)));
6
}

Here are the types of the elements in above lambda expression:

g: SelfApplicableFunc<T -> TResult>
g(g): T -> TResult
f: (T -> TResult) –> T -> TResult
f(g(g)): T => TResult
g => f(g(g)): SelfApplicableFunc<T -> TResult> –> T -> TResult, which is SelfApplicableFunc<T -> TResult> by definition
(g => f(g(g)))(g => f(g(g))): T -> TResult

For Factorial, apparently it is of function type Numeral -> Numeral, so FactorialHelper is of function type (Numeral -> Numeral) –> Numeral -> Numeral:

1
using static FixedPointCombinators<Numeral, Numeral>;
2

3
public static partial class ChurchNumeral
4
{
5
    // FactorialHelper = factorial => n => If(n == 0)(_ => 1)(_ => n * factorial(n - 1))
6
    public static readonly Func<Func<Numeral, Numeral>, Func<Numeral, Numeral>>
7
        FactorialHelper = factorial => n =>
8
            If(n.IsZero())
9
                (_ => One)
10
                (_ => n.Multiply(factorial(n.Subtract(One))));
11

12
    public static readonly Func<Numeral, Numeral>
13
        Factorial = Y(FactorialHelper);
14
}

Calling above Factorial always throws StackOverflowException, because in C# executes in applicative order. When Factorial is called, it calls normal order Y in applicative order, which causes infinite execution.

Applicative order fixed point combinator (Z combinator) and recursion#

The above Y combinator does not work in C#. When reducing Y f in applicative order, the self application in expression f (g g) leads to infinite reduction, which need to be blocked. The solution is to eta convert f (g g) to λx.f (g g) x. So the applicative order fixed point combinator is:

1
Z := λf.(λg.λx.f (g g) x) (λg.λx.f (g g) x)

It is called Z combinator. Now reduce Z f in applicative order:

1
Z f
2
≡ (λf.(λg.λx.f (g g) x) (λg.λx.f (g g) x)) f
3
≡ (λg.λx.f (g g) x) (λg.λx.f (g g) x)
4
≡ λx.f ((λg.λx.f (g g) x) (λg.λx.f (g g) x)) x
5
≡ λx.f (Z f) x

This time Z f is not reduced to f (Z f), but reduced to the eta expanded version λx.f (Z f) x, so any further reduction is blocked. Still take factorial as example:

1
Factorial 3
2
≡ Z FactorialHelper 3
3
≡ (λx.FactorialHelper (Z FactorialHelper) x) 3
4
≡ FactorialHelper (Z FactorialHelper) 3
5
≡ FactorialHelper (λx.FactorialHelper (Z FactorialHelper) x) 3
6
≡ (λf.λn.If (n == 0) (λx.1) (λx.n * (f (n - 1)))) (λx.FactorialHelper (Z FactorialHelper) x) 3
7
≡ (λn.If (n == 0) (λx.1) (λx.n * ((λx.FactorialHelper (Z FactorialHelper) x) (n - 1)))) 3
8
≡ If (3 == 0) (λx.1) (λx.3 * ((λx.FactorialHelper (Z FactorialHelper) x) (3 - 1)))
9
≡ If (False) (λx.1) (λx.3 * ((λx.FactorialHelper (Z FactorialHelper) x) (3 - 1)))
10
≡ 3 * ((λx.FactorialHelper (Z FactorialHelper) x) (3 - 1))
11
≡ 3 * ((λx.FactorialHelper (Z FactorialHelper) x) 2)
12
≡ 3 * (FactorialHelper (Z FactorialHelper) 2)
13
≡ 3 * (FactorialHelper (λx.FactorialHelper (Z FactorialHelper) x) 2)
14
≡ 3 * ((λf.λn.If (n == 0) (λx.1) (λx.n * (f (n - 1)))) (λx.FactorialHelper (Z FactorialHelper) x) 2)
15
≡ 3 * ((λn.If (n == 0) (λx.1) (λx.n * ((λx.FactorialHelper (Z FactorialHelper) x) (n - 1)))) 2)
16
≡ 3 * (If (2 == 0) (λx.1) (λx.2 * ((λx.FactorialHelper (Z FactorialHelper) x) (2 - 1))))
17
≡ 3 * (If (False) (λx.1) (λx.2 * ((λx.FactorialHelper (Z FactorialHelper) x) (2 - 1))))
18
≡ 3 * (2 * ((λx.FactorialHelper (Z FactorialHelper) x) (2 - 1)))
19
≡ 3 * (2 * ((λx.FactorialHelper (Z FactorialHelper) x) 1))
20
≡ 3 * (2 * (FactorialHelper (Z FactorialHelper) 1))
21
≡ 3 * (2 * (FactorialHelper (λx.FactorialHelper (Z FactorialHelper) x) 1))
22
≡ 3 * (2 * ((λf.λn.If (n == 0) (λx.1) (λx.n * (f (n - 1)))) (λx.FactorialHelper (Z FactorialHelper) x) 1))
23
≡ 3 * (2 * ((λn.If (n == 0) (λx.1) (λx.n * ((λx.FactorialHelper (Z FactorialHelper) x) (n - 1)))) 1))
24
≡ 3 * (2 * (If (1 == 0) (λx.1) (λx.1 * ((λx.FactorialHelper (Z FactorialHelper) x) (1 - 1)))))
25
≡ 3 * (2 * (If (False) (λx.1) (λx.1 * ((λx.FactorialHelper (Z FactorialHelper) x) (1 - 1)))))
26
≡ 3 * (2 * (1 * ((λx.FactorialHelper (Z FactorialHelper) x) (1 - 1))))
27
≡ 3 * (2 * (1 * ((λx.FactorialHelper (Z FactorialHelper) x) 0)))
28
≡ 3 * (2 * (1 * (FactorialHelper (Z FactorialHelper) 0)))
29
≡ 3 * (2 * (1 * (FactorialHelper (λx.FactorialHelper (Z FactorialHelper) x) 0)))
30
≡ 3 * (2 * (1 * ((λf.λn.If (n == 0) (λx.1) (λx.n * (f (n - 1)))) (λx.FactorialHelper (Z FactorialHelper) x) 0)))
31
≡ 3 * (2 * (1 * ((λn.If (n == 0) (λx.1) (λx.n * ((λx.FactorialHelper (Z FactorialHelper) x) (n - 1)))) 0)))
32
≡ 3 * (2 * (1 * (If (0 == 0) (λx.1) (λx.0 * ((λx.FactorialHelper (Z FactorialHelper) x) (n - 1))))))
33
≡ 3 * (2 * (1 * (If (True) (λx.1) (λx.0 * ((λx.FactorialHelper (Z FactorialHelper) x) (n - 1))))))
34
≡ 3 * (2 * (1 * 1))

In C#, Z combinator can be implemented in the same pattern. Just eta expand f(g(g)) to x => f(g(g))(x):

1
public static partial class FixedPointCombinators<T, TResult>
2
{
3
    // Z = (g => x => f(g(g))(x))(g => x => f(g(g))(x))
4
    public static readonly Func<Func<Func<T, TResult>, Func<T, TResult>>, Func<T, TResult>>
5
        Z = f => new SelfApplicableFunc<Func<T, TResult>>(g => x => f(g(g))(x))(g => x => f(g(g))(x));
6
}

The types of the elements in above lambda expression are the same as in Y combinator, and x is of type T.

Now Factorial can be defined with Z and above FactorialHelper:

1
using static ChurchBoolean;
2
using static FixedPointCombinators<Numeral, System.Func<Numeral, Numeral>>;
3

4
public static partial class ChurchNumeral
5
{
6
    // DivideByHelper = divideBy => dividend => divisor => If(dividend >= divisor)(_ => 1 + divideBy(dividend - divisor)(divisor))(_ => 0)
7
    private static readonly Func<Func<Numeral, Func<Numeral, Numeral>>, Func<Numeral, Func<Numeral, Numeral>>> DivideByHelper = divideBy => dividend => divisor =>
8
            If(dividend.IsGreaterThanOrEqualTo(divisor))
9
                (_ => One.Add(divideBy(dividend.Subtract(divisor))(divisor)))
10
                (_ => Zero);
11

12
    public static readonly Func<Numeral, Func<Numeral, Numeral>>
13
        DivideBy = Z(DivideByHelper);
14
}

Another recursion example is Fibonacci number. The nth Fibonacci number is defined recursively:

if n is greater than 1, then the nth Fibonacci number is the sum of the (n -1)th Fibonacci number and the (n -2)th Fibonacci number.
if n is 1 or 0, then the nth Fibonacci number is n

So naturally:

1
Fibonacci := λn.If (n > 1) (λx.(Fibonacci (n - 1)) + (Fibonacci (n - 2))) (λx.n)

Again, the above recursive definition is illegal in lambda calculus, because the self reference does not work anonymously:

1
λn.If (n > 1) (λx.(? (n - 1)) + (? (n - 2))) (λx.n)

Following the same helper function pattern as FactorialHelper, a FibonacciHelper can be defined to pass the Fibonacci function as a variable/argument, then Fibonacci can be defined with Z and FibonacciHelper:

1
FibonacciHelper := λf.λn.If (n > 1) (λx.(f (n - 1)) + (f (n - 2))) (λx.n)
2
Fibonacci := Z FibonacciHelper

Now Fibonacci is recursive but still can go anonymous, without any self reference:

1
Fibonacci
2
≡ Z FibonacciHelper
3
≡ (λf.(λg.λx.f (g g) x) (λg.λx.f (g g) x)) FibonacciHelper
4
≡ (λf.(λg.λx.f (g g) x) (λg.λx.f (g g) x)) (λf.λn.If (n > 1) (λx.(f (n - 1)) + (f (n - 2))) (λx.n))

In C#:

1
// FibonacciHelper  = fibonacci  => n => If(n > 1)(_ => fibonacci(n - 1) + fibonacci(n - 2))(_ => n)
2
private static readonly Func<Func<Numeral, Numeral>, Func<Numeral, Numeral>>
3
    FibonacciHelper = fibonacci => n =>
4
        If(n.IsGreaterThan(One))
5
            (_ => fibonacci(n.Subtract(One)).Add(fibonacci(n.Subtract(Two))))
6
            (_ => n);
7

8
// Fibonacci = Z(FibonacciHelper)
9
public static readonly Func<Numeral, Numeral>
10
    Fibonacci = Z(FibonacciHelper);

Previously, in the Church numeral arithmetic, the following illegal DivideBy with self reference was temporarily used:

1
DivideBy := λa.λb.If (a >= b) (λx.1 + (DivideBy (a - b) b)) (λx.0)

Finally, with Z, an legal DivideBy in lambda calculus can be defined, following the same helper function pattern:

1
DivideByHelper := λf.λa.λb.If (a >= b) (λx.1 + (f (a - b) b)) (λx.0)
2
DivideBy := Z DivideByHelper

The following is the formal version of DivideBy:

1
DivideBy
2
≡ Z DivideByHelper
3
≡ (λf.(λg.λx.f (g g) x) (λg.λx.f (g g) x)) DivideByHelper
4
≡ (λf.(λg.λx.f (g g) x) (λg.λx.f (g g) x)) (λf.λa.λb.If (a >= b) (λx.1 + (f (a - b) b)) (λx.0))

In C#:

1
// DivideByHelper = divideBy => dividend => divisor => If(dividend >= divisor)(_ => 1 + divideBy(dividend - divisor)(divisor))(_ => 0)
2
private static readonly Func<Func<Numeral, Func<Numeral, Numeral>>, Func<Numeral, Func<Numeral, Numeral>>>
3
    DivideByHelper = divideBy => dividend => divisor =>
4
        If(dividend.IsGreaterThanOrEqualTo(divisor))
5
            (_ => One.Add(divideBy(dividend.Subtract(divisor))(divisor)))
6
            (_ => Zero);
7

8
// DivideBy = Z(DivideByHelper)
9
public static readonly Func<Numeral, Func<Numeral, Numeral>>
10
    DivideBy = Z(DivideByHelper);

The following are a few examples

1
public static partial class NumeralExtensions
2
{
3
    public static Numeral Factorial(this Numeral n) => ChurchNumeral.Factorial(n);
4

5
    public static Numeral Fibonacci(this Numeral n) => ChurchNumeral.Fibonacci(n);
6

7
    public static Numeral DivideBy(this Numeral dividend, Numeral divisor) =>
8
        ChurchNumeral.DivideBy(dividend)(divisor);
9
}
10

11
[TestClass]
12
public partial class FixedPointCombinatorTests
13
{
14
    [TestMethod]
15
    public void FactorialTest()
16
    {
17
        Func<uint, uint> factorial = null; // Must have to be compiled.
18
        factorial = x => x == 0 ? 1U : x * factorial(x - 1U);
19

20
        Assert.AreEqual(factorial(0U), 0U.Church().Factorial().Unchurch());
21
        Assert.AreEqual(factorial(1U), 1U.Church().Factorial().Unchurch());
22
        Assert.AreEqual(factorial(2U), 2U.Church().Factorial().Unchurch());
23
        Assert.AreEqual(factorial(8U), 8U.Church().Factorial().Unchurch());
24
    }
25

26
    [TestMethod]
27
    public void FibonacciTest()
28
    {
29
        Func<uint, uint> fibonacci = null; // Must have. So that fibonacci can recursively refer itself.
30
        fibonacci = x => x > 1U ? fibonacci(x - 1) + fibonacci(x - 2) : x;
31

32
        Assert.AreEqual(fibonacci(0U), 0U.Church().Fibonacci().Unchurch());
33
        Assert.AreEqual(fibonacci(1U), 1U.Church().Fibonacci().Unchurch());
34
        Assert.AreEqual(fibonacci(2U), 2U.Church().Fibonacci().Unchurch());
35
        Assert.AreEqual(fibonacci(8U), 8U.Church().Fibonacci().Unchurch());
36
    }
37

38
    [TestMethod]
39
    public void DivideByTest()
40
    {
41
        Assert.AreEqual(1U / 1U, 1U.Church().DivideBy(1U.Church()).Unchurch());
42
        Assert.AreEqual(1U / 2U, 1U.Church().DivideBy(2U.Church()).Unchurch());
43
        Assert.AreEqual(2U / 2U, 2U.Church().DivideBy(2U.Church()).Unchurch());
44
        Assert.AreEqual(2U / 1U, 2U.Church().DivideBy(1U.Church()).Unchurch());
45
        Assert.AreEqual(8U / 3U, 8U.Church().DivideBy(3U.Church()).Unchurch());
46
        Assert.AreEqual(3U / 8U, 3U.Church().DivideBy(8U.Church()).Unchurch());
47
    }
48
}