For Christmas this year, I received a shiny hardback copy of Parsing Techniques: A Practical Guide by Grune and Jacobs. It's a thrilling book, if you want to learn parsing, which I do.

Where most books proceed in a sort of linear fashion, this book teaches parsing in layers. First you learn what a grammar is. Then you learn what it means to parse: what's a parse tree? What's bottom-up vs. top-down? What's a leftmost vs. rightmost derivation?

Next you get some general ideas and methods for parsing, e.g. CYK and Unger, and then you dive into the implementations of parsers (in pseudocode and in C) in great detail. This is about as far as I've gotten so far, before having to go back and figure out what the heck I just read. But it's an interesting progression. Reading the book, I feel like I'm constantly revisiting things I learned a few chapters ago, but this time in more detail. The book kind of does a breadth-first traversal of the world of parsing.

Be warned however: this book is not easy reading. It's dense, heavy on the info, light on the entertainment. Unless you really get a kick of out parsing, this will probably put you to sleep if taken in large doses. But it is a trove of information, and I couldn't put the book down during certain chapters.

In fact there's so much information in this book that it's almost depressing. The bibliography alone takes up 1/4 of the book, and lists 1,500(!) authors. It'd take me a week to read the bibliography, and probably many years to read every book listed there. Parsing could easy consume a lifetime of study, and I'm saddened that I'm probably never going to find the time to master all there is to know. But such is life.

If I had one quibble with this book, it'd be the same quibble I have with most math papers. The notation is horrible. Say what you will about programmers, most of us know that code is written for humans, not for machines, and we give our variables descriptive names. In math it's all single letters variable names.

When the authors of this book run out of single letters, they use letters with bars over them, or bold letters vs. normal typeface letters, or they do things like this:

...whenever a non-terminal A is entered in to entry R_i,l of the recognition table because there is a rule A -> BC and B is in R_i,k, and C is in R_i+k,l-k, the rule A_i_l -> B_i_k C_m_n is added to the parse forest grammar, where m = i + k and n = i + l - k.

This is the first paragraph of a section. Those variables are not mentioned before this sentence. This is certainly not a style of writing that I'm used to reading. It takes me a good dozen tries to understand. (Using lowercase i's and l's right next to each other should be prohibited by law.)

In any case, this book is good. One of my favorite tools has always been Perl-style regular expressions, and I feel like this book has expanded my understanding of how they work. Learning to write a recognizer, learning how things are implemented under the hood, you couldn't ask for a more interesting topic. I can't wait to try writing a toy parser generator or regex recognizer in Clojure once I've solidified my understanding of some of these concepts.

Recently I received a preview copy of Peter Seibel's newest book, Coders at Work.

This is a wonderful book if you are a programmer and care at all about the art, craft, and/or science of programming. If there is any wisdom to be had in this fledgling field of ours, this book contains buckets of it.

The book consists entirely of long interviews with some big names in the world of programming: Donald Knuth, Ken Thompson, Jamie Zawinski, Guy Steele, Peter Norvig, the list goes on. There are also some names I wasn't quite so familiar with (but maybe should have been), like Brad Fitzpatrick, the inventor of Livejournal.

But everyone interviewed for the book has produced some grand, successful project in their time. These are tried-and-true, battle-tested programmers and in this book they share their war stories and advice.

I went on a reading binge over Thanksgiving break. Read on for reviews.

Test-Driven Development By Example

First I read Test-Driven Development By Example. This is a very short book, especially given the hefty price tag. I would probably not have bought this if I'd seen it on a shelf at the store rather than online.

That said, it's a good book if you want to understand the mindset behind the whole test-driven development fad. The book is heavy on mindset and light on mechanics; it doesn't tell you how to set up an environment, how to compile and run tests, or any such thing. It just goes through some examples and explains what the programmer was thinking, and how to tackle the problem from a TDD point of view. The intended audience therefore is someone who has plenty of experience programming and wants to learn a new way to look at problem solving.

The book goes through writing some terrible code (admittedly terrible by the author) to solve a simple problem, then refactoring the code to be less and less terrible by means of tests. The writing style is engaging and casual and he describes mistakes as well as successes, which is a nice way to write a tutorial book. The alternate writing style, belting out the correct answer the first time every time, is not as enlightening, and I appreciate it in this book.

The book places a heavy emphasis on writing tests FIRST, making small incremental changes, and refactoring as you go. It also explains how TDD can be related to various OOP design patterns, which I didn't find all that helpful. And it describes some "test patterns", which I found even less helpful. But it's mostly an aesthetic objection; something about "design patterns" sits less and less well with me the more I get away from Java-like languages. The information is still good, straightforward and to the point, take it or leave it.

I have been unable to drink the TDD Kool-Aid, but I can see where it'd probably result in an improvement in some of my code for certain specific kinds of problems. I'll probably try it out again next time I have to write a little library at work.

This book is expensive and short, but the alternative for learning about TDD are half-baked blog posts, which is why I bought a book. I don't know of a better book because this is the only one I have, and I'm unsure at this point whether I really want to buy another book on this topic. But this book is highly recommended by many TDD fanatics enthusiasts, so I don't know.

The Little Schemer

Next I read The Little Schemer. The style of this book can best be described as "cute". Examples all use food, and it instructs you at various points to go make yourself a sammich (even leaving room in the book for "jelly stains"). This somehow makes the topics, which can be rather intimidating, somehow less scary. The book is very short, and not very dense (not many words on a page), but they somehow cram a lot of information into the book anyways, via the many examples. It's a very focused and methodical book.

This book goes through developing a simplified dialect of Scheme, with a focus on recursion and building up parts of the language from very simple primitives. There are some neat little things along the way, like using s-expressions to represent numbers, and building up a full set of arithmetic functions using nothing but "add 1", "subtract 1", and recursion. It'd be insane to do in real life because of performance, but it's really neat from a "hey look what you can do, isn't this cool!" point of view.

The first half of the book is pretty simplistic (at least for me, with some basic knowledge of Lisp and Scheme), but the second half really starts delving into some crazy things, passing lambdas around to lambdas and writing evaluators and stuff. But you almost don't even notice because of how solidly the foundations are built up to that point, and how well the examples are explained. (You probably will notice once you hit the y-combinator, on account of your brains detonating.)

This not a good book for "learning Lisp" in terms of learning the gritty details of to use a real-life implementation of Lisp. But it's a good book for learning some of the concepts that make Lisp and functional languages powerful. This is a very interesting and unique book, also highly recommended by many in the Lisp world. I'm already planning to try The Seasoned Schemer next.

Real World Haskell

Finally I started plowing through the recently-released Real World Haskell. This book is freely available online, which is great. It also allows readers to make comments on every paragraph in the book, which is a highly collaborative and probably very intelligent way to write a book, and also can provide insight for readers who don't understand the text at any given point. I may buy a hard copy, I haven't decided. (The online version has some FIXME notes and typos that I can only hope are fixed in the real thing.)

I'm only up to chapter 11, but it's good so far. It gives a ton of examples and goes slow enough for people completely new to Haskell to pick the language up. And it includes some of the mechanics of compiling and/or running programs in GHC, which is extremely helpful. I did start getting lost around the time monads were introduced, but that's to be expected. It usually takes me two or three good reads of this kind of book before I grok it all, which is no fault of the book.

Haskell. Last time I used it, I wrote Pong in Haskell in one of my college classes. It was an immensely painful experience. I'm going back to re-learn Haskell now because I find myself edging more and more toward functional languages and away from the C/Java world.

Haskell is far too much to swallow if you have no experience with functional programming, which is probably why I hated it in college. (That said, a smarter person than I may have fewer problems.) After graduating school, I got my first whiff of this world again via Perl's map and grep and friends. Then Ruby pushed it home for me with its widespread use of block parameters (lambdas in disguise). And after learning Lisp (and especially later, Clojure) I can't live without higher-order functions. If I had to write a classic for-loop and manually keep track of a counter variable I'd probably vomit at this point. Haskell takes function manipulation to an even greater extreme, which I still haven't fully wrapped my head around, but I like what I've learned so far.

Laziness is awesome, function currying is awesome, and this is the first time I've read about folding, apart from brief struggles with Ruby's (poorly named) Enumerable#inject. Pattern matching strikes me as vaguely similar to Common Lisp's / Clojure's destructuring-binding, which is one of the nicest features I've seen in any language when it comes to making a programmer's life easier.

Maybe it's all just interesting because it's still new to me. But I like the whole idea of functional programming. I like the idea of functions that always produce the same output from a given input. How and when to handle side-effects and object mutation is a problem that's always nagged at the back of my mind even when writing Ruby code.

That said, Haskell still (at this point in the book) does not strike me as a practical or real-world language in the slightest. You've got to jump through some crazy hoops to get a lot of things to work, especially when it comes to I/O. The book describes how to write a pretty-printer, and how to parse a binary file, both of which require some acrobatics to write concisely in Haskell. In particular the parser library lost me entirely; functions were being chained to functions in all directions and I couldn't follow it.

I think one reason Java is so popular is that you don't have to be a genius to write it. To write Haskell (or even Lisp) well, to take advantage of the language and use it smoothly, you really do need to do some deeper thinking. The abstractions are more powerful and more "abstract". It's not too hard to understand a world made of objects with a bunch of knobs you turn via method calls. Lambdas and recursive functions and monads and typeclasses are a more ephemeral thing.

That said I plan to stick with the book. Practice makes perfect.

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.

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.