# LISP - 4 bit adder

## The problem

For this sample program we will simulate a four bit adder chip by constructing it from a series of AND, OR and NOT gates. See Rosetta Code for full details.

## Constructing the solution

LISP provides AND, OR and NOT functions and we can use `T` and `NIL` to represent true and false. First task is to make an XOR gate:

``````(DEFUN XOR (A B)
(OR (AND A (NOT B))
(AND B (NOT A))))
``````

Next we make a half-bit and single bit adder. These return a result and a carry bit which can be fed into the next stage of the full adder. We create a cons cell containing the result and carry bit for the return type.

``````(DEFUN HALF-ADDER (A B)
(CONS (XOR A B) (AND A B)))

(PROG (S1 S2)
(SETQ S2 (HALF-ADDER (CAR S1) B))
(CONS (CAR S2) (OR (CDR S1) (CDR S2)))))
``````

We then connect the adders together to form a four bit adder. As this version of LISP’s `NTH` returns the remainder of the list from the given position, we need a convenience function `BIT` to access individual values.

``````(DEFUN BIT (L N)

(PROG (X1 X2 X3 X4)
(SETQ X1 (ADDER (BIT A 3) (BIT B 3) NIL))
(SETQ X2 (ADDER (BIT A 2) (BIT B 2) (CDR X1)))
(SETQ X3 (ADDER (BIT A 1) (BIT B 1) (CDR X2)))
(SETQ X4 (ADDER (BIT A 0) (BIT B 0) (CDR X3)))
(CONS (MAPCAR 'CAR (LIST X4 X3 X2 X1)) (CDR X4))))
``````

The adder takes as input, and returns, a list of binary values, eg `(NIL T NIL T)` for 5. It would be convenient to have a function that can convert an integer into such a list: we can do this recursively.

``````(DEFUN DEC-BIN (X)
(PROG (BIT)
(SETQ BIT (NOT (ZERO (LAND X 1))))
(COND ((LESS X 2) (LIST BIT))
(T (APPEND (DEC-BIN (SHIFT X -1)) BIT)))))

;; Pad binary list L to length N by adding NILs in front
(COND ((LESS (LENGTH L) N)
(REPEAT '(SETQ L (CONS NIL L)) (SUB N (LENGTH L))))
(T L)))
``````

Finally, we write a test function to take two integers (assuming each is between 0 and 15) and add them, printing the sum:

``````(DEFUN TEST-ADDER-4 (A B)
(PROG (AB BB RES)
(SETQ AB (PAD 4 (DEC-BIN A)))
(SETQ BB (PAD 4 (DEC-BIN B)))
(PRIN1 AB) (PRIN1 '+) (PRIN1 BB)
(PRIN1 '=) (PRIN1 (CAR RES))
(PRIN1 'carry)  (PRIN1 (CDR RES))
(TERPRI)))

``````

Here `PRIN1` prints a single item and a space; `TERPRI` ends the current line.

## Getting it working

The LISP REPL helps here, as you can revise functions and test them until they work; this was fairly simple to get working, though `DEC-BIN` was tricky until I separated out PAD into its own function. I struggled with the LISP editor and found it easier to apply changes back to the file using `*EDIT` as each was done.

Let’s see it in action:

``````# \$run *lisp scards=4bitadd.l
# Execution begins   20:02:38
WELCOME TO LISP/MTS
>    XOR
>    BIT
>    DEC-BIN
>    (NIL NIL T T) + (NIL NIL T NIL) = (NIL T NIL T) carry NIL
>    NIL
# Execution terminated   20:02:38  T=0.007
``````

## Final thoughts on MTS LISP

I like Lisp a lot and even though this is a very basic Lisp compared to Common Lisp (or even Emacs Lisp) it still feels a lot higher level than the ALGOL/FORTRAN family of languages we have seen so far. One issue that we don’t have, as we are running on fast modern computers, is speed: LISP was much slower than FORTRAN for numeric work and garbage collection was very slow.

In the next post, which will be in mid-April, we’ll look at the other LISP in MTS - UTILISP.

## Further information

Full source code for this program is on github.