In Lisp, + is a function, and an expression like (+ 2 3) is a function call. When Lisp evaluates a function call, it does so in two steps:

1. First the arguments are evaluated, from left to right. In this case, each argument evaluates to itself, so the values of the arguments are 2 and 3, respectively.
2. The values of the arguments are passed to the function named by the operator. In this case, it is the + function, which returns 5.

Not all the operators in Common Lisp are functions, but most are. And function calls are always evaluated this way. The arguments are evaluated left-to-right, and their values are passed to the function, which returns the value of the expression as a whole. This is called the evaluation rule for Common Lisp.

One operator that doesn’t follow the Common Lisp evaluation rule is quote. The quote operator is a special operator, meaning that it has a distinct evaluation rule of its own. And the rule is: do nothing. The quote operator takes a single argument, and just returns it verbatim:

(quote (+ 4 5))

For convenience, Common Lisp defines ’ as an abbreviation for quote. You can get the effect of calling quote by affixing a ’ to the front of any expression:

`(+ 4 5)

It is much more common to use the abbreviation than to write out the whole quote expression.

Lisp provides the quote as a way of protecting expressions from evaluation. The next section will explain how such protection can be useful.

Symbols do not (usually) evaluate to themselves, so if you want to refer to a symbol, you should quote it, as above.

Lists are represented as zero or more elements enclosed in parentheses. The elements can be of any type, including lists. You have to quote lists, or Lisp would take them for function calls:

Lisp offers all the data types we find in most other languages, along with several others that we don’t. One data type we have used already is the integer, which is written as a series of digits: 256. Another data type Lisp has in common with most other languages is the string, which is represented as a series of characters surrounded by double-quotes: “ora et labora”. Integers and strings both evaluate to themselves.

Lists are represented as zero or more elements enclosed in parentheses. The elements can be of any type, including lists. You have to quote lists, or Lisp would take them for function calls:

`(pray sunrise)

Notice that one quote protects a whole expression, including expressions within it. You can build lists by calling list. Since list is a function, its arguments are evaluated. Here we see a call to + within a call to list:

(list `my `(+ 2 3))

We are now in a position to appreciate one of the most remarkable features of Lisp. Lisp programs are expressed as lists. If the arguments of flexibility and elegance did not convince you that Lisp notation is a valuable tool, this point should. It means that Lisp programs can generate Lisp code. Lisp programmers can (and often do) write programs to write their programs for them.

The function cons builds lists. If its second argument is a list, it returns a new list with the first argument added to the front:

(cons ' a ' (b c d))

We can build up lists by consing new elements onto an empty list. The list function that we saw in the previous section is just a more convenient way of consing several things onto nil.

The primitive functions for extracting the elements of lists are car and cdr. The car of a list is the first element, and the cdr is everything after the first element:

(car `(ab c))

(cdr `(ab c))

The parentheses in the cdr are for that it is probably a list, since it is everything but the first element, but in car it is only a one element that’s why there is not parentheses.

You can use combinations of car and cdr to reach any element of a list. If you want to get the third element, you could say:

(car (cdr (cdr ' ( a b c d ) ) ) )

However, you can do the same thing more easily by calling third :

( second '( a b c d))

There are also first and second, you can guess what is their functionality.

In Common Lisp, the symbol t is the default representation for truth. Like nil, t evaluates to itself. The function listp returns true if its argument is a list:

(listp `(a b c))

A function whose return value is intended to be interpreted as truth or falsity is called a predicate. Common Lisp predicates often have names that end with p.

The simplest conditional in Common Lisp is if. It usually takes three arguments: a test expression, a then expression, and an else expression. The test expression is evaluated. If it returns true, the then expression is evaluated and its value is returned. If the test expression returns false, the else expression is evaluated and its value is returned:

(if (listp '(abc))
    (+ 1 2)
    (+ 5 6))

Like quote, if is a special operator. It could not possibly be implemented as a function, because the arguments in a function call are always evaluated, and the whole point of if is that only one of the last two arguments is evaluated. The last argument to if is optional. If you omit it, it defaults to nil.

There are and and or functions, you probably can tell what do they do.

You can define new functions with defun. It usually takes three or more arguments: a name, a list of parameters, and one or more expressions that will make up the body of the function. Here is how we might define third:

(defun our-third (x)
    (car (cdr (cdr x ))))

Let’s try to defun member which tells you if whether an element is a member of function:

(defun somemeeber (obj lst)
  (if (null lst) nil
      (if (eql (car lst) obj) t
          (somemeeber obj (cdr lst)))))

The difference between this implementation (along many other things in the internal implementation) is that instead of evaluating the rest of the list the that member does it, I evaluate the truth value t.

(somemeeber 3 '(1 2 3 4))

The most general output function in Common Lisp is f ormat. It takes two or more arguments: the first indicates where the output is to be printed, the second is a string template, and the remaining arguments are usually objects whose printed representations are to be inserted into the template. Here is a typical example:

(format t "~A plus ~A equals ~A. ~%" 2 3 ( + 2 3))

Notice that two things get displayed here. The first line is displayed by format. The second line is the value returned by the call to format, displayed in the usual way by the toplevel. Ordinarily a function like format is not called directly from the toplevel, but used within programs, so the return value is never seen.

The first argument to format, t, indicates that the output is to be sent to the default place. Ordinarily this will be the toplevel. The second argument is a string that serves as a template for output. Within this string, each ~A indicates a position to be filled, and the ~% indicates a newline. The positions are filled by the values of the remaining arguments, in order.

The standard function for input is read. When given no arguments, it reads from the default place, which will usually be the toplevel. Here is a function that prompts the user for input, and returns whatever is entered:

(defun askem (string)
  (format t ""A" string)
    (read))

One of the most frequently used operators in Common Lisp is let , which allows you to introduce new local variables.

A let expression has two parts. First comes a list of instructions for creating variables, each of the form (variable expression). Each variable will initially be set to the value of the corresponding expression.

(defun ask-for-number ()
  (format t "Enter a number")
  (let ((n (read)))
    (if (numberp n)
        n
        (ask-for-number))))

You can create a global variable by giving a symbol and a value to defparameter:

Such a variable will then be accessible everywhere, except in expressions that create a new local variable with the same name. To avoid the possibility of this happening by accident, it’s conventional to give global variables names that begin and end with asterisks. The name of the variable we just created would be pronounced “star-glob-star”.

You can also define global constants, by calling def constant:

(defconstant limit (+ *glob* 1))

There is no’need to give constants distinctive names, because it will cause an error if anyone uses the same name for a variable. If you want to check whether some symbol is the name of a global variable or constant, use boundp:

(defconstant *glob* 43)
(boundp '*glob*)

In Common Lisp the most general assignment operator is setf. We can use it to do assignments to either kind of variable:

(setf *glob* 90)

(defun read-number-and-prefix-with-message ()
  (let ((n (ask-for-number)))
    (setf n (+ n 1))
    (format t "The new number is ~A" n)))

When we want to do something repeatedly, it is sometimes more natural to use iteration than recursion. A typical case for iteration is to generate some sort of table. This function

(defun show-squares (start end)
  (do ((i start (+ i 1)))
      ((> i end) 'done)
    (format t "~A ~A~%" i (* i i))))
(show-squares 2 4)

The do macro is the fundamental iteration operator in Common Lisp. Like let , do can create variables, and the first argument is a list of variable specifications. Each element of this list can be of the form

{variable initial update)

where variable is a symbol, and initial and update are expressions. Initially each variable will be set to the value of the corresponding initial, on each iteration it will be set to the value of the corresponding update. The do in show-squares creates just one variable, i . On the first iteration i will be set to the value of start , and on successive iterations its value will be incremented by one.

The remaining arguments to do comprise the body of the loop. They will be evaluated, in order, on each iteration. On each iteration the variables are updated, then the termination test is evaluated, and then (if the test failed) the body is evaluated.

(defun show-squares (i end)
 (if (> i end)
  'done
  (progn
     (format t M~A ~A~°/,n i (* i i ) )
   (show-squares (+ i 1) e n d))))

Common Lisp has simpler iteration operators for special cases. To iterate through the elements of a list, for example, you would be more likely to use dolist . Observe the following functions:

(defun our-length-without-do (lst)
  (if (null lst)
      0
      (+ (our-length-without-do (cdr lst)) 1)))

In Lisp, functions are regular objects, like symbols or strings or lists. If we give the name of a function to function, it will return the associated object. Like quote, function is a special operator, so we don’t have to quote the argument:

(function +)

You can replace the + with any other operator or function like read.

This strange-looking return value is the way a function might be displayed in a typical Common Lisp implementation.

Until now we have only dealt with objects that look the same when Lisp displays them as when we typed them in. This convention does not apply to functions. Internally, a built-in function like + is likely to be a segment of machine language code. A Common Lisp implementation may choose whatever external representation it likes.

Just as we can use ' as an abbreviation for quote, we can use #' as an abbreviation for function:

(apply #'+ l) ==  (apply (function +) l)

#' (aka function) can be used in front of (lambda …) (we will talk about lambda soon) but it’s redundant there, so the only place where it’s really meaningful is in front of a symbol, as in #'car. In ELisp, #'car and 'car are almost completely equivalent, so one of the main purpose is simply to document the intention (i.e. to indicate to whoever reads this code that you intend to use this symbol as a function). Yet there are a few circumstances, where the difference is more significant:

• The byte-compiler takes advantage of this documented intention and when you write #'car it will check whether car exists as a function, and if it doesn’t find it, it will emit a warning, just like it would if you had a call to that function.

• Inside cl-flet and cl-labels, only #'f can refer to the locally defined function f, because 'f will still refer to the global symbol f (and whichever function might be stored in its symbol-function slot). E.g.

  (cl-flet ((car (x y) (+ x y)))
    (list #'car 'car))
  =>
  ((closure nil (x y) (+ x y)) car)
  

  (read: Get in the habit of using sharp quote)

Like any other kind of object, we can pass functions as arguments. One function that takes a function as an argument is apply. It takes a function and a list of arguments for it, and returns the result of applying the function to the arguments:

(apply #'+ ' ( 1 2 3))

The function f u n c a l l does the same thing but does not need the arguments to be packaged in a list:

(funcall #'+ 1 2 3)

The defun macro creates a function and gives it a name. But functions don’t have to have names, and we don’t need def un to define them. Like most other kinds of Lisp objects, we can refer to functions literally.

To refer literally to an integer, we use a series of digits; to refer literally to a function, we use what’s called a lambda expression. A lambda expression is a list containing the symbol lambda, followed by a list of parameters, followed by a body of zero or more expressions.

Here is a lambda expression representing a function that takes two numbers and returns their sum:

(lambda (x y)
  (+ x y))

A lambda expression can be considered as the name of a function. Like an ordinary function name, a lambda expression can be the first element of a function call, for example:

((lambda (x) (+ x 100)) 2)

Lisp has an unusually flexible approach to types. In many languages, variables are what have types, and you can’t use a variable without specifying its type. In Common Lisp, values have types, not variables. You could imagine that every object had a label attached to it, identifying its type. This approach is called manifest typing. You don’t have to declare the types of variables, because any variable can hold objects of any type.

(read more about manifest typing)

We will study types in details later.

We previously introduced cons, car, and cdr, the primitive list manipulation functions, what cons really does is combine two objects into a two-part objects into a two-part object called cons. Conceptually, a cons is a pair of pointers; the first one is the car and the second is the cdr.

Conses provide a convenient representation for pairs of any type. The two halves of a cons can point to any kind of object, including conses. It is by taking advantage of the latter possibility that we use conses to build lists. One does not tend to think of lists as pairs, but they can be defined that way. Any nonempty list can be considered as a pair of the first element and the rest of the list.

Lisp lists are the embodiment of this idea. We use one half of the cons to point to the first element of the list, and the other to point to the rest of the list (which is either another cons or nil). The convention in Lisp has always been to use the car for the first element and the cdr for the rest of the list. So now car is synonymous with the first element of a list, and cdr with the rest. Lists are not a distinct kind of object, but conses linked together in this way.

The last two lists we made both have three elements; it just happens that the second element of z is also a list. Such a list is called a nested list, while a list like y that doesn’t contain other lists as elements is called a flat list.

The function consp returns true if its argument is a cons. So l i s t p could be defined:

(defun our-listp (x)
   (or (null x) (consp x)))

Since everything that is not a cons is an atom, the predicate atom could be defined:

(defun our-atom (x) (not (consp x )))

(eql (cons 'a nil) (cons 'a nil) )

(equal (cons 'a nil) (cons 'a nil) )

(setf y (list 'a 'b 'c))
(setf x '( a b c))

(setf y (list 'a 'b 'c))
(setf x '( a b c))
(setf y x)
(eql x y)

As an example, this section shows how to perform a simple form of compression on lists. This algorithm goes by the impressive name of run-length, it should work as follows:

(comprs '(a a a c))

(defun comprs (x)
  (ucompr (car x) 1 (cdr x)))


(defun ucompr (elmnt n lst)
  (if (null lst)
      (list (build elmnt n))
      (let ((next (car lst)))
        (if (eql next elmnt)
            (ucompr elmnt (+ n 1) (cdr lst))
            (cons (build elmnt n) (ucompr next 1 (cdr lst)))))))

(defun build (elmnt n)
  (if (> n 1)
      (list n elmnt)
      elmnt))

Can you write one to do uncompress?

(defun unbuild (n elmt)
  (if (zerop n)
      nil
      (cons elmt (unbuild (- n 1) elmt))))

(defun uncompress (lst)
  (if (null lst)
      nil
      (if (listp (car lst))
          (let ((f (car (car lst)))
                (s (cdr (car lst))))
            (cons (unbuild f s)
                  (uncompress (cdr lst))))
          (uncompress (cdr lst)))))

This will work, however, as you will see we are going to get some different kind of lists, lists of lists;

(uncompress (list '(3 A) '(3 B) '(2 C)))

Common Lisp has additional access functions defined in terms of car and cdr. To find the element at a given position in a list we call nth,

(nth 0 ' ( a b c))

and to find the nth cdr, we call nthcdr:

(nthcdr 2 ' ( a b c))

Both nth and nthcdr are zero-indexed; that is, the elements are numbered starting at zero rather than one. In Common Lisp, whenever you use a number to refer to an element of a data structure, the numbering starts at zero. The two functions do almost the same thing; nth is equivalent to car of nthcdr.

Common Lisp provides several functions for calling functions on the elements of a list. The most frequently used is mapcar, which takes a function and one or more lists, and returns the result of applying the function to elements taken from each list, until some list runs out:

(mapcar #'(lambda (x) (+ x 10))
         '(1 2 3))

The related maplist takes the same arguments, but calls the function on successive cdrs of the lists:

(maplist #'(lambda (x) x)
          '(a b c))

Conses can also be considered as binary trees, with the car representing the right subtree and the cdr the left. For example, the list

(a (b c) d)

is also the tree represented in the following figure:

Binary trees without interior nodes are not useful for much. Common Lisp includes functions for operating on trees not because one needs trees as such, but because one needs a way to do something to a list and all the lists within it. For example, suppose we have a list like

(and (integerp x) (zerop (mod x 2)))

and we want to substitute y for x throughout. It won’t do to call substitute, which replaces elements in a sequence:

(substitute 'y 'x '(and (integerp x) (zerop (mod x 2))))

As you can see, this call is ineffective because substitute looks for sequential elements, like this:

(substitute 'y 'x '(x (integerp x) (zerop (mod x 2))))

However, there is a good replacement which is subset, which can access subtrees:

(subst 'y 'x '(and (integerp x) (zerop (mod x 2))))

(AND (INTEGERP Y) (ZEROP (MOD Y 2)))

Another way to think of a list is as a series of objects in a particular order. In Common Lisp, sequences include both lists and vectors.

To copy part of a sequence, we use subseq. The second argument (required) is the position of the first element to be included, and the third argument (optional) is the position of the first element not to be included.

The function reverse returns a sequence with the same elements as its argument, but in the reverse order:

(reverse '(a b c))

Common Lisp has a built-in sort function called sort. It takes a sequence and a comparison function of two arguments, and returns a sequence with the same elements, sorted according to the function:

(sort '( 0 2 1 3 8 ) #'>)

You have to be careful when using sort , because it’s destructive. For efficiency reasons, sort is allowed to modify the sequence given to it as an argument. So if you don’t want your original sequence modified, pass a copy.

Dotted pair notation is a general syntax for cons cells that represents the CAR and CDR explicitly. In this syntax, (a . b) stands for a cons cell whose CAR is the object a and whose CDR is the object b. Dotted pair notation is more general than list syntax because the CDR does not have to be a list. However, it is more cumbersome in cases where list syntax would work. In dotted pair notation, the list (1 2 3) is written as (1 . (2 . (3 . nil))). For nil-terminated lists, you can use either notation, but list notation is usually clearer and more convenient. When printing a list, the dotted pair notation is only used if the CDR of a cons cell is not a list.

Following code contains a program for finding the shortest path through a network. The function shortest-path takes a start node, a destination node, and a network, and returns the shortest path, if there is one.

In this example, nodes are represented as symbols, and networks are represented as assoc-lists with elements of the form

(node . neighbors)

For example:

(setf min '((a b c) (b c) (c d)))

We can visualize it like this:

Lists can be slow for several reasons. They offer sequential instead of random access, so retrieving a given element takes longer in a list than an array, for the same reason that it takes longer to find something on a tape than on a disk. Internally, conses tend to be represented as pointers, so traversing a list means traversing a series of pointers, instead of simply incrementing an index, as in an array. But these two costs can be small compared to the cost of allocating and recycling cons cells.

Automatic memory management is one of Lisp’s most valuable features. The Lisp system maintains a segment of memory called the heap. The system keeps track of unused memory in the heap and doles it out as new objects are created. The function cons, for example, returns a newly allocated cons.

Allocating memory from the heap is sometimes generically known as consing. If such memory were never freed, Lisp would run out of space for new objects and have to shut down. So the system must periodically search through the heap, looking for memory that is no longer needed. Memory that is no longer needed is called garbage, and the scavenging operation is called garbage collection, or GC.

> (setf 1st (list 'a >b }c))
(A B C)
> (setf 1st nil)
NIL

Since we have no way of reaching this list, it might as well not exist. Objects that we no longer have any way of reaching are garbage. The system can safely reuse these three cons cells.

This way of managing memory is a great convenience to the programmer. You never have to allocate or deallocate memory explicitly. And this means that you never have to deal with the bugs that come from doing so. Memory

leaks and dangling pointers are simply impossible in Lisp.

In Common Lisp, you can make an array by calling make-array with a list of dimensions as the first argument. To make a 2x3 array we would say:

(make-array '(2 3))

The n before the A tells how many dimensions the array have. You can also pass a tag initial-element to set its value:

(make-array '(2 3) :initial-element 2)

We can access both vectors and arrays using aref:

(aref (make-array '(2 3) :initial-element 2) 0 0)

However, in the cause of vectors there is a fastere function which is svref

(svref (vector 'a 'b 'c) 2)

We’ve already seen four functions for retrieving elements of sequences: nth for lists, aref and svref for vectors, and char for strings. Common Lisp also provides a function elt that works for sequences of any kind:

(elt '(a b c) 1)

Many sequence functions take one or more keyword arguments from the standard set listed in this table:

Paramater	Purpose	DEAFULT
:key	a function to apply to all elements	identity
:test	the test function for comparison	eql
:from-end	if true, work backwards	nil
:start	position at which start	0
:end	position, if any, at which to stop	nil

• Josh Betts
• Gavin Freeborn
• Baggers
• CodeNextDoor