"He who refuses to do arithmetic is doomed to talk nonsense." ~ John McCarthy

McCarthy Math

by Harry Prevor

In early 1959, John McCarthy wrote a little paper that defined one of the first ever programming languages, LISP. In just nine simple functions (QUOTE, ATOM, EQ, CAR, CDR, CONS, COND, LAMBDA, LABEL), he created the basis from which all LISP-like languages are still founded upon today, including Scheme, Common Lisp, Emacs Lisp, Clojure, and (debatably) even JavaScript. The language was so succinct that modern-day programmer orlp was able to fully implement an interpreter for it in Python in just 770 bytes.

That being said, the man was still not without his critics. Though the language takes pride in its simplicity, the bare-bones version of LISP presented in the original paper lacks every type that isn't a list or an atom — meaning, by default, you don't get numbers. In this article, I'll try to show that with some clever compositions of the above functions, you can re-create the basic arithmetic functions from scratch without too much difficulty, and even display the results in the base-10 format we all know and love, all without a primitive "number" type.

In McCarthy's LISP, every expression must be either evaluate to be an atom which can consist of capital letters, numbers, and spaces:

HI I AM AN ATOM

Or, it may be a list of atoms, delimited by commas and terminated by the special NIL form which is both an atom and a list (not shown because it is implied):

(HI I AM AN ATOM, I AM AN ATOM TOO)

As Paul Graham points out, the most intuitive way to go about representing numbers then, is to disregard the identifiers of the atoms themselves, and instead count how many items are in a given list:

(I, REPRESENT, THE, NUMBER, FIVE)

Then, our first operator addition can be constructed by the simple "list append" function:

(LABEL, ADD, (LAMBDA, (A, B), (COND, ((ATOM, A), B), ((QUOTE, T), (CONS, (CAR, A), (ADD, (CDR, A), B))))))

Or, in Pythonic psuedocode:


def add(a,b):
  if len(a) == 0:
    return b
  elif True:
    return [a[0]] + add(a[1:],b)

Using orlp's interpreter, we can verify this works by manually counting the length of the result:


> (ADD, (QUOTE, (THIS, IS, THREE)), (QUOTE, (PLUS, TWO)))
(THIS, IS, THREE, PLUS, TWO)

Now, counting out the length of every result can be tedious, and there is no primitive LENGTH function in McCarthy's LISP. But using the powerful COND operator, we can assign symbols to various different lengths, symbols like, say, the Arabic numerals:

(LABEL, LEN, (LAMBDA, (L), (COND, ((ATOM, L), (QUOTE, 0)), ((ATOM, (CDR, L)), (QUOTE, 1)), ((ATOM, (CDR, (CDR, L))), (QUOTE, 2)), ((ATOM, (CDR, (CDR, (CDR, L)))), (QUOTE, 3)), ((ATOM, (CDR, (CDR, (CDR, (CDR, L))))), (QUOTE, 4)), ((ATOM, (CDR, (CDR, (CDR, (CDR, (CDR, L)))))), (QUOTE, 5)), ((ATOM, (CDR, (CDR, (CDR, (CDR, (CDR, (CDR, L))))))), (QUOTE, 6)), ((ATOM, (CDR, (CDR, (CDR, (CDR, (CDR, (CDR, (CDR, L)))))))), (QUOTE, 7)), ((ATOM, (CDR, (CDR, (CDR, (CDR, (CDR, (CDR, (CDR, (CDR, L))))))))), (QUOTE, 8)), ((ATOM, (CDR, (CDR, (CDR, (CDR, (CDR, (CDR, (CDR, (CDR, (CDR, L)))))))))), (QUOTE, 9)), ((QUOTE, T), (QUOTE, TEN OR MORE)))))

(The function can be shortened somewhat by making helper routines that repeatedly apply CDR, but in the interest of education I'll use the verbose version here.) We can confirm it works for our above example:


> (LEN, (ADD, (QUOTE, (THIS, IS, THREE)), (QUOTE, (PLUS, TWO))))
5

With some help from our friend recursion, we can go in the reverse direction as well, creating lists of "I" atoms of a given single-digit length (we'll call it DIG, short for digit):

(LABEL, DIG, (LAMBDA, (D), (COND, ((EQ, D, (QUOTE, 1)), (CONS, (QUOTE, I), (QUOTE, NIL))), ((EQ, D, (QUOTE, 2)), (CONS, (QUOTE, I), (DIG, (QUOTE, 1)))), ((EQ, D, (QUOTE, 3)), (CONS, (QUOTE, I), (DIG, (QUOTE, 2)))), ((EQ, D, (QUOTE, 4)), (CONS, (QUOTE, I), (DIG, (QUOTE, 3)))), ((EQ, D, (QUOTE, 5)), (CONS, (QUOTE, I), (DIG, (QUOTE, 4)))), ((EQ, D, (QUOTE, 6)), (CONS, (QUOTE, I), (DIG, (QUOTE, 5)))), ((EQ, D, (QUOTE, 7)), (CONS, (QUOTE, I), (DIG, (QUOTE, 6)))), ((EQ, D, (QUOTE, 8)), (CONS, (QUOTE, I), (DIG, (QUOTE, 7)))), ((EQ, D, (QUOTE, 9)), (CONS, (QUOTE, I), (DIG, (QUOTE, 8)))), ((QUOTE, T), (QUOTE, NIL)))))

Now our addition example is even more straightforward to write:


> (LEN, (ADD, (DIG, (QUOTE, 3)), (DIG, (QUOTE, 2))))
5

While our addition function theoretically has no bounds, it still only 'works' (as in, displays itself correctly) on single-digit numbers. Our number system right now is "base infinity" if you will, but we've only written out the first ten symbols. We'll get to fixing that in a minute, but in the mean time let's go about implementing the other arithmetic functions, like, say, multiplication:

(LABEL, MUL HELPER, (LAMBDA, (A, B, R), (COND, ((ATOM, A), R), ((QUOTE, T), (MUL HELPER, (CDR, A), B, (ADD, B, R))))))

(LABEL, MUL, (LAMBDA, (A, B), (MUL HELPER, A, B, (QUOTE, NIL))))

In Python-like psuedocode, that would be the following:


def mul_helper(a,b,r):
  if len(a) == 0:
    return r
  elif True:
    return mul_helper(a[1:],b,add(b,r))

def mul(a,b):
  return mul_helper(a,b,[])

Aaand the verification:


> (LEN, (MUL, (DIG, (QUOTE, 3)), (DIG, (QUOTE, 2))))
6

Then subtraction is easy enough with the corresponding Python code to ease understanding:

(LABEL, SUB, (LAMBDA, (A, B), (COND, ((ATOM, B), A), ((QUOTE, T), (SUB, (CDR, A), (CDR, B))))))


def sub(a,b):
  if len(b) == 0:
    return a
  elif True:
    return sub(a[1:],b[1:])

Truncating integer division is a bit harder, but not that hard once you have a "less than" predicate function which we'll make first:

(LABEL, LESS, (LAMBDA, (A, B), (COND, ((ATOM, B), (QUOTE, NIL)), ((ATOM, A), (QUOTE, T)), ((QUOTE, T), (LESS, (CDR, A), (CDR, B))))))

(LABEL, DIV HELPER, (LAMBDA, (A, B, R), (COND, ((LESS, A, B), R), ((QUOTE, T), (DIV HELPER, (SUB, A, B), B, (CONS, (QUOTE, I), R))))))

(LABEL, DIV, (LAMBDA, (A, B), (DIV HELPER, A, B, (QUOTE, NIL))))


def less(a,b):
  if len(b) == 0:
    return False
  elif len(a) == 0:
    return True
  elif True:
    return less(a[1:],b[1:])

def div_helper(a,b,r):
  if less(a,b):
    return r
  elif True:
    return div_helper(sub(a,b),b,['I']+r)

def div(a,b):
  return div_helper(a,b,[])

Cool, now that we have the four basic arithmetic functions down, we have a basic one-digit (not reverse) Polish notation calculator that can solve most problems in a 3rd-grade math book! Like, say, (((9 + 4) ÷ (7 − (1 + 1))) × 3) − (2 + (1 + 1)):


> (LEN, (SUB, (MUL, (DIV, (ADD, (DIG, (QUOTE, 9)), (DIG, (QUOTE, 6))), (SUB, (DIG, (QUOTE, 7)), (ADD, (DIG, (QUOTE, 1)), (DIG, (QUOTE, 1))))), (DIG, (QUOTE, 3))), (ADD, (DIG, (QUOTE, 2)), (ADD, (DIG, (QUOTE, 1)), (DIG, (QUOTE, 1))))))
5

While we have all this calculating power, we might as well make the modulo and exponent operations which have simple enough formulae:

(LABEL, MOD, (LAMBDA, (A, B), (SUB, A, (MUL, B, (DIV, A, B)))))

(LABEL, EXP HELPER, (LAMBDA, (A, B, C), (COND, ((ATOM, (CDR, B)), A), ((QUOTE, T), (EXP HELPER, (MUL, A, C), (CDR, B), C)))))

(LABEL, EXP, (LAMBDA, (A, B), (COND, ((ATOM, B), (DIG, (QUOTE, 1))), ((QUOTE, T), (EXP HELPER, A, B, A)))))

Now back to what I promised we'd get back to earlier: Infinite-length base-10 representation. In fact, we'll even extend that to infinite-length representation in any base, by representing a multi-digit number as an ordered list of digits in that number:

(LABEL, BASE, (LAMBDA, (N, B), (COND, ((ATOM, (DIV, N, B)), (CONS, (LEN, N), (QUOTE, NIL))), ((QUOTE, T), (ADD, (BASE, (DIV, N, B), B), (CONS, (LEN, (MOD, N, B)), (QUOTE, NIL)))))))


def base(n,b):
  if len(div(n,b)) == 0:
    return [len(n)]
  elif True:
    return add(base(div(n,b),b),[len(mod(n,b))])

To make things easier on the poor programmer, let's add a wrapper to our EXP function to take care of most of the calls to DIG and LEN and BASE for us now, call it POW:

(LABEL, TEN, (CONS, (QUOTE, I), (DIG, (QUOTE, 9))))

(LABEL, POW, (LAMBDA, (A, B), (BASE, (EXP, (DIG, A), (DIG, B)), TEN)))

And voilà, look at that: Base 10 exponentiation!


> (POW, (QUOTE, 2), (QUOTE, 8))
(2, 5, 6)

(Be wary that if you go much higher than 256 with orlp's interpreter you might need to increase python's recursion limit with sys.setrecursionlimit to avoid crashes.)

In sum, we've shown that using only nine primitive operations and John McCarthy's original 1959 LISP syntax, it's possible to do all of the basic arithmetic functions by using list length to represent a "number" type. Some good excercises to do if I don't get around to them first would be implementing a base-10 list length generator function, and exploring the possibility of decimal representation (by having a '.' atom to separate the integer and decimal parts). McCarthy's LISP actually goes beyond what is required for turing completeness, so in theory the limits are endless. If you make something cool, I'd love to see it and put it on this page to show!

I've uploaded all the code used in this article on my web server here: math.lisp. If you want to run it on the orlp interpreter, just save his code to a .py file, like mclisp.py, and then do python mclisp.py < math.lisp from the command line. And if you have any questions, of course feel free to contact me any time.