Integrating attribute grammar and functional programming language features

Abstract

While attribute grammars (AGs) have several features making them advantageous for specifying language processing tools, functional programming languages offer a myriad of features also well-suited for such tasks. Much other work shows the close relationship between these two approaches, often in the form of embedding AGs into lazy functional languages. This paper continues in this tradition, but in the other direction, by integrating various functional language features into AGs. Specifically we integrate rich static types (including parametric polymorphism, typed distinctions between decorated and undecorated trees, type inference, and generalized algebraic data-types) and pattern-matching, all in a manner that maintains familiar and convenient attribute grammar notations and especially their highly extensible nature.