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|
|Number of pages||21|
|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
|Name||SLE 2020 - Proceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering, Co-located with SPLASH 2020|
|Conference||13th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2020, co-located with SPLASH 2020|
|Period||11/16/20 → 11/17/20|
Bibliographical notePublisher Copyright:
© 2020 ACM.
- attribute grammars