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)


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.