2005-12-30
On Lisp's fundamental data structure
One of the joys of learning new programming languages is the aha moments when something really clicks. The biggest aha moment I've ever had was with Prolog, when an assignment went from nigh impossible to trivial in a blinding flash of obvious insight.
But the one I remember most distinctly is from years ago, when I was looking at Lisp (again), and finally realized that the fundamental data structure of Lisp is not lists but cons cells.
While the major use of cons cells is building lists, cons cells can be
used for a great deal more. The most straightforward thing is binary
trees, with each node being just '(left . right)' (in the traditional
Lisp cons cell notation). If one wants more, Peter Seibel's
Practical Common Lisp has an
entire chapter called
Beyond Lists: Other Uses for Cons Cells.
(Cons cells also show Lisp's roots in the very old days of computing, since they are a very simple data structure: a pair of addresses. The Lisp CAR and CDR functions even take their names from how cons cells were implemented in the first Lisp on IBM 704 computers; see here.)