Welcome to the homepage of Meiage. This project is part of Eifl
Meiage stands for More Efficient Implementation of Attribute Grammar Evaluators. It aims at improving the UU-AG attribute evaluator generator in two ways:
- Implementing visit-oriented evaluation, as described in [KAS91] and [SAR99]
- Implementing en exploiting Lifetime Analysis
- The report of this (unfinished) project can be found in Meiage.pdf (see below)
- Sources can be found in src.zip
- The source of the example in the report can be found in Block.ag
- Checkout the uust repository from cvs.cs.uu.nl: cvs -d :pserver:firstname.lastname@example.org:/data/cvs-rep checkout uust
- Unzip src.zip in the folder uust/tools/ag/dev
- Go to uust/tools/ag and run "make devel"
- run uust/build/bin/uuagdc on an ag-file
- [SAR99] Joćo Saraiva. Purely Functional Implementation of Attribute Grammars. PhD thesis, Department of Computer Science, Utrecht University, The Netherlands, December 1999.
- [KAS80] Uwe Kastens, Ordered attribute grammars, Acta informatica, 13:229-256, 1980
- [KAS91] Uwe Kastens. Implementation of visit-oriented attribute evaluators. In H. Alblas and B. Melichar, editors, Attribute Grammars, Applications and Systems, volume 545 of Lecture Notes in Computer Science, pages 114--139. Springer-Verlag, 1991.
- [IJM03] Jan IJmker, Dependency Analysis in Attribute Grammars
- p. 67: in
plan ConsIts, after
inp(Its2.dcli,Its2.lev) there should be
- p. 67: in
plan Block, it says
inp(Its.dcli,Its.lev) but it should be
- On visit-oriented evaluation:
- Use Jan IJmkers implementation of dependency analysis, and derive an ordering of attributes.
- Check for Order III circularity.
- Derive visit sequences.
- Handle dependencies between visits.
- Adapt code generation to exploit the visit sequences.
- Implement liftime analysis.
- Find a solution for generating circular dependencies in point 1.
- Q: How can I improve on the code? So if I know a visit sequence, what kind of code should I output? Pennings suggests visit functions. This is a function that takes part of the inhereted attributes, and outputs part of the synthesized attributes. How does this make te program faster? A: (Doaitse) Make visit functions. Our hope is that stricness analysis will recognise strictness in these functions.
- Q: How do I extract the attribute dependencies from [Usestream]? A: (Joost) The computation reaches its fixed point when there is no new information. So we can detect a fixed point with this function:
fix res = all (null . snd . snd) res
- Q: How can I handle Inter-Traversal Attribute Dependency? A: (Doaitse) Let visit functions return their continuation, partially parameterized with the attributes that they need from this visit function
- Q: There are two scheduling algerithms, Kastens' ordered scheduling algorithm and Pennings chained scheduling algorithm. Which one is the best?
- Q: In response to 2: Now I've found the
Result for each
Vertex, but how does this give me the dependencies?
The file Dep.ag introduces 1 syntesized attribute
up :: [Usestream]
[Usestream] == [(Vertex,Stream)]
data UsedAttr = Loc Name Name Trace -- field name and attribute name
| Glo Name Trace -- attribute name
data Vertex = Local Name Name Name -- lhs nt, constructor, attribute
| LHSInh Name Name Name -- lhs nt, constructor, attribute
| LHSSyn Name Name Name -- lhs nt, constructor, attribute
| ShRHSInh Name Name Name Name -- lhs nt, constructor, field, attribute !!rhs nt not known, equal to RHSInh!!
| ShRHSSyn Name Name Name Name -- lhs nt, constructor, field, attribute !!rhs nt not known, equal to RHSSyn!!
| RHSInh Name Name Name Name Name -- rhs nt, lhs nt, constructor, field, attribute
| RHSSyn Name Name Name Name Name -- rhs nt, lhs nt, constructor, field, attribute
| NTInh Name Name -- nt, attribute
| NTSyn Name Name -- nt, attribute
I'm still trying to figure out how I can find dependency information in
I encoded the Block AG [SAR99, p. 23-28] in UUAG, and looked at its
. Its not trivial how this corresponds
to [SAR99]'s dependencies.
I encoded the visit functions of the Block AG in Haskell.
The functions take the form of
Childrens catas -> Attrs of previous visits -> Inh -> (Syn, Continuation)
Sadly, [SAR99] does not give Block's Interfaces. I'll try to come up with them myself.
Correction, he does, on page 65. If I can derive these, I'm happy. For this I need to derive an ordering, because from an ordering I can derive an interface:
type Ordering = [Name]
type Interface = [([Name],[Name])] -- The ordering
type Interfaces = [(Nonterminal,Interface)] -- lookup-list, an interface for every nonterminal
-- Split the ordering into inherited and synthesized attributes
makeInterface :: Ordering -> Interface
makeInterface ord =
let (inh,ord') = split isInh ord
(syn,ord'') = split isSyn ord
in (inh,syn):makeInterface ord''
checks if an attribute is inherited, and
checks if it's synthesized. (Of course we need that -HOL notation-=!a. isInh a || isSyn a)=
An ordering is just a list
ord :: [Name]
with the property
(ord[i] `dependsOn` ord[j]) `implies` (i > j)
. So the problem we're left with is to derive
, and then generate the ordering with the best ordering algorithm (see question 4).
Yes! I've found the problem. Jan IJmkers alogrithm does not find all indirect dependencies, only downward ones. This is enough to detect cycles, because every cycle consist of a direct top arch, and an indirect downward part. You can see this in de code; the information of RHS-Inherited attributes flows to RHS-Synthesized attributes, but the information of LHS-Synthesized attributes does not flow to LHS-Inherited attributes. I've modified the algorithm, and now it delivers full dependencies. Of course it still finds all cycles.
With these results I've computed the interfaces, and they work! Now I'm working on generating code...
I'm skipping the type III cyclicity test for now. I've succeeded in creating the semantic domain (types of the functions that I'm going to generate)