Lambda Calculus via C# (18) Encoding Signed Number

[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 lambda calculus, a signed number (integer) can be represented by a Church pair (2-tuple) of Church numerals (natural numbers):

the first Church number represents the positive part
the second Church number represents the negative part

1
Signed := Tuple

So a signed number (npositive, negative) ≡ Subtract npositive nnegative.

Create Signed number from Church numeral#

Church numeral represents natural number and is always greater than or equal to 0. So Converting Church numeral to signed number is easy:

1
ToSigned := λn.CreateTuple n 0

It just need to append a negative part 0.

To create a negative signed number, just swap the Church numeral and 0:

1
Negate := Swap

And it is straightforward to get the positive part or negative part from a signed number:

1
Positive := Item1
2
Negative := Item2

C#:

1
// SignedNumeral is the alias of Tuple<_Numeral, _Numeral>
2
public delegate object SignedNumeral(Boolean<_Numeral, _Numeral> f);
3

4
public static partial class ChurchSignedNumeral
5
{
6
    public static _Numeral Zero { get; } = _Numeral.Zero;
7

8
    // Sign = numeral => ChurchTuple.Create(numeral, Zero)
9
    public static SignedNumeral Sign
10
        (this _Numeral numeral) => new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral>(numeral)(Zero));
11

12
    // Negate = signed => signed.Swap()
13
    public static SignedNumeral Negate
14
        (this SignedNumeral signed) => new SignedNumeral(new Tuple<_Numeral, _Numeral>(signed).Swap());
15

16
    // Positive = signed => signed.Item1()
17
    public static _Numeral Positive
18
        (this SignedNumeral signed) => new Tuple<_Numeral, _Numeral>(signed).Item1();
19

20
    // Negative = signed => signed.Item2()
21
    public static _Numeral Negative
22
        (this SignedNumeral signed) => new Tuple<_Numeral, _Numeral>(signed).Item2();
23
}

Format with 0#

In this way, one signed number can have many representations. For example:

1
1  ≡ (1, 0) ≡ (2, 1) ≡ (3, 2) ≡ (4, 3) ≡ …
2
-1  ≡ (0, 1) ≡ (1, 2) ≡ (2, 3) ≡ (3, 4) ≡ …

So for convenience a format function can be create to consistently represent a signed number in (positive, 0) or (0, negative):

1
FormatWithZero = λs.If (IsEqual sp  sn) (λx.ToSigned 0) (λx.If (IsGreater sp sn) (λy.ToSigned (Subtract sp sn)) (λy.Negate (ToSigned (Subtract sn sp))))

where

1
sp ≡ Positive s
2
sn ≡ Negative s

C#:

1
// FormatWithZero = signed => If(positive == negative)(_ => Zero.Sign())(_ => If(positive > negative)(__ => (positive - negative).Sign())(__ => (negative - positive).Sign().Negate()))
2
public static SignedNumeral FormatWithZero(this SignedNumeral signed)
3
{
4
    // Just to make the code shorter.
5
    _Numeral positive = signed.Positive();
6
    _Numeral negative = signed.Negative();
7

8
    return ChurchBoolean.If<SignedNumeral>(positive == negative)
9
        (_ => Zero.Sign())
10
        (_ => ChurchBoolean.If<SignedNumeral>(positive > negative)
11
            (__ => (positive - negative).Sign())
12
            (__ => (negative - positive).Sign().Negate()));
13
}

Arithmetic#

Naturally, for signed numbers a, b:

1
a + b
2
≡ (ap, an) + (bp, bn)
3
≡ (ap - an) + (bp - bn)
4
≡ (ap + bp, an + bn)
5

6
  a - b
7
≡ (ap, an) - (bp, bn)
8
≡ (ap - an) - (bp - bn)
9
≡ (ap + bn, an + bp)
10

11
  a * b
12
≡ (ap, an) * (bp, bn)
13
≡ (ap - an) * (bp - bn)
14
≡ (ap * bp + an * bn, ap * bn + an * bp)
15

16
  a / b
17
≡ (ap, an) / (bp, bn)
18
≡ (ap - an) / (bp - bn)
19
≡ (ap / bp + an / bn, ap / bn + an / bp)

So in lambda calculus:

1
AddSigned := λa.λb.FormatWithZero (CreateTuple (Add ap bp) (Add an bn))
2

3
SubtractSigned := λa.λb.FormatWithZero (CreateTuple (Add ap bn) (Add an bp))
4

5
MultiplySigned := λa.λb.FormatWithZero (CreateTuple (Add (Multiply ap bp) (Multiply an bn)) (Add (Multiply ap bn) (Multiply an bp)))
6

7
DivideBySigned := λa.λb.FormatWithZero (CreateTuple (Add (DivideByIgnoreZero ap bp) + (DivideByIgnoreZero an bn)) (Add (DivideByIgnoreZero ap bn) (DivideByIgnoreZero an bp))))

In DivideBySigned,

1
DivideByIgnoreZero = λa.λb.If (IsZero b) (λx.0) (λx._DivideBy a b)

When a Church numeral a is divided by Church numeral 0, just returns 0.

C#:

1
// Add = a => b => ChurchTuple.Create(a.Positive() + b.Positive())(a.Negative() + b.Negative()).FormatWithZero()
2
public static SignedNumeral Add
3
    (this SignedNumeral a, SignedNumeral b) =>
4
        new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral>
5
            (a.Positive() + b.Positive())
6
            (a.Negative() + b.Negative()))
7
        .FormatWithZero();
8

9
// Subtract = a => b => ChurchTuple.Create(a.Positive() + b.Negative())(a.Negative() + b.Positive()).FormatWithZero()
10
public static SignedNumeral Subtract
11
    (this SignedNumeral a, SignedNumeral b) =>
12
        new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral>
13
            (a.Positive() + b.Negative())
14
            (a.Negative() + b.Positive()))
15
        .FormatWithZero();
16

17
// Multiply = a => b => ChurchTuple.Create(a.Positive() * b.Positive() + a.Negative() + b.Negative())(a.Positive() * b.Negative() + a.Negative() * b.Positive()).FormatWithZero()
18
public static SignedNumeral Multiply
19
    (this SignedNumeral a, SignedNumeral b) =>
20
        new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral>
21
            (a.Positive() * b.Positive() + a.Negative() * b.Negative())
22
            (a.Positive() * b.Negative() + a.Negative() * b.Positive()))
23
        .FormatWithZero();
24

25
// DivideBy = dividend => divisor => ChurchTuple.Create((dividend.Positive() | divisor.Positive()) + (dividend.Negative() | divisor.Negative()))((dividend.Positive() | divisor.Negative()) + (dividend.Negative() | divisor.Positive()))).FormatWithZero();
26
public static SignedNumeral DivideBy
27
    (this SignedNumeral dividend, SignedNumeral divisor) =>
28
        new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral>
29
            ((dividend.Positive() | divisor.Positive()) + (dividend.Negative() | divisor.Negative()))
30
            ((dividend.Positive() | divisor.Negative()) + (dividend.Negative() | divisor.Positive())))
31
        .FormatWithZero();

In DivideBy, operator | is DivideByIgnoreZero, since it looks like /:

1
public static partial class _NumeralExtensions
2
{
3
    // DivideByIgnoreZero = dividend => divisor => If(divisor.IsZero())(_ => Zero)(_ => dividend._DivideBy(divisor))
4
    public static _Numeral DivideByIgnoreZero
5
        (this _Numeral dividend, _Numeral divisor) =>
6
            ChurchBoolean.If<_Numeral>(divisor.IsZero())
7
                (_ => Zero)
8
                (_ => dividend._DivideBy(divisor));
9
}
10

11
public partial class _Numeral
12
{
13
    public static _Numeral operator |
14
        (_Numeral dividend, _Numeral divisor) => dividend.DivideByIgnoreZero(divisor);
15
}

Unit tests#

1
[TestClass()]
2
public class ChurchSignedNumeralTests
3
{
4
    [TestMethod()]
5
    public void SignNegatePositiveNegativeTest()
6
    {
7
        SignedNumeral signed = 0U._Church().Sign();
8
        Assert.IsTrue(0U == signed.Positive());
9
        Assert.IsTrue(0U == signed.Negative());
10
        signed = signed.Negate();
11
        Assert.IsTrue(0U == signed.Positive());
12
        Assert.IsTrue(0U == signed.Negative());
13

14
        signed = 1U._Church().Sign();
15
        Assert.IsTrue(1U == signed.Positive());
16
        Assert.IsTrue(0U == signed.Negative());
17
        signed = signed.Negate();
18
        Assert.IsTrue(0U == signed.Positive());
19
        Assert.IsTrue(1U == signed.Negative());
20

21
        signed = 2U._Church().Sign();
22
        Assert.IsTrue(2U == signed.Positive());
23
        Assert.IsTrue(0U == signed.Negative());
24
        signed = signed.Negate();
25
        Assert.IsTrue(0U == signed.Positive());
26
        Assert.IsTrue(2U == signed.Negative());
27

28
        signed = 123U._Church().Sign();
29
        Assert.IsTrue(123U == signed.Positive());
30
        Assert.IsTrue(0U == signed.Negative());
31
        signed = signed.Negate();
32
        Assert.IsTrue(0U == signed.Positive());
33
        Assert.IsTrue(123U == signed.Negative());
34

35
        signed = new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral>(12U._Church())(23U._Church()));
36
        Assert.IsTrue(12U == signed.Positive());
37
        Assert.IsTrue(23U == signed.Negative());
38
        signed = signed.Negate();
39
        Assert.IsTrue(23U == signed.Positive());
40
        Assert.IsTrue(12U == signed.Negative());
41
    }
42

43
    [TestMethod()]
44
    public void FormatWithZeroTest()
45
    {
46
        SignedNumeral signed = new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral>(12U._Church())(23U._Church()));
47
        signed = signed.FormatWithZero();
48
        Assert.IsTrue(0U == signed.Positive());
49
        Assert.IsTrue(11U == signed.Negative());
50

51
        signed = new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral>(23U._Church())(12U._Church()));
52
        signed = signed.FormatWithZero();
53
        Assert.IsTrue(11U == signed.Positive());
54
        Assert.IsTrue(0U == signed.Negative());
55
    }
56

57
    [TestMethod()]
58
    public void AddTest()
59
    {
60
        SignedNumeral a = 0U._Church().Sign();
61
        SignedNumeral b = 0U._Church().Sign();
62
        SignedNumeral result = a.Add(b);
63
        Assert.IsTrue(0U == result.Positive());
64
        Assert.IsTrue(0U == result.Negative());
65

66
        a = 1U._Church().Sign();
67
        b = 1U._Church().Sign().Negate();
68
        result = a.Add(b);
69
        Assert.IsTrue(0U == result.Positive());
70
        Assert.IsTrue(0U == result.Negative());
71

72
        a = 3U._Church().Sign();
73
        b = 5U._Church().Sign().Negate();
74
        result = a.Add(b);
75
        Assert.IsTrue(0U == result.Positive());
76
        Assert.IsTrue(2U == result.Negative());
77
    }
78

79
    [TestMethod()]
80
    public void SubtractTest()
81
    {
82
        SignedNumeral a = 0U._Church().Sign();
83
        SignedNumeral b = 0U._Church().Sign();
84
        SignedNumeral result = a.Subtract(b);
85
        Assert.IsTrue(0U == result.Positive());
86
        Assert.IsTrue(0U == result.Negative());
87

88
        a = 1U._Church().Sign();
89
        b = 1U._Church().Sign().Negate();
90
        result = a.Subtract(b);
91
        Assert.IsTrue(2U == result.Positive());
92
        Assert.IsTrue(0U == result.Negative());
93

94
        a = 3U._Church().Sign();
95
        b = 5U._Church().Sign().Negate();
96
        result = a.Subtract(b);
97
        Assert.IsTrue(8U == result.Positive());
98
        Assert.IsTrue(0U == result.Negative());
99
    }
100

101
    [TestMethod()]
102
    public void MultiplyTest()
103
    {
104
        SignedNumeral a = 0U._Church().Sign();
105
        SignedNumeral b = 0U._Church().Sign();
106
        SignedNumeral result = a.Multiply(b);
107
        Assert.IsTrue(0U == result.Positive());
108
        Assert.IsTrue(0U == result.Negative());
109

110
        a = 1U._Church().Sign();
111
        b = 1U._Church().Sign().Negate();
112
        result = a.Multiply(b);
113
        Assert.IsTrue(0U == result.Positive());
114
        Assert.IsTrue(1U == result.Negative());
115

116
        a = 3U._Church().Sign();
117
        b = 5U._Church().Sign().Negate();
118
        result = a.Multiply(b);
119
        Assert.IsTrue(0U == result.Positive());
120
        Assert.IsTrue(15U == result.Negative());
121
    }
122

123
    [TestMethod()]
124
    public void DivideByTest()
125
    {
126
        SignedNumeral a = 0U._Church().Sign();
127
        SignedNumeral b = 0U._Church().Sign();
128
        SignedNumeral result = a.DivideBy(b);
129
        Assert.IsTrue(0U == result.Positive());
130
        Assert.IsTrue(0U == result.Negative());
131

132
        a = 1U._Church().Sign();
133
        b = 1U._Church().Sign().Negate();
134
        result = a.DivideBy(b);
135
        Assert.IsTrue(0U == result.Positive());
136
        Assert.IsTrue(1U == result.Negative());
137

138
        a = 11U._Church().Sign();
139
        b = 5U._Church().Sign().Negate();
140
        result = a.DivideBy(b);
141
        Assert.IsTrue(0U == result.Positive());
142
        Assert.IsTrue(2U == result.Negative());
143
    }
144
}

An alternative way to encode signed number#

More intuitively, signed number can also be encoded by a Church pair of a Church Boolean and a Church numeral: (sign, absolute-value). For example, +1 will be (True, 1), -2 will be (False, 2), etc.

So:

1
Signed2 := Tuple
2
Sign := Item1
3
Absolute := Item2

Its arithmetic, for example, multiply, also becomes intuitively:

1
MultiplySigned2 = λa.λb.CreateTuple (Xor (Sign a) (Sign b)) (Multiply (Absolute a) (Absolute b))