Root of Lisp

John McCarthy shows that given a few operators and notation for functions, you can build a whole programming language.

Lisp Model of Computation


  • an atom , which is a sequence of letters (e.g., foo)
  • a list of zero or more expressions, separated by whitespace and enclosed by parenthesis.

Seven primitive operators:

  • (quote x) returns x. For example, 'x, (quote a),(quote (a b c))
    • by quoting a list, we prevent it from being evaluated
  • (atom x) returns the atoms t if the value of x is an atom or the empty list.
    • (atom 'x) -> t
    • (atom '(a b c)) -> ()
    • (atom '())-> t
  • (eq x y) returns t if the values of x and y are the same atom or both the empty list
    • (eq 'a 'a) -> t
    • (eq 'a 'b)-> ()
  • (car x) returns x’s first element
  • (cdr x) returns everything after the first element
  • (cons x y) returns a list containing the value x followed by the elements of the value of y
  • (cond (p1 e1) …(pn en). The p expressions are evaluated in order until one returns t. When one is found, the corresponding e expression is returned as the value of the whole cond expression.

Denoting function

  • (lambda ( e). p1, are atoms(parameters) and e is an expression
  • function call: ((lambda ( e)
    • Each expression ai is evaluated. Then e is evaluated. During the evaluation of e, the value of any occurrence of one of the pi is the corresponding ai in the most recent function call
    • parameters can be used as operators in expressions as well as arguments.
	((lambda (f) (f '(b c))) '(lambda (x) (cons 'a x))) 
	output:(a b c)

  • (label f (lambda ( e)) denotes a function behaves like (lambda ( e)
  • (defun null. (x) (eq x ‘()))
  • (defun and. (x y) (cond (x (cond ( y ‘t) (‘t ‘()))) (‘t ‘())))

Using just quote, atom, eq, car, cdr, cons , cond, we can define a function eval, that actually implements our language, and then using that we can define any additional functions we want. This is a very elegant model of computation.