Lambda Calculus via C# (23) Y Combinator, And Divide

998 words

5 minutes

Lambda Calculus via C# (23) Y Combinator, And Divide

2018-11-23

.NET

/

.NET Core

/

.NET Standard

/

C#

/

LINQ

[LINQ via C# series]#

[Lambda Calculus via C# series]#

Latest version: https://weblogs.asp.net/dixin/lambda-calculus-via-csharp-7-fixed-point-combinator-and-recursion#

Fix point#

p is the fixed point of function F if and only if:

1
p
2
≡ F p

The following picture is stolen from Wikipedia:

A simple example:

F := 0 - x

has a fixed point 0:

The above fixed point definition also leads to:

1
p
2
≡ F p
3
≡ F (F p)
4
≡ ...
5
≡ F (F (F … (F p) …))

Fixed point combinator#

In lambda calculus and combinatory logic, Y combinator is a fixed point combinator:

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

It is called so because it calculates a function F’s fixed point Y F.

According to the above definition of fixed point p ≡ F p, there is:

1
(Y F)
2
≡ F (Y F)

Proof:

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

Y combinator was discovered by Haskell Curry.

As a fixed point combinator, Y also has the same property of:

1
Y F
2
≡ F (Y F)
3
≡ F (F (Y F))
4
≡ ...
5
≡ F (F (F … (F (Y F)) …))

So Y can be used to implement recursion.

And this is Y in SKI:

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

or just in SK:

1
Y3 := S S K (S (K (S S (S (S S K)))) K)

And in C#:

1
public delegate Func<T, TResult> Recursion<T, TResult>(Recursion<T, TResult> f);
2

3
public static class YCombinator
4
{
5
    // Y = λf.(λx.f(x x)) (λx.f(x x))
6
    // Y = f => (λx.f(x x)) (λx.f(x x))
7
    // Y = f => (x => f(x(x)))(x => f(x(x)))
8
    // Y = (x => arg => f(x(x))(arg))(x => arg => f(x(x))(arg))
9
    public static Func<T, TResult> Y<T, TResult>
10
        (Func<Func<T, TResult>, Func<T, TResult>> f) =>
11
            new Recursion<T, TResult>(x => arg => f(x(x))(arg))(x => arg => f(x(x))(arg));
12
}

Recursion#

As explaned in the part of Church numeral arithmetic, recursion cannot be implemented directly in lambda calculus.

Example - factorial#

The factorial function can be intuitively implemented by recursion. In C#:

1
Func<uint, uint> factorial = null; // Must have. So that factorial can recursively refer itself.
2
factorial = x => x == 0U ? 1U : factorial(x - 1U);

But in lambda calculus:

1
λn.If (IsZero n) (λx.1) (λx.Self (Decrease n))

An anonymous function cannot directly refer itself by its name in the body.

With Y, the solution is to create a helper to pass “the algorithm itself” as a parameter. So:

1
FactorialHelper := λf.λn.If (IsZero n) (λx.1) (λx.f (Decrease n))

Now Y can be applied with the helper:

1
Y FactorialHelper n

So:

1
Factorial := Y FactorialHelper
2
           ≡ Y (λf.λn.If (IsZero n) (λx.1) (λx.f (Decrease n)))

In C# lambda calculus:

1
public static partial class _NumeralExtensions
2
{
3
    // Factorial = factorial => numeral => If(numeral.IsZero())(_ => One)(_ => factorial(numeral.Decrease()));
4
    public static Func<_Numeral, _Numeral> Factorial
5
        (Func<_Numeral, _Numeral> factorial) => numeral =>
6
            ChurchBoolean.If<_Numeral>(numeral.IsZero())
7
                (_ => One)
8
                (_ => factorial(numeral.Decrease()));
9

10
    public static _Numeral Factorial
11
        (this _Numeral numeral) => YCombinator.Y<_Numeral, _Numeral>(Factorial)(numeral);
12
}

Example - Fibonacci#

Another recursion example is Fibonacci:

1
Func<uint, uint> fibonacci = null; // Must have. So that fibonacci can recursively refer itself.
2
fibonacci = x => x > 1U ? fibonacci(x - 1U) + fibonacci(x - 2U) : x;

The recursion cannot be done in anonymous function either:

1
λn.If (IsGreater n 1) (λx.Add (Self (Subtract n 1)) (Self (Subtract n 2))) (λx.n)

The same solution can be used - create a helper to pass “the algorithm itself” as a parameter:

1
FibonacciHelper := λf.λn.If (IsGreater n 1) (λx.Add (f (Subtract n 1)) (f (Subtract n 2))) (λx.n)

Application to Y will be the same way too:

1
Y FibonacciHelper n

So:

1
Fibonacci := Y FibonacciHelper
2
           ≡ Y (λf.λn.If (IsGreater n 1) (λx.Add (f (Subtract n 1)) (f (Subtract n 2))) (λx.n))

C#:

1
public static partial class _NumeralExtensions
2
{
3
    // Fibonacci  = fibonacci  => numeral => If(numeral > One)(_ => fibonacci(numeral - One) + fibonacci(numeral - One - One))(_ => numeral);
4
    public static Func<_Numeral, _Numeral> Fibonacci
5
        (Func<_Numeral, _Numeral> fibonacci) => numeral =>
6
            ChurchBoolean.If<_Numeral>(numeral > One)
7
                (_ => fibonacci(numeral - One) + fibonacci(numeral - One - One))
8
                (_ => numeral);
9

10
    public static _Numeral Fibonacci
11
        (this _Numeral numeral) => YCombinator.Y<_Numeral, _Numeral>(Fibonacci)(numeral);
12
}

DivideBy#

In the Church numeral arithmetic, this (cheating) recursive _DivideBy was temporarily used:

1
_DivideBy := λa.λb.If (IsGreaterOrEqual a b) (λx.Add One (_DivideBy (Subtract a b) b)) (λx.Zero)

Finally, with Y, a real DivideBy in lambda calculus can be defined:

1
DivideByHelper := λf.λa.λb.If (IsGreaterOrEqual a b) (λx.Add One (f (Subtract a b) b)) (λx.Zero)
2

3
DivideBy := Y DivideByHelper
4
          ≡ Y (λf.λa.λb.If (IsGreaterOrEqual a b) (λx.Add One (f (Subtract a b) b)) (λx.Zero))

Once again, just create a helper to pass itself as a parameter to implement recursion, as easy as Factorial and Fibonacci.

C#:

1
public static partial class _NumeralExtensions
2
{
3
    // DivideBy = divideBy => dividend => divisor => If(dividend >= divisor)(_ => One + divideBy(dividend - divisor)(divisor))(_ => Zero)
4
    public static Func<_Numeral, Func<_Numeral, _Numeral>> DivideBy
5
        (Func<_Numeral, Func<_Numeral, _Numeral>> divideBy) => dividend => divisor =>
6
            ChurchBoolean.If<_Numeral>(dividend >= divisor)
7
                (_ => One + divideBy(dividend - divisor)(divisor))
8
                (_ => Zero);
9

10
    public static _Numeral DivideBy
11
        (this _Numeral dividend, _Numeral divisor) =>
12
            YCombinator.Y<_Numeral, Func<_Numeral, _Numeral>>(DivideBy)(dividend)(divisor);
13
}

Notice a difference here: Factorial and Fibonacci both takes 1 parameter, but DivideBy takes 2 parameters - dividend, divisor. However, with currying, Y<T, TResult> can just be closed type Y<X, Func<Y, Z>>, so that this difference is nicely and easily handled.

Unit tests#

1
[TestClass()]
2
public class _NumeralExtensionsTests
3
{
4
    [TestMethod()]
5
    public void FactorialTest()
6
    {
7
        Func<uint, uint> factorial = null; // Must have. So that factorial can recursively refer itself.
8
        factorial = x => x == 0U ? 1U : factorial(x - 1U);
9

10
        Assert.IsTrue(factorial(0U) == 0U._Church().Factorial());
11
        Assert.IsTrue(factorial(1U) == 1U._Church().Factorial());
12
        Assert.IsTrue(factorial(2U) == 2U._Church().Factorial());
13
        Assert.IsTrue(factorial(3U) == 3U._Church().Factorial());
14
        Assert.IsTrue(factorial(10U) == 10U._Church().Factorial());
15
    }
16

17
    [TestMethod()]
18
    public void FibonacciTest()
19
    {
20
        Func<uint, uint> fibonacci = null; // Must have. So that fibonacci can recursively refer itself.
21
        fibonacci = x => x > 1U ? fibonacci(x - 1U) + fibonacci(x - 2U) : x;
22

23
        Assert.IsTrue(fibonacci(0U) == 0U._Church().Fibonacci());
24
        Assert.IsTrue(fibonacci(1U) == 1U._Church().Fibonacci());
25
        Assert.IsTrue(fibonacci(2U) == 2U._Church().Fibonacci());
26
        Assert.IsTrue(fibonacci(3U) == 3U._Church().Fibonacci());
27
        Assert.IsTrue(fibonacci(10U) == 10U._Church().Fibonacci());
28
    }
29

30
    [TestMethod()]
31
    public void DivideByTest()
32
    {
33
        Assert.IsTrue(1U / 1U == (1U._Church().DivideBy(1U._Church())));
34
        Assert.IsTrue(1U / 2U == (1U._Church().DivideBy(2U._Church())));
35
        Assert.IsTrue(2U / 2U == (2U._Church().DivideBy(2U._Church())));
36
        Assert.IsTrue(2U / 1U == (2U._Church().DivideBy(1U._Church())));
37
        Assert.IsTrue(10U / 3U == (10U._Church().DivideBy(3U._Church())));
38
        Assert.IsTrue(3U / 10U == (3U._Church().DivideBy(10U._Church())));
39
    }
40
}