Extending Dynamic Rules

A. van Dam. Extending Dynamic Rules. An Application-Oriented Study into Stratego's new Dynamic Rules. Master's thesis, Utrecht University, Utrecht, The Netherlands, February 2004. INF/SCR-04-25 (pdf).

From the Introduction

The research described in this thesis is part of ongoing work in the development of the Stratego system [VBT98, Vis00, Vis04a]. Focus lies on the concept of dynamic rules that allow the use of context information in rewrite rules, thus making more sophisticated rewriting possible. Dynamic rules were introduced in Stratego 0.6, and had some occasional improvements up to and including Stratego 0.9.3. We will sometimes refer to this 0.9.3 release as the old-style dynamic rules. In Stratego 0.9.4 the extend rules feature was already silently introduced, but a major redesign including many new features was released in Stratego 0.10, followed by some small internal optimizations in 0.11. At the time of writing Stratego 0.11 reflects the current state of our research.

Outline

To describe the context in which this research was performed, Chapter 2 introduces the key parts of the Stratego language. Readers who are already familiar with the Stratego language constructs may skip this chapter, although the formal semantics described within will come back in the semantics of dynamic rules. Appendix A contains all formal semantics in one overview. Chapter 3 further explains the need for context-aware rewriting and describes the dynamic rule constructs that were available in the old-style dynamic rules, i.e. as in Stratego 0.9.3 and before.

Chapters 4, 5 and 6 describe three cases where dynamic rules are used in some optimizing transformation. Starting the reasoning from the old-style dynamic rules, undesirable or missing features of these dynamic rules are identified, and a solution described. Chapter 4 introduces a small lambda calculus and a shrinking optimizer, based on an article by Andrew Appel and Trevor Jim [AJ97]. Basic rule definition and rule scoping is of importance here. Chapter 5 describes constant propagation in the Tiger language. Previous work on this matter was done by Olmos and Visser [OV02], but new dynamic rules enable a cleaner implementation of constant propagation. Rule undefining, dynamic scoping and proper handling of control flow (i.e. forking and meeting of dynamic rule environments) are the important issues here. Chapter 6 is a study built around the deforestation algorithm for first-order functional languages described by Philip Wadler [Wad90]. Implementation of the deforestation algorithm shows the need for extending rule sets an higher-order matching. Within the same study, also a type inferencer was implemented, which allows for a comparison between type inferencing using attribute grammars (e.g. as implemented [DS01] in the UUAG system) and type inferencing using dynamic rule sets. Both implementations are based on the W algorithm by Milner [Mil78, DM82]. To keep the original chapter focused on deforestation, the type inferencer is described separately in Appendix B. Each case thus introduces one or more improvements or new features of dynamic rules in Stratego, and altogether they form the new set of dynamic rule constructs as they were initially released in Stratego 0.10.

Most new features of dynamic rules have been made possible by a smarter representation of rule sets and scopes. Chapter 7 describes how stacks of hash tables provide the appropriate functionality and efficiency. The supposed efficiency of the new rule set representation has been benchmarked. Chapter 8 describes these benchmarks, compares the results to the expected qualitative costs behavior and concludes which constructs are the most costly.

Chapters 9 and 10 describe related and future work and Chapter 11 concludes.

BibTeX

@mastersthesis{Dam04,
  author  = {Arthur van Dam},
  title   = {Extending Dynamic Rules. {A}n Application-Oriented Study into {Stratego's} new Dynamic Rules},
  school  = {Utrecht University},
  year    = 2004,
  address = {Utrecht, The Netherlands},
  month   = {February},
  note    = {INF/SCR-04-25},
  urlpdf  = {http://www.cs.uu.nl/~visser/ftp/Dam04.pdf},
  project = {Stratego},
}