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.

- Each expression

```
((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.