Lambda Calculus via C# (10) Church Numeral Arithmetic Operators

1
public partial class _Numeral
2
{
3
    public static _Numeral operator +
4
        (_Numeral a, _Numeral b) => a.Add(b);
5

6
    public static _Numeral operator -
7
        (_Numeral a, _Numeral b) => a.Subtract(b);
8

9
    public static _Numeral operator *
10
        (_Numeral a, _Numeral b) => a.Multiply(b);
11

12
    public static _Numeral operator ^
13
        (_Numeral a, _Numeral b) => a.Pow(b);
14

15
    public static _Numeral operator ++
16
        (_Numeral numeral) => numeral.Increase();
17

18
    public static _Numeral operator --
19
        (_Numeral numeral) => numeral.Decrease();
20
}

This cannot be done to delegate type Numeral. In C#, custom operators cannot be defined for delegates/functions/lambda expressions.

Now Church numerals and arithmetic operations are all implemented in C#. Now it’s time for testing.

Conversion between Church numeral (now _Numeral) and System.UInt32#

Similar to Church Boolean <-> System.Boolean, some conversion helper methods can be created between _Numeral and System.UInt32:

1
public static partial class ChurchEncoding
2
{
3
    public static _Numeral _Church
4
        (this uint n) => n > 0 ? new _Numeral(_Church(n - 1)) : _Numeral.Zero;
5

6
    public static uint _Unchurch
7
        (this _Numeral numeral) => numeral.Numeral<uint>()(x => x + 1)(0);
8
}

Once again, these 2 methods are tagged with underscore because unit is C# specific.

In _Unchurch, a Church numeral (now a _Numeral) n is converted to natural number by “applying add 1” n times on 0.

Similarly to _Unchurch, _Numeral can be converted to string too:

1
public static partial class ChurchEncoding
2
{
3
    public static string _Visualize(this _Numeral numeral)
4
    {
5
        return numeral.Numeral<string>()(x => string.Concat(x, "#"))(string.Empty);
6
    }
7
}

0 will be converted to empty string, 1 will be “#”, 2 will be “##”, etc.

Compare _Numeral and System.UInt32#

Similar to above operators, == and != can be defined between Church numeral and System.UInt32:

1
public partial class _Numeral
2
{
3
    public static bool operator ==
4
        (_Numeral a, uint b) => a._Unchurch() == b;
5

6
    public static bool operator ==
7
        (uint a, _Numeral b) => a == b._Unchurch();
8

9
    public static bool operator !=
10
        (_Numeral a, uint b) => a._Unchurch() != b;
11

12
    public static bool operator !=
13
        (uint a, _Numeral b) => a != b._Unchurch();
14
}

bool and uint - these are totally C# specific, and will be only used for unit tests.

Unit tests#

The last function needed is a Pow function for uint, because .NET only has a Math.Pow function for double.

1
public static class UInt32Extensions
2
{
3
    public static uint Pow(this uint mantissa, uint exponent)
4
    {
5
        uint result = 1;
6
        for (int i = 0; i < exponent; i++)
7
        {
8
            result *= mantissa;
9
        }
10
        return result;
11
    }
12
}

The same way as Church Boolean tests, Church numeral and arithmetic operation can be unit tested by directly comparing results with System.UInt32’s arithmetic operation results:

1
[TestClass()]
2
public class _NumeralExtensionsTests
3
{
4
    [TestMethod()]
5
    public void IncreaseTest()
6
    {
7
        _Numeral numeral = 0U._Church();
8
        Assert.IsTrue(0U + 1U == ++numeral);
9
        Assert.IsTrue(1U + 1U == ++numeral);
10
        Assert.IsTrue(2U + 1U == ++numeral);
11
        Assert.IsTrue(3U + 1U == ++numeral);
12
        numeral = 123U._Church();
13
        Assert.IsTrue(123U + 1U == ++numeral);
14
    }
15

16
    [TestMethod()]
17
    public void AddTest()
18
    {
19
        Assert.IsTrue(0U + 0U == 0U._Church() + 0U._Church());
20
        Assert.IsTrue(0U + 1U == 0U._Church() + 1U._Church());
21
        Assert.IsTrue(10U + 0U == 10U._Church() + 0U._Church());
22
        Assert.IsTrue(0U + 10U == 0U._Church() + 10U._Church());
23
        Assert.IsTrue(1U + 1U == 1U._Church() + 1U._Church());
24
        Assert.IsTrue(10U + 1U == 10U._Church() + 1U._Church());
25
        Assert.IsTrue(1U + 10U == 1U._Church() + 10U._Church());
26
        Assert.IsTrue(3U + 5U == 3U._Church() + 5U._Church());
27
        Assert.IsTrue(123U + 345U == 123U._Church() + 345U._Church());
28
    }
29

30
    [TestMethod()]
31
    public void DecreaseTest()
32
    {
33
        _Numeral numeral = 3U._Church();
34
        Assert.IsTrue(3U - 1U == --numeral);
35
        Assert.IsTrue(2U - 1U == --numeral);
36
        Assert.IsTrue(1U - 1U == --numeral);
37
        Assert.IsTrue(0U == --numeral);
38
        numeral = 123U._Church();
39
        Assert.IsTrue(123U - 1U == --numeral);
40
    }
41

42
    [TestMethod()]
43
    public void SubtractTest()
44
    {
45
        Assert.IsTrue(0U - 0U == 0U._Church() - 0U._Church());
46
        Assert.IsTrue(0U == 0U._Church() - 1U._Church());
47
        Assert.IsTrue(10U - 0U == 10U._Church() - 0U._Church());
48
        Assert.IsTrue(0U == 0U._Church() - 10U._Church());
49
        Assert.IsTrue(1U - 1U == 1U._Church() - 1U._Church());
50
        Assert.IsTrue(10U - 1U == 10U._Church() - 1U._Church());
51
        Assert.IsTrue(0U == 1U._Church() - 10U._Church());
52
        Assert.IsTrue(0U == 3U._Church() - 5U._Church());
53
        Assert.IsTrue(0U == 123U._Church() - 345U._Church());
54
    }
55

56
    [TestMethod()]
57
    public void MultiplyTest()
58
    {
59
        Assert.IsTrue(0U * 0U == 0U._Church() * 0U._Church());
60
        Assert.IsTrue(0U * 1U == 0U._Church() * 1U._Church());
61
        Assert.IsTrue(10U * 0U == 10U._Church() * 0U._Church());
62
        Assert.IsTrue(0U * 10U == 0U._Church() * 10U._Church());
63
        Assert.IsTrue(1U * 1U == 1U._Church() * 1U._Church());
64
        Assert.IsTrue(10U * 1U == 10U._Church() * 1U._Church());
65
        Assert.IsTrue(1U * 10U == 1U._Church() * 10U._Church());
66
        Assert.IsTrue(3U * 5U == 3U._Church() * 5U._Church());
67
        Assert.IsTrue(12U * 23U == 12U._Church() * 23U._Church());
68
    }
69

70
    [TestMethod()]
71
    public void PowTest()
72
    {
73
        Assert.IsTrue(0U.Pow(1U) == (0U._Church() ^ 1U._Church()));
74
        Assert.IsTrue(10U.Pow(0U) == (10U._Church() ^ 0U._Church()));
75
        Assert.IsTrue(0U.Pow(10U) == (0U._Church() ^ 10U._Church()));
76
        Assert.IsTrue(1U.Pow(1U) == (1U._Church() ^ 1U._Church()));
77
        Assert.IsTrue(10U.Pow(1U) == (10U._Church() ^ 1U._Church()));
78
        Assert.IsTrue(1U.Pow(10U) == (1U._Church() ^ 10U._Church()));
79
        Assert.IsTrue(3U.Pow(5U) == (3U._Church() ^ 5U._Church()));
80
        Assert.IsTrue(5U.Pow(3U) == (5U._Church() ^ 3U._Church()));
81
    }
82
}