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
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)
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.
Full source code for this program is on github.