Numbers in a Nutshell, an Update

Aug 27, 2022

We discuss numbers and math in Coalton, as they are so far. Coalton is under active development, so this blog post may go out of date in due time.

Introduction

Coalton is statically typed, which presents some challenges in how we work with numbers, both syntactically and semantically. For instance, consider the following Common Lisp code:

CL-USER> (loop :for b :in '(2 2.0d0 -2) :do
           (loop :for p :in '(2 2.0 1/2) :do
             (format t "(expt ~A ~A) ~20T= ~A~%" b p (expt b p))))
(expt 2 2)          = 4
(expt 2 2.0)        = 4.0
(expt 2 1/2)        = 1.4142135
(expt 2.0d0 2)      = 4.0d0
(expt 2.0d0 2.0)    = 4.0d0
(expt 2.0d0 1/2)    = 1.4142135623730951d0
(expt -2 2)         = 4
(expt -2 2.0)       = 4.0
(expt -2 1/2)       = #C(8.6595606e-17 1.4142135)

We see that in Common Lisp, the expt function can take a variety of possibly mixed input parameter types, and produce a variety of result types, where input and output types in each invocation need not be related (at least in some intrinsic sense, though they are through a series of rules in the Common Lisp standard). In general, this type of behavior won’t happen in ordinary Coalton programs. In fact, Coalton’s most general exponentiation function pow requires that the input and output types are all the same.

However, not all is peachy in Common Lisp. The expt function is not extensible. It is locked in to the data types and methods of computation that are stipulated by the Common Lisp standard. If you happen to make your own matrix or quaternion or gaussian-integer classes in Lisp, you’ll have no luck using expt with them. The best you can do is make your own function.

In Coalton, we have no such issue. In fact, Coalton code routinely defines its own number types for particularly advanced mathematical applications, without sacrificing efficiency in any way, since Coalton can statically inline custom arithmetic automatically and without fuss.

The goal of this post is intended more to be a tutorial or quick-reference to numbers and math in Coalton, and less a comprehensive justification of the state of affairs. We also don’t list every function and method available to users.

The standard library reference can be found here which has all of the latest information about available functions. It is updated as the main branch is updated.

We are assumed to be in the coalton-user package. A variety of symbols in this post are actually in specific standard library packages, usually coalton-library/math/*. These are listed explicitly in the library reference.

The concrete types

Signed integers: I8, I16, I32, I64, and a machine-sized IFix. Arithmetic errors when out-of-bounds.

Unsigned integers: U8, U16, U32, U64, and a machine-sized UFix. Arithmetic wraps around.

Unlimited-sized integer: Integer (but these are efficiently represented when they’re machine-sized)

Integer literals are “overloaded”, they can represent whatever integer type so long as the surrounding context permits. Lacking definitive context, they’re defaulted to Integer. One can construct the integer 5 of type T using (the T 5).

Machine float types: Single-Float and Double Float.

Float literals are as they are in Common Lisp, like 1.0f0 and 1.0d0.

Big floats: Big-Float

The number of bits of precision a Big-Float represents is controlled by with-precision or set-precision!. There is no general literal syntax, but all standard types can be converted into Big-Floats.

Rational numbers: Fraction

Fraction literals use Common Lisp ratio syntax, like 1/2. It’s also valid to write (the Fraction 2), but note that this is not a conversion of 2, but rather an interpretation of the literal 2. Fractions can be dynamically constructed from integers with mkFraction.

Almost every number type can be dynamically constructed using the fromInt function.

Rudimentary classes

In much of the remainder of this post, we’re going to summarize various classes. We write Cls :a to mean a class Cls parameterized by a type :a. Writing Cls :a indicates that :a is an instance of Cls.

Eq :a means that :a can be compared for mathematical equality with == or inequality with /=.

Ord :a means that :a can be compared with >, >=, <, and <=.

Into :a :b means that :a can be converted faithfully into :b (like I8 to I16) with the into function.

TryInto :a :b means that :a can sometimes be converted into :b (like I16 to I8) with the tryInto function, but not always and may error. This function returns a Result String :b, where the String is a failure message if the conversion wasn’t possible.

Bounded :a means that :a has a minimum value minBound and a maximum value maxBound. These are values, not functions, whose type is inferred from context.

> (cl:use-package '(:coalton-library/math/bounded))
COMMON-LISP:T
> (coalton (make-list (the I16 minBound)
                      (the I16 maxBound)))
(-32768 32767)

Transfinite :a means that :a has NaN and/or infinite member values, which are accessed via nan and infinity. Numbers can be checked with nan? and infinity?.

Arithmetic

Num :a means you can do ordinary addition +, subtraction -, and multiplication * with :a. Note that (- x) does not negate x, but rather curries (fn (y) (- x y)). Additionally, Num requires objects of :a can be constructed from Integer values with fromInt.

Arithmetic is always closed, and there is never implicit casting done by arithmetic operations. You must convert explicitly. Note that

> (coalton (+ 0.5 10))
10.5

works not because of an implicit cast, but because the literal 10 is statically understood to represent a Single-Float and is interpreted as such at compile-time.

Reciprocable :a is a Num type that has multiplicative inverses (with reciprocal) for most elements, and thus supports closed division with /.

Dividable :a :b means that two elements of :a divide to produce a :b. For instance, (Dividable Integer Fraction) means that Integers can divide to produce Fractions. There might be more than one instance for a given :a-type. This non-closed division is done with general/. Of course, if Reciprocable :a has an instance, then Dividable :a :a is automatically true.

Remainder :a is a Num type that looks roughly like an integral domain, somewhere that quotients (quo x y) (or (div x y)) and remainders (rem x y) (or (mod x y)) can be computed. Note that the quotients and remainders have to be expressible as values in :a.

Integral :a is a Remainder type that can be converted to an integer with toInteger.

A Num object x can be raised to the power of a non-negative Integral object p with (^ x p).

A Reciprocable object x can be raised to the power of an Integral object p with (^^ x p).

Both ^ and ^^ have to be “closed” in the first argument: powers of integers have to result in integers, powers of floats have to return floats. These functions are nothing more than repeated multiplication of a value (or its reciprocal).

Quantizable :a is a type that allows for rounding with floor and ceiling.

Real :a is a Quantizable and Num type, allowing us to approximate a value x of type :a as a Fraction to an arbitrary n bits of precision with (real-approx n x).

Rational :a is a Real and Ord type that allows us to represent any value of :a exactly (in the sense of into or tryInto) as a fraction with to-fraction, and perhaps as a simpler fraction with best-approx. If this does not make sense, consider that a value might be equally well approximated by a variety of fractions:

> (cl:import '(coalton-library/math/real:to-fraction 
               coalton-library/math/real:best-approx
               coalton-library/math/real:inexact/))
COMMON-LISP:T
> (coalton (to-fraction 0.1d0))
3602879701896397/36028797018963968
> (coalton (best-approx 0.1d0))
1/10
> (coalton (inexact/ 1 10))
0.1d0
> (coalton (inexact/ 3602879701896397 36028797018963968))
0.1d0

With these classes, we have all sorts of convenient functions, including rounding functions floor, ceiling, round, truncate, round-half-up, and round-half-down; as well as convenient division functions, like safe/, floor/, ceiling/, round/, exact/, and inexact/.

Complex numbers

Complex :a means two things!

Complex :a is a type representing a complex number whose real and imaginary components are of type :a. The underlying representation of this type is not defined. (See below.)
Complex :a is a class representing objects that behave like complex numbers, which allow construction using a method called complex, and extraction of rectangular parts with real-part and imag-part.

The imaginary unit is ii.

There are currently no complex number literals, but they can be constructed with the method complex. Their values are represented (when possible) as Common Lisp complex number types.

> (coalton (complex 1.0 2.0))
#C(1.0 2.0)
> (coalton (complex (the Big-Float 1) (the Big-Float 2)))
#.(COALTON-LIBRARY/MATH/COMPLEX::%COMPLEX .10000000000000000e1 .20000000000000000e1)

Both of these values are technically internal representations that the user ought not be concerned with.

Polar :a is a Complex and Num that supports the extraction of the phase of a complex number, and its decomposition into magnitude and phase with the polar method. The function magnitude. Though we often work with complex numbers whose rectangular parts are any real number, that doesn’t need to be the case. We can have lattices of discrete complex numbers whose real and imaginary part types can’t express the angles these numbers form.

Powers, roots, and logs

We’ve already seen ^ and ^^, but those are merely repeated multiplication. What if we have fractional powers?

Exponentiable :a are types that allow exp (the exponential function), pow (closed exponentiation), ln (the natural log), and (log b) (log base-b).

Radical :a are types that allow sqrt and nth-roots. The roots must be closed. An integer square root can be done with the function isqrt, which is not relevant to the Radical class.

In both of these cases, the operations are closed. That means (sqrt -2.0d0) will not result in a complex number. (By default, it results in nan.)

> (cl:use-package '(:coalton-library/math/elementary))
COMMON-LISP:T
> (coalton (sqrt -2.0d0))
#<DOUBLE-FLOAT quiet NaN>
> (coalton (sqrt (complex -2.0d0 0.0d0)))
#C(8.659560562354934d-17 1.4142135623730951d0)

Trigonometry

Trigonometric :a are types that support sin, cos, and tan; as well as their inverses asin, acos, and atan.

If we have a type that is both Trigonometric and Complex, then we get the cis function where (cis t) is $e^{it}$.

$\pi$ and elementary functions

Elementary :a is a type that is Reciprocable, Polar, Trigonometric, Exponentiable, and Radical. Despite the real grab bag of classes here, Elementary types represent values that can go into elementary functions. Moreover, if a type is Elementary, it means it has a representation of pi and the exponential number ee (which is $e\approx 2.71828$).

In addition to the aforementioned functions, we also get:

hyperbolic trig: sinh, cosh, tanh, asinh, acosh, and atanh
with Ord, the two-argument arctangent: atan2
free implementation of (Elementary (Complex :a)) and all of its predecessor classes

Big floats

Arbitrary precision floats are supported in Coalton, but currently requires loading a separate (but included) library:

(ql:quickload :coalton/library/big-float)
(cl:use-package '(:coalton-library/big-float))

This gives us a Big-Float type, as well as the following functions for controlling precision:

(with-precision n f) calls the function f with Big-Float precision set to n bits.
(set-precision! n) globally sets the precision of Big-Floats to n.
(get-precision) gets the current precision in bits.

For exmaple,

> (coalton (the Big-Float (* 4 (atan 1))))
.31415926535897931e1
> (coalton (set-precision! 500))
COALTON::UNIT/UNIT
> (coalton (the Big-Float (* 4 (atan 1))))
.31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081283e1

Similarly, we can control the rounding mode, which is described by the RoundingMode enumeration: rndn (round down), rndz (round toward zero), rndu (round up), etc.

(with-rounding m f) calls the function f with the rounding mode set to m.
(set-rounding-mode! m) globally sets the rounding mode to m.
(get-rounding-mode) gets the current rounding mode.

Both precision and rounding can be controlled with with-rounding-mode for the extent of a function call.

Precision of big floats

The functions with-precision and set-precision! set the precision of the floats themselves. It does not ensure precision of the results. For example, lets first set our precision to 100 bits (about 30 decimal digits).

> (coalton (set-precision! 100))
COALTON::UNIT/UNIT

Now let’s compute $\sin \pi$, which we know should be zero:

> (coalton (the Big-Float (sin pi)))
.12246467991473531772260659322748e-15

We see we got $0.122\times 10^{-15}$, which is about half of the number of correct digits allowed by our precision.

How about $\sin (10^{1000} \pi)$, which should also be zero?

> (coalton (the Big-Float (sin (* (pow 10 1000) pi))))
.34821834409748947095450130704533e0

The state of affairs is even worse, we have no correct digits after the decimal point!

Just like ordinary floats, Big-Floats demand care when writing mathematical code. The good news, though, is that you’re free to experiment by changing the precision, possibly upping it until you find convergence.