Some Inconsequential Lisp History; or, the Story of Associative Lists

June 1, 2022

Today in IRC (#lisp in libera.chat) there was an interesting question posed:

are plists or alists older? or were both always used?

So I decided to go dig in the Lisp 1 Programmer's Manual (1960) and the Lisp 1.5 Programmer's Manual (1962). I'm sure there's lots of computing history buried in those pages, from how real programming on the IBM 704 is done to how they made a full-featured interpreter and self-hosted compiler work on such a system. But we don't have time for that, so I just grepped for association list and property list.

An Aside

In Lisp there are two semi-common data structures called association lists (“alists”) and property lists (“plists”). Collectively they may be rather confusingly called associative lists, because they associate keys and values.

An alist is structured like so:

((key1 . value1) (key2 . value2) <...> (keyn . valuen))

Basically, it's a list of pairs, where the car (first item in a pair) is the key and the cdr (second item in a pair) is the value.

A plist is structued like so:

(key1 value1 key2 value2 <...> keyn valuen)

Basically, it's a flat list where the first item is a key, the next item is the value for that key, then the item after that is the next key, and so on.

They're both functionally equivalent for many operations, although alists are easier to iterate over (iterate over every item in the list rather than having to jump over items) and plists are easier to type (no need for nesting or dotted pairs). And you can treat alists like normal lists, since they are just that, normal lists; while if you treat a plist like a normal list it'll often break the plist.

Back to the Question At Hand

Lisp 1.5

So, starting with Lisp 1.5, I discovered mentions of both alists and plists.

Association lists seemed to be pretty much in the same form as they are today. It has operations like assoc defined for it to get a key-value pair from it, etc. This implies that they were probably largely used for user code. The Lisp 1.5 implementation itself primarily seems to use alists as a handy way to create a list of variables and their associated values. For instance, there's a function called sublis that functions sorta similarly to let, you give it an association list of variables and values and in the body it will replace instances of each variable symbol with its associated value.
See the Lisp 1.5 Programmer's Manual pp. 11–13, 103.

Property lists don't seem to have any operations defined for them that would encourage programmers to use it, and seem to be used in Lisp 1.5 itself for one thing: storing the eponymous properties about an interned symbol. So each interned symbol would have an associated property list, storing things such as its internal ID, what its printing name is, and its associated value if it's a variable or its associated s-expression or compiled machine code if its a function.
See the Lisp 1.5 Programmer's Manual § 7.3.

I imagine modern plists came about when someone used the structure of a symbol property list in their user code, and just adopted the same name for it.

Lisp 1

But let's go back further to Lisp 1, to see what it's like there.

There are mentions of both alists and plists; but strangely it seems that in Lisp 1, what they call association lists throughout the manual are actually identical in form and function to Lisp 1.5's property lists.
See the Lisp 1 Programmer's Manual § 6.2 .

There's still mentions of property lists as well… However, it's only mentioned in a single footnote:

In the local M.I.T. patois, association lists are also referred to as “property lists”

—Lisp 1 Programmer's Manual p. 88.

So in Lisp 1, alists and plists referred to the same thing, and it was only sometime between Lisp 1 and 1.5 that they diverged into distinct structures. I assume that at some point someone introduced modern alists, and they decided to finalize on the term property list to refer to the list of properties for each symbol and changed association list to refer to the more common form of an associative lists in user code.