briancarper.net (λ) (Tag: PAIP)

PAIP review

Mon, 10 Mar 2008 17:21:35 -0700

It's been a while since I acquired PAIP. I can't say I've read all of it over the past couple months, but I've read most of it.

The initial chapters that give an intro to Common Lisp seem largely useless to me. There are better books to introduce Common Lisp (especially now that we have PCL). Norvig admits as much himself, and thankfully doesn't devote much of the book to intro material.

Once you get past those, this book is densely packed with information. Just tracing through and understanding the source code would probably take me a couple of months, let alone grasping all the concepts the source code is trying to exemplify. It's a wonder to me that one person can produce this much material. But the downside is that it's a bit difficult to read at times; it's kind of dry and reads like a text book. In spite of that, I was glued to this book for quite some time; the information inside is engaging enough to make up for the lack of presentation.

Some of the examples of code in the book really are quite startling. For example Norvig writes a pattern-matcher that implements some subset of Perlish regular expressions, and it only takes a couple pages of code. Later in another couple pages of code, he implements a variant of Prolog. At one point he writes some pattern-matchers that can parse a surprisingly large subset of the English language. But a lot of other examples of code weren't quite so interesting to me personally; a lot of the material is dedicated to tree and graph search algorithms, which brought to mind long boring lectures from my college days. (As a side note, it's very sad how much of the history of AI can be reduced to "clever graph search algorithms". I don't know much about AI today but I hope it's advanced a bit past that.)

This book is from 1992 and some of it does feel a bit dated. This book was apparently written just after Common Lisp was standardized. Object oriented programming was apparently relatively new back then, and Norvig glosses over CLOS. Most of the code is written in functional style. However Common Lisp today still doesn't force OO on you by any means, and a lot of Lispers today apparently still don't care much for OO, so the code is more relevant than you'd imagine.

And as you can't help realizing after reading an old CS book or two, CS as a science hasn't seen all that many breakthroughs in the short couple of decades it's been around. It's really quite sad in a way that a book written over 15 years ago can still be so relevant; we have all these huge advances in computer hardware, yet it still feels like we're in the Stone Age of computer programming.

Not being an Artifical Intelligence person myself, I can't judge how well this book serves as a guide to AI. But Norvig's stated goal was in large part to show the history of AI, and he does that very well. (This was history back in 1992 when the book was written, so it's even older now, but still interesting.) He walks through implementing a lot of famous AI programs from the past, and explains their limitations and how they can be improved. Want to write ELISA or other chat-bots? He does that. Want to write an Othello-playing program? He does that too.

One of the best things about this book is that Norvig's code is just about the Lispiest code I've seen. He does many things that take full advantage of all the nooks and crannies of Common Lisp and wouldn't make much sense in other languages. This is a good book to help you think in Lisp.

So I recommend this book. Though I'm unsure I'll ever manage to absorb most of the information in it.

PAIP, review one of probably many

Wed, 06 Feb 2008 01:12:18 -0800

I got through the first four chapters of PAIP yesterday and today. It's good so far. I had reservations about spending $80 on a book, but it's 950 pages and almost all of it is good stuff, from what I can see at a glance. Little space is wasted on introduction material or tutorials for people who know nothing about programming. He dives right into the good stuff in chapter four.

Already I've picked up a few nice bits of info, interesting standard functions / macros like TRACE which is good for debugging. And SUBLIS which takes a list of (key . value) sublists and replaces all the keys with all the values, in some other list. Common Lisp is such a freaking huge language, in terms of its standard library of functions. Good thing or bad thing? It may be a bad thing if not for the fact that you load Lisp once and it persists forever.

Norvig makes an interesting point about the REPL. What do most programs need to do? Take input from the user, do something with it, and give output back to the user.

To get input, your program can read from command-line args, or prompt to STDIN, or take it out of text fields in a QT app, or read it from a config file. But it's generally always strings. So you get some strings, and then what? You have to figure out what the strings say, and either turn the strings into something usable or use the strings to figure out what action to perform. So you may have a dedicated library to parse command-line args and a dispatch table to map them to function calls. Or you may match the strings against a regex and depending what the strings look like, turn them into your language's representation of an integer or float using some "parseInt" or "parseFloat" functions. Or if your strings are XML, you may parse them into some big funky XML structure, then access bits of that structure to figure out what to do.

In Lisp on the other hand, you happen already to have a powerful reader/parser at your disposal: the REPL itself. It already knows how to read string representations of lists, numbers, pathnames, and many other things, and it can turn them into Lisp objects for you with no effort on your part. If you were using Ruby or Perl, short of ~~evil~~ eval, you wouldn't get anything close to that capability in your program.

What's more, the REPL knows how to read string representations of Lisp code (new functions and function calls etc.), and evaluate the code and end up with Lisp objects. It would be like if you wrote a C program which prompted you for input, and the input you gave could be a string representing a new C program that when run would produce a string that contained your input (or produce in-memory C structures your C program could use). So the main program would call GCC and compile and run your input to get results and use those results as its final input. Except that still wouldn't be nearly as powerful as what Lisp is doing.

So if you can figure out how to shape your input into a form that the Lisp reader can read, you're set. And it so happens sexps are a great representation for a great many things. Maybe this is part of why Lispers seem to worship the REPL and shun compiling their apps into command-line, standalone executables? Maybe this is part of what's meant by the oft-quoted-to-death Greenspun's 10th Rule?

Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

Much more PAIP to follow. It should be enjoyable. There's nothing like a good book.