The Abstraction and Instantiation of String-Matching Programs

Torben Amtoft
Charles Consel
Olivier Danvy
Karoline Malmkjær

April 2001


We consider a naive, quadratic string matcher testing whether a pattern occurs in a text, we equip it with a cache mediating its access to the text, and we abstract the traversal policy of the pattern, the cache, and the text. We then specialize this abstracted program with respect to a pattern, using the off-the-shelf partial evaluator Similix.

Instantiating the abstracted program with a left-to-right traversal policy yields the linear-time behavior of Knuth, Morris and Pratt's string matcher. Instantiating it with a right-to-left policy yields the linear-time behavior of Boyer and Moore's string matcher.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.