The Stratego transformation was born from a pure rewriting approach to program transformation by the introduction of traversal combinators1 and programmable rewriting strategies2.
This section reviews the classic definition of term rewriting and motivates the transition to strategic rewriting.
Rather than defining high-level strategies as primitives, Stratego provides basic strategies combinators for composing strategies. The section in the reference manual provides a definition of all the combinators. Here we expand that description with many examples.
Origin tracking is a term rewriting feature that has been put into Stratego to track connections between terms through a transformation. If you for example parse a file into an abstract syntax tree (AST) and the parser leaves some information about what term refers to what part of the file, you can keep track of that even after transformations.
However, origin tracking in Stratego is rather limited, and people are often confused about how it works. On the page for Origin Tracking you can find an explanation of origin tracking, how it works in Stratego, and plans on future improvements.
Bas Luttik and Eelco Visser. Specification of rewriting strategies. In M. P. A. Sellink, editor, 2nd International Workshop on the Theory and Practice of Algebraic Specifications (ASF+SDF 1997), Electronic Workshops in Computing. Berlin, November 1997. Springer-Verlag. ↩
Eelco Visser, Zine-El-Abidine Benaissa, and Andrew P. Tolmach. Building program optimizers with rewriting strategies. In Matthias Felleisen, Paul Hudak, and Christian Queinnec, editors, Proceedings of the third ACM SIGPLAN international conference on Functional programming, 13–26. Baltimore, Maryland, United States, 1998. ACM. URL: http://doi.acm.org/10.1145/289423.289425, doi:10.1145/289423.289425. ↩
Created: May 17, 2023