John McCarthy shows that given a few operators and notation for functions, you can build a whole programming language.
Lisp Model of Computation
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,
(quote (a b c))
- by quoting a list, we prevent it from being evaluated
(atom x)returns the atoms
tif the value of x is an atom or the empty list.
(atom 'x) -> t
(atom '(a b c)) -> ()
(atom '())-> t
(eq x y)returns
tif the values of
yare the same atom or both the empty list
(eq 'a 'a) -> t
(eq 'a 'b)-> ()
x’s first element
(cdr x)returns everything after the first element
(cons x y)returns a list containing the value
xfollowed by the elements of the value of
(cond (p1 e1) …(pn en). The
pexpressions are evaluated in order until one returns
t. When one is found, the corresponding
eexpression is returned as the value of the whole
(lambda (p1...pn) e).
p1, ...pnare atoms(parameters) and
eis an expression
- function call:
((lambda (p1...pn) e) a1...an)
- Each expression
aiis evaluated. Then
eis evaluated. During the evaluation of
e, the value of any occurrence of one of the
piis the corresponding
aiin 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 ‘())))
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.