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

[LINQ via C# series]

[Lambda Calculus via C# series]

Latest version:

Fix point

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

≡ F p

The following picture is stolen from Wikipedia:

A simple example:

F := 0 - x

has a fixed point 0:

≡ F 0

The above fixed point definition also leads to:

≡ 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)


  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));


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


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 =>
                (_ => 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


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


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);


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.


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

public class _NumeralExtensionsTests
    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());

    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());

    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())));



  • To activate McAfee antivirus, you need to first setup the device for internet connection. Next, go to the activation page on mcafee com activate. Ensure that you are entering your email address and password correctly. After logging in, you will be redirected to a new page where you need to enter the information about your product key and activation code. Then you can enter your billing information and accept terms of service by selecting "I Agree". And finally click on "Activate Now" button for completing the process of activating McAfee antivirus protection on your computer or mobile device.

Add a Comment

As it will appear on the website

Not displayed

Your website