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.)
A Python surprise: the consequences of variable scope
The comment on my AClosureConfusion entry brought up a little Python surprise that I had known about in the back of my mind but never thought about fully before: the consequences of Python's scoping rules for variables.
Ignoring closures for the moment, Python only has two scopes for variables: global to the module and local to the entire function. (Closures introduce additional scopes for the variables of the 'outer' functions.)
Well, sure, you know that. But the consequence is that any variable
in a function is 'live' for the entire function, including variables
used only as the index in for loops and variables used only for
elements in list comprehensions. So when you write:
newlst = [x for x in lst if foobar(x)]
For the rest of the function (or the entire module) you will have an
x variable (in this case with the value of the last element of lst
at the time of the list comprehension).
This is a little bit surprising, at least for me, because
intellectually I usually consider such variables dead the moment the
list comprehension or for loop is done. For example, I don't read
their value after that point.
In some languages, index variables really are dead after the loop finishes; references to them outside the loop will get some sort of 'no such variable' error. In some other languages, such as perl, such scope restriction is optional but the recommended style.