PARTIAL EVALUATION OF PATTERN-MATCHING IN CONSTRAINT LOGIC PROGRAMMING-LANGUAGES

A standard example in the literature on partial evaluation is the derivation of an efficient pattern matcher by partial evaluation of a (more or less) naive matcher. The effect can be summarized by the claim that partial evaluation 'automatically' performs the optimization central to the Knuth-Morris-Pratt (KMP) string matching algorithm. In this paper we generalize the previous results by showing that the idea behind the KMP optimization extends to pattern matching in domains other than linear strings. In particular, we give examples that demonstrate how the same idea is applicable to the derivation of efficient pattern matchers for finite trees (Prolog terms with variables), for Boolean algebra, and for finite sets. For this purpose we utilize the constraint logic programming languages CLP(FT), CLP(Bool), and CLP(Finite Domain). Our analysis of how partial evaluation is able to perform these derivations leads us to introduce the notion of the failure continuation, which we utilize in the derivation of a program for matching against a set of pattern strings.