(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:

• Code is written as lists that are evaluated by Lisp to produce results.
• Comments begin with a semi-colon and are ignored by Lisp.
• Lists and atoms that are "quoted" are evaluated as data.
• Anything else is evaluated as a form ~ a list starting with an atom that Lisp understands (telling it to do something).

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 6.

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 Lisp¹.

The 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)

The atom function returns the atom t (representing true) if its argument is an atom. Otherwise it returns nil (representing false):

(atom 'foo)
t
(atom '(foo bar baz))
nil

The eq function returns t if the two arguments have the same value. Otherwise it returns nil:

(eq 'foo 'foo)
t
(eq 'foo 'bar)
nil

The car function expects its argument to be a list and returns the first item therein:

(car '(foo bar baz))
foo

The 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)

The 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)

The cond (short for conditional) function takes any number of lists as arguments. Each list must contain two items: a form that evaluates to either t or nil and some other expression. Each list is evaluated in order until a form returns t at which point the other expression in the list is evaluated and returned by cond :

(cond ((eq 'foo 'bar) 'first)
      ((atom 'baz) 'second)
      ((atom 'qux) 'third))
second

In the example above, the first eq function evaluates to 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.

The 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 qux and 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)

The function 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. Assuming <= 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 24.

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 eval and it is possible to define such a function using only the features described above.

First, some shorthand functions need defining: cxr and list. The cxr set of functions replace the x with a sequence of as or ds to indicate a corresponding sequence of nested car or cdr calls. For example,

(cadr a)

is shorthand for:

(car (cdr a))

returning the second element of a.

The list function returns a list containing a given sequence of expressions:

(list 'a 'b 'c)

is equivalent to:

(cons 'a (cons 'b (cons 'c '())))

which returns the list: (a b c). In many Lisp implementations the list function is abbreviated to ` (backquote). 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.

Here's the eval function:

; 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)))))

The 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 evcon and evlis functions that evaluate conditionals and lists respectively.

Notice how 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 called homoiconic. 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 features.

The macro is what makes this possible. Macros look a lot like functions but are different in two ways:

• Macros generate Lisp code.
• They are evaluated during macro expansion time - before "regular" code is evaluated.

For example:

; A simple macro that generates code to square things
(defmacro square (x)
  `(* ,x ,x))

The ` is shorthand for the list function. The , (comma) unquotes an expression (in this case the argument x). Therefore, the following use of the square macro:

(square 3)

results in this generated code,

(* 3 3)

that Lisp evaluates to produce a useful result.

Recursion, eval and macros are just three fascinating aspects of Lisp. Happily, there are many great resources about Lisp (including classic texts in computing) if you want to find out more. If you want to learn online, why not try 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.