The Universe of Discourse


Wed, 09 Sep 2009

You think you're All That, but you're not!
I have long been interested in term rewriting systems, and one of my long-term goals is to implement the Knuth-Bendix completion algorithm, described by Knuth and Bendix in their famous paper "Word Problems in Universal Algebras". This paper grabbed my attention around 1988; I found it in an anthology edited by John Leech (of Leech lattice fame) that I was probably looking into because it also contained an enumeration by J.H. Conway of all knots with at most eleven crossings. I found the Knuth-Bendix paper very hard to read, but the examples at the end were extremely compelling. I still find the paper very hard to read, but fortunately better explanations are now available. (For example, this one by A.J.J. Dick.) One of the also-ran topics for Higher-Order Perl was a structured drawing system based on Wm Leler's "Bertrand" term-rewriting system.

So I was delighted to discover that there was a new book out called Term Rewriting and All That. The "...and All That" suffix is a reference to the tongue-in-cheek classic of British history, 1066 and All That, and promised a casual, accessible, and possibly humorous treatment.

Unfortunately the promise was not kept. The book is very good, but it is not casual or humorous. Nor is it especially accessible. It is a solid slab of term rewriting, one of those books that make me think "I would not want to drop it on my foot." That is not a bad thing; the Barendregt book is superb, an enormous superb slab of lambda calculus that you would not want to drop on your foot. But it is not titled "Lambda Calculus and All That".

So why the title? I don't know. The authors are Germans, so perhaps they don't understand the joke?

[ Addendum: There's exactly one review of this book on Amazon, and it says the same thing I do. It begins: "My main criticism of this book is its title." ]


[Other articles in category /book] permanent link