Fine-tuned Scheduling of Linear Ordered Attribute Grammars

Abstract

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.