5.5 cons Cells: Building Blocks of Dynamic Memory Structures
To develop functions that are more sophisticated than pow, we need to examine how lists are represented in memory. Such an examination helps us conceptualize and conceive abstract data structures and design algorithms that operate on and manipulate those structures to solve a variety of problems. In the process, we also consider how we can use BNF to define data structures inductively. (Recall that in Lisp, code and data are one and the same.) In a sense, all programs are interpreters, so the input to those programs must conform to the grammar of some language. Therefore, as programmers, we are also language designers. A well-defined recursive data structure naturally lends itself to the development of recursive algorithms that operate on that structure. An important theme of a course on data structures and algorithms is that data structures and algorithms are natural reflections of each other. In turn, “when defining a program based on structural induction, the structure of the program should be patterned after the structure of the data” (Friedman, Wand, and Haynes 2001, p. 12). We move onward, bearing these two themes in mind.
5.5.1 List Representation
In Lisp, a list is represented as a cons cell, which is a pair of pointers (Figure 5.1):
Figure 5.1 List box representation of a cons cell.
a pointer to the head of the list as an atom or a list (known as the car6)
a pointer to the tail of the list as a list (known as the cdr)
The function cons constructs (i.e., allocates) new memory—it is the Scheme analog of 
in C (i.e., it allocates memory for two pointers of 8 bytes each). The running time of cons is constant [i.e., O(1)]. Cons cells are the building blocks of dynamic memory structures, such as binary trees, that can grow and shrink at run-time.
5.5.2 List-Box Diagrams
A cons cell can be visualized as a pair of horizontally adjacent square boxes (Figure 5.1). The box on the left contains a pointer to the car (the head) of the list, while the box on the right holds a pointer to the cdr (the tail) of the list. Syntactically, in Scheme (and in this text), a full stop 
is usedto denotethe vertical partition between the boxes. For instance, the list 
is equivalent to the list 
and both are represented in memory the same way. The diagram in Figure 5.2, called a list-box, depicts the memory structure created for this list, where a cdr box with a diagonal line from the bottom left corner to the top right corner denotes the empty list [i.e., 
]. Similarly, Figure 5.3 illustrates the list 
. The dot notation makes the distinction between the car and cdr explicit. When the cdr of a list is not a list, the list is not a proper list and is called an improper list. The list 
(Figure 5.4) is an improper list.
Figure 5.2 ′(a b) = ′(a . (b))
Description
Figure 5.3 ′(a b c) = ′(a . (b c)) = ′(a . (b . (c)))
Description
Figure 5.4 ′(a . b)
The dot notation also helps reveal another important and pioneering aspect of Lisp—namely, that everything is a pointer, even though nothing appears to be because of implicit pointer dereferencing. This is yet another example of uniformity and consistency in the language. Uniform and consistent languages are easy to learn and use. English is a difficult language to learn because of the numerous exceptions to the voluminous set of rules (e.g., i before e except after c7). Similarly, many programming languages are inconsistent in a variety of aspects. For instance, all objects in Java must be accessed through a reference (i.e., you cannot have a direct handle to an object in Java); moreover, Java uses implicit dereferencing. However, Java is not entirely uniform in this respect because only objects—not primitives such as ints—are accessed through references. This is not the case in C++, where a programmer can access an object directly or through a reference.
Understanding how dynamic memory structures are represented through list-box diagrams is the precursor to building and manipulating abstract data structures. Figures 5.5–5.8 depict the list-boxes for the following lists:
Figure 5.5 ′((a) (b) ((c))) = ′((a) . ((b) ((c)))) = ′((a) . ((b) . (((c)))))
Description
Note that Figures 5.6 and 5.8 depict improper lists. The following transcript illustrates how the Scheme interpreter treats these lists. The car function returns the value pointed to by the left side of the list-box, and the cdr function returns the value pointed to by the right side of the list-box.
Figure 5.6 ′(((a) b) c)
Description
Figure 5.7 ′((a b) c) = ′(((a) b) . (c)) = ′(((a) . (b)) . (c))
Description
Figure 5.8 ′((a . b) . c)
Description
When working with lists, always follow The Laws of car, cdr, and cons (Friedman and Felleisen 1996a):
The Law of car: The primitive car is defined only for non-empty lists (p. 5).
The Law of cdr: The primitive cdr is only defined for non-empty lists. The cdr of a non-empty list is always another list (p. 7).
The Law of cons: The primitive cons accepts two arguments. The second argument to cons must be a list [(so to construct only proper lists)]. The result is a list (p. 9).
Conceptual Exercise for Section 5.5
Exercise 5.5.1 Give the list-box notation for the following lists:
6. The names of the functions car and cdr are derived from the IBM 704 computer, the computer on which Lisp was first implemented (McCarthy 1981). A word on the IBM 704 had two fields, named address and decrement, which could each store a memory address. It also had two machine instructions named CAR (contentsofaddressregister)and CDR (contents of decrement register), which returned the values of these fields.
7. There are more exceptions to this rule than adherents.