Thursday 14th March 2013 (10:45PM)
(As with all "concise and simple" articles I assume no prior knowledge of the subject and keep the length to less than 1500 words.)
Lisp is a beautiful programming language, famous for its hidden depths that lead to moments of kensho. I want to give you a sense of why I believe this.
For me, Lisp's beauty is revealed when its simple core concepts lead to moments of sudden insight and shifts of perspective. Lisp's simplicity begins with its syntax (how it is written): a simple notation that anyone can understand.
Lisp expressions are either atoms or lists (Lisp stands for LISt Processor).
Here are five atoms:
foo bar baz 123 "Hello World"
Atoms are sequences of characters. The penultimate atom is a number and the final one is a string (enclosed in quotes).
Here's a list:
(ham eggs bacon sausages beans)
A list is bounded by parenthesis. Lists can contain other lists:
((soup salad garlic-mushrooms) (roast-beef chicken-casserole vegetable-lasagne) (cake fruit jam-pudding))
The list above contains three items. Each item is itself another list containing three atoms. I've split the contained lists over three lines to aid readability.
Lisp's semantics (that define what the syntax means) are equally simple:
Comments are natural-language annotations added to the code by programmers. They're meant to help humans work out how the code works:
; This is a comment in Lisp
Quoting is a simple concept: it's the difference between quoting
and "quoting" - the former is a word that means something whereas the latter
refers to the word itself. To quote something, append a single quote
') to it. Here's a quoted list:
'(ham eggs bacon sausages beans)
Lisp evaluates this as just a list of atoms:
(ham eggs bacon sausages beans)
Here's an example of a form:
(+ 1 2 3)
When Lisp evaluates a form it's told to do something to produce a result. In
this case, the result is
If you guessed the result correctly then you've figured out prefix notation: the command comes first (in this case the atom representing the operator for summing numbers) and is followed by its arguments (the things the operator uses to generate the answer).
Can you work out the answer to the following?
(+ 1 (- 5 (+ 2 3)))
If you answered
1 then you've worked out the order in which
Lisp evaluates nested expressions - it starts from the inner most
expression before evaluating the enclosing outer expressions.
Here's how Lisp evaluated the example above:
(+ 1 (- 5 (+ 2 3))) (+ 1 (- 5 5)) (+ 1 0) 1
Usually, the first item in a form (the operator) is the name of a function. A function is a discrete block of code that receives input (its arguments) and returns a result. In the examples above we used the functions that sum and subtract numbers. Lisp comes with many useful built-in functions including a special one for creating new functions.
I want to describe some fundamental Lisp functions; these will allow me to reveal a surprise at the heart of Lisp1.
quote function is a long version of quoting mentioned
above. The example below is equivalent to the abbreviated version
'(foo bar baz):
(quote (foo bar baz)) (foo bar baz)
atom function returns the atom
(representing true) if its argument is an atom. Otherwise it
nil (representing false):
(atom 'foo) t (atom '(foo bar baz)) nil
eq function returns
t if the two
arguments have the same value. Otherwise it returns
(eq 'foo 'foo) t (eq 'foo 'bar) nil
car function expects its argument to be a list and returns
the first item therein:
(car '(foo bar baz)) foo
cdr function (say kud-r) expects its argument to be a list
and returns everything after the first element:
(cdr '(foo bar baz)) (bar baz)
cons function expects two arguments, the second of which
must be a list. It returns a new list containing the first argument followed
by the elements in the second argument:
(cons 'foo '(bar baz)) (foo bar baz)
cond (short for conditional) function takes any
number of lists as arguments. Each list must contain two items: a form that
evaluates to either
nil and some other
expression. Each list is evaluated in order until a form returns
at which point the other expression in the list is evaluated and returned by
(cond ((eq 'foo 'bar) 'first) ((atom 'baz) 'second) ((atom 'qux) 'third)) second
In the example above, the first
nil, whereas the second
atom function is true. Therefore, the second element
of the list containing the
atom function is returned
as the result. Although the third
atom function is
also true, it is ignored. This is somewhat similar to
if ... elif statements in other programming languages.
lambda function is used to create user defined functions. It
expects two lists as arguments: the first contains named place-holders for the
new function's arguments, the second contains the form to be evaluated to
generate the new function's result:
(lambda (x y) (cons x (cdr y)))
Notice how the argument names are used in the evaluated form to refer to the values that may be passed in to the new function. This can be demonstrated by defining then immediately calling a function like this:
((lambda (x y) (cons x (cdr y))) 'qux '(foo bar baz)) (qux bar baz)
The value of
x becomes the atom
y becomes the list
(foo bar baz). It's useful
to name new functions. Unsurprisingly, there is a way:
(defun replace-head (x y) (cons x (cdr y))) (replace-head 'qux '(foo bar baz)) (qux bar baz)
replace-head is defined
defun) then used to give the result
(qux bar baz). Being able to name a function makes
it possible for the function to refer to itself. This very important behaviour
is called recursion.
<= means less than or equal and
* means multiply, can you tell how the following
recursive example works?
; Returns the product of all positive integers less than or equal to n. (defun factorial (n) (cond ((<= n 1) 1) ('t (* n (factorial (- n 1)))))) (factorial 4) 24
After a useful comment a function called factorial (that takes a
single argument called n) is defined. The function checks if
n is less than or equal to 1 and if so returns the number 1.
Otherwise, it returns n multiplied by the result of calling
factorial (i.e. itself) of n minus 1. Finally, the new
function is tested with the number 4, producing the result
Recursion is when the function returns n multiplied by factorial of n minus 1. The value of n keeps decreasing and is fed back in to the factorial function until n equals 1, at which point the number 1 is returned to complete the following chain of arithmetic: 1 × 2 × 3 × 4
Here's the surprise: given the fundamental functions described above, it is
possible to write a Lisp in Lisp. When Lisp evaluates an expression,
a list (the code) is itself an argument to a function that returns the result
of evaluating the code. In Lisp, this function is called
it is possible to define such a function using only the features described
First, some shorthand functions need defining:
cxr set of functions replace the
x with a sequence of
ds to indicate
a corresponding sequence of nested
is shorthand for:
returning the second element of a.
(car (cdr a))
list function returns a list containing a given sequence
(list 'a 'b 'c)
is equivalent to:
(cons 'a (cons 'b (cons 'c '())))
which returns the list:
(a b c). In many Lisp implementations
list function is abbreviated to
Remember this, we'll use it later!
Next, we define some useful helper functions:
; tests if the argument is an empty list. (defun null? (x) (eq x '())) ; returns t if both arguments also return t - otherwise returns nil. (defun and. (x y) (cond (x (cond (y 't) ('t nil))) ('t nil))) ; returns t if the argument returns nil, or nil if its argument returns t. (defun not. (x) (cond (x nil) ('t 't))) ; concatenates two lists. (defun append. (x y) (cond ((null? x) y) ('t (cons (car x) (append. (cdr x) y))))) ; pairs up the elements of two lists of the same length. ; e.g. (pair. '(x y z) '(a b c)) -> ((x a) (y b) (z c)) (defun pair. (x y) (cond ((and. (null? x) (null? y)) '()) ((and. (not. (atom x)) (not. (atom y))) (cons (list (car x) (car y)) (pair. (cdr x) (cdr y)))))) ; takes an atom x and list of pairs y and returns the ; second element of the first list in y whose first ; element is x. ; e.g. (assoc. 'x '((x a) (y b))) -> a (defun assoc. (x y) (cond ((eq (caar y) x) (cadar y)) ('t (assoc. x (cdr y)))))
Notice how the final two functions use recursion as the mechanism for looping over lists.
; Lisp's eval function written in Lisp. ; Takes Lisp source code as a list, e, and a context of arguments, ; a, and returns the result of evaluating e in context a. (defun eval. (e a) (cond ((atom e) (assoc. e a)) ((atom (car e)) (cond ((eq (car e) 'quote) (cadr e)) ((eq (car e) 'atom) (atom (eval. (cadr e) a))) ((eq (car e) 'eq) (eq (eval. (cadr e) a) (eval. (caddr e) a))) ((eq (car e) 'car) (car (eval. (cadr e) a))) ((eq (car e) 'cdr) (cdr (eval. (cadr e) a))) ((eq (car e) 'cons) (cons (eval. (cadr e) a) (eval. (caddr e) a))) ((eq (car e) 'cond) (evcon. (cdr e) a)) ('t (eval. (cons (assoc. (car e) a) (cdr e)) a)))) ((eq (caar e) 'label) (eval. (cons (caddar e) (cdr e)) (cons (list (cadar e) (car e)) a))) ((eq (caar e) 'lambda) (eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr e) a)) a))))) ; A recursive function to evaluate a conditional. (defun evcon. (c a) (cond ((eval. (caar c) a) (eval. (cadar c) a)) ('t (evcon. (cdr c) a)))) ; A recursive function to evaluate a list. (defun evlis. (m A) (cond ((null? m) '()) ('t (cons (eval. (car m) a) (evlis. (cdr m) a)))))
eval function takes two arguments: e (the
expression to be evaluated) and a (a list of pairs representing the
named parameters passed in as arguments). It evaluates e in the
context of a. The function body is relatively simple: a conditional
containing four clauses for handling atoms, the fundamental functions,
cond statements and the
lambda function. The clause
for the fundamental functions is itself a conditional containing sub-clauses
for each fundamental function. The last two clauses call out to the recursive
evlis functions that evaluate conditionals
and lists respectively.
eval treats the incoming Lisp source code as a list
to be manipulated like any other data structure. When a language's code is also
merely data (as it is for the
eval function above), it is
This introduces the potential for yet another mind bending capability: it
is possible to change Lisp from within Lisp since all code is written as lists
and Lisp is a LISt Processor. Therefore, Lisp is able to
transform and change its own source code in order to add unforeseen
The macro is what makes this possible. Macros look a lot like functions but are different in two ways:
; A simple macro that generates code to square things (defmacro square (x) `(* ,x ,x))
` is shorthand for the
, (comma) unquotes an expression (in this case the
argument x). Therefore, the following use of the
results in this generated code,
(* 3 3)
that Lisp evaluates to produce a useful result.
eval and macros are just three fascinating aspects
of Lisp. Happily, there are many great
resources about Lisp (including
in computing) if you want to find out more. If you want to learn online, why
casting SPELs in Lisp or
the Vivid Schemer..?
1 This section is based upon Paul Graham's article, The Roots of Lisp that is itself derived from John McCarthy's original 1960 paper on Lisp, Recursive Functions of Symbolic Expressions and their Computation by Machine. ⇪ Return to article.
1498 words (not including code examples or footnotes). Image credits: The public domain Lisp Alien logo was created by Conrad Barski, M.D.. Lisp Cycles and Lisp Enlightenment cartoons © Randall Munroe under a Creative Commons license.