Building Interpreters With Rewriting Strategies
Stratego -- Strategies for Program Transformation
EelcoDolstra and EelcoVisser. Building Interpreters With Rewriting Strategies
In MarkVanDenBrand and RalfLaemmel (editors)
Workshop on Language Descriptions, Tools and Applications (LDTA'02). volume 65.3 of Electronic Notes in Theoretical Computer Science. Elsevier Science Publishers, April 2002. (To appear)
Abstract
Programming language semantics based on pure rewrite rules suffers 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 programming languages based on rewrite rules. The advantage of this approach is
that reduction rules are first class entities that can be reused in different
strategies, even in other kinds of program transformations such as optimizers. The approach is illustrated with several interpreters for the lambda
calculus based on implicit and explicit (parallel) substitution, different
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.
Preprint
Related
CategoryPaper