In writing Interpreting Lisp: programming and data structures, Knott aims to meet several goals in a concise and direct manner: first, to provide a gentle but precise introduction to Lisp; second, to illustrate the flavor of Lisp programming through several idioms; and third, to present the implementation of a Lisp interpreter in C. The result is a short (150 pages), somewhat idiosyncratic, and occasionally challenging book that can be used by computer science students, professionals, and hobbyists who know C and are interested in Lisp. The book focuses on the core functionality of the language, close to that of the original Lisp 1.5 presented by McCarthy et al. .
The book, which requires an unusually high degree of concentration and perseverance, provides a solid foundation for further explorations into the more advanced features and possibilities of Lisp. It will certainly be attractive to readers willing to invest some time and determination.
The only explicit expectation is some programming maturity. In practice, prior acquaintance with Lisp, but not necessarily expertise, would be helpful. Failing that, I would recommend reading concurrently an introductory book such as Touretzky’s Common Lisp: a gentle introduction to symbolic computation . Calculus is required to understand an application shown near the end of the book, and a solid knowledge of C, especially C pointers, is absolutely essential to understand the implementation of the Lisp interpreter.
The book, organized into 29 short chapters and a bibliography, begins by introducing the basic data structures of the interpreter and of Lisp; these are the foundations on which subsequent language features and the interpreter structures are elaborated. Although required by the format Knott has selected for presenting the material, the initial chapters are rather conceptual and consequently intellectually demanding.
Lisp appears gradually at first, then grows by turns rapidly or introspectively, and culminates in chapters 25 and 26, which deal with symbolic computation and game playing, two nontrivial topics not usually shown with this level of detail in books that introduce a programming language at an elementary level.
Chapter 25 develops a framework for computing the derivatives of real-value functions with real number arguments. Some fairly simple work to flesh out the desired functionality is left for the reader to provide. Chapter 26 sketches the theoretical background and develops the core of implementations for playing two-person zero-sum perfect-information games (games in which the entire state of the game is known to the players and the sum of the amounts won or lost is zero) using the minimax and alpha-beta pruning strategies. This chapter leaves significant amounts of work for the reader to complete in order to be able to play any given game that meets the criteria.
Exercises are inserted frequently within the running text. This makes them sharply relevant and appropriate; solutions are shown for many, but not all, exercises. Some require thought, outside research, and online experimentation. Questions and exercises are well thought out; few are trivial. Even when the solution is given, I would advise the reader to work out the solutions in detail; this will enhance the understanding of the material. Lisp, after all, is a language that repays, more than most languages, deep insight with unusually clean and elegant solutions.
Chapter 27 contains the C code of the Lisp interpreter. The source code (in fact, the entire book) can be downloaded from the author’s website . Installation in Linux should be straightforward; installation in other environments may require some customization.
The C code contains a fair amount of comments, but it is not explained in detail either in the body of the book nor within the code. Knott acknowledges that reading the code may be the most difficult part of the book, and that the code may at times be opaque. The reader not fluent in C can find himself easily lost. Along the way, Knott also inserts exercises that ask the reader to modify and extend the functionality provided; I strongly endorse those recommendations. The time and effort invested are well worth the rewards.
As I said, this is a potentially challenging, but correspondingly rewarding, book. It is best used within a classroom, but would also be useful to a motivated and persistent autodidact.