> That's why I like Clojure's philosophy of a few data structures and many functions operating on them.
Which in practice means that a few data structures that are not perfect for solving a specific problem are forced (with repeated hammer blows) to bend to the problem. Like the old style LISP AList's used as a map. Probably the worst possible structure for representing a map. But yeah it kinda works as long as you don't have much data.
The assocation list is a poor data structure for representing a map, if the most important requirement is to have fast access to any key of a large map.
However, the association list is an excellent data structure if an important requirement is to be able to cheaply extend a map with new keys functionally: without altering the original. It also provides the requirement that duplicate keys added to the front shadow existing ones. It is also very simple; it is easy to verify that operations are correct.
With the above properties, association lists, directly provide an easy and correct implementation model for lexical environments.
The empty top-level lexical environment is an empty list. Adding a frame with new variables, including ones that shadow existing variables, is just consing pairs onto the list. The assoc operation correctly implements lexical variable lookup. The environment for making a lexical closure is just a copy of the assoc list pointer that you have now. Because the bindings are independent pair objects in the association list, individual bindings can be located and selected, and combined into another association list. A newly created association list environment can trivially capture an arbitrary subset of bindings from another one without mutating it.
Even if we don't use this representation in production use, it provides an important reference model. Anything more complicated has to produce the same results; we can start with assoc based environments, build a lot of code, and then use that as regression test cases for going to a different environment representation.
It's good enough for pattern matching and logic languages where the number of variables isn't great, but the search has to do things that are complicated enough without a heavy-weight environment structure.
> AList's used as a map. Probably the worst possible structure for representing a map.
They're more flexible than hash tables and often faster; what makes them so awful? They both have trade-offs that make them better and worse in different contexts, depending what you're optimising for.
Under the right circumstances, a lookup table could be worse. In a simple interpreter, I would hate to pass down a vector of pairs for the environment representation; it would have to be wholly duplicated to extend the environment.
Which in practice means that a few data structures that are not perfect for solving a specific problem are forced (with repeated hammer blows) to bend to the problem. Like the old style LISP AList's used as a map. Probably the worst possible structure for representing a map. But yeah it kinda works as long as you don't have much data.