Strictifying Attribute Evaluation

Date: 2007-01-18

Time: 11:45

Room: BBL room 471

Speaker: Joost Verhoog

Title: Strictifying Attribute Evaluation

Abstract

The UU-AG system provides a way to specify computations over datastructures. It allows specification of the computation that is compositional: different aspects of the computation can be described independently, and combined later. The UU-AG compiler takes an AG file, combines the different aspects, and generates Haskell code that performs the computation.

The main advantage of using AG's is that one only specifies the relation between parts of the computation - the way this is implemented is the task of the AG compiler. This method of software development has proven useful in different projects in our group, such as EHC, Proxima and UU-AG itself.

One of the problems is that the resulting code is slow. Scheduling of the computation is left to the laziness of Haskell. Haskell compilers optimise code by rewriting it, but that doesn't seem to work well for AG's. In this talk I will discuss analyses on the AG that allow generation of code that will run faster. This work is inspired by static scheduling algorithms that were developed for strict imperative implementations of AG's. Static scheduling results in strict code. With some further analyses, we are able to use static scheduling even in programs that use all of the features of lazy programming (such as cyclic fixed-point computations).

Our work has been integrated into the UU-AG compiler. We have measured the resulting programs with encouraging results, and our results give rise to plenty of other opportunities to improve the code even further.