Jun 26, 2018

Categories:

From 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

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.

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.

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
```

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.

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)))))
}
```

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)))))
```

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 imutable 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))))))
```

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 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 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

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.

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.