Deriving the Y Combinator in C# - Just the code

Arialdo Martini — 11/08/2022 — C# Functional Programming Lambda Calculus

Index

Recursive Y Combinator

Step 1 - An ordinary recursive function

public class YCombinator
{
    private const int Max = 12_000;
    private readonly Arbitrary<int> PositiveNumbers = Arb.From(Gen.Choose(0, Max));
        
    private static readonly Func<int, int> sum =
        n =>
            n == 0 ? 0 : n + sum(n - 1);
    
    [Property]
    Property it_meets_the_gauss_formula() =>
        ForAll(PositiveNumbers, n =>
            sum(n) == n * (n + 1) / 2);
}

Type alias

private delegate int Sum(int n);

private static readonly Sum sum =
    n =>
        n == 0 ? 0 : n + sum(n - 1);

Step 2 - Inject a continuation

Define MkSum with Extract Method

delegate int Sum(int n);

static readonly Sum sum =
    MkSum();
    
static Sum MkSum() =>
    n =>
        n == 0 ? 0 : n + sum(n-1);

Let sum float up

delegate int Sum(int n);

static readonly Sum sum =
    MkSum(sum);
    
static Sum MkSum(Sum continuation) =>
    n =>
        n == 0 ? 0 : n + continuation(n-1);

Make sum lazy

delegate int Sum(int n);

static readonly Sum sum = 
    n =>
        MkSum(sum)(n);
    
static Sum MkSum(Sum continuation) =>
    n =>
        n == 0 ? 0 : n + continuation(n-1);

Reduce recursion

public class YCombinator
{
    private const int Max = 8_000;
    private readonly Arbitrary<int> PositiveNumbers = Arb.From(Gen.Choose(0, Max));
        
    [...]

Step 3 - Define Y with Extract Method

delegate int Sum(int n);
delegate Sum MkSum(Sum continuation);
    
static Sum MkSum(Sum continuation) =>
        n =>
            n == 0 ? 0 : n + continuation(n-1);

static Sum Y() =>
    MkSum(sum);

static readonly Sum sum =
    n =>
        Y()(n);

Inject MkSum as a parameter

delegate int Sum(int n);
delegate Sum MkSum(Sum continuation);
    
static Sum MkSum(Sum continuation) =>
    n =>
        n == 0 ? 0 : n + continuation(n-1);

static Sum Y(Func<Sum, Sum> f) =>
    f(sum);

static readonly Sum sum =
    n =>
        Y(MkSum)(n);

Move laziness from sum to Y

delegate int Sum(int n);
delegate Sum MkSum(Sum continuation);
    
static Sum MkSum(Sum continuation) =>
        n =>
            n == 0 ? 0 : n + continuation(n-1);

static Sum Y(Fun<Sum, Sum> f) =>
    n =>
        f(sum)(n);

static readonly Sum sum =
    Y(MkSum);

Replace sum with Y(MkSum)

delegate int Sum(int n);
        
static Sum MkSum(Sum continuation) =>
    n =>
        n == 0 ? 0 : n + continuation(n-1);

static Sum Y(MkSum f) =>
    n =>
        f(Y(f))(n);

static readonly Sum sum =
    Y(MkSum);

Convert Y to field

delegate int Sum(int n);

static Sum MkSum(Sum continuation) =>
    n =>
        n == 0 ? 0 : n + continuation(n-1);

static Func<Func<Sum, Sum>, Sum> Y = 
    f => 
        n => f(Y(f))(n);

static readonly Sum sum =
    Y(MkSum);

Step 1 - An ordinary recursive function

public class YCombinator
{
    private const int Max = 12_000;
    private readonly Arbitrary<int> PositiveNumbers = Arb.From(Gen.Choose(0, Max));
        
    private static readonly Func<int, int> sum =
        n =>
            n == 0 ? 0 : n + sum(n - 1);
    
    [Property]
    Property it_meets_the_gauss_formula() =>
        ForAll(PositiveNumbers, n =>
            sum(n) == n * (n + 1) / 2);
}

Type alias

private delegate int Sum(int n);

private static readonly Sum sum =
    n =>
        n == 0 ? 0 : n + sum(n - 1);

Step 2 - Inject a continuation

Define MkSum with Extract Method

delegate int Sum(int n);

static readonly Sum sum =
    MkSum();
    
static Sum MkSum() =>
    n =>
        n == 0 ? 0 : n + sum(n-1);

Let sum float up

delegate int Sum(int n);

static readonly Sum sum =
    MkSum(sum);
    
static Sum MkSum(Sum continuation) =>
    n =>
        n == 0 ? 0 : n + continuation(n-1);

Make sum lazy

private const int Max = 8_000;

private readonly Arbitrary<int> PositiveNumbers = Arb.From(Gen.Choose(0, Max));
    
delegate int Sum(int n);

static readonly Sum sum = 
    n =>
        MkSum(sum)(n);
    
static Sum MkSum(Sum continuation) =>
    n =>
        n == 0 ? 0 : n + continuation(n-1);

Step 3 - Define Y with Extract Method

delegate int Sum(int n);
delegate Sum MkSum(Sum continuation);
    
static Sum MkSum(Sum continuation) =>
        n =>
            n == 0 ? 0 : n + continuation(n-1);

static Sum Y() =>
    MkSum(sum);

static readonly Sum sum =
    n =>
        Y()(n);

Inject MkSum as a parameter

delegate int Sum(int n);
delegate Sum MkSum(Sum continuation);
    
static Sum MkSum(Sum continuation) =>
    n =>
        n == 0 ? 0 : n + continuation(n-1);

static Sum Y(Func<Sum, Sum> f) =>
    f(sum);

static readonly Sum sum =
    n =>
        Y(MkSum)(n);

Move laziness from sum to Y

delegate int Sum(int n);
delegate Sum MkSum(Sum continuation);
    
static Sum MkSum(Sum continuation) =>
        n =>
            n == 0 ? 0 : n + continuation(n-1);

static Sum Y(Fun<Sum, Sum> f) =>
    n =>
        f(sum)(n);

static readonly Sum sum =
    Y(MkSum);

Replace sum with Y(MkSum)

delegate int Sum(int n);
        
static Sum MkSum(Sum continuation) =>
    n =>
        n == 0 ? 0 : n + continuation(n-1);

static Sum Y(MkSum f) =>
    n =>
        f(Y(f))(n);

static readonly Sum sum =
    Y(MkSum);

Non-recursive Y Combinator

Step 1 - Extract Y to a local function

Make n => f(Y(mkSum))(n) a variable

private static Sum Y(Func<Sum, Sum> f)
{
    Sum sum1 = n => f(Y(f))(n);
    return sum1;
}

Extract a local function

private static Sum Y(Func<Sum, Sum> f)
{
    Sum sub() =>
        n => f(Y(f))(n);

    Sum sum1 = sub();
    return sum1;
}

Get rid of the temporary variable

private static readonly Sum sum =
    Y(mkSum);

private static Sum Y(Func<Sum, Sum> f)
{
    Sum sub() =>
        n => f(Y(f))(n);

    return sub();
}

Step 2 - Replace Y(f) with sub()

private static Sum Y(Func<Sum, Sum> f)
{
    Sum sub() =>
        n => f(sub())(n);

    return sub();
}

Step 3 - Inject self

private delegate Sum Rec(Rec self);

private static Sum Y(Func<Sum, Sum> f)
{
    Sum sub(Rec self) =>
        n => f(sub(self))(n);

    return sub(sub);
}

Replace sub with self

private delegate Sum Rec(Rec self);

private static Sum Y(Func<Sum, Sum> f)
{
    Sum sub(Rec self) =>
        n => f(self(self))(n);

    return sub(sub);
}

Step 4 - Replace variable with lambda

Replace sub(sub) with lambda

private static Sum Y(Func<Sum, Sum> f)
{
    Sum sub(Rec self) =>
        n => f(self(self))(n);

    return Func<Rec, Sum>(f => f(f))(sub);
}

Step 5 - Inline sub

private static Sum Y(Func<Sum, Sum> f) =>
    new Func<Rec, Sum>(f =>
        f(f))
    (self =>
        n =>
            f(self(self))(n));