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

# [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:

```
p
≡ F p
```

The following picture is stolen from Wikipedia:

A simple example:

F := 0 - x

has a fixed point 0:

```
0
≡ F 0
```

The above fixed point definition also leads to:

```
p
≡ F p
≡ F (F p)
≡ ...
≡ F (F (F … (F p) …))
```

# Fixed point combinator

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

`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:

```
(Y F)
≡ F (Y F)
```

Proof:

```
Y F
≡ (λf.(λx.f (x x)) (λx.f (x x))) F
≡ (λx.F (x x)) (λx.F (x x))
≡ F ((λx.F (x x)) (λx.F (x x)))
≡ F (Y F)
```

Y combinator was discovered by Haskell Curry.

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

```
Y F
≡ F (Y F)
≡ F (F (Y F))
≡ ...
≡ F (F (F … (F (Y F)) …))
```

So Y can be used to implement recursion.

And this is Y in SKI:

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

or just in SK:

`Y3 := S S K (S (K (S S (S (S S K)))) K)`

And in C#:

public delegate Func<T, TResult> Recursion<T, TResult>(Recursion<T, TResult> f); public static class YCombinator { // Y = λf.(λx.f(x x)) (λx.f(x x)) // Y = f => (λx.f(x x)) (λx.f(x x)) // Y = f => (x => f(x(x)))(x => f(x(x))) // Y = (x => arg => f(x(x))(arg))(x => arg => f(x(x))(arg)) public static Func<T, TResult> Y<T, TResult> (Func<Func<T, TResult>, Func<T, TResult>> f) => new Recursion<T, TResult>(x => arg => f(x(x))(arg))(x => arg => f(x(x))(arg)); }

# 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#:

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

But in lambda calculus:

`λ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:

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

Now Y can be applied with the helper:

`Y FactorialHelper n`

So:

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

In C# lambda calculus:

public static partial class _NumeralExtensions { // Factorial = factorial => numeral => If(numeral.IsZero())(_ => One)(_ => factorial(numeral.Decrease())); public static Func<_Numeral, _Numeral> Factorial (Func<_Numeral, _Numeral> factorial) => numeral => ChurchBoolean.If<_Numeral>(numeral.IsZero()) (_ => One) (_ => factorial(numeral.Decrease())); public static _Numeral Factorial (this _Numeral numeral) => YCombinator.Y<_Numeral, _Numeral>(Factorial)(numeral); }

## Example - Fibonacci

Another recursion example is Fibonacci:

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

The recursion cannot be done in anonymous function either:

`λ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:

`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:

`Y FibonacciHelper n`

So:

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

C#:

public static partial class _NumeralExtensions { // Fibonacci = fibonacci => numeral => If(numeral > One)(_ => fibonacci(numeral - One) + fibonacci(numeral - One - One))(_ => numeral); public static Func<_Numeral, _Numeral> Fibonacci (Func<_Numeral, _Numeral> fibonacci) => numeral => ChurchBoolean.If<_Numeral>(numeral > One) (_ => fibonacci(numeral - One) + fibonacci(numeral - One - One)) (_ => numeral); public static _Numeral Fibonacci (this _Numeral numeral) => YCombinator.Y<_Numeral, _Numeral>(Fibonacci)(numeral); }

# DivideBy

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

`_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:

```
DivideByHelper := λf.λa.λb.If (IsGreaterOrEqual a b) (λx.Add One (f (Subtract a b) b)) (λx.Zero)
DivideBy := Y DivideByHelper
≡ 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#:

public static partial class _NumeralExtensions { // DivideBy = divideBy => dividend => divisor => If(dividend >= divisor)(_ => One + divideBy(dividend - divisor)(divisor))(_ => Zero) public static Func<_Numeral, Func<_Numeral, _Numeral>> DivideBy (Func<_Numeral, Func<_Numeral, _Numeral>> divideBy) => dividend => divisor => ChurchBoolean.If<_Numeral>(dividend >= divisor) (_ => One + divideBy(dividend - divisor)(divisor)) (_ => Zero); public static _Numeral DivideBy (this _Numeral dividend, _Numeral divisor) => YCombinator.Y<_Numeral, Func<_Numeral, _Numeral>>(DivideBy)(dividend)(divisor); }

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

[TestClass()] public class _NumeralExtensionsTests { [TestMethod()] public void FactorialTest() { Func<uint, uint> factorial = null; // Must have. So that factorial can recursively refer itself. factorial = x => x == 0U ? 1U : factorial(x - 1U); Assert.IsTrue(factorial(0U) == 0U._Church().Factorial()); Assert.IsTrue(factorial(1U) == 1U._Church().Factorial()); Assert.IsTrue(factorial(2U) == 2U._Church().Factorial()); Assert.IsTrue(factorial(3U) == 3U._Church().Factorial()); Assert.IsTrue(factorial(10U) == 10U._Church().Factorial()); } [TestMethod()] public void FibonacciTest() { Func<uint, uint> fibonacci = null; // Must have. So that fibonacci can recursively refer itself. fibonacci = x => x > 1U ? fibonacci(x - 1U) + fibonacci(x - 2U) : x; Assert.IsTrue(fibonacci(0U) == 0U._Church().Fibonacci()); Assert.IsTrue(fibonacci(1U) == 1U._Church().Fibonacci()); Assert.IsTrue(fibonacci(2U) == 2U._Church().Fibonacci()); Assert.IsTrue(fibonacci(3U) == 3U._Church().Fibonacci()); Assert.IsTrue(fibonacci(10U) == 10U._Church().Fibonacci()); } [TestMethod()] public void DivideByTest() { Assert.IsTrue(1U / 1U == (1U._Church().DivideBy(1U._Church()))); Assert.IsTrue(1U / 2U == (1U._Church().DivideBy(2U._Church()))); Assert.IsTrue(2U / 2U == (2U._Church().DivideBy(2U._Church()))); Assert.IsTrue(2U / 1U == (2U._Church().DivideBy(1U._Church()))); Assert.IsTrue(10U / 3U == (10U._Church().DivideBy(3U._Church()))); Assert.IsTrue(3U / 10U == (3U._Church().DivideBy(10U._Church()))); } }