This article describes how automatically specializing a fairly naive pattern matcher by partial
evaluation leads to the Knuth, Morris & Pratt algorithm. Interestingly enough, no theorem
proving is needed to achieve the partial evaluation, as was previously argued, and it is
sufficient to identify a static component in the computation to get the result—a deterministic
finite automaton. This experiment illustrates how a small insight and partial evaluation can
achieve a nontrivial result.

Specializing string matchers is a canonical example of partial evaluation. A naive
implementation of a string matcher repeatedly matches a pattern against every substring of
the data string; this operation should intuitively benefit from specializing the matcher with
respect to the pattern. In practice, however, producing an efficient implementation by
performing this specialization using standard partial-evaluation techniques has been found
to require non-trivial binding-time improvements. Starting with a naive matcher, we thus …