# Ivory: Numerical Towers

The witchery that is cast in these towers

It transcends the limits of my mind

Ivory Towers in the sky

A dreadful and enchanting sight— Acid Mammoth,

Ivory Towers

Numerical Towers are a particular way to design and organise a programming language’s numeric values and operations, notably used by the Lisp, Scheme & Smalltalk families. We will characterise the approach as follows:

- Multiple types of number are provided, e.g.
`natural`

,`integer`

,`rational`

, etc. - These types are constant, e.g. no parameterising like
`(integer-modulo 7)`

or`(matrix 3 3)`

- Different types of number can use different representations,
e.g.
`integer`

may use a sign to distinguish positives from negatives; whilst`rational`

may store a separate numerator and denominator. - These types are related as strict subsets/supersets of each other,
e.g. every
`natural`

is also an`integer`

, and a`rational`

, etc. - This subset relationship forms a “tower” (a total ordering between the types)
- Each number is represented uniquely by its highest level in the
tower. For example,
`-12`

is an`integer`

, so there is no separate`rational`

like`-12/1`

. Likewise, there is no dedicated value for`9/12`

, since that number’s unique represention is`3/4`

. - Numbers are equal precisely when their unique representations are identical.
- Every number can be automatically “normalised” to its unique representation.
- Numbers only store their intrinsic information, not where they’re from or how they’re supposed to be used.
- Each arithmetic operation has a single definition, which handles any
type of number (that it’s defined for; e.g. we can’t divide by a
`zero`

). There are no separate functions like`integer-+`

,`rational-+`

, etc.

For contrast, here are some features of *other* designs for
numerical systems, which are not numerical towers:

**Operator-based** approaches, also called modular
programming or programming-to-interfaces, focuses on the operations
provided by each numerical type; ignoring their underlying
representations. For example, instead of `natural`

,
`integer`

, `rational`

, etc. we may have
`additive`

(has a defined addition operation),
`invertable`

(has a division operation), `ring`

(has multiplication, division and distributivity), `monoid`

(has an associative operation and identity element), etc. This approach
can be seen in Haskell’s Typeclassopedia, and is also well-suited to ML
signatures, Scala’s type class pattern, and (more awkwardly) to Java
interfaces.

**Computer Algebra Systems**, like Maxima and SageMath,
allow arbitrary expressions to be represented symbolically, and
rewritten via user-defined rules. However, the price for this generality
is that expressions do not have a unique normal form, or any general
algorithm for deciding their equality. Computer Algebra is therefore
reserved for interactive applications, rather than used as a general
purpose programming language.

**Parameterised types** allow more fine-grained control
over what values and operations are acceptable. For example, in Haskell
the types `Sum Int`

, `Product Int`

,
`Sum Float`

and `Product Float`

are all different:
“appending” values of type `Sum t`

will add them, and the
“empty” value is the representation of zero in type `t`

;
whilst values of type `Product t`

will be multiplied, and the
“empty” value is the representation of one in type `t`

.
Dependently-typed languages can go even further, with types like
`Fin n`

for numbers less than `n`

.

Finally, many programming languages don’t provide any structured
relationships between their numerical types. For example, Python has
types `int`

, `float`

and `complex`

, but
they are not related (e.g. via Python’s “subclass” mechanism). Their
values are disjoint, rather than nested, requiring multiple ways to
represent the same number (e.g. `2`

, `2.0`

and
`2+0j`

), with explicit coercion required to turn one of those
representations into another. Other languages, like OCaml, even require
separate operations for different numeric types, e.g. providing
`+`

to add integers and `+.`

to add floats.

## Tradeoffs

Organising numerical types into a linear “tower” provides more generality and flexibility than unstructured systems. It is also simpler and less abstract than operator-based or parameterised approaches, which are better suited to statically checked languages. Numerical towers are a good fit for dynamic languages.

This simplicity comes at the cost of having less precise types for
our functions to choose from. For example, in a numerical tower with
`integer`

as a subset of `rational`

, then any
function accepting `rational`

inputs *must* handle
negative values; indeed, we cannot restrict anything to “non-zero”
numbers, if `zero`

is at the top of the tower! In such cases
we may have to rely on assertions, and convince ourselves that our usage
is correct on a case-by-case basis 🤞

### Mezzanines

Whilst a case can be made for including this or that level, and perhaps having some “sibling” levels where neither contains the other, there are ultimately too many partially-overlapping cases to adequately express in a simple “tower” structure. Since the whole point of a numerical tower is to simplify for common cases, such relationships are perhaps better suited to a language/library based on operators or parameterised types.

That said, Ivory does define additional structure *within*
some levels, which we call “mezzanines”. Mezzanines cannot cross between
multiple levels, so they do not alter the linear structure of the
tower’s levels. The main purpose of mezzanines is to support siblings,
which allows many more useful types to be defined that would otherwise
conflict; with the overall tower being agnostic about such internal
distinctions.

For example, there are many useful subsets of `natural`

which contain `zero`

, and hence could appear as an
intermediate level in our tower. Unfortunately, most are incompatible
with each other, such that choosing one would prevent us being able to
express others; e.g. if we included a `boolean`

level
containing `0`

and `1`

, we could not have an
`even`

level (since it couldn’t appear above or below
`boolean`

). Mezzanines are more flexible, allowing us to
provide `boolean`

*and* `even`

, as siblings
inside `natural`

: this is permitted since their intersection
(the values they have in common) is precisely the `zero`

level that sits above both!

The relationship between `square`

and `even`

is
more delicate: both are useful sets to provide; but they cannot be
levels of the tower, since neither contains the other; yet they can’t be
directly encoded as siblings without including *another* subset
above them to represent their intersection. The latter would give
`boolean`

an `even-square`

sibling, but we must
ask ourselves if there is any merit to such subdivision, or whether it’s
an arbitrary hack? In this case it seems worthwhile, since
`even-square`

has a non-trivial relationship to
`even`

via `quadruple`

(multiples of four, which
also have nice closure properties and number-theoretic significance).
`even-square`

also complements its sibling
`boolean`

, as being the most natural subsets of
`square`

that include `zero`

(no pun
intended).

In contrast, we *cannot* use mezzanines to define, say, an
`odd`

subset of `natural`

(or
`odd-square`

, etc.), since every subdivision occuring
*inside* the `natural`

level must necessarily sit
below (and hence contain) `zero`

.

### Operations

Numerical towers primarily focus on the representation of numbers,
with their operations being a secondary concern. A common pattern is for
operations to “lower” their inputs down the tower, to a level where that
operation is defined. For example, to subtract `natural`

numbers we consider them as `integer`

numbers, since that can
represent all of the possible results (which may be negative). Special
cases will be “lifted” back up by normalisation, e.g. if the first input
happens to be as large as the second, then the resulting
`integer`

will be its `natural`

subset; if the
inputs happen to be equal, that `natural`

will also be in its
`zero`

subset; and so on.

Although a good rule of thumb, unfortunately this “lowering”
behaviour doesn’t always hold; e.g. comparison functions like
`≤`

are not defined below the `real`

level.