I was talking to one of my students earlier, and lent him a book to read over summer. It was only after he’d left that I realised that — for me at any rate — the book I’d given him is probably the most seminal work in the whole of computer science, and certainly the book that’s most influenced my career and research interests.
So what’s the book? Structure and interpretation of computer programs by Hal Abelson and Jerry Sussman (MIT Press. 1984. ISBN 0-262-01077-1), also known as SICP. The book’s still in print, but — even better — is available online in its entirety.
OK, everyone has their favourite book: why’s this one so special to me? The first reason is the time I first encountered it: in Newcastle upon Tyne in the second year of my first degree. I was still finding my way in computer science, and this book was a recommended text after you’d finished the first programming courses. It’s the book that introduced me to programming as it could be (rather than programming as it was, in Pascal at the time). What I mean by that is that SICP starts out by introducing the elements of programming — values, names, binding, control and so on — and then runs with them to explore a quite dazzling breadth of issues including:
- lambda-abstraction and higher-order computation
- complex data structures, including structures with embedded computational content
- modularity and mutability
- streams
- lazy evaluation
- interpreter and compiler construction
- storage management, garbage collection and virtual memory
- machine code
- domain-specific languages
…and so forth. The list of concepts is bewildering, and only stays coherent because the authors are skilled writers devoted to their craft. But it’s also a remarkable achievement to handle all these concepts within a single language framework — Scheme — in such a way that each builds on what’s gone before.
The second reason is the way in which Hal and Jerry view everything as an exercise in language design:
We have also obtained a glimpse of another crucial idea about languages and program design. This is the approach of stratified design, the notion that a complex system should be structured as a sequence of levels that are described using a sequence of languages. Each level is constructed by combining parts that are regarded as primitive at that level, and the parts constructed at each level are used as primitives at the next level. The language used at each level of a stratified design has primitives, means of combination, and means of abstraction appropriate to that level of detail.
Layered abstraction of course is second nature to all computer scientists. What’s novel in this view is that each level should be programmable: that the layers are all about computation and transformation, and not simply about hiding information. We don’t see that in the mainstream of programming languages, because layering doesn’t extend the language at all: Java is Java from top to bottom, with class and libraries but no new control structures. If a particular domain has concepts that would benefit from dedicated language constructs, that’s just tough. Conversely (and this is something that very much interests me) if there are constructs it’d be desirable not to have in some domain, they can’t be removed. (Within the language, anyway: Java-ME dumps some capabilities in the interests of running on small devices, but that’s not something you can do without re-writing the compiler.)
The third influential feature is the clear-sighted view of what computer science is actually about:
The computer revolution is a revolution in the way we think and in the way we express what we think. The essence of this change is the emergence of what might best be called procedural epistemology — the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects. Mathematics provides a framework for dealing precisely with notions of “what is.” Computation provides a framework for dealing precisely with notions of “how to.”
I’ve taken a view before about computers being the new microscopes, opening-up new science on their own as well as facilitating existing approaches. The “how to” aspect of computer science re-appears everywhere in this: in describing the behaviours of sensor networks that can adapt while continuing the reflect the phenomena they’ve been deployed to sense; in the interpretation of large-scale data mined and mashed-up across the web; in capturing scientific methods and processes for automation; and so forth. The richness of these domains mitigates against packaged software and encourages integration through programming languages like R, so that the interfaces and structures remain “soft” and open to experimentation.
When I looked at my copy, the date I’d written on the inside was September 1988. So a book I bought nearly 22 years ago is still relevant. In fact, I’d go further and say that it’s the only computer science book of that age that I’d happily and usefully read again without it being just for historical interest: the content has barely aged at all. That’s not all that unusual for mathematics books, but it’s almost unheard of in computer science, where the ideas move so quickly and where much of what’s written about is ephemeral rather than foundational. It goes to show how well SICP nailed the core concepts. In this sense, it’s certainly one of the very few books on computer science that it’s worth reading twice (or more). SICP is to computer science what Feynman’s Lectures on Physics are to physics: an accessible distillation of the essence of the subject that’s stood the test of time.
UPDATED 27Jan2024: This book also appears in my annotated Lisp bibliography