Efficient Embedding of Strategic Attribute Grammars via Memoization

on YouTube ↗30m

" summary

Memoizing attribute values inside the zipper eliminates repeated recomputation and yields a practical embedding of attribute grammars combined with strategic term rewriting. Implementation is the Ztrategic library (Rascal/ASCO, plus a Python port) that stores attributes in memoized zippers and adapts strategic combinators. Benchmarks on ASCO (116 constructors) show performance close to Strafunski, remove roughly 100–850 code smells in student projects, and run much faster than Kiama, which times out on larger examples.

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 0:26Motivating let expressions
3. 4:03Strategic combinators
4. 6:31Strafunski limitations
5. 7:57Attribute grammars
6. 10:24Zipper navigation
7. 13:16Memoization to avoid recomputation
8. 15:24Full implementation
9. 17:14Benchmarking tools
10. 22:17Conclusions and future
11. 24:22Q&A

" related talks

• 15mParsing with Zippers (Functional Pearl)Michael D. Adams, Pierce Darragh · ICFP 2020
• 15mMonadification of Attribute GrammarsEric Van Wyk, Dawn Michaelson · SLE 2020
• 18mSynthesizing Efficient Memoization AlgorithmsYingfei Xiong, Xuanyu Peng, Yican Sun · OOPSLA 2023
• 29mNanopass Attribute GrammarsLucas Kramer, Eric Van Wyk, Nathan Ringo · SLE 2023
• 21mSynthesizing Formal Semantics from Executable InterpretersLoris D'Antoni, Thomas Reps, Jiangyi Liu, Charlie Murphy, Anvay Grover, Keith J.C. Johnson · OOPSLA 2024
• 28mOriented Metrics for Bottom-Up Enumerative SynthesisRoland Meyer, Jakob Tepe · POPL 2026
• 28mScimitar: Functional Programs as Optimization ProblemsJeffrey S. Foster, Philip Zucker, Nate F. F. Bragg · Onward! 2024
• 18mAssociativity and Commutativity in Equality SaturationSebastian Hack, Marcel Ullrich, Tarik Rosin · EGRAPHS 2026