Wednesday, June 30, 2004

Programming Language Pragmatics

Programming Language Pragmatics
Michael Scott; Morgan Kaufmann; 1-55860-442-1

I recently finished reading this and thought I should provide a review as it is a truely remarkable book. Fundamentally the book is an informal survey of the various fields of computer science and engineering that impact the design and implementation of programming languages, their interpreters, and compilers --- and it succeeds admirably. Specifically the chapters include:

  1. Introduction
  2. Programming Language Syntax. (FA/PDA's; regular expressions; context-free grammars; LL/LR parsers, including one of the clearest descriptions of LR parsing I have come across.)
  3. Names, Scopes, and Bindings. (Value lifetime; garbage collection; different scoping rules; different implementation approaches to scoping.)
  4. Semantic Analysis. (Attribute grammars; attribute flow. While well written, I personally found this one of the weaker chapters.)
  5. Assembly-Level Computer Architecture. (Effectively a one chapter synopsis of Hennersey and Patterson.)
  6. Control Flow. (Selection; Iteration; Recursion; and Non-determinisim)
  7. Data Types. (Static and Dynamic checking; discussion of implementation; A short discussion of HM-style type inference; as well as discussions on the particular issues associated with Records, Arrays, Pointers, Lists, and IO.)
  8. Subroutines and Control Abstraction. (Calling sequences and conventions; call-stack/tree management; exceptions - including continuations; coroutines.)
  9. Building a running program. (Compiler backends; intermediate code; register allocation; linking - including dynamic linking and pic.)
  10. Data Abstraction and Object Orientation. (OOP, including semantics and implementation concerns of encapsulation; inheritance; finalisation; polymorphism. All discusses with reference to a multitude of different languages and approaches to OOP).
  11. Nonimperative Programming Models: Functional and Logic Languages. (Split into two sections, one on functional and one on logic programming. Of particular interest are introductions to both the lambda and first-order predicate calculi; and discussions on the advantages these mathmatical groundings provide programmers).
  12. Concurrency. (Background; Theory; Shared-memory; and Message-Passing. A very impressive introduction to concurrency.)
  13. Code Improvement. (By necessity of space, a very limited introduction to code optimisation. Still it manages to cover a reasonable amount of ground, although I would have liked more discussion on cache optimisation techniques. Peephole Optimisation; Global Redundancy; Data Flow Analysis; Loop Invariants and Unrolling; Instruction Scheduling; Register Allocation).
Given the breadth of the coverage, the reader will require additional reading to gain any appreciable capacity in any specific area. However this book does provide a very reasonable introduction to areas that will provide much needed context when approaching any more focused work. It's not going to replace the Dragon Book, but it will make the Dragon Book far more approachable, and I wish I had read PLP before I had to wade my way through the much less approachable prose of Aho, Sethi and Ullman. Similarly, the reader is still going to want to read Patterson and Hennersey. However the discussions of language semantics and their associated demands on computer architecture will answer many questions of motivation given short treatment in the more advanced work.

In conclusion, I would highly recommend this to any programmer who has experience in only one or two languages; any undergraduate wanting to broaden their understanding of programming; any professional wanting to learn more about compiler/interpreter/parser theory and implementation and wants context for the more focuses works in this field.