Lambda Calculus via C# (14) Church Pair (2-Tuple) and Church Numeral Decrease

466 words

2 minutes

Lambda Calculus via C# (14) Church Pair (2-Tuple) and Church Numeral Decrease

2018-11-14

.NET

/

.NET Core

/

.NET Standard

/

C#

/

LINQ

[LINQ via C# series]#

[Lambda Calculus via C# series]#

Latest version: https://weblogs.asp.net/dixin/lambda-calculus-via-csharp-4-tuple-and-signed-numeral#

In the Church numeral arithmetic part, the Decrease was defined as:

1
Decrease := λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)

This is complex. Now with Church pair (called tuple here to align to C# terms), Decrease can be defined in a easier way.

Shift a Church Pair (2-Tuple)#

First, a function is needed to shift a tuple:

1
Shift = λf.λt.CreateTuple (Item2 t) (f (Item1 t))

It takes a tuple (x, y) and a function f, then returns a new tuple (y, f y).

C# implementation is:

1
// (x, y) -> (y, f(y))
2
// Shift = tuple => f => Create(tuple.Item2())(f(tuple.Item1()))
3
public static Tuple<T, T> Shift<T>
4
    (this Tuple<T, T> tuple, Func<T, T> f) => Create<T, T>(tuple.Item2())(f(tuple.Item2()));

Again, the implementation is uncurried extension method for convenience of application, and readability.

Decrease a Church numeral#

Remember a Church numeral n can be considered to do “Increase” n times from 0:

1
n Increase Zero
2
≡ n

What if doing “Shift” n times base on (0, 0)?

1
3 (Shift Increase) (0, 0)
2
≡ (Shift Increase) ∘ (Shift Increase) ∘ (Shift Increase) (0, 0)
3
≡ (Shift Increase) ∘ (Shift Increase) (0, Increase 0)
4
≡ (Shift Increase) ∘ (Shift Increase) (0, 1)
5
≡ (Shift Increase) ∘ (1, Increase 1)
6
≡ (Shift Increase) ∘ (1, 2)
7
≡ (2, Increase 2)
8
≡ (2, 3)

And generally:

1
n (Shift Increase (0, 0))
2
≡ (n - 1, n)

This turns out a way to get the predecessor of n. So:

1
Decrease2 := λn.Item1 (n (Shift Increase) (CreateTuple 0 0))

And C#:

1
public static partial class _NumeralExtensions
2
{
3
    // Decrease2 = n => n(tuple => tuple.Shift(Increase))(ChurchTuple.Create(Zero)(Zero)).Item1();
4
    public static _Numeral Decrease2
5
        (this _Numeral numeral) =>
6
            numeral.Numeral<Tuple<_Numeral, _Numeral>>()
7
                (tuple => tuple.Shift(Increase)) // (x, y) -> (y, y + 1)
8
                (ChurchTuple.Create<_Numeral, _Numeral>(Zero)(Zero))
9
            .Item1();
10
}

Unit tests#

The following unit tests also shows how to apply the uncurried methods Swap, Shift, _Create:

1
[TestClass()]
2
public class ChurchTupleTests
3
{
4
    [TestMethod()]
5
    public void CreateItem1Item2Test()
6
    {
7
        Tuple<int, string> tuple1 = ChurchTuple.Create<int, string>(1)("a");
8
        Assert.AreEqual(1, tuple1.Item1());
9
        Assert.AreEqual("a", tuple1.Item2());
10
        Tuple<string, int> tuple2 = ChurchTuple.Create<string, int>("a")(1);
11
        Assert.AreEqual("a", tuple2.Item1());
12
        Assert.AreEqual(1, tuple2.Item2());
13
        object @object = new object();
14
        Tuple<object, int> tuple3 = ChurchTuple.Create<object, int>(@object)(1);
15
        Assert.AreEqual(@object, tuple3.Item1());
16
        Assert.AreEqual(1, tuple3.Item2());
17
    }
18

19
    [TestMethod()]
20
    public void ShiftTest()
21
    {
22
        Tuple<int, int> tuple1 = ChurchTuple.Create<int, int>(1)(2).Shift(_ => _);
23
        Assert.AreEqual(2, tuple1.Item1());
24
        Assert.AreEqual(2, tuple1.Item2());
25
        Tuple<int, int> tuple2 = ChurchTuple.Create<int, int>(2)(3).Shift(value => value * 2);
26
        Assert.AreEqual(3, tuple2.Item1());
27
        Assert.AreEqual(6, tuple2.Item2());
28
        Tuple<string, string> tuple3 = ChurchTuple.Create<string, string>("a")("b").Shift(value => value + "c");
29
        Assert.AreEqual("b", tuple3.Item1());
30
        Assert.AreEqual("bc", tuple3.Item2());
31
    }
32

33
    [TestMethod()]
34
    public void SwapTest()
35
    {
36
        Tuple<int, string> tuple1 = ChurchTuple.Create<string, int>("a")(1).Swap();
37
        Assert.AreEqual(1, tuple1.Item1());
38
        Assert.AreEqual("a", tuple1.Item2());
39
        Tuple<string, int> tuple2 = ChurchTuple.Create<int, string>(1)("a").Swap();
40
        Assert.AreEqual("a", tuple2.Item1());
41
        Assert.AreEqual(1, tuple2.Item2());
42
        object @object = new object();
43
        Tuple<object, int> tuple3 = ChurchTuple.Create<int, object>(1)(@object).Swap();
44
        Assert.AreEqual(@object, tuple3.Item1());
45
        Assert.AreEqual(1, tuple3.Item2());
46
    }
47

48
    [TestMethod()]
49
    public void _CreateTest()
50
    {
51
        Tuple<int, string> tuple1 = ChurchTuple._Create(1, "a");
52
        Assert.AreEqual(1, tuple1.Item1());
53
        Assert.AreEqual("a", tuple1.Item2());
54
        Tuple<string, int> tuple2 = ChurchTuple._Create("a", 1);
55
        Assert.AreEqual("a", tuple2.Item1());
56
        Assert.AreEqual(1, tuple2.Item2());
57
        object @object = new object();
58
        Tuple<object, int> tuple3 = ChurchTuple._Create(@object, 1);
59
        Assert.AreEqual(@object, tuple3.Item1());
60
        Assert.AreEqual(1, tuple3.Item2());
61
    }
62
}