\chapter*{Preface}
\markboth{Preface}{Preface}
\addcontentsline{toc}{chapter}{Preface}

With Attribute Grammars (AGs), \citet{DBLP:journals/mst/Knuth68} presented a
formalism that turned out to be excellent for reasoning about computations
that can be expressed as a traversal over a tree.
It is surprising how many programs can be conceptually
described as an attribute grammar. On the other hand, it may be difficult to
precisely formulate a program as such.
In particular, several aspects of type inference algorithms are not
straightforward to describe with an AG because these aspects require
fixpoint iteration combined with dynamic tree construction in their implementation.
In this thesis, we address this issue, and this thesis is thus a potpourri of
type systems and AGs, with the greater focus being on the latter.

Recent attribute grammar systems compute attributes in a demand-driven
evaluation order determined at runtime, which is relatively straightforward
to implement when incorporating or embedding AGs in some other
programming language~\citep{Sloane:2010:POE:1860132.1860322}.
We, on the other hand, resurrect ordered attribute grammars,
for which there exists a static order in which the attributes
can be computed~\citep{DBLP:journals/acta/Kastens80}.
This concept played an important role in the past
to obtain efficient implementations when every byte of memory
and every clock tick mattered.

For us, however, another consequence of the existence of a static order
is important. In a recent paper, \citet{kaminski11} show the need to
express in the AG description a distinction between trees that have
not been attributed yet and trees that have been.
Owing to the static order, we go a step further and
distinguish and make assumptions about trees in various stages
of their attribution. We show that this provides a means to
describe, control and orchestrate chunks of attribute evaluation,
which we exploit to fine-tune AG evaluation to capture inference algorithms.

With this thesis, we hope to show the power of AGs to implementors
of type inference algorithms, and shed a new light on ordered AGs for
implementors of AGs.

\paragraph{Acknowledgements.}
My promotor Doaitse Swierstra and copromotor Atze Dijkstra were a crucial source of
inspiration.
Despite his busy life, Doaitse takes the time to spread his brilliant ideas and interesting anecdotes.
Doaitse is a great advocate of functional programming.
We had many interesting discussions, although these usually started with an account of the low-level details
of the tools that he fiddled with the day before. Or the latest functional programming exams.
Nevertheless, Doaitse sets a great example, and it was an honor to work under
his supervision.

Atze sets another example, especially when the exploration of a design
space is concerned, and the decomposition into orthogonal aspects.
It is amazing how Atze approaches
problems with clear and concrete solutions, yet reasons at a high level of abstraction.
%% Atze took a customer role in my research project, which motivated me a lot to make changes to
%% the UUAG system.
Atze has a calm appearance, yet I also experienced some of his adventurous
and active traits. In particular, I recall early-morning training runs during conferences, at
times that others were deep asleep.

The reading committee deserves a compliment for bravely reading through my thesis, as well as the
anonymous reviewers before them that had to go through the papers from which this thesis is composed.

The Software Technology group at Utrecht is a pleasant group to be part of, and
I thank all my colleagues and former colleagues for the enjoyable time. I especially recall
the crazy group effort for the ICFP contest in 2007.

%% During many discussions related to the UHC project, Jeroen Fokker took heroic efforts to
%% keep our discussions concrete and focussed. Jeroen was very helpful in many organizational
%% matters, and in fact, I learned programming with a copy of his lecture notes when I was still
%% in secondary school.

I thank my former office mates Eelco Dolstra, Jos\'{e} Pedro Magalh\~{a}es, and Stefan Holdermans.
I hope that Stefan does not tear his eyes out if he spots errors in the Dutch summary at the
back of this thesis.
I also had pleasant discussions with my room mates Jeroen Bransen and Alexander Elyasov. I hope
that you will enjoy attribute grammars as much as I do.

Halfway in my thesis project, I worked for half a year in Brazil.
I want to heartily thank Luc\'{\i}lia Camar\~{a}o de Figueiredo for her effort in making my stay
in Brazil pleasant.
%% My greetings to everybody I met while I was there.
%% It is a pity that we did not have more opportunities to work together.
%% My greetings to your family and friends, because of the time they spend with me, and also to
%% Elton and the others that were with me in the lab.

The last year, I worked together with Wishnu Prasetya and Jurriaan Hage to statically
instrument ActionScript bytecode.
%% It was certainly not easy to combine writing a thesis with developing a framework for
%% bytecode manipulation. However, the use of Haskell and attribute grammars turns out to be
%% a good choice so far.
%% I know Jurriaan already since when I still was a second year student.
Jurriaan creates a warm atmosphere in the group, and is always around for a conversation or two.

The Universit\"{a}t Freiburg, and the ProgLang group in particular,
generously providing me with a place to work each time I visited Freiburg.
%% I actually performed large chunks of the programming and paper writing for this thesis during
%% my many short visits.
\emph{Herzlichen Dank!} Also to Peter Thiemann for some heavy sport training sessions after work.

Thanks to Andres L\"{o}h for taking the initiative, we have with several colleagues
a weekly distraction after work in the form of the Ars Magica games that we are still playing remotely. It is
surprising what hidden personalities colleagues expose when exploring a fantasy setting.

The rather secretive IRC channel @#klaplopers@, formed by former
occupants of the ST-Lab, provided welcoming
distractions, both online and in real life.
%% The channel is becoming somewhat silent as more
%% participants have a reduced online presence. Unfortunately, I was also too occupied with
%% my thesis to participate actively.
I want to thank Arthur van Dam and others for several
nice mountainbike trips, although I'm not insane enough on a bike to be a real challenge.
Together with Martin Bravenboer, we still have an Ironman Triathlon to finish.
Eelco Dolstra, a living index of Wikipedia~$^{[\mbox{\emph{citation needed}}]}$,
Rob Vermaas, Dick Eimers, my greetings to you.
Last but not least, Armijn Hemel saved the IRC channel countless of times from my
incorrect spelling and grammar.

Words fail to describe the wonderful role that Annette Bieniusa plays in my life.
I tried once, but did not come close. Not even with 91 pages of emails.
She may appear cute, small and innocent, but in the meantime she stole my heart.
She is my greatest source of happiness and support.
Although she cleverly managed to keep attribute grammars out of our discussions,
she bravely read through my thesis and gave me valuable comments.

Tot slot wil ik mijn ouders en zusjes bedanken. Ik heb jullie tijdens het schrijven
van dit werk niet veel aandacht kunnen geven, en ik hoop in de komende tijd daar
wat verandering in aan te brengen, ondanks dat ik nu wat verder weg woon.

\paragraph{Sponsors.}
I am grateful to Microsoft Research in Cambridge
for granting me a Ph.\ D.\ Scholarship, which made my employment at the Universiteit Utrecht possible.
%% I was fortunate that the department was willing to finance my fourth year, despite the harsh financial
%% constraints that universities face nowadays.
Also, the European project LerNet and the Universidade Federal de Minas Gerais partially financed
me so that I could work for half a year in Brazil.
Many ideas in this thesis arose during my daily walks to and from the university in Belo Horizonte.
%% Finally, the European project FITTEST
%% allowed me to stay a year longer in Utrecht, so that I could apply attribute grammars to
%% implement bytecode transformations in a fancy way.