Monadification of attribute grammars

Dawn Michaelson, Eric Van Wyk

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationSLE 2020 - Proceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering, Co-located with SPLASH 2020
EditorsRalf Lammel, Laurence Tratt, Juan de Lara
PublisherAssociation for Computing Machinery, Inc
Pages175-195
Number of pages21
ISBN (Electronic)9781450381765
DOIs
StatePublished - Nov 16 2020
Event13th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2020, co-located with SPLASH 2020 - Virtual, Online, United States
Duration: Nov 16 2020Nov 17 2020

Publication series

NameSLE 2020 - Proceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering, Co-located with SPLASH 2020

Conference

Conference13th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2020, co-located with SPLASH 2020
CountryUnited States
CityVirtual, Online
Period11/16/2011/17/20

Bibliographical note

Publisher Copyright:
© 2020 ACM.

Keywords

  • attribute grammars
  • monadification
  • monads

Fingerprint Dive into the research topics of 'Monadification of attribute grammars'. Together they form a unique fingerprint.

Cite this