Wandering Thoughts archives

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

programming/OnLispConsCells written at 17:21:46; Add Comment

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.

python/VariableScopeConsequences written at 00:40:19; Add Comment


Page tools: See As Normal.
Search:
Login: Password:
Atom Syndication: Recent Pages, Recent Comments.

This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.