Custom '+' (sum) function in lisp

Question

I was reading Roots of Lisp by Paul Graham where he claims that any lisp functionality can be build with the combination of this 7 base functions: quote, atom, eq, cond, cons, car, cdr.

Question: are Lisp dialects really based solely on those functions? How can we define a 'sum' or 'plus' function using the aforementioned 7 primitive functions? e.g. Our own (+ 1 2) function

Note: I'm totally newbie to Lisp but I'm also starting to get very excited about the language. The purpose of this question is purely genuine interest

Answer 1

The author refers to a very famous paper written in 1960 by the Turing Award and Lisp inventor John McCarthy “Recursive Functions of Symbolic Expressions and Their Computation by Machine”, in which he defined the semantics of Lisp as a new computational formalism, equivalent in power to the Turing Machine.

In the paper (and in the Lisp 1.5 Manual) McCarthy described the interpreter for the language, that can be completely written by using only the seven primitive functions mentioned by Graham.

The language was devoted primarily to symbolic computations, and the interpreter presented in the papers concerned only those computations, without resorting to numbers or other data types different from atoms and pairs.

As Graham says in a note at page 11 of Root of Lisp, “It is possible to do arithmetic in McCarthy's 1960 Lisp by using e.g. a list of n atoms to represent the number n”, so performing a sum is simply equivalent to appending two lists.

Of course this way of doing is very inefficient: it is presented only to show the equivalence with other computational formalisms, and in the real interpreters/compilers integers are represented as usual, and have the usual operators.

Answer 2

as far as i remember, there was also an approach to do this using list nesting level (don't really remember, where). Starting from () as zero, (()) == 1 and so on. Then you can simply define inc as list and dec as car:

CL-USER> (defun zero? (x) (eq () x))
ZERO?

CL-USER> (zero? nil)
T

CL-USER> (zero? 1)
NIL

CL-USER> (defparameter *zero* ())
*ZERO*

CL-USER> (defun inc (x) (list x))
INC

CL-USER> (defun dec (x) (car x))
DEC

CL-USER> (defun plus (x y)
           (if (zero? y) x (plus (inc x) (dec y))))
PLUS

CL-USER> (plus *zero* (inc (inc *zero*)))
((NIL))

CL-USER> (defparameter *one* (inc *zero*))
*ONE*

CL-USER> (defparameter *two* (inc *one*))
*TWO*

CL-USER> (defparameter *three* (inc *two*))
*THREE*

CL-USER> (plus *two* *three*)
(((((NIL)))))

CL-USER> (equal *two* (dec (dec (dec (plus *two* *three*)))))
T

Answer 3

TL; DR: No. Modern lisp systems have many more primitives than the first lisp and a new primitives are needed for each new primitive data type.

The first Lisp didn't have numbers but it was turing complete. That means it can do any computation that is possible in any other language, but it doesn't mean it would be practical to do so. Number were not hard to mimic, but calculations were slow. There are rumers today about slow arithmetic dating back pre Lisp 1.5.

When I made my first lisp interpreter I couldn't care much for numbers. It's not really an interesting aspect of an interpreter. I did however implement fibonacci as an example and this is how it looks like:

;; This is NOT Common Lisp code. It's Zozotez
(setq + (lambda (x y)
  (if x (cons (car x) 
              (+ (cdr x) y))
      y)))

(setq - (lambda (z w)
  (if w (- (cdr z) 
           (cdr w)) 
      z)))

(setq fibonacci
  (lambda (n a1 a2)
    (if n
        (fibonacci (- n '(1))
                   a2 
                   (+ a2 a1)) 
        a1)))

(fibonacci '(1 1 1 1 1 1 1 1 1) () '(1))
; ==> (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

No numbers! (1 in my language is a symbol so it needs to be quoted or else it will be evaluated like a variable)

As alternative number system I have implemented a positional system, pretty much like how we write numbers with the same rules for adding/multiplying etc. Perhaps a tad faster than lits of length n but more complex to make.

If the Lisp has closures you can do church numerals. Using the same as lambda calculus you can compute anything with just closures. You only need one primitive, lambda. (Again, not the easiest to work with)