A programming language is an essential ingredient for writing concise, maintainable, and error-free computer programs. A compiler takes a text written in such a language and compiles into machine instructions, and is usually implemented as a number of traversals over the abstract syntax of the program. Attribute Grammars (AGs) are a powerful tool for the description of such traversals and thus the implementation of a compiler: AGs offer aspect-oriented programming, abstraction over common traversal patterns, and automatic inference of a sound and efficient traversal algorithm.

Over the years, computer languages have become more complex and harder to implement. Notoriously difficult to implement is type checking or type inference, which for complex languages is not only specified in terms of the abstract syntax but also in terms of the inferred types, and requires traversals that are hard to describe in general, and in particular with AGs. The reason is that the traversals mutually depend on types, which are not known apriori, thus the traversal represents some strategy that decides during the process in which order type information is collected and processed.

In this thesis, we investigated the application of attribute grammars to the description of inference algorithms, with the goal of being able to describe such algorithms while retaining the good properties of AGs. To this end, this thesis builds on higher-order attribute grammars to describe traversals over semantics instead of syntax, conditional attribute grammars to describe the decisions to be made during the inference process, and ordered attribute grammars to express inference strategies.

Visits, a concept from ordered attribute grammars, play an essential role in our work. A visit to a node in the abstract syntax tree represents a unit of evaluation. We make visits explicit in our AG descriptions so that we can express the order of evaluation and conditionally iterate visits. Moreover, we show that on top of visits, we can express decision points, and present a stepwise evaluation strategy that allows us to explore alternative choices until reaching a decision.

Our work is a conservative extension of attribute grammars, and preserves their good aspects. We declaratively express properties of the evaluation order, while keeping the automatic scheduling of attribute computations. Our work integrates well with various attribute grammar extensions, such as parallel evaluation. In particular, our work facilitates an integration with dependently typed programming, which paves the way to prove and enforce the correctness of compilers described with attribute grammars.


Conclusions: Our work brings ordered attribute grammars back to life, and motivates their use for the implementation of compilers, and type inference in particular. We present various extensions to ordered attribute grammars that allow type inference strategies based on fixpoint iteration or search strategies to be expressed.


Short dutch summary: Computerprogramma's zijn duur om te maken, moeilijk te onderhouden en bevatten veel fouten. Betere programmeertalen dragen hun steentje bij om deze problemen tegen te gaan, omdat ze het mogelijk maken een programma compacter en duidelijker op te schrijven en triviale details weg te laten. Het maken van een compiler, wat de broncode van een programma omzet in instructies die door de computer uitgevoerd kunnen worden, wordt moeilijker naarmate de programmeertaal beter is omdat de compiler werk van de programmeur moet overnemen. In dit proefschrift brengen we een geavanceerde techniek in stelling, namelijk attributengrammatica's, om het maken van zulke ingewikkelde compilers mogelijk te maken.

Een getypeerde programmeertaal maakt het mogelijk domme fouten te voorkomen omdat de compiler kan controleren of het programma niet per ongeluk waarden in het geheugen van de computer van verschillende vorm door elkaar haalt. Dergelijke fouten hebben in het verleden al tot flinke kostenposten geleidt. Door ingewikkeldere typen te onderscheiden kunnen meer fouten voorkomen worden, maar dat kost ook meer moeite om deze op te schrijven. Daarom willen we dat de compiler de types zelf uitzoekt, maar dat compliceert het maken van een compiler aanzienlijk.

In dit proefschrift beschouwen we daarom uitbreidingen aan attributengrammatica's waarin we precieze strategien kunnen specificeren die bepalen op welke plaatsen de compiler types kiest en op welke manier de compiler informatie over types verwerkt. Deze uitbreidingen maken het mogelijk om ingewikkeldere compilers te maken, en daarmee ingewikkeldere programmeertalen, en dus uiteindelijk betere computerprogramma's.