AbstractSpecialization of a string matcher 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 requires non-trivial binding-time improvements. Starting with a naive matcher, we thus present a derivation of such a binding-time improved string matcher. We show that specialization with respect to a pattern yields a matcher with code size linear in the length of the pattern and a running time independent of the length of the pattern and linear in the length of the data string. We then consider several variants of matchers that specialize well, amongst them the first such matcher presented in the literature, and we demonstrate how variants can be derived from each other systematically.
Categories and Subject Descriptors: D.1.1 [Programming Techniques]: Applicative (Functional) Programming; D.3.2 [Programming Languages]: Language Classifications; D.2.3 [Software Engineering]: Coding; D.3.4 [Programming Languages]: Processors; F.3.1 [Logics and Meanings of Programs]: Specifying and Verifying and Reasoning about Programs; F.3.2 [Logics and Meanings of Programs]: Semantics of Programming Languages
Additional Key Words and Phrases: partial evaluation, Knuth-Morris-Pratt string matching, binding-time improvements, functional programming, program transformation, complexity, optimization, reasoning about programs
Selected references
- Charles Consel. A tour of Schism: A partial evaluation system for higher-order applicative languages. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 145-154, Copenhagen, Denmark, 14-16 June 1993.
- Charles Consel and Olivier Danvy. Partial evaluation of pattern matching in strings. Information Processing Letters, 30(2):79-86, 30 January 1989.
- Carsten Kehler Holst and Carsten Krogh Gomard. Partial evaluation is fuller laziness. In Proceedings of the Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 223-233, Yale University, 17-19 June 1991. SIGPLAN Notices 26(9), September 1991.
- Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323-350, June 1977.
- Donald A. Smith. Partial evaluation of pattern matching in constraint logic programming languages. In Proceedings of the Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 62-71, Yale University, 17-19 June 1991. SIGPLAN Notices 26(9), September 1991.