What do you think?
Rate this book
448 pages, Hardcover
Published March 9, 2021
Term-rewriting systems are powerful tools for creating domain-specific languages for manipulating expression-like information. If we have a syntactic system of expressions, where we may need to replace some subexpressions with "equivalent" subexpressions, we can often use a rule-based term-rewriting system to describe those transformations. For example, many compiler optimizations can be expressed as local rewrites of program fragments in a larger context. The essential features of a term-rewriting system are the use of a pattern matcher to identify the information the be transformed, and a template system for instantiating the replacement. There has been extension research into the problem of constructing convergent term-rewriting systems from equational theories (systems of "equivalent" expressions), but we won't get into that here. Also, there is a superficial similarity between the patterns matched against and the templates for instantiation, which may suggest the possibility of making bidirectional rules; we won't look at that either. First we develop a simple unidirectional system, ni which patterns are used to recognize inputs and templates are used to make outputs.