Peano Numbers

Last updated at 11:39 pm UTC on 10 August 1998

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 roughly (I didn't look them up):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?