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.

Comments

comments powered by Disqus