Canonical form

also: normal form

A representation chosen so that mathematically equal objects are structurally identical. Once expressions have one, deciding equality is a comparison rather than a search, and a zero test is a look at the representation rather than an attempt to prove an identity. It is the property every layer of a CAS is built to preserve.

A representation is canonical when mathematically equal objects are structurally identical. That one property is what turns hard questions into cheap ones:

Before and after.

equality       a search for a proof    ->  a structural comparison
zero test      an identity to prove    ->  a look at the representation
hashing        impossible              ->  well defined
caching        unreliable              ->  correct by construction

The zero test is the load-bearing one. Almost every algorithm above the representation branches on whether something is zero, and without a canonical form none of them can, which is why a CAS invests so heavily in maintaining it.

It is stronger than a normal form, which only requires that a rewriting process terminates. Canonical means the result is unique, so $x + y$ and $y + x$ must arrive at the same expression, not merely at two irreducible ones.

Order of construction stops mattering. Verbatim from the REPL.

> x + y + x
y + 2*x
> tree x + y + x
(+ y (* 2 x))

The limit is Richardson's theorem: for expressions with exponentials, logarithms, absolute values and a transcendental constant, deciding equality with zero is undecidable. So no CAS has a canonical form for everything, and the practical design is to keep one for a large well-behaved fragment, polynomials and rational functions, and fall back to heuristics outside it.

Building a CAS in OCaml Part 2Exact rationals over the bignums, an n-ary expression tree, and the automatic simplifier that turns it into a canonical form.