Category Archives: SICP

Why lists are not primitive

Yesterday’s SICP study group call indulged briefly in the “why LISP hasn’t caught on” theme. I suggested that some programmers seem to have a limited tolerance for abstraction, and cited the well-known Primitive Obsession anti-pattern as evidence. One of the other participants (I’m sorry that I don’t know all the voices yet) challenged that statement. After pointing out how often the humble list is used as a universal data structure, he asked whether that was Primitive Obsession in another disguise. The conversation moved on, but that question stuck in the back of my mind.

This morning it re-emerged, dragging the following conjecture.

Although the list is a fundamental structuring mechanism in LISP, it is far from “primitive” in way that e.g. int is a primitive data type in Java. Although number theory is a well-respected branch of Mathematics, Ben Bitdiddler and Eva Lu Ator can write application code littered with int variables without ever appealing to the theoretical properties of integers–Peano’s Postulates and the like. After all, they’ve known how to count and do arithmetic since elementary school, right?

On the other hand, the LISP list is a fairly abstract and conceptual beast; list-based code normally uses recursion, either explicitly or hidden beneath the thinnest of veneers, such as map and reduce. And from there, it’s the tiniest of steps to begin reasoning about one’s code via full-blown Mathematical Induction. Furthermore, all of the conceptual properties of lists are lying there in plain sight every time a list appears. Therefore I’m encouraged to think of generalities that can re-use those tasty properties with great freedom.

In contrast, how many Java programmers routinely make the jump from

String personName;


public class PersonName {
    public final String firstName;
    public final String lastName;

to including (correctly-working!) methods for comparison and equality? (And I’m not just picking on Java; the same is true of many other “C-like” language communities.) Even though strings are comparable, and ordered composites of comparable types have an obvious default comparability, realizing that obvious comparison is tedious and error-prone. If my language trains me to think that certain things are too much trouble, then I’ll tend to stop thinking about them. And when offered a language that makes them freely available again, it will be all too easy to ask, “Who needs all that stuff?”