Implementing numbers in ‘pure’ Ruby
UPD. I’ve migrated my posts to my personal blog
Object-Oriented Programming to me means that the system is divided into objects. An object is just an entity that has some state and some behaviour. You can make your object do something by sending it a message, hoping that it will understand you.
For practical reasons, every language has some primitives; basic data types you can use to write your program. Even though Ruby is, supposedly, a pure OO language (everything is an object), it has some primitives nevertheless.
For instance, numbers. They look like objects, they have methods and stuff. However, what are they really?
3 are different instances of the
Integer class, so they are supposed to have a different state. But what is that state? Magic.
Let’s try and implement numbers on our own, without magic. Just for fun.
So, I came up with this set of constraints:
- We can’t use any of the basic types except
- Blocks are ok (just for some expressiveness, they won’t hurt).
- Using the equality operator for objects is ok. This is to check if two given object links point to the same object.
- Rules do not apply to tests because tests are just there to check if something works as intended.
- Rules do not apply to the
#inspectmethod since it serves only for demonstration purposes.
Rule #1 is quite controversial. On the one hand, we are using magic primitives. On the other hand, I think that every program has to have logical expressions in order for it to be of any use. And we can’t have logical expressions without “falsey” entities (
I believe we don’t really need
false because we can use
false and any object for
true. However, why not? Just for expressiveness.
One of the things I remember from my time at university is our professor showing us a way to implement natural numbers in terms of Peano axioms during a set theory lecture.
Essentially, what we need is:
- Some basic entity (it will represent zero in the natural numbers set).
- Some function
next(x)that returns the number after
In set theory we can use:
- Empty set
- The function that returns a 1-element set containing its argument:
next(s) = [s]
So our natural numbers are presented as:
0 = 
1 = []
2 = [[]]
The problem is, we don’t have sets at our disposal. Instead of them, we can use lists.
List — our basic data structure
As you can see, I implemented
List as a pair. The first element is some object and the second one is some other list. Notice that lists are immutable.
I decided that every created node has to have a tail, except for the empty list which should be instantiated only once. In order to achieve that I had to use a hack, which I indicated with a comment.
Now that we have our basic data structure, we can use it instead of sets for our implementation like this:
0 = ()
1 = (())
Every number object will have an inner list representation as a state. So, the
bare minimum looks like this:
But it’s no use to us. We can’t do anything with that. And what’s with all these
new(…)? It’s completely impractical!
In order to make this class useful, we need to define some behaviour.
Some utility before we start
Let’s add some helper methods to
These will come in handy later.
Also, we need to have an access to other list representations:
protected attr_reader :list_representation
This is an interesting bit. Not everyone knows that
protected in Ruby is
different from the one in Java. In Java (and some other languages), protected methods are only accessible to child classes.
protected means that this message can be sent from an object of the
If we think about it, each actual number equals the nesting level of an empty list. For
0 the nesting level is zero,
1 wraps an empty list once,
2 does it twice, and so on. So, to add two numbers we just need to increase the nesting level of one of them by the nesting level of the other:
n * 5 mean? It means that we are adding
n with itself five
times. We already have a plus operator. Let’s use it:
Again, we just need to compare the nesting levels:
Other operators can be defined in terms of the basic ones:
Subtraction is a tricky one because it’s not defined on the whole set of natural numbers. You can’t subtract a bigger number from a smaller one.
But it may become useful:
Okay, now we have defined basic operations. What next? How do we use them? I don’t want to initialize numbers with lists every time I need one.
Well, the beauty of it is that by having the number
1 and the
+ operation, we can create any number we want without having to explicitly provide state:
two = NaturalNumber::ONE + NaturalNumber::ONE
three = two + NaturalNumber::ONE# Don't forget we have multiplication as well!
fifty_four = three * three * three * two
As you can see, there can be multiple instances for the same number. But that’s okay because they are equivalent in terms of usage.
All right. We have natural numbers and we can even do some math with it. But so what? We need integers!
Integers are exactly the same as natural numbers, but for every natural number they have an additional negative one:
So, that said, we can implement integers by using naturals:
I will not bother you with all of them, I will just show a couple to give you an
As you can see, adding an additional element to the state has complicated things drastically. Even though basic operations were already implemented on natural numbers, I still had to add a lot of logic on top of it. Big states are bad, children!
Let’s analyse what we’ve done so far. One of the things I found interesting is the number of methods inside our classes. It’s an interesting question if the class
IntegerNumber has many responsibilities or not.
It really does have a lot of methods. Right now we are facing the “fat models” problem from Rails. What can we do? We can extract the behaviour to other classes. I think it’s a good design when data and behaviour are divided. Let’s try a bit:
The problem here is that we actually have to make
#value public. It’s interesting because, on the one hand, we want to make
IntegerNumber just a data class, but, on the other hand, we don’t really want to expose its inner state since it’s so low-level. I guess we just have to make sacrifices or allow usage of
Add and all similar classes.
On the bright side, we can introduce some functional programming features to this design. For example, currying:
Without our “ground rules” it would look even better.
It was an interesting experience because I had some thoughts about software design in the process. I didn’t prove anything by this nor discovered anything new. But I had some fun.
You can find the code here. I hope I will find something else fun to do with