A representation of lists within Lisp or its bastard children. The principle is that since every list is essentially a dotted pair of an S-expression and a list, you can represent any list as a series of dotted pairs drawn as two joined boxes, each with a car, which is the data in that particular node (or a pointer to the cons box contained within it; see example c), and a cdr, which is a pointer to the next box in the diagram, or the final null list.
(a) A cons box diagram of the list (a b c d): (keep in mind that I can’t really show you this without either a picture or using table tags)
[a][-]—> [b][-]—> [c][-]—> [d][/]
(b) A cons box diagram of the list (a b c . d):
{a}[-]—> [b][-]—> [c][d]
(c) A cons box diagram of the list (a (b c) d e):
[a][-]—> [|][-]—> [d][-]—> [e][/]
|
—> [b][-]—> [c][/]
The real advantage of this is that forcing a beginning Lisp/Scheme programmer to diagram cons boxes very quickly strips them of their misconceptions about the structure of lists. I always found questions involving cons boxes on exams to be easy points, but that’s just me.
History of Cons Boxes: Well, gang, I looked around, and couldn’t find anything. Can any of you recommend a text I could read so that I could amend this section?
Source: Professor Richard Salter of Oberlin College