# Object-oriented Peano arithmetic in Python

I'm not sure what would be the best way to implement Peano arithmetics in Python
or another language without algebraic data types, but I think I've found the
*worst* (and the funniest) way to do it.

Python has introspection and for every class we can find its base class(es). It can also create classes on the fly and attach string representation functions to classes. So we can assume that some base class is zero, its subclasses are S(O), subclasses of its subclasses is S(S(O)) and so on.

**Note:** this only works in Python2, Python3 made a lot of changes
to metaclasses and I haven't found a way to add pretty print to classes there yet.

Download the file: oo-peano.py

#!/usr/bin/env python import uuid # Axiom 0: every language feature can # and will be misused. class Nat(type): def __repr__(self): if self == Zero: return "O" else: return "S({0})".format(repr(self.__bases__[0])) # Axiom 1: Zero is a natural number class Zero(object): __metaclass__ = Nat # Axiom 2: for every natural number N, # succ(N) is a natural number @classmethod def succ(self): # Class names don't matter but must be unique name = str(uuid.uuid4()) # By successor Peano meant a subclass, right? t = type(name, (self,), {"__metaclass__": Nat}) return t @classmethod def add(self, x): if self == Zero: return x else: return self.__bases__[0].add(x.succ()) @classmethod def mul(self, x): if self == Zero: return self else: return x.add(self.__bases__[0].mul(x)) if __name__ == '__main__': one = Zero.succ() two = Zero.succ().succ() three = Zero.succ().succ().succ() print("{0} + {1} = {2}".format(Zero, Zero, Zero.add(Zero))) print("{0} + {1} = {2}".format(Zero, one, Zero.add(one))) print("{0} + {1} = {2}".format(two, three, two.add(three))) print("{0} + {1} = {2}".format(three, two, three.add(two))) print "" print("{0} * {1} = {2}".format(Zero, Zero, Zero.mul(Zero))) print("{0} * {1} = {2}".format(Zero, one, Zero.mul(one))) print("{0} * {1} = {2}".format(two, one, two.mul(one))) print("{0} * {1} = {2}".format(two, three, two.mul(three))) print("{0} * {1} = {2}".format(three, two, three.mul(two)))

The output demonstrates that zero and one are indeed the additive and multiplicative identity elements respectively, and that addition and multiplication as we defined them are commutative.

$ python peano.py O + O = O O + S(O) = S(O) S(S(O)) + S(S(S(O))) = S(S(S(S(S(O))))) S(S(S(O))) + S(S(O)) = S(S(S(S(S(O))))) O * O = O O * S(O) = O S(S(O)) * S(O) = S(S(O)) S(S(O)) * S(S(S(O))) = S(S(S(S(S(S(O)))))) S(S(S(O))) * S(S(O)) = S(S(S(S(S(S(O))))))

If you've never heard of Peano arithmetic before, here's an informal introduction to what's going on.
To define natural numbers axiomatically, we postulate that there's
a thing called Zero (we'll render it as *O*) and it's a natural number.
Then we postulate that there's a *successor*
function *S(n)* (also called *succ(n)*) such that for any natural number *n*, *S(n)*
is also a natural number, and if two natural numbers are equal, then their
successors are also equal.

Thus we can construct any number from Zero by using the *S* function.
0 = O, 1 = S(O), 2 = S(S(O)) and so on.

We also assume that there is a way to extract the *n* from *S(n)*,
that is, that there is a *predecessor* function *P* such that *P(S(n)) = n*.
We also assume that the predecessor of Zero is Zero, although we don't really need this fact in the program above.

Now we can define addition and multiplication. We'll use inductive definitions with Zero as the base case:

N + O = N (1) N + S(M) = S(N) + M (2) N * O = O (1') N * S(M) = N + N*M (2')

Since every natural number if either Zero or can be represented as *S...(S(O))*,
we know that for every number *M* this process will eventually hit the base case and
terminate.