I had the pleasure of meeting the amazing Alan Perlis and talking with him a few times, when I was still a student. He and I had in common a deep love and respect for two very different programming languages: Lisp and APL. Following in his footsteps is a daunting task, even though he blazed an excellent trail. Still, I would like to reexamine one comment he made in the original foreword to this book (and, please, I suggest that you read his foreword, which immediately follows this one, before you finish this one). Is it really true that it is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures?

To answer that question carefully, we first need to ask whether that one data structure is universal: can it conveniently fulfill the roles of those 10 more specialized data structures?

For that matter, we can also ask: do we really need 100 functions? Is there a single universal function that can fulfill the roles of all those other functions?

The surprising answer to that last question is yes; it is only slightly tricky to construct a function that accepts (1) a data structure that serves as a description of some other function, and (2) a list of arguments, and behaves exactly as that other function would when applied to the given arguments. And it is only slightly tricky to design a data structure capable of describing any computation whatsoever. One such data structure (the tagged-list representation of expressions and statements, paired with environments that associate names with values) and one such universal function (apply) are described in Chapter 4 of this book. So maybe we need only one function and one data structure.

That is true in theory. In practice, we find it convenient to draw distinctions that help us, as human beings constructing descriptions of computations, to organize the structure of our code so that we can better understand them. I believe that Perlis was making a remark not about computational capability, but about human abilities and human limitations.

One thing the human mind seems to do well is to name things; we have powerful associative memories. Given a name, we can quickly recall some associated thing to mind. This is why we typically find it easier to work with the lambda calculus than the combinatory calculus; it is much easier for most people to interpret the Lisp expression (lambda (x) (lambda (y) (+ x y))) or the JavaScript expression x => y => x + y than the combinatory expression

((S ((S (K S)) ((S ((S (K S)) ((S (K K)) (K +)))) ((S (K K)) I)))) (K I))

So while in principle we could get by with just one universal function, we prefer to modularize our code, to give names to the various pieces, and to mention the names of function descriptions rather than constantly feeding the descriptions themselves to the universal function.

In my 1998 talk Growing a Language, I commented that a good programmer does not just write programs. A good programmer builds a working vocabulary. As we design and define more and more parts of our programs, we give names to those parts, and the result is that we have a richer language in which to write the rest.

But we also find it natural to draw distinctions among data structures, and to give them names.

It may be that nested lists are a universal data structure (and it is worth noting that many modern and widely used data structures, such as HTML and XML and JSON, are also parenthetically nested representations, only slightly more elaborate than Lisp's bare parentheses). There are also many functions, such as finding the length of a list or applying a function to every element of a list and getting back a list of the results, that are useful in a wide variety of situations. And yet, when I am thinking about a specific computation, I often say to myself, This list of two things I expect to be a personal name and a surname, but that list of two things I expect to be the real and imaginary parts of a complex number, and that other list of two things I will regard as the numerator and denominator of a fraction. In other words, I draw distinctions—and it may be useful to represent those distinctions explicitly in the data structure, in part to prevent mistakes such as accidentally treating a complex number as a fraction. (Again, this is a comment about human abilities and human limitations.)

Since the first edition of this book was written, almost four decades ago, a lot more ways of organizing data have become relatively standard, in particular the object-oriented approach, and many languages, including JavaScript, support specialized data structures such as objects and strings and heaps and maps with a variety of built-in mechanisms and libraries. But in doing so, many languages abandoned support for more general, universal notions. Java, for example, originally did not support first-class functions, and has incorporated them only relatively recently, greatly increasing its expressive power.

APL, likewise, originally did not support first-class functions, and moreover its original single data structure—arrays of any number of dimensions—was not so conveniently useful as a universal data structure because arrays could not contain other arrays as elements. More recent versions of APL do support anonymous function values and nested arrays, and these have made APL dramatically more expressive. (The original design of APL did have two very good things going for it: a comprehensive set of functions applicable to that one data structure, and moreover an extremely well chosen set of names for those functions. I'm not talking about the funny symbols and Greek letters, but the spoken words that APL programmers use when mentioning them, words like shape, reshape, compress, expand, and laminate; these are names not for the symbols, but for the functions they represent. Ken Iverson had a real knack for choosing short, memorable, vivid names for functions on arrays.)

While JavaScript, like Java, was originally designed with objects and methods in mind, it also incorporated first-class functions from the beginning, and it is not difficult to use its objects to define a universal data structure. As a result, JavaScript is not as distant from Lisp as you would think, and as this edition of Structure and Interpretation of Computer Programs demonstrates, it is a good alternate framework for presenting the key ideas. SICP was never about a programming language; it presents powerful, general ideas for program organization that ought to be useful in any language.

What do Lisp and JavaScript have in common? The ability to abstract a computation (code plus some associated data) for later execution as a function; the ability to embed references to such functions within data structures; the ability to invoke functions on arguments; the ability to draw a distinction (conditional execution); a convenient universal data structure; completely automatic storage management for that data (which seems like a no-brainer, given everything else, until you realize that many widely used programming languages don't have it); a large set of useful functions for operating on that universal data structure; and standard strategies for using the universal data structure to represent more specialized data structures.

So maybe the truth is somewhere in between the extremes that Perlis so eloquently posited. Maybe the sweet spot is something more like 40 functions general enough to operate usefully on a universal data structure such as lists, but also 10 sets of 6 functions each that are relevant when we take one of 10 specialized views of that universal data structure. This is manageable if we give good names to these functions and specialized views.

As you read this book, please pay attention not only to the programming language constructs and how they are used, but also to the names given to functions and variables and data structures. They are not all as short and vivid as the names Iverson chose for his APL functions, but they have been chosen in a deliberate and systematic way to enhance your understanding of the overall program structure.

Primitives, means of combination, functional abstraction, naming, and conventions for using a universal data structure in specialized ways by drawing distinctions: these are the fundamental building blocks of a good programming language. From there, imagination and good engineering judgment based on experience can do the rest.