Research Projects

Swierstra
%TOC%
---++ 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 [[http://www.cs.uu.nl/groups/ST/twiki/bin/view/Center/AttributeGrammarSystem][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

Current projects include:

---+++ 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
   * integration of this with flow annotations for semantic functions
   * 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 [[http://www.cs.uu.nl/groups/ST/twiki/bin/view/Center/Proxima][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