# 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)))
(DEFUN ADDER (A B C0)
(PROG (S1 S2)
(SETQ S1 (HALF-ADDER C0 A))
(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)
(CAR (NTH L (ADD1 N))))
(DEFUN ADDER-4 (A B)
(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
(DEFUN PAD (N L)
(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)))
(SETQ RES (ADDER-4 AB BB))
(PRIN1 AB) (PRIN1 '+) (PRIN1 BB)
(PRIN1 '=) (PRIN1 (CAR RES))
(PRIN1 'carry) (PRIN1 (CDR RES))
(TERPRI)))
(TEST-ADDER-4 3 2)
```

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
> HALF-ADDER
> ADDER
> BIT
> ADDER-4
> DEC-BIN
> PAD
> TEST-ADDER-4
> (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.