Research Projects
Swierstra
UAG related projects
In this project we seek to reestablish the efficiency of traditional attribute grammar evaluators, while keeping the elegance of Haskell. The current UAG system already performs an circularity check. The UAG system however currently relies on the lazy evaluation of Haskell to schedule its computations. Despite its elegant formulation this has some disadvantages:- large dependency graphs may be constructed at runtime, demanding a lot of memory
- memoisation of functions does not go well with lazy evaluation
Strictness analysis
Most attribute grammar systems perform some form of flow analysis to schedule the computations of attributes. So we seek to:- extend this check into a full static scheduling of the attribute evaluations
- the generation of strictness annotations in the generated Haskell code
- the generation of uniqueness annotations
- extend the UHC compiler to make use of these annotation and pass them on to the LVM
- extension of the LVM so it allocates memory more efficiently
Incremental Attribute Grammar Evaluation
Attribute grammars are quite useful in describing systems like Proxima; for this however we will need efficient incremental evaluation. This may be achieved by a combination of two techniques:Memoisation of generated semantic (sub)functions
- the generation of memoisation annotations in the generated Haskell code
- extend the UHC compiler to make use of these annotation and pass them on to the LVM
- extending the UHC compiler to make use of these annotation and pass them on to the LVM
- extension of the LVM so it performs memoisation wehere indicated
Grammar Transformations
in order to increase the effectiveness of memoisation it may be beneficial to transform the attribute grammar.Extension of the formalism
Many ideas exist about extending the current AG system such as:- being able to handle polymorphic data types
- integrating UAG with UHC
- context sensitive attribution rules, through pattern matching