Thinner, an optimizer for a LISP-like language, is based on grammar thinning, a technique for eliminating redundant computation from programs. It compiles an input program into a trace grammar, analyzes the grammar to identify a weak conservative thinning example, reformulates the grammar with respect to that example, and finally decompiles the grammar back into the source language. After an introductory example and a discussion of related work, the author proceeds to a well-presented and detailed treatment of the grammar thinning problem for context-free grammars. To allow grammar thinning to be used for program optimization, he develops a comprehensive trace grammar formalism that supports grammatical reformulation.

As Webber points out, Thinner was developed as a proof of concept. Although it can perform a number of optimizations solely by applying grammar thinning (elimination of common subexpressions, elimination of dead code, constant folding, code sinking, loop invariant removal, loop jamming, and loop splitting), using it for such optimizations is inefficient. Rather, grammar thinning should be applied only when its power and generality are needed for more difficult reformulations. The author concludes this well-written paper by pointing out a number of open problems that may prompt further work on the subject.