Representing Negative and Complex Numbers Using Lambda Calculus

Question

Most tutorials on Lambda Calculus provide example where Positive Integers and Booleans can be represented by Functions. What about -1 and i?

Answer 1

First encode natural numbers and pairs, as described by jmad.

Represent an integer $k$ as a pair of natural numbers $(a,b)$ such that $k = a - b$. Then you can define the usual operations on integers as (using Haskell notation for $\lambda$-calculus):

neg = \k -> (snd k, fst k)
add = \k m -> (fst k + fst m, snd k + snd m)
sub = \k m -> add k (neg m)
mul = \k m -> (fst k * fst m + snd k * snd m, fst k * snd m + snd k * fst m)

The case of complex numbers is similar in the sense that a complex number is encoded as a pair of reals. But a more complicated question is how to encode reals. Here you have to do more work:

1. Encode a rational number $q$ as a pair $(k,a)$ where $k$ is an integer, $a$ is natural, and $q = k / (1 + a)$.
2. Encode a real number $x$ by a function $f$ such that for every natural $k \in \mathbb{N}$, $f k$ encodes a rational number $q$ such that $|x - q| < 2^{-k}$. In other words, a real is encoded as a sequence of rationals converging to it at the rate $k \mapsto 2^{-k}$.

Encoding reals is a lot of work and you do not want to actually do it in the $\lambda$-calculus. But see for example the etc/haskell subdirectory of Marshall for a simple implementation of reals in pure Haskell. This could in principle be translated to the pure $\lambda$-calculus.

Answer 2

Lambda-calculus can encode most data structures and basic types. For example, you can encode a pair of existing terms in the lambda calculus, using the same Church encoding that you usually see to encode nonnegative integers and boolean:

$$\mbox{pair}= λxyz.zxy$$ $$\mbox{fst} = λp.p(λxy.x)$$ $$\mbox{snd} = λp.p(λxy.y)$$

Then the pair $(a,b)$ is $p=(\mbox{pair }ab)$ and if you want to get back $a$ and $b$ you can do $(\mbox{fst }p)$ and $(\mbox{snd }p)$.

That means that you can easily represent positive and negative integers with a pair: the sign on the left and the absolute value on the right. The sign is be a boolean that specified whether the number is positive. The right is a natural number using Church encoding.

$$(sign,n)$$

And now that you have relative integers. The multiplication is easy to define, you just have to apply the $\mbox{xor}$ function on the sign and the multiplication on natural numbers on the absolute value:

$$\mbox{mult}_ℤ=λab.\mbox{pair} ~~(\mbox{xor}(\mbox{fst }a)(\mbox{fst }b)) ~~(\mbox{mult}_ℕ(\mbox{snd }a)(\mbox{snd }b))$$

To define the addition, you have to compare two natural numbers and use subtraction when the signs are different, so this is not a λ-term but you can adapt it if you really want to:

$$\mbox{add}_ℤ=λab.\left\{\begin{array}{ll} (\mbox{true},\mbox{add}_ℕ(\mbox{snd }a)(\mbox{snd }b)) & \mbox{if } a≥0∧b≥0 \\ (\mbox{false},\mbox{add}_ℕ(\mbox{snd }a)(\mbox{snd }b)) & \mbox{if } a<0∧b<0 \\ (\mbox{true},\mbox{sub}_ℕ(\mbox{snd }a)(\mbox{snd }b)) & \mbox{if } a≥0∧b<0∧|a|≥|b| \\ (\mbox{false},\mbox{sub}_ℕ(\mbox{snd }b)(\mbox{snd }a)) & \mbox{if } a≥0∧b<0∧|a|<|b| \\ (\mbox{true},\mbox{sub}_ℕ(\mbox{snd }b)(\mbox{snd }a)) & \mbox{if } a<0∧b≥0∧|a|<|b| \\ (\mbox{false},\mbox{sub}_ℕ(\mbox{snd }a)(\mbox{snd }b)) & \mbox{if } a<0∧b≥0∧|a|≥|b| \\ \end{array}\right.$$

but then subtraction is really easy to define:

$$\mbox{minus}_ℤ=λa.\mbox{pair}(\mbox{not}(\mbox{fst } a))(\mbox{snd } a)$$ $$\mbox{sub}_ℤ=λab.\mbox{add}_ℤ(a)(\mbox{minus}_ℤb)$$

Once you have positive and negative integers you can define complex integers very easily: it is just a pair of two integers $(a,b)$ which represents $a+b\mbox{i}$. Then addition is point-wise and multiplication is as usual, but I won't write it, it should be easy:

$$\mbox{add}_{ℤ[\mbox{i}]}=λz_1z_2.\mbox{pair} (\mbox{add}_ℤ(\mbox{fst }z_1)(\mbox{fst }z_2)) (\mbox{add}_ℤ(\mbox{snd }z_1)(\mbox{snd }z_2))$$