The Abstraction and Instantiation of String-Matching Programs

  • Torben Amtoft
  • Charles Consel
  • Olivier Danvy
  • Karoline Malmkjær

Abstract

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.

Published
2001-04-12
How to Cite
Amtoft, T., Consel, C., Danvy, O., & Malmkjær, K. (2001). The Abstraction and Instantiation of String-Matching Programs. BRICS Report Series, 8(12). https://doi.org/10.7146/brics.v8i12.20469