[pept:140] Fast Partial Evaluation of Pattern Matching in Strings

[Olivier Danvy <danvy@xxxxxxxx>]

We would like to announce the following result.


Title: Fast Partial Evaluation of Pattern Matching in Strings

Abstract:
  We show how to obtain all of Knuth, Morris, and Pratt's linear-time
  string matcher by partial evaluation of a quadratic-time string matcher
  with respect to a pattern string.  Although it has been known for 15
  years how to obtain this linear matcher by partial evaluation of a
  quadratic one, how to obtain it _in_linear_time_ has remained an open
  problem.
 
  Obtaining a linear matcher by partial evaluation of a quadratic one is
  achieved by performing its backtracking at specialization time and
  memoizing its results.  We show (1) how to rewrite the source matcher
  such that its static intermediate computations can be shared at
  specialization time and (2) how to extend the memoization capabilities
  of a partial evaluator to static functions.  Such an extended partial
  evaluator, if its memoization is implemented efficiently, specializes
  the rewritten source matcher in linear time.

URL: <http://www.brics.dk/RS/03/11/>


Questions, comments, and suggestions are welcome.

-- Mads Sig Ager, Olivier Danvy, and Henning Korsholm Rohde