How to create Natural numbers as objects in Scala

Kamen Kotsev

Jun 26, 2018

Categories:

Numbers

From a young age, we are taught what numbers are. Schools teach us how to write them down, how to add, subtract, multiply and divide them. We have an intuition of what a number is, but if you have to give a formal definition what would you say?

What is the number 3 for example? We know how to write it down, we know what word to use in order refer to it, we know how to use it when counting, but what is it really? Does it have a physical form? Is it only imaginary? Can you explain to the computer what numbers mean to you?

We are taught that computers work in binary numbers, and the reason is that “modern” computers use the absence of electricity to represent 0 and presence of such (roughly speaking) to represent 1. Since there is a way to represent any number in binary, having 0 and 1 is sufficient for any computation. There’s a lot of history to be told behind the decision to use binary systems but we are not interested in binary numbers today. Why? Well, because today we want to create numbers using only objects. And we will do this without a super solid background in Maths. We will use only the knowledge we received in primary school.

So what do we want anyway? We want to be able to say “this object is 1”, “this object is 5234” without using the numbers or their representation in the computer.

TL;DR: We want to create numbers and simple arithmetic functions (addition, subtraction, multiplication, division) without writing any number in our program (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Another way to put it: We want to create the entire infinite set of Natural numbers using only objects.

That way we can get a sense of what the number object is in real life, rather than just what we can do with a number.

Describing Numbers

For starters, let’s see what the definition of the Natural Numbers Set is

Positive integer numbers or just The numbers we use to count. Each of these numbers can be individually described by adding one to the number before. Having this in mind we can conclude that no matter what number we have, we can always add one to represent the next.

There’s a theorem that states that Natural numbers are infinitely many. The proof:

Suppose that the statement in this theorem is incorrect and there are finite number of integers.
If there are finite number of integers, there is an integer bigger than all of them.
We take that integer and call it ‘N’ for example.
Going back to the definition, we know that we can add ‘one’ to every natural number in order to represent the next natural number.
We take the next number after ‘N’ That’s ‘N+1’ which is larger than the assumed “largest” number. ‘N+1’ is also a Natural number so it is indeed in the Natural numbers set.
Our assumption is therefor incorrect and this proves the theorem.

So having all of this info we can start writing code.

Programming

We will describe numbers using only sets (and sets that contain sets). You can imagine a set as a container of unique elements.

For example {'a', 5, G, {7, 'x'}} is a set, containing the elements:

the letter ‘a’
the number 5
some object called G
a set that contains the number 7 and the letter ‘x’

But we don’t want to use letters, numbers or other objects. We want to use only sets.
Let’s take for example the empty set. It is a special set that doesn’t contain any elements. There is a mathematical notation for such a set: ‘∅’. But let’s stick to this ‘{}’ notation for now.
Let’s think of the empty set as a zero in the Natural numbers. Then we can describe the number one like this ‘{{}}’. A set containing only the empty set. The number two can be described like so: ‘{{{}}}’ and so on and so on. We can describe every single number like this, by just wrapping the previous number in another set.
But how do we describe a set programmatically? Well, we can use a class, that takes arguments in its constructor. The constructor will create an immutable object with no side effects that contains all the arguments that we’ve passed as its elements.
So a class that creates immutable objects and takes no arguments in its constructor will create our zero!

To summarize:

{{{{}}}} = 3
 {{{}}}  = 2
  {{}}   = 1
   {}    = 0

The model

We can now create the first integer and call it Zero.
As promised, let’s write this down in Scala

// in this case trait means that every number we describe will
// have the option to be referred to as a "NaturalNumber"
trait NaturalNumber

// Zero is a NaturalNumber
case class Zero() extends NaturalNumber

Note: the case class means that this will be an immutable object (and some other things but this is a topic of a different article).

And since it is a member of the Natural numbers it should have the property of “having a number after it”. We can do that by wrapping it into another set as we decided earlier. Since we want to work with types, we will create a different class for the sets that contain elements. And since all objects are immutable we will be able to tell one object from the other by comparing them by the way they were created. If they were created in the same way – we will consider them to be equal by definition.

trait NaturalNumber

case class Zero() extends NaturalNumber

case class Int(previous: NaturalNumber) extends NaturalNumber

That’s it! We’ve successfully created Natural Numbers.
Don’t believe me? Let me show you how can we represent any natural number:

object Main extends App {
  val zero = Zero()
  val one = Int(Zero())
  val five = Int(Int(Int(Int(Int(Zero())))))
}

Every number can be represented this way without using anything but sets because we can always wrap a number with Int() and refer to the next number.

Operations with numbers

Okay, but how do we use these “numbers” that we’ve created? Can we add/subtract/multiply/divide them? Do we have a notion of comparison, e.g. A is bigger than B (can they be ordered)?

Before we move forward implementing the basic arithmetic functions let me just set the goals. This is the final structure we are aiming for:

trait NaturalNumber {
  // Addition
  def + (other: NaturalNumber): NaturalNumber
  
  // Subtraction
  def - (other: NaturalNumber): NaturalNumber
  
  // Multiplication
  def * (other: NaturalNumber): NaturalNumber
  
  // Division
  def / (other: NaturalNumber): NaturalNumber
  
  // Mod Division (only remainder)
  def % (other: NaturalNumber): NaturalNumber
  
  // Less than
  def < (other: NaturalNumber): Boolean
}

Note if you are new to Scala: method names in Scala can be operators. We take advantage in this when we create our methods. So instead of naming them “add()”, “subtract()”, “multiply” etc. we can just call them by their operator.

Note that in Scala, methods like these can be called without using a dot notation.
Example: a.+(b) is the same as calling a + b

Quick side note

Just for convenience sake let’s change the definition of Zero to something a bit easier to write down:

// An "object" in Scala is a singleton class.
// we can change our "class Zero" to a singleton class since it
// doesn't take any arguments and will always be the same object
case object Zero extends NaturalNumber

This lets us refer to Zero by omitting the brackets after it: Now Zero() becomes Zero since we’re always talking about the same Zero.

The code so far:

trait NaturalNumber
case object Zero extends NaturalNumber
case class Int(previous: NaturalNumber) extends NaturalNumber

object Main extends App {
  val zero = Zero
  val one = Int(Zero)
  val two = Int(Int(Zero))
  val three = Int(Int(Int(Zero)))
  val five = Int(Int(Int(Int(Int(Zero)))))
}

Addition

Let’s define what an addition would look like in our terms: If we want to add {{}} with {{{}}} we will take advantage of the fact that 2 + 3 is the same as 1 + 4 and the same as 0 + 5 and whenever we add zero to any number a we get the number a as a result.
0 + a = a for every a from the set of Natural numbers

So we will take the outer most set of the first “number” and wrap it around the second number until the first number becomes Zero.
Example:

// Representation
     2            3
  {{{ }}} +   {{{{ }}}}  =
     1            4
=  {{ }}  +  {{{{{ }}}}} =
     0            5
=   { }   + {{{{{{ }}}}}}

Now let’s write it in code:

trait NaturalNumber {

  // A method that takes one argument of type NaturalNumber and returns type NaturalNumber
  def + (other: NaturalNumber): NaturalNumber = {

    // Pattern match that compares the object "this" with the objects "A" in "case A"
    this match {
      // If "this" is actually the object "Zero" return the other number because 0 + a = a
      case Zero => other

      // If "this" is an object that is constructed passing a "number" in an "Int": Int(numuber)
      // add it to the next number after "other"
      case Int(prev) => prev + Int(other)
    }
  }
}

Note: In Scala, the returned value is the last value in a function

The pattern matching ⬇️ we use compares the given object with the objects listed below, and if they are constructed in the same way – they are considered equal.

Let’s test our addition function:

val two = Int(Int(Zero))
val three = Int(Int(Int(Zero)))

println(two + three) // Int(Int(Int(Int(Int(Zero)))))

Multiplication

Multiplying 3 * 5 means that we add 5 to itself 3 times or that we add 3 to itself 5 times. Both interpretations lead to the same result. So we can implement it with a loop that adds one number to Zero the same number of times as the value of the other number.
In other words, we can unwrap the first number (this) step by step until we get to Zero and on each step – add the second number (other) to the accumulated sum.

Ok, so let’s implement multiplication:

def * (other: NaturalNumber): NaturalNumber = {
  // An inline recursive method for hiding the need of an accumulator argument to store the temporary "result"
  def iter(timesLeft: NaturalNumber, result: NaturalNumber): NaturalNumber = {
    timesLeft match {
      case Zero => result
      case Int(prev) => iter(prev, result + other)
    }
  }

  iter(this, Zero)
}

if you didn’t quite get what’s happening in this last method, don’t worry! It’s not as easy as it looks. Take a second and think about it.
Because we want to be immutable throughout our program, we create an inline recursive function to act as a loop for adding numbers.
Then in the last line of our *() function, we return the result from our inline recursive function and we pass in the number of times we want to add the second number to itself, and a starting point for the result to accumulate to. The number of times we want to add other to itself is exactly this many times, and the starting point for accumulation is Zero.

Let’s test it out:

val two = Int(Int(Zero))
val three = Int(Int(Int(Zero)))

println(two * three) // Int(Int(Int(Int(Int(Int(Zero))))))

Ordering (a < b)

Let’s now define what does it mean for one number to be less than another.
We can achieve this by taking advantage of the fact that if we subtract the number one from both sides of an inequality – the inequality remains the same. And Zero is smaller than all other Natural numbers.
Example:

3 < 4 // take 1 from each side
2 < 3 // take 1 from each side
1 < 2 // take 1 from each side
0 < 1 // this is true

{{{{}}}} < {{{{{}}}}} // unwrap one set in each side
 {{{}}}  <  {{{{}}}}  // and again
  {{}}   <   {{{}}}   // and again
   {}    <    {{}}    // until we can say that one side is Zero

Let’s see that in code

def < (other: NaturalNumber): Boolean = {
  (this, other) match {
    case (_, Zero) => false
    case (Zero, _) => true
    case (Int(prev), Int(otherPrev)) => prev < otherPrev
  }
}

Testing it out:

println(two < three) // true
println(two < two) // false
println(three < two) // false
println(one < five) // tru

Subtraction

Subtraction is a bit harder, but just a bit. We just need to consider the fact that we don’t currently have a proper way to describe negative numbers. Until we make a model of negative numbers as well as positive – we’ll throw an ugly exception.

def - (other: NaturalNumber): NaturalNumber = {
  (this, other) match {
    case (Zero, _)=> throw new Exception("Can't unwrap zero")
    case (_, Zero) => this
    case (Int(prev), Int(prevOther)) => prev - prevOther
  }
}

Here we do the same thing that we did with less than, only this time we are actually interested in the value of the first number when the second number reaches zero.
The ugly exception we throw is just until we get an idea of what a negative number is. Then we can fix it.

Division

Division of integer numbers returns two results, the result of the division and a remainder.

17 / 3 = 5 with remainder 2

We’ll implement division by subtracting the second number from the first one, until the first one becomes less than the second number. When we reach this condition – the number of times we managed to subtract the second number from the first is the result of the division and the part of the first number that remains after all the subtractions is the “remainder”

We’ll create two methods: one for returning the result of division, and one for returning just the remainde.

def / (other: NaturalNumber): NaturalNumber = {
  def iter(tempNumber: NaturalNumber, result: NaturalNumber): NaturalNumber = {
    if(tempNumber < other) result
    else iter(tempNumber - other, Int(result))
  }

  iter(this, Zero)
}

Testing it out:

val one = Int(Zero)
val two = Int(Int(Zero))
val three = Int(Int(Int(Zero)))
val four = Int(Int(Int(Int(Zero))))
val five = Int(Int(Int(Int(Int(Zero)))))
val six = Int(Int(Int(Int(Int(Int(Zero))))))

println(six / two) // Int(Int(Int(Zero)))
println(six / three) // Int(Int(Zero))
println(six / four) // Int(Zero)
println(one / five) // Zero

The remainder function:

def % (other: NaturalNumber): NaturalNumber = {
  this - ((this / other) * other)
}

Testing it out:

println(one % five) // Int(Zero)
println(five % two) // Int(Zero)
println(five % three) // Int(Int(Zero))

If you are still reading this far CONGRATULATIONS! You’ve successfully created numbers in the form of objects and implemented some basic calculation methods with them!
Here’s the code so far:

trait NaturalNumber {
  def + (other: NaturalNumber): NaturalNumber = this match {
    case Zero => other
    case Int(prev) => prev + Int(other)
  }

  def * (other: NaturalNumber): NaturalNumber = {
    def iter(timesLeft: NaturalNumber, result: NaturalNumber): NaturalNumber = {
      timesLeft match {
        case Zero => result
        case Int(prev) => iter(prev, result + other)
      }
    }

    iter(this, Zero)
  }

  def < (other: NaturalNumber): Boolean = (this, other) match {
      case (_, Zero) => false
      case (Zero, _) => true
      case (Int(prev), Int(otherPrev)) => prev < otherPrev
    }

  def - (other: NaturalNumber): NaturalNumber =
    (this, other) match {
      // Incorrect since we don't have a definition of a "negative number"
      // if a > b at the moment and we call "b - a" we will get Zero
      case (Zero, _)=> Zero
      case (_, Zero) => this
      case (Int(prev), Int(prevOther)) => prev - prevOther
    }

  def / (other: NaturalNumber): NaturalNumber = {
    def iter(tempNumber: NaturalNumber, result: NaturalNumber): NaturalNumber = {
      if(tempNumber < other) result
      else iter(tempNumber - other, Int(result))
    }

    iter(this, Zero)
  }

  def % (other: NaturalNumber): NaturalNumber = this - (this / other) * other
}

case object Zero extends NaturalNumber

case class Int(previous: NaturalNumber) extends NaturalNumber

object Main extends App {
  val zero = Zero
  val one = Int(Zero)
  val two = Int(Int(Zero))
  val three = Int(Int(Int(Zero)))
  val four = Int(Int(Int(Int(Zero))))
  val five = Int(Int(Int(Int(Int(Zero)))))
  val six = Int(Int(Int(Int(Int(Int(Zero))))))

  println(two + three)

  four match {
    case Int(prev) => println(prev)
  }

  println(two * three)

  println(two < three) // true
  println(two < two) // false
  println(three < two) // false
  println(one < five) // true

  println(three - two) // Int(Zero)
  println(two - three) // Zero
  println(zero - zero) // Zero
  println(five - two) // Int(Int(Int(Zero)))

  println(six / two) // Int(Int(Int(Zero)))
  println(six / three) // Int(Int(Zero))
  println(six / four) // Int(Zero)
  println(one / five) // Zero

  println(one % five) // Int(Zero)
  println(five % two) // Int(Zero)
  println(five % three) // Int(Int(Zero))
}

We managed to “create” a representation of infinitely many Natural numbers using only immutable classes. We used the numbers we created even when counting how many times has a recursive function ran. The representation we created can be used as a substitution of unsigned int and also to define simple algebraic structures but there is still more we can do to improve it. We need to define negative numbers, fractions, and lots of other stuff!
But let’s leave that for another time 🙂

The definition of Natural numbers in this article is a direct implementation of the Peano Axioms

Author’s notes

I hope this article gave you some food for thought. Please let me know if you’d like to read more articles like this one and if you’d like to learn some more Scala.

Footnotes

Pattern matching

So if we ask if Int(Int(Int(Zero))) matches with Int(prev) – it does, because Int(Int(Int(Zero))) is constructed by Int(prev) with prev being Int(Int(Zero)). That’s what the pattern matching does. It extracts the parameter with witch the object was created in prev and gives it to you.

For example If we call:

val four = Int(Int(Int(Int(Zero))))
four match {
  case Int(prev) => println(prev)
}

we will get

Int(Int(Int(Zero)))

as output.

Your development partner beyond code.