đŸ Archived View for nytpu.com âș gemlog âș 2022-07-01.gmi captured on 2023-09-08 at 16:10:38. Gemini links have been rewritten to link to archived content
âŹ ïž Previous capture (2023-01-29)
âĄïž Next capture (2024-05-10)
-=-=-=-=-=-=-
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â.
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.
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.
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.
â