Draft by
EelcoDolstra and
EelcoVisser
Abstract
Programming language semantics based on pure rewrite rules su ers from
the gap between rewriting strategy implemented in rewriting engines and
the intended evaluation strategy. This paper shows how programmable
rewriting strategies can be used to implement interpreters for program-
ming languages based on rewrite rules. The advantage of this approach is
that reduction rules are rst class entities that can be reused in di erent
strategies, even in other kinds of program transformations such as optimiz-
ers. The approach is illustrated with several interpreters for the lambda
calculus based on implicit and explicit (parallel) substitution, di erent
strategies including normalization, eager evaluation, lazy evaluation, and
lazy evaluation with updates. An extension with pattern matching and
choice shows that such interpreters can easily be extended.
Online
CategoryPaper