Meiage

Welcome to the homepage of Meiage. This project is part of Eifl?

Goals

Meiage stands for More Efficient Implementation of Attribute Grammar Evaluators. It aims at improving the UU-AG attribute evaluator generator in two ways:

1. Implementing visit-oriented evaluation, as described in [KAS91] and [SAR99]
2. Implementing en exploiting Lifetime Analysis

Deliverables

• 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

Installation instructions:

• Checkout the uust repository from cvs.cs.uu.nl: cvs -d :pserver:anonymous@cvs.cs.uu.nl:/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

Participants

• Students.JoostVerhoog

Literature

• [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

Errata

• [SAR99]
  • p. 67: in

    plan ConsIts

    , after

    inp(Its2.dcli,Its2.lev)

    there should be

    out(Its2.dclo)

  • p. 67: in

    plan Block

    , it says

    inp(Its.dcli,Its.lev)

    but it should be

    inp(Its.lev,Its.dcli)

Plan

1. On visit-oriented evaluation:
   1. Use Jan IJmkers implementation of dependency analysis, and derive an ordering of attributes.
   2. Check for Order III circularity.
   3. Derive visit sequences.
   4. Handle dependencies between visits.
   5. Adapt code generation to exploit the visit sequences.
2. Implement liftime analysis.
3. Find a solution for generating circular dependencies in point 1.

Questions

Answered questions

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.
2. 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
3. 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

Open questions

1. Q: There are two scheduling algerithms, Kastens' ordered scheduling algorithm and Pennings chained scheduling algorithm. Which one is the best?
2. Q: In response to 2: Now I've found the Result for each Vertex, but how does this give me the dependencies?

Log

The file Dep.ag introduces 1 syntesized attribute

up :: [Usestream]

[Usestream] == [(Vertex,Stream)]
            == [(Vertex,[Result])]
            == [(Vertex,[([UsedAttr],[UsedAttr])])]

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 [UseStream]. I encoded the Block AG [SAR99, p. 23-28] in UUAG, and looked at its [UseStream]. 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''

Where isInh checks if an attribute is inherited, and isSyn 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 the function dependsOn from the [UseStream], 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)