Performance enhancement in a well-structured pattern matcher through partial evaluation

Sammanfattning: Partial evaluation is a technique which can be utilized for the generation of compiled code from the corresponding interpreter. In this work the partial evaluation technique is applied to a pattern match interpreter, in order to achieve the simultaneous goals of a general, well-structured program which is extendible and still make high performance at execution possible. A formal definition of pattern matching is presented, which is the basis for the interpreter. The partial evaluation technique is evaluated with respect to other techniques for implementation of pattern matchers. Control structures for pattern matching such as backtracking, generators, and recursion are presented, and the appropriateness of these for use in partial evaluation is discussed.