John Allen. Anatomy of Lisp. McGraw-Hill. ISBN
0-07-001115-X. 1978.
This is a hard book to characterise. It’s simultaneously an
introduction, a collection of advanced (for the time) programming
techniques, and a guide to some very low-level implementation
details. It contains a lot of the usual introductory material, but
then delves into different representational choices for the basic
data structures – lists, but also arrays and hash tables as well
as Lisp code itself – and for the frames needed to represent
function calls. It the tackles interpretation versus
compilation, and even topics such as cross-compilation and
just-in-time or memoised compilation.
It’s impossible to read this book without thinking of SICP, and
indeed I think in many ways it’s a direct precursor. (It’s
referenced a couple of times in SICP.) It has that same
combination of high-level, semantics-driven programming combined
with descriptions of underlying mechanisms. Where I think it
mainly differs is that it mixes representations, using a more
semantics-driven notation and explicit assembler instructions
rather than sticking with Lisp variants for everything. It’s
only when you see the two approaches side by side that you realise
how clear Lisp can be in radically different contexts..
Another important book was published in 1978: Kernighan and
Ritchie’s The C programming language. The two books share a
certain low-level focus, but come to very different conclusions
about the correct approach to dynamic storage, as the following
footnote by Allen (slightly edited for clarity) illustrates:
Experiments have been performed in which Lisp programmers were
allowed to return “garbage” to the free-space list themselves. The
results were disastrous: list structure thought to be garbage was
returned to the free-space list even though the structure was
still being used by other computations.
C, of course, accepts this “disaster” as a natural consequence of
manual allocation management. It encapsulates the different
attitudes of the two contemporary language communities, though:
one wanting a machine in which to think (and willing to use
computing power to simplify tasks), and those wanting raw
performance from limited hardware (and willing to complicate the
programming task to get it).
Overall, Allen’s book is a great attempt at an end-to-end
discussion of Lisp all the way down to the metal. Many of the
techniques are still relevant, at least as exemplars against
later, more efficient, techniques should be judged.
(Thanks to Paul McJones for pointing me to the free PDF of the book,
which he was responsible for developing. See this post for a history
of how this came about.)
