common-lisp Cons cells and lists Sketching cons cells
Example
To better understand the semantics of conses and lists, a graphical representation of this kind of structures is often used. A cons cell is usually represented with two boxes in contact, that contain either two arrows that point to the car and cdr values, or directly the values. For instance, the result of:
(cons 1 2)
;; -> (1 . 2)
can be represented with one of these drawings:
Note that these representations are purely conceptual, and do not denote the fact that the values are contained into the cell, or are pointed from the cell: in general this depends on the implementation, the type of the values, the level of optimization, etc. In the rest of the example we will use the first kind of drawing, which is the one more commonly used.
So, for instance:
(cons 1 (cons 2 (cons 3 4))) ; improper “dotted” list
;; -> (1 2 3 . 4)
is represented as:
while:
(cons 1 (cons 2 (cons 3 (cons 4 nil)))) ;; proper list, equivalent to: (list 1 2 3 4)
;; -> (1 2 3 4)
is represented as:
Here is a tree-like structure:
(cons (cons 1 2) (cons 3 4))
;; -> ((1 . 2) 3 . 4) ; note the printing as an improper list
The final example shows how this notation can help us to understand important semantics aspects of the language. First, we write an expression similar to the previous one:
(cons (cons 1 2) (cons 1 2))
;; -> ((1 . 2) 1 . 2)
that can be represented in the usual way as:
Then, we write a different expression, which is apparently equivalent to the previous one, and this seems confirmed by printed representation of the result:
(let ((cell-a (cons 1 2)))
(cons cell-a cell-a))
;; -> ((1 . 2) 1 . 2)
But, if we draw the diagram, we can see that the semantics of the expression is different, since the same cell is the value both of the car part and the cdr part of the outer cons (this is, cell-a is shared):
and the fact that the semantics of the two results is actually different at the language level can be verified by the following tests:
(let ((c1 (cons (cons 1 2) (cons 1 2)))
(c2 (let ((cell-a (cons 1 2)))
(cons cell-a cell-a))))
(list (eq (car c1) (cdr c1))
(eq (car c2) (cdr c2)))
;; -> (NIL T)
The first eq is false since the car and cdr of c1 are structurally equal (that is true by equal), but are not “identical” (i.e. “the same shared structure”), while in the second test the result is true since the car and cdr of c2 are identical, that is they are the same structure.
