An ode to Paradigms of AI Programming
Ignore the title. Even if your eyes are attracted to the word “Lisp”, ignore that too. Paradigms of AI Programming (PAIP) is just the best introduction to data-driven programming that you’ll ever find.
By the time you reach Chapter 2, you’ll see the difference between a straight-forward solution (not extensible) to a problem and a truly data-driven solution.
The two versions of the preceding program represent two alternate approaches that come up time and time again in developing programs: (1) Use the most straight-forward mapping of the problem description directly into Lisp code. (2) Use the most natural notation available to solve the problem, and then worry about writing an interpreter for that notation.
The reader may notice that in most cases, we choose the second.
As you continue to work through the book, you’ll get this approach reinforced and develop your sense of aesthetics.
There are six maxims that every programmer should follow:
· Be specific.
· Use abstractions.
· Be concise.
· Use the provided tools.
· Don’t be obscure.
· Be consistent.
Once you’ve got an overview of Lisp, you’ll get the chance to implement classic AI problems (such as the General Problem Solver or Eliza). Moreover, you explore how to turn concrete implementations into abstract solutions.
I love the code above because of its simplicity. Plug the right argument in, and you have got depth-first, breadth-first, beam search or even an A* search from that one concisely written lump of code.
The book doesn’t just present beautiful abstract code that performs a job, and there’s a whole chapter on efficiency.
However, this does not mean that writing an efficient program is fundamentally different from writing a working program. Ideally, developing an efficient program should be a three-step process. First, develop a working program, using proper abstractions so that the program will be easy to change if necessary. Second, instrument the program to determine where it is spending most of the time. Third, replace the slow parts with faster versions, while maintaining the program’s correctness.
To improve performance doesn’t mean “uglifying the code”. It doesn’t mean using bit-twiddling tweaks or mutating state everywhere. PAIP presents four language-independent techniques, Caching, Compiling, Delaying and Indexing.
Caching gives a lovely demonstration of the power of Lisp by introducing memoization. If you’ve not come across it before, memoization is a technique to make functions remember calls so that subsequent calls to a function with the same argument return a cached value.
The classic implementation of the Fibonacci function is dog slow (a very technical term!) but it’s also very clean. Introduce memoization appropriately, and you have a version with a much-improved runtime, without sacrificing the clarity of the code.
The section on Compiling builds upon the “interpreter for the notation” style introduced early on in PAIP. To write a compiler, we take the Lisp code that defines the problem and use macros to rewrite them in a new, more efficient language.
Delaying computation is a common theme now (Lazy<T> in C# is a great example), but when I read PAIP, this introduced me to a new way of thinking (infinite lists? Thunks?).
There are many different models of programming (such as functional or object-oriented). I’m a big believer that the more paradigms you experience, the more tools you have at your disposal for finding the right solution.
PAIP introduced me to Prolog (a logic-based programming language). Prolog has three big ideas, a database of assertions, unification and back-tracking. I’m not going to attempt to explain these; I’d do a much lower quality job of it than the book would. I’m just trying to leave a few nuggets to convince you to read the book and work through the exercises 😉 .
Norvig also introduces object-oriented programming in Lisp (Design Patterns in Dynamic Programming is another exciting read in this context.). What’s eye-opening here is that object-oriented systems are just another language written in Lisp — it’s not the be-all and end-all of the language as it is in C# / Java.
I could carry on, but I’ve waffled for a fair few words. So to round things off, PAIP is an under-appreciated classic! It’s one of the few books worth devoting a few months working through the exercises; you’ll come out of the other side a better programmer!