Attribute grammar for the dleaf, free, and tail
attributes of a quirk21 program.  [Revision 2]

Revision history:

Revision 2, 6 October 2004:
    Added productions to define E.tail for all expressions,
        not just expressions that occur inside a lambda
        expression.

Revision 1, 5 October 2004:
    Fixed bug in computation of E.free for case expressions.
    Fixed bug in specification of Ei.tail for new record expressions.
    Fixed attribution rules for unary operator expressions.


The attribute grammar is defined over abstract syntax trees
that contain no errors.

Attributes.

        F.free          synthesized

        E.dleaf         synthesized
        E.free          synthesized
        E.tail          inherited

F.free, a synthesized attribute, is the set of all identifiers
that occur free within F.

E.dleaf is a synthesized boolean attribute that is true iff E is
an expression that contains no non-tail calls.
E.free, a synthesized attribute, is the set of all identifiers
that occur free within E.
E.tail is an inherited boolean attribute that is true iff E is in
a tail position.

Notation:  In set contexts, + and - mean union and set difference,
respectively.


P  -->  E where M1 ... Mk       E.tail = false.                              !

M  -->  export I1 ... Im from D1 ... Dn where E1 ... Ek                      !

                                E1.tail = ... = Ek.tail = false.             !

D  -->  variables I1 = E1 ... Im = Em                                        !

                                E1.tail = ... = Em.tail = false.             !


D  -->  functions I1 = F1 ... Im = Fm                                        !


D  -->  types I1 = T1 ... Im = Tm                                            !


F  -->  lambda (I1 : T1, ..., Im : Tm) : T0 . E0

                                F.free = E0.free - {I1, ..., Im};
                                E0.tail = true.


E  -->  F                       E.dleaf = true;
                                E.free = F.free.


E  -->  let I1 = E1 ... Im = Em in E0

                                E.dleaf = E1.dleaf & ... & Em.dleaf & E0.dleaf;
                                E.free = E1.free
                                       + (E2.free - {I1})
                                       + ...
                                       + (Em.free - {I1, ..., I{m-1}})
                                       + (E0.free - {I1, ..., Im});
                                E1.tail = ... = Em.tail = false;
                                E0.tail = E.tail.


E  -->  letrec I1 = F1 ... Im = Fm in E0

                                E.dleaf = E0.dleaf;
                                E.free = F1.free + ... + Fm.free + E0.free
                                       - {I1, ..., Im};
                                E0.tail = E.tail.


E  -->  new I0 [ E0 ] E1        E.dleaf = E0.dleaf & E1.dleaf;
                                E.free = E0.free + E1.free;
                                E0.tail = E1.tail = false.


E  -->  new I0 { N1 = E1 ... Nm = Em }

                                E.dleaf = E1.dleaf & ... & Em.dleaf;
                                E.free = E1.free + ... + Em.free;
                                E1.tail = ... = Em.tail = false.              !


E  -->  case E0 of N1 : I1 then E1 ... Nm : Im then Em else Em+1

                                E.dleaf = E0.dleaf
                                        & E1.dleaf & ... & Em.dleaf
                                        & E{m+1}.dleaf;
                                E.free = E0.free
                                       + (E1.free - {I1}) + ...               !
                                       + (Em.free - {Im})                     !
                                       + E{m+1}.free;
                                E0.tail = false;
                                E1.tail = ... = Em.tail = E{m+1}.tail = E.tail.


E  -->  if E0 then E1 else E2   E.dleaf = E0.dleaf & E1.dleaf & E2.dleaf;
                                E.free = E0.free + E1.free + E2.free;
                                E0.tail = false;
                                E1.tail = E2.tail = E.tail.


E  -->  begin E1; ...; Ek end   E.dleaf = E1.dleaf & ... & Ek.dleaf;
                                E.free = E1.free + ... + Ek.free;
                                E1.tail = ... = E{k-1}.tail = false;
                                Ek.tail = E.tail.


E  -->  E1 B E2                 E.dleaf = E1.dleaf & E2.dleaf;
                                E.free = E1.free + E2.free;
                                E1.tail = E2.tail = false.


E  -->  U E1                    E.dleaf = E1.dleaf;                           !
                                E.free = E1.free;                             !
                                E1.tail = false.                              !


E  -->  L                       E.dleaf = true;
                                E.free = { }.


E  -->  I1                      E.dleaf = true;
                                E.free = { I1 }.


E  -->  E0 (E1, ..., Em)        E.dleaf = E0.dleaf & E1.dleaf & ... & Em.dleaf
                                        & E.tail;
                                E.free = E0.free + E1.free + ... + Em.free;
                                E0.tail = E1.tail = ... = Em.tail = false.


E  -->  E1 . N1                 E.dleaf = E1.dleaf;
                                E.free = E1.free;
                                E1.tail = false.


E  -->  E1 [ E2 ]               E.dleaf = E1.dleaf & E2.dleaf;
                                E.free = E1.free + E2.free;
                                E1.tail = E2.tail = false.