Within ARM's Reach: Compilation of Rewrite Systems

Wan Fokkink

(University of Wales Swansea)

A new compilation technique for left-linear term rewriting systems is presented. It assumes the rightmost innermost rewriting strategy, and adopts a rule order in which a rewrite rule has higher priority if it has more syntactic structure. First, the rewrite rules are transformed into so-called minimal rewrite rules, using the pattern-match automaton of Hoffmann and O'Donnell. These minimal rules have such a simple form that they can be viewed as instructions for an abstract rewriting machine (ARM). The equational programming language Epic has been implemented using ARM. This is joint work with Jasper Kamperman and Pum Walters.
Tuesday 9th March 1999, 15:00
Seminar Room 322
Department of Computer Science