previous: code grinding | contents | next: logic programming |

Even purely symbolic LISP is a Turing-complete language, so
natural numbers and their basic operations can be implemented in
it, although not very efficiently. The term
`12 × 34 + 567`, for instance, would be calculated
as follows:

* (load 'src//nmath) t * (plus (times '(1 2) '(3 4)) '(5 6 7)) (9 7 5) * _

The implementation works rather well and even implements unbounded
integers ("bignums"). It is not even *that* slow on modern
hardware: on the author's 750MHz notebook computer, calculating
`(expt #2 #100)`

takes 1.2 seconds and truthfully spits out

(1 2 6 7 6 5 0 6 0 0 2 2 8 2 2 9 4 0 1 4 9 6 7 0 3 2 0 5 3 7 6)

Kilo LISP offers a nicer notation
for writing lists consisting of single-character symbols exclusively.
For instance, `#12345`

equals `'(1 2 3 4 5)`

. This
notation is particularly practical for numbers. In the
previous chapter it was used for base-1 numbers, so both
`#iiiii`

and `#12345`

would represent the number
5. In this chapter, `#12345`

represents the decimal integer
`12345` and `#iiiii`

denotes the base-1 number
`5`.

So how do arithmetics work in a language where the only relationship
between two objects is the identity operation, a.k.a. `eq`

?
The following snippets will illustrate how numbers are represented and
how addition is performed using only symbols.

As shown above, a number is a list of symbols that represent decimal digits. The digits themselves have no values, but can be tested for identity, e.g.:

* (eq '5 '5) t * (eq '5 '7) nil

This observation alone is enough to assign base-1 values to the digits and implement the successor (SUCC, N+1) and predecessor (PRED, N-1) functions as well as the test for the zero digit, DZEROP.

* (setq value (lambda (x) (cond ((eq x '0) nil) ((eq x '1) #i) ((eq x '2) #ii) ((eq x '3) #iii) ((eq x '4) #iiii) ((eq x '5) #iiiii) ((eq x '6) #iiiiii) ((eq x '7) #iiiiiii) ((eq x '8) #iiiiiiii) ((eq x '9) #iiiiiiiii) (else (error 'not/ a/ digit x))))) value * (setq pred cdr) pred * (value '5) (i i i i i) * (pred (value '5)) (i i i i)

The SUCC, PRED, and DZEROP functions assign values to the
digit symbols `0`

...`9`

. This was the hard
part! The rest is elementary school-level arithmetic.

When adding two numbers on a sheet of paper, what is basically
done is to slide a *decimal full adder* over the operands:

<------- +-+ 2 3 |4| + 7 8 |9|+0 -------|-|-- |3|+1 +-+

A full adder adds two digits and a carry digit and yields a result digit and a new carry digit that will be fed to next full adder operation. In the above example, it maps the input (4,9,0) to (3,1), meaning 4+9+0=3, carrying 1 to the next operation.

There is one problem, though: adding digits requires the "add" operation, but the purpose of the entire exercise is to implement addition in the first place. The classic bootstrapping problem. However, since the domain of the full adder function is small (0..9 × 0..9), it can be implemented using table lookup. The result of 4+9 can be looked up in the following table by moving to the 4th row and then to the 9th column (rows and columns start at 0):

(setq sums '(((0.0) (1.0) (2.0) (3.0) (4.0) (5.0) (6.0) (7.0) (8.0) (9.0) (0.1)) ((1.0) (2.0) (3.0) (4.0) (5.0) (6.0) (7.0) (8.0) (9.0) (0.1) (1.1)) ((2.0) (3.0) (4.0) (5.0) (6.0) (7.0) (8.0) (9.0) (0.1) (1.1) (2.1)) ((3.0) (4.0) (5.0) (6.0) (7.0) (8.0) (9.0) (0.1) (1.1) (2.1) (3.1)) ((4.0) (5.0) (6.0) (7.0) (8.0) (9.0) (0.1) (1.1) (2.1)(3.1)(4.1)) ((5.0) (6.0) (7.0) (8.0) (9.0) (0.1) (1.1) (2.1) (3.1) (4.1) (5.1)) ((6.0) (7.0) (8.0) (9.0) (0.1) (1.1) (2.1) (3.1) (4.1) (5.1) (6.1)) ((7.0) (8.0) (9.0) (0.1) (1.1) (2.1) (3.1) (4.1) (5.1) (6.1) (7.1)) ((8.0) (9.0) (0.1) (1.1) (2.1) (3.1) (4.1) (5.1) (6.1) (7.1) (8.1)) ((9.0) (0.1) (1.1) (2.1) (3.1) (4.1) (5.1) (6.1) (7.1) (8.1) (9.1))))

In case the carry digit is 1, the result can be found in the entry to the right or in the same column in the row below.

The
DTH function finds the D^{th} element
of a list, where D is a base-1 number, as described above.

(setq dth (lambda (d lst) (if (dzerop d) (car lst) (dth (pred d) (cdr lst)))))

The DPLUS function uses DTH to implement the full adder via table lookup, where A and B are the operands and C is the carry digit:

(setq dplus (lambda (a b c) (let ((row (dth (value b) sums))) (if (eq c '1) (dth (value a) (cdr row)) (dth (value a) row)))))

The PLUS function, which is a bit more complex, "slides" the full adder over two operands, adding their digits and propagating the carry digit. It distinguishes four cases:

- if the end of operand A is reached
*and*the end of operand B is reached, it attaches the carry digit to the result R and returns it - if the end of operand A is reached, but the end of operand B is not reached, it fills A with leading zeros
- if the end of operand B is reached, but the end of operand A is not reached, it fills B with leading zeros
- otherwise, it looks up the result digit and the new carry digit in the table, adds the result digit to the result R, and moves to the next pair of digits

Theoretically, the PLUS function adds two decimal numbers of any size. The actual size of the numbers is only limited by available node space and time allocated to the computation.

* (plus #234 #789) (1 0 2 3) * _

The DIFF ("difference") function is
implemented in basically the same way as PLUS, but it uses a
different table for lookup. Also, its
result has to be normalized by
removing leading zeros, so that it does not return `0001`
for `1000-999`.

* (diff #1023 #789) (2 3 4) * (diff #0 #1) negative * _

Because the NMATH package implements *natural numbers*, the
DIFF function returns the symbol NEGATIVE when its result would be
negative. This fact can be used to implement the numeric comparison
predicates LESS,
GRTR, etc:

(setq less (lambda (a b) (eq 'negative (diff a b)))) (setq grtr (lambda (a b) (less b a))) (setq lteq (lambda (a b) (not (less b a)))) (setq gteq (lambda (a b) (not (less a b))))

There is no "equal" predicate, because the EQUAL function of LISP can be used to test lists of digits for equality.

The TIMES and DIVIDE functions implement multiplication and floored division:

* (times #123 #456) (5 6 0 8 8) * (divide #56000 #456) ((1 2 2) 3 6 8) * _

DIVIDE returns a pair consisting of the floored quotient in the
car field and the division remainder in the cdr field. In the above
example it indicates that `56000 = 122 × 456 + 368`.

In principle, this implementation can be extended to cover integers, rational numbers, real number, complex numbers, etc. However, it would make more sense to implement some native numeric data types first.

But then, not every interesting problem that can be solved with LISP requires numbers!

previous: code grinding | contents | next: logic programming |