Transformation

In this section of the course we study transformations on abstract syntax trees and how to define these using rewrite rules and rewriting strategies.

Lecture 5: Transformation by Term Rewriting

Topics

• program transformation
  • simplification, desugaring
• rewrite rules
  • match, build, scope
  • conditional rules
• programmable rewriting strategies
  • strategy combinators
  • generic traversal, traversal combinators
  • type-unifying transformations

Slides

• PDF
• github

Reading Material

• Eelco Visser, Zine-El-Abidine Benaissa, Andrew P. Tolmach. Building Program Optimizers with Rewriting Strategies. In Matthias Felleisen, Paul Hudak, Christian Queinnec, editors, Proceedings of the third ACM SIGPLAN international conference on Functional programming. pages 13-26, ACM, Baltimore, Maryland, United States, 1998. [DOI] This paper introduces the initial idea of programmable rewriting strategies and decomposing rewrite rules into first-class operations for matching and building terms.

• Eelco Visser. Program Transformation with Stratego/XT: Rules, Strategies, Tools, and Systems in Stratego/XT 0.9. In Christian Lengauer, Don S. Batory, Charles Consel, Martin Odersky, editors, Domain-Specific Program Generation, International Seminar, Dagstuhl Castle, Germany, March 23-28, 2003, Revised Papers. Volume 3016 of Lecture Notes in Computer Science, pages 216-238, Springer, 2003. doi This paper provides an easy to read high-level overview of Stratego and its role in the Stratego/XT transformation tool suite.

• Transformation with Stratego. Documentation

• Martin Bravenboer, Arthur van Dam, Karina Olmos, Eelco Visser. Program Transformation with Scoped Dynamic Rewrite Rules. Fundamenta Informaticae, 69(1-2):123-178, 2006. IOS Press This paper formally defines the semantics of Stratego including its extension with dynamic rewrite rules feature. Consult this paper if you want to dig deeper.