Numerical tower

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In Scheme and in Lisp dialects inspired by it, the numerical tower is a set of data types that represent numbers and a logic for their hierarchical organisation.

A representation of the numerical tower with five types of numbers.

Each type in the tower conceptually "sits on" a more fundamental type, so an integer is a rational number and a number, but the converse is not necessarily true, i.e. not every number is an integer. This asymmetry implies that a language can safely allow implicit coercions of numerical types—without creating semantic problems—in only one direction: coercing an integer to a rational loses no information and will never influence the value returned by a function, but to coerce most reals to an integer would alter any relevant computation (e.g., the real 1/3 does not equal any integer) and is thus impermissible.

In Lisp[edit]

Principally, the numerical tower is designed to codify the set theoretic properties of numbers in an easy-to-implement language facility: every integer is a rational with an implicit denominator of 1, and all reals are complex with an implicit imaginary part of 0. Practically, the implementation may save time and space by ignoring these properties unless they become arithmetically relevant, and also may correspondingly improve the efficiency of its representation when reducing numerical values to their canonical representation by eliminating negligible components of a number. For example, a series of multiplications of complex numbers may be simplified to a series of multiplications of reals if any of the multiplicands includes a 0 as either its real or imaginary part.

The most generic type, number, is somewhat confusingly named: it exists to capture all mathematical values whose type is more general complex, but which are still usable with standard mathematical operations, as defined by Scheme. Thus it captures, for example, positive and negative infinity (+inf.0 and -inf.0, the significand here meaning approximation up to cardinality), since those are mathematical objects to which at least some numerical operations may validly apply (e.g. one can add to or multiply by infinity, yielding infinity; or compare cardinality against infinity, with infinity always being greater than any finite value).[1] On a more technical level, number in Lisp simply provides a place in the type hierarchy for the kinds of non-strictly-numerical values defined by IEEE 754.

The Scheme programming language defines all its arithmetic within this model, as do most other Lisp dialects.[2][3] Some implementations may extend or adapt the tower. Kawa, a Scheme implementation for the JVM, extends the tower to include both quaternions[4] and quantities,[5] with quantities being a way of subtyping numerical values with units; e.g. a number of grams cannot meaningfully be added to a number of metres because via quantities numbers inherit logic derived from dimensional analysis to govern their meaning in relation to and thus valid arithmetical interactions with each other.

Another common variation is to support both exact and inexact versions of the tower or parts of it; R7RS Scheme recommends but does not strictly require this of implementations. In this case, similar semantics are used to determine the permissibility of implicit coercion: inexactness is a contagious property of numbers,[6] and any numerical operation involving both exact and inexact values must yield inexact return values of at least the same precision as the most precise inexact number appearing in the expression, unless the precision is practically infinite (e.g. containing a detectable repetend), or unless it can be proven that the precision of the result of the operation is independent of the inexactness of any of its operands (for example, as above, a series of multiplications where at least one multiplicand is 0).

In other languages[edit]

Most programming languages and language implementations do not support a Scheme-like numerical tower, though some languages provide limited or inconsistent support if implementation simplicity permits. Python, for example, provides a similar structure via PEP3141,[7] citing Scheme's example, though in practice rational numbers (fractions) must be imported from their own module, and both rational and complex numbers use slightly variant syntax from normal number literals, since Python's syntax is less explicit than Lisp's.

Thus in the following Scheme examples we see:

1 -2 +3
 1
 -2
 3
1/3
 1/3
72/6+8/3i
 12+8/3i              ; coercion: canonical form
(+ 3+2i 2-2i)
 5                    ; coercion: canonical form
(- 3-62/32i 1+inf.0i)
 2-inf.0i             ; coercion: infinite cardinality
(> 3+0/2i 3)
 #f                   ; coercion: 3 ≯ 3

While in the following Python examples we see:

1; -2; +3
 1
 -2
 3
1/3
 0.3333333333333333
inf = float('inf')                       # infinity not first-class
from fractions import Fraction
x = Fraction(1, 3)
y = Fraction(2, 3)
x + y
 Fraction(1, 1)                         # no coercion
(3+2j)
 (3+2j)
complex(x, inf)
 (0.3333333333333333+infj)              # coercion: equality violated
a = 1/3
b = Fraction(1, 3)
caz = complex(a, 0)
cbz = complex(b, 0)
a == b
 False
caz == cbz
 True                                   # proof of equality violation
complex(x + y, -inf)
 (1-infj)                               # coercion: equality preserved
(3+0j) > 3
 Traceback (most recent call last):
   File "<stdin>", line 1, in <module>  # no coercion: type error
 TypeError: '>' not supported between instances of 'complex' and 'int'

In the Python examples, we can see that numerical issues freely arise with an inconsistent application of the semantics of its type coercion. While 1/3 in Python is treated as a call to divide 1 by 3, yielding a float, the inclusion of rationals inside a complex number, though clearly permissible, implicitly coerces them from rationals into floats or ints, even in cases where this is incorrect.

Smalltalk is another programming language that follows this model, but it has ArithmeticValue and Magnitude as superclasses of Number.

References[edit]

  1. ^ "Revised7 Report on the Algorithmic Language Scheme: 6.2.4: Implementation extensions" (PDF).
  2. ^ "Revised5 Report on the Algorithmic Language Scheme: 6.2.1: Numerical types" (PDF).
  3. ^ "Revised7 Report on the Algorithmic Language Scheme: 6.2.1: Numerical types" (PDF).
  4. ^ "Kawa Reference‌ Documentation: 12.4. Quaternions".
  5. ^ "Kawa Reference‌ Documentation: 12.5 Quantities and Units".
  6. ^ "Revised7 Report on the Algorithmic Language Scheme: 6.2.2: Exactness" (PDF).
  7. ^ "PEP 3141 – A Type Hierarchy for Numbers".