Alexey Rodriguez

Aspect Oriented Haskell

This project aims to nicely integrate a Haskell compiler (UHC) and an attribute grammar system (UU_AG).

One of the key issues of this project is attribute grammar compositionality. In UU_AG compositionality is achieved by processing all the required files at one given time. This is syntactic compositionality. Semantic compositionality is required to be able to process the source files individually. Some extensions to the Haskell type system will surely be required for this to work.

Literature

Literature to read:

• Saraiva, Joao Baptiste, Purely Functional Implementation of Attribute Grammars, PhD thesis, December 9,
• Oege de Moor, Kevin Backhouse, S. Doaitse Swierstra, First-class Attribute Grammars (2000) http://citeseer.nj.nec.com/299789.html In this paper an attribute grammar system is developed as an embedded language in Haskell. Aspects are first class values and they can be combined to form new aspects and later on one can obtain a semantic function from them. A drawback of this approach is that undefined attributes or repeated definition of attributes are errors that can't be detected statically.
• Oege de Moor, Simon Peyton Jones, Eric Van Wyk, Aspect-Oriented Compilers (1999) http://citeseer.nj.nec.com/demoor99aspectoriented.html This paper uses extensible records to type check Attribute Grammar Aspects. The notation is curbersome and several type aliases and functions have to be redefined for production nodes of different arity. It is not clear from the paper what are the expressive power differences when compared to the previous paper. There seems to be no example source code available from de Moor's homepage.

Updates

Examples are now provided in the files attached to this page. The types in the fantasy syntax are incorrect though. The translation can be run using Hugs with extensible records.

Also the presentation for the course is now included. It shows the new translation using extensible records. All issues are solved. Well, provided that the extensions required in extensible records are present.

A new translation has also been attempted but with no success. The new translation assumes that aspects always extend a previously existing aspect. It is less flexible than the previous translation. I tried to use semantic functions instead attribute family transformers but it doesn't work. The reason for this attempt is that when using attribute family transformers you have to do special operations on children. Another problem is that we need special operations for composing/extending aspects. So i tried to see whether i could obtain something by adding the semantic function directly in the datatype.

• example.uhc: AG fantasy syntax for UHC

• example.hs: Translation using extensible records

• uhc-ag.pdf: Project Presentation

Examples

This section is outdated. It is conserved because the explanations can be useful.

These are some examples that show how a program would look like. The example is the repmin problem for the following tree:

module MinTree where
data Root = Root Tree
data Tree = Branch Tree Tree | Leaf Int

The following aspect synthesises the min attribute

module MinSyn where
import MinTree

minTree = aspect
  attribute Tree with syn min :: Int
  rules Tree where
  | Leaf lhs.min = @1    -- note positional field
  | Branch lhs.min = @1.min `min` @2.min

The aspect construct can be used wherever an expression can be used. It constructs a value of type Aspect that has the defined/required attributes represented in its type. Probably this will be done using rows.

This module propagates the min down the tree

module MinInh where
import MinTree

propMinTree = aspect
  attribute Tree with inh min::Int
  rules Tree where
  | Branch 1.min = @lhs.min
           2.min = @lhs.min
  rules Root where
  | Root 1.min = @1.min

The last example makes the copy rules explicit. Two problems arise from this example:

• How do we know which constructors are going to be used for the attribute grammar. Probably the programmer will need to specify it somehow. Also, for now we restrict ourselves to monomorphic datatypes.
• How do we handle inherited attributes that are not connected? There can be children nodes for which their parent has to assign a value to it through a rule. For now we impose the restriction that no aspect can have an unconnected inherited attribute. If we would want to pass an initial environment to a root node we can use a value from the current environment. For example we can have a function that builds a name analysis aspect:

nameAnalysis initialEnv = aspect ...
  ...
  | Expressions head.env = initialEnv
  ...

Note that this restriction doesn't allow us to decompose aspects into separate productions. All productions from an aspect must be there. For example you can't separate the name analysis into nameStmnt and nameExpr, etc. This is because there will necessarily be some unconnected attributes. It is not yet clear to me how much more work involves the relaxation of that restriction.

Another module:

module MinGen where
import MinTree

repMin = aspect
  attribute Root with syn tree::Tree
  rules Root where
  | Root lhs.tree = @1.tree
  attribute Tree with syn tree::Tree
  | Branch lhs.tree = Branch @1.tree @2.tree
  | Leaf lhs.tree = Leaf @lhs.min

The module that glues it all together:

module MinRepMin where
import MinTree
import MinSyn
import MinInh
import MinGen

-- ag has an Aspect type that reflects the combination of attributes
-- of all aspects
ag = minTree `cat` propMinTree `cat` repMin

-- the knit function can only be applied if there is no missing needed attribute
-- that should be checked at typed level, thus statically
-- we also will need to specify to which datatype we apply it (Root)
-- the resulting type is Data -> Rec {| synthesised attributes |}
agFun = knit ag

example = (agFun example_tree).tree    -- record selection

example_tree = ... some example tree ...

-- AlexeyRodriguez - 18 Sep 2003