Peano Numbers

Last updated at 1:35 pm UTC on 7 January 2018

What would happen if you had a computer that did not implement arithmetic on integers, i.e., if integers were not primitive? Mathematicians face similar problems when they try to define arithmetic operations on integers without using any underlying number system. One such definition is the Peano Axioms, which define integers in terms of increment. These axioms are https://en.wikipedia.org/wiki/Peano_axioms

The first axiom states that the constant 0 is a natural number:

1. 0 is a natural number.

The next four axioms describe the equality relation. Since they are logically valid in first-order logic with equality, they are not considered to be part of "the Peano axioms" in modern treatments.[6]

2. For every natural number x, x = x. That is, equality is reflexive.

3. For all natural numbers x and y, if x = y, then y = x. That is, equality is symmetric.

4. For all natural numbers x, y and z, if x = y and y = z, then x = z. That is, equality is transitive.

5. For all a and b, if b is a natural number and a = b, then a is also a natural number. That is, the natural numbers are closed under equality.

The remaining axioms define the arithmetical properties of the natural numbers. The naturals are assumed to be closed under a single-valued

6. For every natural number n, S(n) is a natural number.

7. For all natural numbers m and n, m = n if and only if S(m) = S(n). That is, S is an injection.

8. For every natural number n, S(n) = 0 is false. That is, there is no natural number whose successor is 0.

Simplified this is

x + 0 = x

x + y = y + x

x + inc(y) = inc(x) + y

We are going to implement integers the same way. This implementation is not only good when your machine does not implement integer arithmetic, but also when you want programs that take a long time.

Define three subclasses of Integer, Zero, PositiveInteger, and NegativeInteger. Zero has no instance variables, but a PositiveInteger has an instance variable decr that is a number one smaller than itself, and NegativeInteger has an instance variable incr that is a number one larger than itself. Each class must define incr and decr, which return a number one greater or less than the reciever. This is done either by returning an instance variable or by creating a new PostiveInteger or NegativeInteger and making the receiver be its decr or incr.

For instances of Zero:

^NegativeInteger oneLessThan: self

^PositiveInteger oneMoreThan: self

NegativeInteger and PositiveInteger need class method and instance methods to implement oneLessThan: and oneMoreThan: Try writing them.

It is easy to define + for Zero, since + returns its argument. + on the other two classes is implemented by

For instances of PositiveInteger:

^decr + aNumber incr

For instances of NegativeInteger:

^incr + aNumber decr

It is easy to implement, for Zero, since - returns the negation of its argument. Negative is easy to define for all three classes, since 0 negative is 0 and the negative of the other two classes is one less (or greater) than the negatives of their incr's or decr's. - can be implemented the same for both classes using + and negative.

For instances of PositiveInteger:

^self + aNumber negative

Implement + and - on these three classes. It aids debugging if each number will print out its value. Thus, try

For instances of All three classes:

self value printOn: aStream!

For instances of Zero:

^0

For instances of PositiveInteger:

^decr value + 1

For instances of NegativeInteger:

^incr value - 1

It is easy to get in trouble when you try to define new subclasses of Integer, because so much code is implemented by Integer, much of it inappropriate for subclasses. I found that I got several infinite loops. If an operation doesn't return after a second or two, press ^C. Don't wait a half minute to do it, because then the system makes far more garbage to clean up.

I did not tell you what the class hierarchy is like. All three classes could be subclasses of Integer. I made Zero a subclass of Integer and the other two subclasses of Zero. This seems a little funny. What are other alternatives, and which is best?