SICP
I got back from Wales on Tuesday, to find my copy of Structure and Interpretation of Computer Programs (sometimes known as the Wizard book, or SICP, or "sickup", as I've taken to calling it) waiting for me. It's the first-year computer science textbook used at MIT, and early signs are that it's going to be worth its weight in rather good coffee.
It's divided into five chapters, and it's meant to take you from knowing nothing about programming to being able to write a fairly accomplished compiler for a Scheme-like language.
Chapter 1, Building Abstractions with Procedures, introduces the very basics of the Scheme language (procedure definitions and calls, basically, plus lambdas and let-bindings), and does some stuff with numeric algorithms (calculation of Fibonacci numbers, factorials, square roots, trig functions, primality testing1, etc2) in both recursive and iterative (by which they really mean tail-recursive) forms, before introducing higher-order functions and showing how to generalise much of the code from the previous exercises. They also introduce classic CS tools like loop invariants and big-O notation.
Chapter 2, Building Abstractions with Data, introduces data structures, starting with rational numbers (represented as cons cells), then moving on to interval arithmetic; lists; trees; symbols; a DSL for constructing pictures; Huffman trees; and symbolic algebra, before unifying some of the previous examples by doing some generic programming that makes use of them all.
Chapter 3, Modularity, Objects and State does pretty much what it says on the tin - all the code to this point has been referentially transparent, and here they introduce assignment and destructive update, discussing the pros and cons of allowing them. They use this as a jumping-off point for discussing data modularity, concurrency, constraint programming, memoisation and lazy data (and hence infinite data structures). This chapter is heavily philosophical, with much discussion as to the nature of "time" and "sameness", and at one point they conclude that the real problems in concurrency are probably more likely to be solved by philosophers than hackers.
Chapter 4, Metalinguistic Abstraction3, seems in many ways to be the core of the book: they advocate designing software as a program written in a highly domain-specific language, atop an interpreter for that language (or possibly as several such layers...). Based on On Lisp and general Lisp advocacy I've encountered on the Net, I'd expected this to be all about the joys of macros, but actually macros only get one mention in the book, and that's in a footnote. This is all about writing traditional interpreters with an eval-apply cycle and symbol tables and that, and they conclude the chapter by having you write interpreters for a variant of Scheme that has lazy evaluation, and (as seems to be traditional) for a Prolog-like language with nondeterminism.
I haven't looked at Chapter 5, Computing with Register Machines, much: on a first glance, it looks like solid traditional stuff about writing compiler backends. Useful to know, no doubt, and I'm sure there's more exciting stuff in there too.
I've been working through the exercises, and I'm up to about page 70 (most of the way through Chapter 1). So far, there hasn't been anything really difficult, though a couple of the exercises require you to do Actual Experiments on a computer, and since, what with one thing and another, I don't have a working one at the moment (I'm typing this on wormwood_pearl's laptop), I haven't been able to do these. Some of the algorithms are new to me, and I've particularly enjoyed doing some programming with loop invariants (but how do you find them in the first place? Presumably there are techniques...), but it's hard to shake off the feeling that a lot of it is old hat; I've been programming computers for nearly twenty years, I'm no longer surprised by the concept of a data structure :-) I've enjoyed the philosophical and historical asides - if an algorithm dates back to ancient Egypt, they'll tell you which papyrus fragment it was found on - and the generally thoughtful and informed tone of the book. The progression from procedural to data-driven to metalinguistic programming reminds me of Eric Raymond's The Art of Unix Programming, but this is surely not coincidence - like many expert Unix hackers, Eric was a Lisper first. totherme may be amused to learn that his old tutor, Joe Stoy, is a frequently-cited contributor :-)
1Including some probabilistic algorithms - the ease with which one can roll a die in Lisp is not such a trivial matter :-)
2Plus ways of making change from a dollar or pound - I was amused to note that they haven't updated it to reflect the disappearance of the halfpenny :-)
3They're quite fond of the prefix "meta": for instance, they call an interpreter for language X written in language X a "metacircular interpreter", rather than just a circular one, for reasons which I can't quite fathom.
It's divided into five chapters, and it's meant to take you from knowing nothing about programming to being able to write a fairly accomplished compiler for a Scheme-like language.
Chapter 1, Building Abstractions with Procedures, introduces the very basics of the Scheme language (procedure definitions and calls, basically, plus lambdas and let-bindings), and does some stuff with numeric algorithms (calculation of Fibonacci numbers, factorials, square roots, trig functions, primality testing1, etc2) in both recursive and iterative (by which they really mean tail-recursive) forms, before introducing higher-order functions and showing how to generalise much of the code from the previous exercises. They also introduce classic CS tools like loop invariants and big-O notation.
Chapter 2, Building Abstractions with Data, introduces data structures, starting with rational numbers (represented as cons cells), then moving on to interval arithmetic; lists; trees; symbols; a DSL for constructing pictures; Huffman trees; and symbolic algebra, before unifying some of the previous examples by doing some generic programming that makes use of them all.
Chapter 3, Modularity, Objects and State does pretty much what it says on the tin - all the code to this point has been referentially transparent, and here they introduce assignment and destructive update, discussing the pros and cons of allowing them. They use this as a jumping-off point for discussing data modularity, concurrency, constraint programming, memoisation and lazy data (and hence infinite data structures). This chapter is heavily philosophical, with much discussion as to the nature of "time" and "sameness", and at one point they conclude that the real problems in concurrency are probably more likely to be solved by philosophers than hackers.
Chapter 4, Metalinguistic Abstraction3, seems in many ways to be the core of the book: they advocate designing software as a program written in a highly domain-specific language, atop an interpreter for that language (or possibly as several such layers...). Based on On Lisp and general Lisp advocacy I've encountered on the Net, I'd expected this to be all about the joys of macros, but actually macros only get one mention in the book, and that's in a footnote. This is all about writing traditional interpreters with an eval-apply cycle and symbol tables and that, and they conclude the chapter by having you write interpreters for a variant of Scheme that has lazy evaluation, and (as seems to be traditional) for a Prolog-like language with nondeterminism.
I haven't looked at Chapter 5, Computing with Register Machines, much: on a first glance, it looks like solid traditional stuff about writing compiler backends. Useful to know, no doubt, and I'm sure there's more exciting stuff in there too.
I've been working through the exercises, and I'm up to about page 70 (most of the way through Chapter 1). So far, there hasn't been anything really difficult, though a couple of the exercises require you to do Actual Experiments on a computer, and since, what with one thing and another, I don't have a working one at the moment (I'm typing this on wormwood_pearl's laptop), I haven't been able to do these. Some of the algorithms are new to me, and I've particularly enjoyed doing some programming with loop invariants (but how do you find them in the first place? Presumably there are techniques...), but it's hard to shake off the feeling that a lot of it is old hat; I've been programming computers for nearly twenty years, I'm no longer surprised by the concept of a data structure :-) I've enjoyed the philosophical and historical asides - if an algorithm dates back to ancient Egypt, they'll tell you which papyrus fragment it was found on - and the generally thoughtful and informed tone of the book. The progression from procedural to data-driven to metalinguistic programming reminds me of Eric Raymond's The Art of Unix Programming, but this is surely not coincidence - like many expert Unix hackers, Eric was a Lisper first. totherme may be amused to learn that his old tutor, Joe Stoy, is a frequently-cited contributor :-)
1Including some probabilistic algorithms - the ease with which one can roll a die in Lisp is not such a trivial matter :-)
2Plus ways of making change from a dollar or pound - I was amused to note that they haven't updated it to reflect the disappearance of the halfpenny :-)
3They're quite fond of the prefix "meta": for instance, they call an interpreter for language X written in language X a "metacircular interpreter", rather than just a circular one, for reasons which I can't quite fathom.