# 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

`Signed := Tuple`

So a signed number (n_{positive}, n_{egative}) ≡ Subtract n_{positive} n_{negative}.

# 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:

`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:

`Negate := Swap`

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

```
Positive := Item1
Negative := Item2
```

C#:

// SignedNumeral is the alias of Tuple<_Numeral, _Numeral> public delegate object SignedNumeral(Boolean<_Numeral, _Numeral> f); public static partial class ChurchSignedNumeral { public static _Numeral Zero { get; } = _Numeral.Zero; // Sign = numeral => ChurchTuple.Create(numeral, Zero) public static SignedNumeral Sign (this _Numeral numeral) => new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral>(numeral)(Zero)); // Negate = signed => signed.Swap() public static SignedNumeral Negate (this SignedNumeral signed) => new SignedNumeral(new Tuple<_Numeral, _Numeral>(signed).Swap()); // Positive = signed => signed.Item1() public static _Numeral Positive (this SignedNumeral signed) => new Tuple<_Numeral, _Numeral>(signed).Item1(); // Negative = signed => signed.Item2() public static _Numeral Negative (this SignedNumeral signed) => new Tuple<_Numeral, _Numeral>(signed).Item2(); }

# Format with 0

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

```
1 ≡ (1, 0) ≡ (2, 1) ≡ (3, 2) ≡ (4, 3) ≡ …
-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):

`FormatWithZero = λs.If (IsEqual s`_{p} s_{n}) (λx.ToSigned 0) (λx.If (IsGreater s_{p} s_{n}) (λy.ToSigned (Subtract s_{p} s_{n})) (λy.Negate (ToSigned (Subtract s_{n} s_{p}))))

where

`s`_{p} ≡ Positive s
s_{n} ≡ Negative s

C#:

// FormatWithZero = signed => If(positive == negative)(_ => Zero.Sign())(_ => If(positive > negative)(__ => (positive - negative).Sign())(__ => (negative - positive).Sign().Negate())) public static SignedNumeral FormatWithZero(this SignedNumeral signed) { // Just to make the code shorter. _Numeral positive = signed.Positive(); _Numeral negative = signed.Negative(); return ChurchBoolean.If<SignedNumeral>(positive == negative) (_ => Zero.Sign()) (_ => ChurchBoolean.If<SignedNumeral>(positive > negative) (__ => (positive - negative).Sign()) (__ => (negative - positive).Sign().Negate())); }

# Arithmetic

Naturally, for signed numbers a, b:

```
a + b
≡ (a
```_{p}, a_{n}) + (b_{p}, b_{n})
≡ (a_{p} - a_{n}) + (b_{p} - b_{n})
≡ (a_{p} + b_{p}, a_{n} + b_{n})
a - b
≡ (a_{p}, a_{n}) - (b_{p}, b_{n})
≡ (a_{p} - a_{n}) - (b_{p} - b_{n})
≡ (a_{p} + b_{n}, a_{n} + b_{p})
a * b
≡ (a_{p}, a_{n}) * (b_{p}, b_{n})
≡ (a_{p} - a_{n}) * (b_{p} - b_{n})
≡ (a_{p} * b_{p} + a_{n} * b_{n}, a_{p} * b_{n} + a_{n} * b_{p})
a / b
≡ (a_{p}, a_{n}) / (b_{p}, b_{n})
≡ (a_{p} - a_{n}) / (b_{p} - b_{n})
≡ (a_{p} / b_{p} + a_{n} / b_{n}, a_{p} / b_{n} + a_{n} / b_{p})

So in lambda calculus:

`AddSigned := λa.λb.FormatWithZero (CreateTuple (Add a`_{p} b_{p}) (Add a_{n} b_{n}))
SubtractSigned := λa.λb.FormatWithZero (CreateTuple (Add a_{p} b_{n}) (Add a_{n} b_{p}))
MultiplySigned := λa.λb.FormatWithZero (CreateTuple (Add (Multiply a_{p} b_{p}) (Multiply a_{n} b_{n})) (Add (Multiply a_{p} b_{n}) (Multiply a_{n} b_{p})))
DivideBySigned := λa.λb.FormatWithZero (CreateTuple (Add (DivideByIgnoreZero a_{p} b_{p}) + (DivideByIgnoreZero a_{n} b_{n})) (Add (DivideByIgnoreZero a_{p} b_{n}) (DivideByIgnoreZero a_{n} b_{p}))))

In DivideBySigned,

`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#:

// Add = a => b => ChurchTuple.Create(a.Positive() + b.Positive())(a.Negative() + b.Negative()).FormatWithZero() public static SignedNumeral Add (this SignedNumeral a, SignedNumeral b) => new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral> (a.Positive() + b.Positive()) (a.Negative() + b.Negative())) .FormatWithZero(); // Subtract = a => b => ChurchTuple.Create(a.Positive() + b.Negative())(a.Negative() + b.Positive()).FormatWithZero() public static SignedNumeral Subtract (this SignedNumeral a, SignedNumeral b) => new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral> (a.Positive() + b.Negative()) (a.Negative() + b.Positive())) .FormatWithZero(); // Multiply = a => b => ChurchTuple.Create(a.Positive() * b.Positive() + a.Negative() + b.Negative())(a.Positive() * b.Negative() + a.Negative() * b.Positive()).FormatWithZero() public static SignedNumeral Multiply (this SignedNumeral a, SignedNumeral b) => new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral> (a.Positive() * b.Positive() + a.Negative() * b.Negative()) (a.Positive() * b.Negative() + a.Negative() * b.Positive())) .FormatWithZero(); // DivideBy = dividend => divisor => ChurchTuple.Create((dividend.Positive() | divisor.Positive()) + (dividend.Negative() | divisor.Negative()))((dividend.Positive() | divisor.Negative()) + (dividend.Negative() | divisor.Positive()))).FormatWithZero(); public static SignedNumeral DivideBy (this SignedNumeral dividend, SignedNumeral divisor) => new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral> ((dividend.Positive() | divisor.Positive()) + (dividend.Negative() | divisor.Negative())) ((dividend.Positive() | divisor.Negative()) + (dividend.Negative() | divisor.Positive()))) .FormatWithZero();

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

public static partial class _NumeralExtensions { // DivideByIgnoreZero = dividend => divisor => If(divisor.IsZero())(_ => Zero)(_ => dividend._DivideBy(divisor)) public static _Numeral DivideByIgnoreZero (this _Numeral dividend, _Numeral divisor) => ChurchBoolean.If<_Numeral>(divisor.IsZero()) (_ => Zero) (_ => dividend._DivideBy(divisor)); } public partial class _Numeral { public static _Numeral operator | (_Numeral dividend, _Numeral divisor) => dividend.DivideByIgnoreZero(divisor); }

# Unit tests

[TestClass()] public class ChurchSignedNumeralTests { [TestMethod()] public void SignNegatePositiveNegativeTest() { SignedNumeral signed = 0U._Church().Sign(); Assert.IsTrue(0U == signed.Positive()); Assert.IsTrue(0U == signed.Negative()); signed = signed.Negate(); Assert.IsTrue(0U == signed.Positive()); Assert.IsTrue(0U == signed.Negative()); signed = 1U._Church().Sign(); Assert.IsTrue(1U == signed.Positive()); Assert.IsTrue(0U == signed.Negative()); signed = signed.Negate(); Assert.IsTrue(0U == signed.Positive()); Assert.IsTrue(1U == signed.Negative()); signed = 2U._Church().Sign(); Assert.IsTrue(2U == signed.Positive()); Assert.IsTrue(0U == signed.Negative()); signed = signed.Negate(); Assert.IsTrue(0U == signed.Positive()); Assert.IsTrue(2U == signed.Negative()); signed = 123U._Church().Sign(); Assert.IsTrue(123U == signed.Positive()); Assert.IsTrue(0U == signed.Negative()); signed = signed.Negate(); Assert.IsTrue(0U == signed.Positive()); Assert.IsTrue(123U == signed.Negative()); signed = new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral>(12U._Church())(23U._Church())); Assert.IsTrue(12U == signed.Positive()); Assert.IsTrue(23U == signed.Negative()); signed = signed.Negate(); Assert.IsTrue(23U == signed.Positive()); Assert.IsTrue(12U == signed.Negative()); } [TestMethod()] public void FormatWithZeroTest() { SignedNumeral signed = new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral>(12U._Church())(23U._Church())); signed = signed.FormatWithZero(); Assert.IsTrue(0U == signed.Positive()); Assert.IsTrue(11U == signed.Negative()); signed = new SignedNumeral(ChurchTuple.Create<_Numeral, _Numeral>(23U._Church())(12U._Church())); signed = signed.FormatWithZero(); Assert.IsTrue(11U == signed.Positive()); Assert.IsTrue(0U == signed.Negative()); } [TestMethod()] public void AddTest() { SignedNumeral a = 0U._Church().Sign(); SignedNumeral b = 0U._Church().Sign(); SignedNumeral result = a.Add(b); Assert.IsTrue(0U == result.Positive()); Assert.IsTrue(0U == result.Negative()); a = 1U._Church().Sign(); b = 1U._Church().Sign().Negate(); result = a.Add(b); Assert.IsTrue(0U == result.Positive()); Assert.IsTrue(0U == result.Negative()); a = 3U._Church().Sign(); b = 5U._Church().Sign().Negate(); result = a.Add(b); Assert.IsTrue(0U == result.Positive()); Assert.IsTrue(2U == result.Negative()); } [TestMethod()] public void SubtractTest() { SignedNumeral a = 0U._Church().Sign(); SignedNumeral b = 0U._Church().Sign(); SignedNumeral result = a.Subtract(b); Assert.IsTrue(0U == result.Positive()); Assert.IsTrue(0U == result.Negative()); a = 1U._Church().Sign(); b = 1U._Church().Sign().Negate(); result = a.Subtract(b); Assert.IsTrue(2U == result.Positive()); Assert.IsTrue(0U == result.Negative()); a = 3U._Church().Sign(); b = 5U._Church().Sign().Negate(); result = a.Subtract(b); Assert.IsTrue(8U == result.Positive()); Assert.IsTrue(0U == result.Negative()); } [TestMethod()] public void MultiplyTest() { SignedNumeral a = 0U._Church().Sign(); SignedNumeral b = 0U._Church().Sign(); SignedNumeral result = a.Multiply(b); Assert.IsTrue(0U == result.Positive()); Assert.IsTrue(0U == result.Negative()); a = 1U._Church().Sign(); b = 1U._Church().Sign().Negate(); result = a.Multiply(b); Assert.IsTrue(0U == result.Positive()); Assert.IsTrue(1U == result.Negative()); a = 3U._Church().Sign(); b = 5U._Church().Sign().Negate(); result = a.Multiply(b); Assert.IsTrue(0U == result.Positive()); Assert.IsTrue(15U == result.Negative()); } [TestMethod()] public void DivideByTest() { SignedNumeral a = 0U._Church().Sign(); SignedNumeral b = 0U._Church().Sign(); SignedNumeral result = a.DivideBy(b); Assert.IsTrue(0U == result.Positive()); Assert.IsTrue(0U == result.Negative()); a = 1U._Church().Sign(); b = 1U._Church().Sign().Negate(); result = a.DivideBy(b); Assert.IsTrue(0U == result.Positive()); Assert.IsTrue(1U == result.Negative()); a = 11U._Church().Sign(); b = 5U._Church().Sign().Negate(); result = a.DivideBy(b); Assert.IsTrue(0U == result.Positive()); Assert.IsTrue(2U == result.Negative()); } }

# 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:

```
Signed2 := Tuple
Sign := Item1
Absolute := Item2
```

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

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