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

## Lisp Model of Computation

### expression:

• 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 (p1...pn) e). p1, ...pn are atoms(parameters) and e is an expression
• function call: ((lambda (p1...pn) e) a1...an)
• 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 (p1...pn) e)) denotes a function behaves like (lambda (p1...pn) 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.