Lambda the Ultimate

Obtaining KMP String Matcher by Partial Evaluation
started 12/12/2002; 2:34:24 AM - last post 12/26/2002; 1:11:24 AM

Ehud Lamm - Obtaining KMP String Matcher by Partial Evaluation

12/12/2002; 2:34:24 AM (reads: 946, responses: 3)

Obtaining KMP String Matcher by Partial Evaluation

Mads Sig Ager, Olivier Danvy, and Henning Korsholm Rohde. On Obtaining Knuth, Morris, and Pratt's String Matcher by Partial Evaluation. ASIAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, ASIA-PEPM '02. July 2002.

Obtaining a KMP-like string matcher is a canonical example of partial evaluation: starting from the naive, quadratic program checking whether a pattern occurs in a text, one ensures that backtracking can be performed at partial-evaluation time (a binding-time shift that yields a staged string matcher); specializing the resulting staged program yields residual programs that do not back up on the text, a la KMP.

The authors formally prove that the staged string matcher performs the same sequence of comparisons as the KMP string matcher.

The authors make extensive use of operational semantics, both big-step (for expressions) and small-step (for statements).

Posted to general by Ehud Lamm on 12/12/02; 2:40:15 AM

Patrick Logan - Re: Obtaining KMP String Matcher by Partial Evaluation

12/12/2002; 8:29:23 AM (reads: 548, responses: 1)

I'm fascinated by this. Is the future of partial evaluation obvious? Or is there some controversy?

I've never worked with partial evaluation beyond the toy systems available, e.g. for Scheme. But I see opportunities everywhere.

Ehud Lamm - Re: Obtaining KMP String Matcher by Partial Evaluation

12/12/2002; 3:44:48 PM (reads: 543, responses: 0)

Several varieties of partial evaluation are introduced in these course notes.

Ehud Lamm - Re: Obtaining KMP String Matcher by Partial Evaluation

12/26/2002; 1:11:24 AM (reads: 421, responses: 0)

I started wondering what other string mathcing algorithms can be benfit from such an approach (it seems that quite a few). Which led me to wonder if genetic sequence analysis software use methods of partial evaluation? Any examples?