Implementing numbers in ‘pure’ Ruby

Dmitry Non
Jan 17, 2020 · 6 min read
Image for post
Image for post
Photo by Andrew Buchanan on Unsplash

UPD. check out my new similar post but even cooler: https://weird-programming.dev/oop/classes-only.html

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:

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:

In set theory we can use:

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 🙇

carwow Product, Design & Engineering

What happens under the hood at carwow.co.uk

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store