# Ivory: Sums And Products

We tend to learn about sums (“adding numbers”) quite early, either when starting school or even before. We also learn about products (“times-ing numbers”) shortly after. We often represent each using a table, to show their patterns. For example:

We can generalise these ideas of sum and product to much more than
simple numbers. To do so we have to decide which aspects to keep, and
which to ignore. In other words, what is the “essence” that makes the
above tabulations a sum and a product? Which things *cannot* be
considered as sums or products? Whilst we’re at it, what’s the actual
*distinction* between a “sum” and a “product”?

### Representing Sums And Products in Scheme

Ivory will represent sums and products as “uninterpreted function
symbols”, i.e. as lists like `'(+ 1 2)`

or `'(× 3 4)`

.
This page defines various normalisation procedures, to reduce such lists
into a unique normal form.

## Types

We can think of addition and multiplication as *operations* or
*functions* which transform “input values” into an “output
value”. A fundamental aspect of these values is their *type*:
what sort of things are we talking about?

For the addition and multiplication we learn in school, all of the
values are *numbers*; i.e. they “have type `number`

”.
Numbers can be “literal”, like `12`

; or a
(named) “variable” which *represents* some number, like `x`

; or, crucially, they can be the
*output* of some *other* numerical operation, like `(+ 1 2)`

.

Having the same type for inputs and outputs allows sums and products
to be *nested* in arbitrary ways: with the output of one used as
the input of another, forming “trees”:

This is a crucial aspect of sums and products. An operation which
*doesn’t* output the same type as its inputs, or which combines
inputs of different types, is not usually considered a sum or a
product.

## Laws of Algebra

We can characterise operations *algebraically* by stating
“laws”: equations which an operation always satisfies, regardless of its
inputs. This latter aspect can be represented by using variables for
inputs (we’ll use the names `a`

, `b`

and
`c`

), and stating the laws “for all” values of those
variables. (Programmers may also know these as invariants
or properties).

Since these laws state that different forms of sums and products are equal, and our goal with Ivory is to represent all numbers in a unique normal form, we will choose one form for each law, and rewrite the other equal forms into that one.

### Associativity

This law states that sums-of-sums, or products-of-products, do not
depend on how they are nested; so long as the inputs occur in the same
order from left-to-right. This justifies the application of
`+`

and `×`

to *arbitrarily-many* inputs,
which are equivalent to nested operations (but don’t require an
arbitrary choice of branching structure).

#### Implementing Associativity

We will normalise such nested operations by flattening them, using the following procedure:

```
define (normalise:associative normalise ≤ n) (match n
(;; Match nested operations; bind the inner operation's inputs to xs, and
;; append them to the outer operation's other inputs (pre and suf)
[(cons '+ (app (split +?) (list pre (cons '+ xs) suf)))
cons '+ (append pre xs suf)))]
(changed (
[(cons '× (app (split ×?) (list pre (cons '× xs) suf)))
cons '× (append pre xs suf)))]
(changed (
[n (unchanged n)]))
```

These make use of a few trivial helper functions:

```
;; Predicates for spotting products and sums
define (×? n) (and (pair? n) (equal? '× (car n))))
(define (+? n) (and (pair? n) (equal? '+ (car n))))
(
;; Indicates whether a value was/wasn't in normal form, and hence may need
;; further normalising.
define (unchanged x) (values x #f))
(define ( changed x) (values x #t)) (
```

More interestingly, we use the `split`

function to split
up a list (above, we’re splitting up the inputs of a sum or product), by
finding an element `y`

that satisfies a given predicate
(above, the predicates are `+?`

and
`×?`

, to spot a nested sum or product). The result also
includes all the elements occuring before `y`

(which we call `xs`

) and all those following `y`

(which we call `ys`

). If no such element is found, we
return `#f`

(and hence the above clauses won’t match):

```
;; Return #f when no element of xs satisfies pred, otherwise return (list a b c)
;; where (append a (cons b c)) = xs, and (pred b)
(define ((split pred) xs)
(match/values (splitf-at xs (negate pred))
[(xs (cons y ys)) (list xs y ys)]
[(_ _ ) #f]))
```

### Identity

In mathematics, the word “identity” refers to something that leaves a
value unchanged. Here we consider two sorts of identity. Firstly, the
*identity function* (or operation) is that which outputs its
input. Since a sum with only a single input does not add anything to it,
the output equals that input; and hence that sum is an identity
function. Likewise, a product with only a single input does not multiply
it by anything, so the output equals that input, and the product too is
an identity function. These facts allow us to “unwrap” sums or products
of a single value when normalising expressions.

The second sort of identity is a *value*, whose inclusion in
the inputs of an operation does not change the output. We know from
associativity that nested operations are equivalent to a single
operation with all the same inputs; hence an *empty* operation is
the identity value, since it does not affect the inputs (only the
nesting). For example, `(+ a (+))`

is (by associativity) the same as `(+ a)`

, and
hence the same as `a`

(since, as
described above, the sum of a single input leaves it unchanged). Here is
the same example shown graphically (with a half-line `╵`

to
indicate no inputs):

```
+ +
┌──┴──┐ = │ = a
a + a
╵
```

Hence `(+)`

is the
identity value for sums, and a similar argument shows that `(×)`

is the identity value for
products.

Now, we know from primary school that adding `0`

to a
number *also* leaves it unchanged; so zero must *also* be
an identity for addition. In which case, what happens if we add zero to
an empty sum, like `(+ 0 (+))`

?
Adding `0`

leaves the empty sum unchanged, so the result is
`(+)`

; yet
we also showed that adding `(+)`

will leave
the `0`

unchanged, so the result is *also* `0`

. This only
makes sense if both of these are the same value! We can use the same
approach to find that `(×)`

and
`1`

must be
the same value. Hence:

#### Implementing Identity

`define (normalise:identity normalise ≤ n) (match n (`

Unwrapping a single-input sum or product is easy:

```
;; A singleton sum or product outputs its only input
[(list '+ n) (changed n)]
[(list '× n) (changed n)]
```

Since the identity values can be written in two ways (`0`

or `(+)`

; `1`

or `(×)`

) our normal form needs to choose
one for each. We’ll use the empty operation, since that exposes
structure that other clauses can use, e.g. to allow the existing
associativity clauses to simplify multiplication by `1`

and
addition of `0`

:

```
;; Empty sums and products are their identity elements
[0 (changed (list '+))]
[1 (changed (list '×))]
[n (unchanged n)]))
```

### Distributivity

So far all of these laws have applied equally to both sums and
products. Not only does distributivity apply differently to each, but it
tells us which operations act like sums, and which act like products.
Specifically, it says that multiplying a sum, like `(× 2 (+ 3 7 19))`

,
is the same as multiplying each element of that sum individually, like
`(+ (× 2 3) (× 2 7) (× 2 19))`

.
We say that multiplication “distributes over” addition. The same is not
true if we switch the role of `+`

and `×`

(you may
like to convince yourself of this by finding a counter-example)!

Notice that distributing a multiplication doesn’t change its order:
distributing a multiplication “on the left”, like `(× a ...)`

,
produces a sum of products which *also* multiply on the left; and
vice versa “on the right”, like `(× ... a)`

. This
isn’t relevant for types like `integer`

, since their product
also obeys the *commutativity law*, that `(= (× a b) (× b a))`

;
however, we’ll soon encounter numbers which *don’t* commute, so
it’s important that we don’t swap things around by accident!

#### Absorption

Distributivity has an important relationship to our identity laws.
When a product contains a sum, distributivity says that all of the
product’s other inputs can be distributed over the inputs of that sum.
If that sum has *no* inputs, the result will be an empty sum; we
say that the empty sum has absorbed the
products.

We showed that an empty sum must equal `0`

, so this
“absorption” behaviour tells us that products with zero occuring as an
input will always output zero (regardless of any other inputs).

#### Implementing Distributivity

Distributivity can help us normalise expressions, by replacing one of
these forms with the other. We’ll choose the sum-of-products form to be
normal, since it’s easy to convert *into* that form by
distributing multiplications over sums; going the other way, to produce
a product-of-sums, would require factorising,
which is notoriously slow!

We need to be careful not to change the order of any multiplications;
to ensure this, when a sum is multiplied by many values we’ll only
distribute those which occur immediately to its left or right; this can
be repeated until all of the values have been distributed into the sum.
For example, given a product like `(× a b (+ c d))`

we will first distribute `b`

, to get `(× a (+ (× b c) (× b d)))`

,
then distribute `a`

to get `(+ (× a b c) (× a b d))`

.

To find a sum and its immediate neighbour in a product, we use a
modified version of the above `split`

function: `split-pair`

will split a list at a
*pair of consecutive elements* which satisfy the given
*binary* predicate:

```
;; Check (pred (nth 0 xs) (nth 1 xs)), (pred (nth 1 xs) (nth 2 xs)), etc. until
;; we find a neighbouring pair elements a & b which pass the predicate, then
;; return (list pre a b suf), where (append pre (cons a (cons b suf))) = xs.
;; If no such pair of elements is found, return #f.
define ((split-pair pred) xs)
(
(define/match (go xs ys)[((cons x xs) '() ) (go xs (list x))]
[('() ys ) #f]
[((cons x xs) (cons y ys))
if (pred y x)
(list (reverse ys) y x xs)
(cons x (cons y ys))))])
(go xs (
(go xs '()))
```

We use `split-pair`

to define
two separate clauses. We first look through the inputs of a product, for
a neighbouring pair of the form `(cons '+ xs)`

(a sum with inputs `xs`

) and any
value `y`

. If found, we remove both
from the product’s inputs, and insert a sum that’s had the
multiplication by `y`

distributed
across its inputs (i.e. replacing each element `x`

of `xs`

with `(× x y)`

):

```
define (normalise:distributivity normalise ≤ n) (match n
([(cons '× (app (split-pair (lambda (x y) (+? x))) ;; A sum followed by y
list pre (cons '+ xs) y suf)))
(;; Keep the product, in case pre/suf contain more elements
cons '× (append
(changed (
pre;; Multiply all of xs's summands by y on their right
list (cons '+ (map (lambda (x) (list '× x y)) xs)))
(
suf] )))
```

Next we do the same when the *second* value is a sum:

```
[(cons '× (app (split-pair (lambda (x y) (+? y))) ;; x followed by a sum
list pre x (cons '+ ys) suf)))
(;; Keep the product, in case pre/suf contain more elements
cons '× (append
(changed (
pre;; Multiply all of ys's sumands by x
list (cons '+ (map (curry list '× x) ys)))
(
suf]
)))
[n (unchanged n)]))
```

Notice that we do not have to implement absorption separately, since
the identity clauses will replace `0`

with
`'(+)`

, and the two clauses above will cause it to absorb all
of a product’s inputs. In particular, their results use `(map ... xs)`

,
which will return an empty list when `xs`

is empty!

### Commutativity

Addition and multiplication of numbers are both *commutative*,
meaning that the order of their inputs does not affect their output. We
will require sums to be commutative, but we will not assume that
products are; since that turns out to be quite restrictive. We can use
commutativity to normalise sums, by sorting their inputs into a
consistent order.

#### Implementing Commutativity

The following clause implements a form of Bubble Sort, by spotting a pair of neighbouring inputs which are in the wrong order:

```
(define (normalise:commutativity normalise ≤ n) (match n
[(cons '+ (app (split-pair (lambda (x y) (not (lex≤ x y))))
(list pre x y suf)))
(changed (append '(+) pre (list y x) suf))]
[n (unchanged n)]))
```

Note that we cannot sort the inputs based on their *numerical
value*, since we will encounter multi-dimensional values which don’t
have a linear ordering. Instead we will compare the *literal
syntax* of expressions, known as a lexicographical
ordering:

```
;; Compare expressions lexicographically (i.e. via "dictionary order" of their
;; literal syntax)
define (lex≤ . args)
(define (to-string x)
(let ([o (open-output-string)])
(write x o)
(
(get-output-string o)))string<=? (map to-string args))) (apply
```

## Final Pieces

Our `normalise`

functions need a few more clauses to be
complete. Firstly, if we find a sum or product containing ordinary
Racket `number`

s, then we should add/multiply them using
Racket’s usual addition/multiplication operations:

```
define (normalise:sums-and-products normalise ≤ n) (match n
(;; Sums of multiple Racket numbers simplify via addition
[(cons '+ (app (split number?)
list pre x (app (split number?)
(list mid y suf)))))
(append (list '+ (+ x y)) pre mid suf))]
(changed (
;; Products of multiple Racket numbers simplify via multiplication
[(cons '× (app (split number?)
list pre x (app (split number?)
(list mid y suf)))))
(append (list '× (× x y)) pre mid suf))] (changed (
```

If we have a sum or product which doesn’t match *any* of the
above clauses, we should try normalising its inputs recursively:

```
;; Recurse through the elements of a sum or product to see if any change
[(cons (and op (or '+ '×)) xs)
[result (list op)]
(for/fold ([any-changed #f])
[(x changed) (map normalise xs)])
(values (snoc result x) (or any-changed changed)))] (
```

Finally, a value which doesn’t match any of the clauses defined on this page should be left unchanged:

```
;; Otherwise there's nothing left to do
[n (unchanged n)]))
```

## Code

Here’s a URI containing all of the Racket code generated by this post:

## Test results

```
raco test: (submod "sums-and-products.rkt" test)
✓ property ×-matches-* passed 100 tests.
✓ property integer?-implies-rational? passed 100 tests.
✓ property rational?-implies-number? passed 100 tests.
✓ property natural?-implies-integer? passed 100 tests.
✓ property natural-is-closed passed 100 tests.
✓ property lex≤-is-reflexive passed 100 tests.
✓ property lex≤-is-total passed 100 tests.
✓ property lex≤-is-transitive passed 100 tests.
✓ property split-works passed 100 tests.
✓ property split-pair-works passed 100 tests.
31 tests passed
```