Implementing numbers in ‘pure’ Ruby

Photo by Andrew Buchanan on Unsplash

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? 2 and 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.

Ground rules

So, I came up with this set of constraints:

1. We can’t use any of the basic types except nil, true, and false.
2. No Stdlib (duh).
3. Blocks are ok (just for some expressiveness, they won’t hurt).
4. Using the equality operator for objects is ok. This is to check if two given object links point to the same object.
5. Rules do not apply to tests because tests are just there to check if something works as intended.
6. Rules do not apply to the #inspect method 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 (nil and false).

I believe we don’t really need true and false because we can use nil for
false and any object for true. However, why not? Just for expressiveness.

Implementation idea

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:

1. Some basic entity (it will represent zero in the natural numbers set).
2. Some function next(x) that returns the number after x.

In set theory we can use:

1. Empty set []
2. 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 = (())
• …

Natural numbers

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.

Methods

Some utility before we start

Let’s add some helper methods to List:

These will come in handy later.

Also, we need to have an access to other list representations:

class NaturalNumber
  protected
  attr_reader :list_representation
end

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.

In Ruby, protected means that this message can be sent from an object of the
same class:

Addition

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:

Multiplication

What does n * 5 mean? It means that we are adding n with itself five
times. We already have a plus operator. Let’s use it:

Comparison operators

Again, we just need to compare the nesting levels:

Other operators can be defined in terms of the basic ones:

Subtraction

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:

Usage

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

Integers are exactly the same as natural numbers, but for every natural number they have an additional negative one: -1, -2, -3.

So, that said, we can implement integers by using naturals:

Methods

I will not bother you with all of them, I will just show a couple to give you an
idea:

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!

What next?

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 send in 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.

Conclusion?

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
programming paradigms.

While you’re here: carwow is hiring developers!
Interested? Check out our available roles 🙇