| 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 Dth 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:
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 |