 # 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())));
}
}```