Exercise 1.1.4

Lists, Cons-Cells, and Memory

It is significant to separate the representation and implementation of S-Expressions in your mind as you learn Lisp---since McCarthy's first paper on LISP, S-Expressions have been defined by their representation, but in Common Lisp, S-Expressions are defined by their implementation and their representation is only treated as an interface to the underlying objects.

Lists are a proper type, descending from Sequences in Lisp's type hierarchy. A list only conses as long as there are values to be consed. For example, consider the following:

* (list)
=> NIL
* (list 'a)
=> (A)
* (list 'a nil)
=> (A NIL)
* (cons 'a nil)
=> (A)

To understand what's happening in the example above, you have to understand consing, and how lists are built on top of Cons-Cells.

;; this:
(list 'a 'b 'c)
;; is the same as this:
(cons 'a (cons 'b (cons 'c nil)))
;; while this:
(list 'a 'nil)
;; is the same as this:
(cons 'a (cons nil nil))

The end of a chain of cons-cells normally terminates in nil, but you can have the cdr of a cons-cell point to a value too, and eliminate the need for an extra consing by using dot-notation:

;; this:
'(a . b)
;; is the same as this:
(cons 'a 'b)

A list of dot-notation pairs like this is called an association list, or alist for short. They are one of many structures available in Lisp for storing key/value pairs, and have a good API.

'((a . b)
  (c . d)
  (e . f))

So then, just what is this "Cons-Cell" I keep talking about, you ask?

A Cons-Cell is a pair of pointers, the car and the cdr---acronyms for "Contents of Address Register" and "Contents of Decrement Register", respectively. The car is usually a pointer to a value, while the cdr can be a pointer to the car of another cons-cell, a pointer to NIL, or in the case of a dotted-pair, another pointer to a value.

Consider again the examples above. Now you can more clearly see how lists are built on top of Cons-Cell chains, and what is happening when you work with Cons-Cells directly:

;; this creates three cons-cells, the quoted symbols 'A, 'B, and 'C each in the CAR of their own Cons-Cell
(list 'a 'b 'c)
;; it would be the same as typing this:
(cons 'a (cons 'b (cons 'c nil)))
;; or this:
'(a . (b . (c . nil)))
;; or this:
'(a b c . nil)
;; or simply this:
'(a b c)

A common focal-point of Lisp source code optimization centers on minimizing the number of conses performed by your application. Note how a dotted-pair only conses once, while a two item list that contains the same information conses twice; so by using an alist instead of other list-based data structures such as plists, you are already eliminating half the memory and processing requirements.