# Ivory: Numerical Towers

The witchery that is cast in these towers
It transcends the limits of my mind
Ivory Towers in the sky

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.

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.