On Lisp's fundamental data structure

December 30, 2005

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.)

Written on 30 December 2005.
« A Python surprise: the consequences of variable scope
A logical consequence of def being an executable statement »

Page tools: View Source, Add Comment.
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Fri Dec 30 17:21:46 2005
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.