Abstract
We describe a monadification process for attribute grammars for more concisely written attribute equations, closer to the style of inference rules used in traditional typing and evaluation specifications. Inference rules specifying, for example, a typing relation typically consider only typable expressions, whereas well-defined attribute grammars explicitly determine attribute values for any term, including untypable ones. The monadification approach lets one represent, for example, types as monadic optional/maybe values, but write non-monadic equations over the value inside the monad that only specify the rules for a correct typing, leading to more concise specifications. The missing failure cases are handled by a rewriting that inserts monadic return, bind, and failure operations to produce a well-defined attribute grammar that handles untypable trees. Thus, one can think in terms of a type T and not the actual monadic type M(T). To formalize this notion, typing and evaluation relations are given for the original and rewritten equations. The rewriting is total, preserves types, and a correctness property relating values of original and rewritten equations is given. A prototype implementation illustrates the benefits with examples such as typing of the simply-typed lambda calculus with Booleans, evaluation of the same, and type inference in Caml Light.
Original language | English (US) |
---|---|
Title of host publication | SLE 2020 - Proceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering, Co-located with SPLASH 2020 |
Editors | Ralf Lammel, Laurence Tratt, Juan de Lara |
Publisher | Association for Computing Machinery, Inc |
Pages | 175-195 |
Number of pages | 21 |
ISBN (Electronic) | 9781450381765 |
DOIs | |
State | Published - Nov 16 2020 |
Event | 13th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2020, co-located with SPLASH 2020 - Virtual, Online, United States Duration: Nov 16 2020 → Nov 17 2020 |
Publication series
Name | SLE 2020 - Proceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering, Co-located with SPLASH 2020 |
---|
Conference
Conference | 13th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2020, co-located with SPLASH 2020 |
---|---|
Country/Territory | United States |
City | Virtual, Online |
Period | 11/16/20 → 11/17/20 |
Bibliographical note
Publisher Copyright:© 2020 ACM.
Keywords
- attribute grammars
- monadification
- monads