So, what happens if we deviate from the classic “string of conses” formula? How will a Lisp environment deal with this when printing lists?

Suppose we try to create a list of the numbers 1, 2, and 3, like this:

(cons 1 (cons 2 3))

Here, instead of creating a third cons cell for the third number of our list, we stuff it into the right slot of the previous cell. What would the printed response look like if we were to enter this structure into a Lisp REPL? Let’s try it out:

> (cons 1 (cons 2 3))
(1 2 . 3)

To indicate that the final item in the list wasn’t found in the proper location for a nil-terminated list, Lisp places a dot in front of this final item. This dot is basically Lisp’s way of saying, “I tried to print this structure you entered using list notation, but the last item in the list didn’t contain the usual nil I expected; instead, it contained 3.”

A list in Lisp that ends in something other than a nil is referred to as a dotted list. Dotted lists are kind of an oddity in the Land of Lisp. In and of themselves, they are not that useful a tool for Lisp programming. It would be quite unusual for a Lisp programmer to store data in dotted lists as a regular practice. However, given the pervasiveness of cons cells in Lisp, you will frequently encounter a non-nil value at the end of a chain of cons cells. That’s why you should become familiar with dotted lists, even if you may never use them directly.

Another way of thinking about this dot notation is to consider it as simply an alternate syntax for the cons command, used in data mode. In fact, if we wanted to make life hard for ourselves, we could even create regular, proper lists using the dot notation, like this:

> '(1 . (2 . (3 . nil)))
(1 2 3)

Using this line of thinking, the dot appears in a dotted list simply because Lisp is forced to show the final cons cell in order to maintain the consistency of its list-printing mechanism.

One common and practical use for dotted lists in Lisp programs is to elegantly represent pairs. For instance, suppose we wanted to represent a pair of the numbers 2 and 3. One way to do this would be to cons together these two numbers:

> (cons 2 3)
(2 . 3)

Essentially, all we’re doing here is creating a dotted list of length two. As expected, Lisp uses dot notation to display this pair.

Creating pairs in this manner in Lisp is very convenient and efficient. It’s convenient because we can extract members from the pair using the standard car and cdr commands. It’s relatively efficient because the Lisp environment needs to allocate only a single cons cell to connect the two items.

These types of pairs are commonly used in Lisp programs. For instance, you could use them to store the x- and y-coordinates of a point or a key/value pair in a complex data structure. You will see this latter use for pairs when we discuss association lists.

Here is the picture we used in Chapter 3 to illustrate the cons cells that make up the list '(1 2 3):

Now suppose that we created a weird mutant of this list. Let’s have the cdr of the third cons cell point back to the first cons cell, rather than to nil:

Every cons cell in a list theoretically exists as a separate object in memory. Since the car and cdr slots in a cell can point to any other object in memory, a cons cell can point to an upstream cons cell of a list. We call this a circular list.

But before you experiment with circular lists in any Common Lisp environment, you should run this command:

(setf *print-circle* t)

Setting *print-circle* to true warns Lisp that you plan on playing shenanigans with self-referential data structures, and that it needs to be extra careful when printing on the screen any of the monstrosities you may create. If you were to print a circular list without this variable set, there’s no telling what would happen, but whatever the outcome, it wouldn’t be pretty (unless you find some beauty in stack overflows and infinite loop printing).

When you have *print-circle* set to true, Common Lisp will use more complex printing routines for printing data structures. These routines (which are disabled by default to improve performance) will check to see if you’ve run into a previously seen cons cell, so that printing doesn’t end up putting you into an infinite loop.

So how would you go about creating a circular list? The most straightforward way is to use the setf command to put extra stuff in the first parameter, like so:

> (defparameter foo '(1 2 3))
FOO
> (setf (cdddr foo) foo)
#1=(1 2 3 . #1#)

In this example, we’ve created an infinite list of '(1 2 3 1 2 3 1 2 3 ...) by replacing the nil at the end of a simple list with a reference to the list itself.

The ability to place complex expressions in the first parameter of a setf command, as in this example, is very cool, and we’ll explore it in greater detail in Chapter 9.

One particularly useful data structure that can be created out of cons cells is an association list, or alist for short. An alist consists of key/value pairs stored in a list.

By convention, if a key appears multiple times in the list, it is assumed that the first appearance of the key contains the desired value. For instance, here is an alist representing an order for coffee drinks placed by Bill, Lisa, and John:

(defparameter *drink-order* '((bill . double-espresso)
                              (lisa . small-drip-coffee)
                              (john . medium-latte)))

To look up the order for a given person, use the function assoc:

> (assoc 'lisa *drink-order*)
(LISA . SMALL-DRIP-COFFEE)

This function searches the list from the beginning for the desired key, and then returns the key/value pair. Now suppose that, before picking up the drink order, Lisa flags you down and opts to change her order to something slightly more decadent. You can change her order using the push function:

> (push '(lisa . large-mocha-with-whipped-cream) *drink-order*)
((LISA . LARGE-MOCHA-WITH-WHIPPED-CREAM)
 (BILL . DOUBLE-ESPRESSO)
 (LISA . SMALL-DRIP-COFFEE)
 (JOHN . MEDIUM-LATTE))

This function simply adds a new item to the front of an existing list.

Because, by default, the first reference to a key in an association list takes precedence over later references to the same key, the order Lisa placed for a small drip coffee is superseded by her more recent order:

> (assoc 'lisa *drink-order*)
(LISA . LARGE-MOCHA-WITH-WHIPPED-CREAM)

As you can see, alists are a great way to keep track of any changeable collection of key/value pairs. Alists are easy to understand, to manipulate with Lisp functions, and to comprehend when printed out (they’re just lists of pairs, after all).

Furthermore, once a value is stored in an alist, it remains there forever, making it easy to audit the history of any data. For instance, in our coffee example, the order Lisa placed for her drip coffee is still available even after it has been replaced.

However, alists do have one serious limitation: They are not a very efficient way to store and retrieve data, unless you’re dealing with very short lists (under a dozen items). Because of this inefficiency, although alists are often one of the first tools in the Lisp programmer’s toolbox, they may be replaced by other types of data structures as a program matures. (In Chapter 9, we’ll discuss the performance limitations of list-based data structures, such as alists, in greater detail.)