Strategic Tree Rewriting in Attribute Grammars
summary
Introduces strategy attributes: higher-order synthesized attributes with attached rewrite strategies implemented as a modular Silver extension that translate strategies into generated equations via a propagate declaration. Shows concrete uses — let inlining that reads an inherited env, regex simplification via Brzozowski derivatives, and loop normalization in ableC-Halide — and explains congruence strategies to respect attribute dependencies between children to avoid repeated full redecorations (naive innermost redecorating is inefficient). Implementation yields production-specific optimizations and about a 20% speedup.
AI-written summary · about
chapters (13)
- 0:00Intro
- 1:41Solution
- 2:47Example: Attributes
- 3:45Example: Rewrite rules
- 5:43Strategy Attributes: Using Contextual Information
- 6:17Strategy Attributes: Traversal Order with Context
- 8:34Implementation: Rules
- 8:57Implementation: Lifting Sequence
- 9:33Implementation: Total Sequence, all
- 10:18Implementation: Partial Sequence, Choice
- 11:17Applications: for-Loop Normalization
- 12:06Applications: Optimizing Strategy Expressions
- 13:17Discussion and Conclusion
related talks
25mEGSTRA: E-Graph-Based Strategy for Test Suite Reduction and Abstraction
36mRethinking legacy modernisation with automated reasoning and comprehension models
17mContextual Equality Saturation
19mLanguage Support for Refactorability Decay Prevention
27mRooting for Efficiency: Mechanised Reasoning about Array-Based Trees in Separatio...
22mProgram Synthesis for Artifacts beyond Programs
18mTowards a Language-parametric DSL for Refactoring (Short Paper)
30mTactic Script Optimisation for Aesop