## Fine-tuned Scheduling of Linear Ordered Attribute Grammars

##### Summary

Attribute Grammars (AGs) are a formalism for defining tree-based computations.
Trees are extended with attributes representing results and parameters
of such computations. A programmer using AGs does not have to worry about the
order in which the attributes are {evaluated, this task is delegated
to an AG compiler. AGs are typically used for writing compilers, as
most compilers perform a number of static analyses that should be efficiently
interleaved. By relying on an AG compiler to perform this task, a
programmer can focus on the crucial aspects of the analyses.
Linear Ordered Attribute Grammars (LOAGs) form the largest class of AGs
for which a {static evaluation order is determined.
For LOAGs strict, small-sized evaluators are generated that are assumed to be
the most efficient evaluators of all AG classes.
Finding a static evaluation order for an AG, thus determining whether it is
an LOAG,
is an NP-complete problem. In order to find a static evaluation order for
LOAGs, Kastens'
algorithm (1980) is commonly used. However, this polynomial runtime
algorithm only works for a subset of the
LOAGs, the Ordered Attribute Grammars (OAGs). The algorithm optimistically
schedules the evaluation of incompatible attributes together.
LOAGs are transformed to OAGs using fake dependencies: manual additions to the source code
with the sole purpose of forcing the AG compiler to separate the evaluation of certain attributes.
Finding the right combination of fake dependencies is tedious
work, often forcing programmers to resort to trial and error.
Especially for large compilers this approach is undesirable.
In order to find a static evaluation order for the Utrecht Haskell Compiler (UHC), 24 fake dependencies
are required. The tedious work of finding these fake dependencies is
the main motivation for this thesis. We show that, even though the problem
is NP-complete, static evaluation orders can be found for all LOAGs in
acceptable runtimes, presenting a Haskell implementation of two new algorithms.
The first algorithm is inspired by the use of fake dependencies. The algorithm
calculates the constructions produced by Kastens' algorithm and uses them to
find a set of candidates: dependencies that, when added to the source code,
might lead to a static evaluation order. Since their correctness is not
certain, their selection is implemented as a backtracking procedure.
The algorithm requires no backtracking to find an evaluation
order for the UHC, gathering a set of 10 fake dependencies. We argue that
backtracking will be rare for practical AGs.
After a thorough examination of multiple characterisations of LOAGs,
a minimal decision problem is formulated. This formulation translates directly
into a Boolean formula, for which a satisfying assignment represents an
evaluation order. A SAT-solver is used to find a satisfying assignment.
The result is an algorithm finding an evaluation order for the UHC in 10 seconds {without fake dependencies,
while Kastens' algorithm requires 25 seconds with a set of fake dependencies.
With a static evaluation order, an AG compiler can optimise this order with respect to user-defined criteria.
Kastens' algorithm finds an evaluation order that is efficient for
evaluators generated in imperative languages, while Pennings (1994)
introduced chained scheduling to find orders more suitable for
evaluators generated in purely functional languages.
We argue that the SAT-based algorithm presented in this thesis
can be extended to produce schedules efficient for either programming
paradigm, by providing user-defined optimisations.