Automatic attributes

Some repetitive idioms exist in AG specifications that we would like to avoid writing boilerplate for by hand. These attributes fall into various common patterns (functor, monoid, etc.) As a first step, we add an extension to Silver such that in production bodies we can write

propagate attr1, attr2, ...;

This statement is overloaded for different kinds of attributes, forwarding to the appropriate equations on the production.

If env is declared as an inherited attribute, then just writing propagate env; in a production body will generate copy equations for env on all children with the attribute.

inherited attribute env::Env;

nonterminal Stmt with env;

abstract production seqStmt
top::Stmt ::= s1::Stmt s2::Stmt
{
  propagate env;
}

This translates to the following equivalent specification:

inherited attribute env::Env;

nonterminal Stmt with env;

abstract production seqStmt
top::Stmt ::= s1::Stmt s2::Stmt
{
  s1.env = top.env;
  s2.env = top.env;
}

This mechanism replaced “autocopy attributes”, a variant of inherited attributes in which attribute values were implicitly copied down the tree. This feature was removed because of the potential for undesired (and potentially incorrect!) implicit equations.

Monoid attributes allow for collections of values to be assembled and passed up the tree. The type of a monoid attribute must be in the monoid category, having an empty value and append operator (e.g. [] and ++ for lists.)

A common use of monoid attributes is collecting a list of error messages up a syntax tree. For example in ableC,

monoid attribute errors::[Message] with [], ++;

nonterminal Stmt;

attribute errors occurs on Stmt;

abstract production nullStmt
top::Stmt ::=
{
  propagate errors;
}
abstract production seqStmt
top::Stmt ::= s1::Stmt s2::Stmt
{
  propagate errors;
}
abstract production errorStmt
top::Stmt ::= msg::[Message]
{
  top.errors := msg;
}
abstract production ifStmt
top::Stmt ::= c::Expr  t::Stmt  e::Stmt
{
  propagate errors;
  top.errors <-
    if c.typerep.isScalarType then []
    else [err(c.location, "If condition must be scalar type")];
}

This translates to the following equivalent specification:

synthesized attribute errors::[Message] with ++;

nonterminal Stmt;

attribute errors occurs on Stmt;

abstract production nullStmt
top::Stmt ::=
{
  top.errors := [];
}
abstract production seqStmt
top::Stmt ::= s1::Stmt s2::Stmt
{
  top.errors := s1.errors ++ s2.errors;
}
abstract production errorStmt
top::Stmt ::= msg::[Message]
{
  top.errors := msg;
}
abstract production ifStmt
top::Stmt ::= c::Expr  t::Stmt  e::Stmt
{
  top.errors := c.errors ++ t.errors ++ e.errors;
  top.errors <-
    if c.typerep.isScalarType then []
    else [err(c.location, "If condition must be scalar type")];
}

Monoid attributes become collection attributes with the same append operator. This means that non-propagated equations must use := instead of =, and additional values can be contributed besides the propagated equation using the <- operator.

When propagated on a production with no children on which the attribute occurs, the empty value is used. Otherwise, the append operator is used to combine the value of the attribute on all children with the attribute. This includes shared children, since we typically wish to consider them in analyses, but excludes decorated children, since they have typically been fully analyzed elsewhere.

Monoid attributes commonly have list, string, integer or Boolean types. If the type of the attribute is in the Monoid type class (as is the case with strings and lists), then the empty value and operator (the with [], ++) can be omitted.

Functor attributes allow for a mapping-style transformation over a tree, where we only wish to modify the tree in a few places. Thus the type of a functor attribute is effectively in the functor category, being a nonterminal that in some way encapsulates values that we wish to modify. Functor transformations are distinct from forwarding, as these transformed trees are not necessarily semantically equivalent to the original tree. Also more than one functor transformation of the same tree is possible, while a production may only have one forward.

An example functor transformation is host in ableC, which transforms away ``injection'' productions by lifting declarations to higher points in the tree.

functor attribute host;

nonterminal Stmt;

attribute host occurs on Stmt;

abstract production nullStmt
top::Stmt ::=
{
  propagate host;
}
abstract production seqStmt
top::Stmt ::= s1::Stmt s2::Stmt
{
  propagate host;
}
abstract production errorStmt
top::Stmt ::= msg::[Message]
{
  propagate host;
}
abstract production injectGlobalDeclsStmt
top::Stmt ::= lifted::Decls
{
  top.host = nullStmt();
  top.globalDecls = lifted.decls;
}

This translates to the following equivalent specification:

synthesized attribute host<a>::a;

nonterminal Stmt;

attribute host<Stmt> occurs on Stmt;

abstract production nullStmt
top::Stmt ::=
{
  top.host = nullStmt();
}
abstract production seqStmt
top::Stmt ::= s1::Stmt s2::Stmt
{
  top.host = seqStmt(s1.host, s2.host);
}
abstract production errorStmt
top::Stmt ::= msg::[Message]
{
  top.host = errorStmt(msg);
}
abstract production injectGlobalDeclsStmt
top::Stmt ::= lifted::Decls
{
  top.host = nullStmt();
  top.globalDecls = lifted.decls;
}

A functor attribute is implemented as just an ordinary synthesized attribute whose type is the same as the type of the nonterminal on which it occurs. To enable this, a functor attribute forwards to an ordinary synthesized attribute with a type parameter a. Functor attributes provide an overload for attribute occurrence such that occurs on for a functor attribute with no type argument provided will forward to an attribute occurrence with the nonterminal provided as the type argument.

propagate is overloaded for functor attributes such that propagating a functor attribute will result in an equation that constructs the same production with the result of accessing the attribute on all children. Any children on which the attribute does not occur are simply used unchanged in the new tree.

Note that explicitly providing a different type as the type parameter is permitted, however attempting to propagate the attribute in this case would result in an error. One may however wish to reuse a functor attribute in a different context, and provide explicit equations:

nonterminal ExtStmt;

attribute host<Stmt> occurs on ExtStmt;

abstract production extThing
top::ExtStmt ::= ...
{
  top.host = seqStmt(..., ...);
}

Note that propagating a functor attribute on a production with a shared child will result in an error, as the generated equation will attempt to apply the production with shared children, which is not permitted outside of forwards-to equations. In most cases, a dispatching production that forwards to this production should instead be used in an explicit equation.

Consider the problem of comparing two trees in some fashion, for example checking them for equality. Some mechanism is needed to associate the nodes of two decorated trees of (possibly) the same shape. This can be done by an inherited (destruct) attribute passing a reference to one tree being compared down the other, and a corresponding synthesized (equality) attribute that at every production determines whether the current tree is equal to the one that was passed down.

Destruct attributes can be thought of as sort of an inverse of functor attributes; functor attributes are to tree construction as destruct attributes are to tree deconstruction via pattern matching.

A destruct attribute is an inherited attribute on some tree that decomposes another decorated tree of the same shape; it is an error if a destruct attribute is ever demanded from a tree whose parent was constructed by a different production than the one provided in the attribute.

A destruct attribute might be used for comparing types in a functional language implementation. Here types are represented by a Type nonterminal, with constructors for integer types, named data types, and function types:

destruct attribute compareTo;

nonterminal Type;

attribute compareTo occurs on Type;

abstract production intType
top::Type ::=
{
  propagate compareTo;
}

abstract production dataType
top::Type ::= name::String
{
  propagate compareTo;
}

abstract production fnType
top::Type ::= inputType::Type outputType::Type
{
  propagate compareTo;
}

The above translates to the following equivalent specification:

inherited attribute compareTo<a (i::InhSet)>::Decorated a with i;

nonterminal Type;

attribute compareTo<Type {}> occurs on Type;

abstract production intType
top::Type ::=
{
  -- No children for which to propagate the attribute
}

abstract production dataType
top::Type ::= name::String
{
  -- No children for which to propagate the attribute
}

abstract production fnType
top::Type ::= inputType::Type outputType::Type
{
  inputType.compareTo =
    case top.compareTo of
    | fnType(inputType2, outputType2) -> inputType2
    | _ -> error("Destruct attribute compareTo demanded on child a of production fnType when given value doesn't match")
    end;
  outputType.compareTo =
    case top.compareTo of
    | fnType(inputType2, outputType2) -> outputType2
    | _ -> error("Destruct attribute compareTo demanded on child a of production fnType when given value doesn't match")
    end;
}

The type of a destruct attribute is a Decorated (reference) type, such that attributes may be accessed on the corresponding tree. The type of the destructed tree and the inherited attributes carried by the reference are specified as two type parameters on the attribute, of kind * and InhSet.

Destruct attributes provide an overload for attribute occurrence such that occurs on for a destruct attribute with no type arguments will forward to an attribute occurrence with the nonterminal and {} (the empty set of inherited attributes) provided as the type arguments. Often one wishes to make use of inherited attributes on the deconstructed tree; if a single type argument is provided, it will be used as the set of inherited attributes for the reference. For example writing

attribute compareTo<{someInh}> occurs on Type;

will forward to

attribute compareTo<{someInh} Type> occurs on Type;

giving a type Decorated Type with {someInh}; thus we could access inputType.compareTo.someInh in the fnType production.

Destruct attributes are typically used in conjunction with equality or ordering attributes, described next.

Equality attributes are used to compare trees for equality. They are synthesized attributes of type Boolean that work in conjunction with a destruct attribute that specifies the tree to compare; the declaration of an equality attribute specifies what inherited attribute should be used.

equality attribute isEqual with compareTo
  occurs on Type;

aspect production intType
top::Type ::=
{
  propagate isEqual;
}

abstract production dataType
top::Type ::= name::String
{
  propagate isEqual;
}

abstract production fnType
top::Type ::= inputType::Type outputType::Type
{
  propagate isEqual;
}

The above translates to the following equivalent specification:

synthesized attribute isEqual::Boolean occurs on Type;

aspect production intType
top::Type ::=
{
  top.isEqual =
    case top.compareTo of
    | intType() -> true
    | _ -> false
    end;
}

abstract production dataType
top::Type ::= name::String
{
  top.isEqual =
    case top.compareTo of
    | dataType(name2) -> name == name2
    | _ -> false
    end;
}

abstract production fnType
top::Type ::= inputType::Type outputType::Type
{
  top.isEqual =
    case top.compareTo of
    | fnType(_, _) -> inputType.isEqual && outputType.isEqual
    | _ -> false
    end;
}

The == operator is used to compare any children that do not have the isEqual attribute.

Note for any nonterminal types that have the standard isEqual and compareTo attributes defined in silver:core, the == operator itself is overloaded to use them for comparison. Thus propagating compareTo and isEqual on a nonterminal type is comparable to writing deriving Eq in Haskell or similar languages.

Bidirectional equality attributes are a variant of equality attributes for defining symmetric comparisons on nonterminals, where for some productions some specialized, non-structural behavior is desired - for example in implementing unification, or error handling in type checking. If a regular equality attribute were used, overriding on some productions would only have an effect in one direction; one would need to override the attribute on every production to include the special case.

For example, consider the case of implementing type equality with an errorType that should be considered equal to any other type. Instead of just passing one tree down as an inherited attribute to the other tree, we would like to pass both trees in to the corresponding trees. This can be done with a destruct attribute, where the reference set is set to contain the attribute itself:

destruct attribute compareTo;
attribute compareTo<{compareTo}> occurs on Type;
propagate compareTo on Type;

A bidirectional equality attribute consists of two Boolean synthesized attribute: the final result of the comparison, and the partial result of the comparison in one direction. On each production, the partial attribute is propagated like a normal equality attribute, while the total attribute checks if the partial attribute succeeded in either direction. The partial attribute can then be overridden on a production, and will have the desired affect in both directions.

biequality attribute isTypeEqual, isTypeEqualPartial with compareTo occurs on Type;

aspect production errorType
top::Type ::= tv::TyVar
{
  propagate isTypeEqual;
  top.isTypeEqualPartial = true;
}

abstract production dataType
top::Type ::= name::String
{
  propagate isTypeEqual, isTypeEqualPartial;
}

abstract production fnType
top::Type ::= inputType::Type outputType::Type
{
  propagate isTypeEqual, isTypeEqualPartial;
}

The above translates to the following equivalent specification:

synthesized attribute isTypeEqual::Boolean occurs on Type;
synthesized attribute isTypeEqualPartial::Boolean occurs on Type;

aspect production intType
top::Type ::=
{
  top.isTypeEqual = top.isTypeEqualPartial || top.compareTo.isTypeEqualPartial;
  top.isTypeEqualPartial = true;
}

abstract production dataType
top::Type ::= name::String
{
  top.isTypeEqual = top.isTypeEqualPartial || top.compareTo.isTypeEqualPartial;
  top.isTypeEqualPartial =
    case top.compareTo of
    | dataType(name2) -> name == name2
    | _ -> false
    end;
}

abstract production fnType
top::Type ::= inputType::Type outputType::Type
{
  top.isTypeEqual = top.isTypeEqualPartial || top.compareTo.isTypeEqualPartial;
  top.isTypeEqualPartial =
    case top.compareTo of
    | fnType(_, _) -> inputType.isTypeEqual && outputType.isTypeEqual
    | _ -> false
    end;
}

As with equality attributes, == is used as a fallback to compare any children that don’t use the biequality attributes for comparison; == is inserted when propagating the partial attribute for any children that don’t have the total attribute.

The above attributes could then be used to define a function for comparing types:

function typesEqual
Boolean ::= a::Type b::Type
{
  a.compareTo = b;
  b.compareTo = a;
  return a.isTypeEqual;
}

instance Eq Type {
  eq = typesEqual;
}

Ordering attributes are used define a total ordering for trees, e.g. to sort them or use them as map keys. An ordering attribute pair consists of a “key” synthesized attribute of type String that assigns a unique identifier to every production, and the “result” synthesized attribute of type Integer that is similar in nature to an equality attribute. The value of the result attribute is negative if the compared tree is “less” than the other, positive if it is “greater”, and 0 if the trees are equal.

ordering attribute compareKey, compare with compareTo
  occurs on Type;

aspect production intType
top::Type ::=
{
  propagate compareKey, compare;
}

abstract production dataType
top::Type ::= name::String
{
  propagate compareKey, compare;
}

abstract production fnType
top::Type ::= a::Type b::Type
{
  propagate compareKey, compare;
}

The above translates to the following equivalent specification:

synthesized attribute compareKey::String occurs on Type;
synthesized attribute compare::Integer occurs on Type;

aspect production intType
top::Type ::=
{
  top.compareKey = "example:intType";
  top.compare =
    case top.compareTo of
    | intType() -> 0
    | _ -> silver:core:compare(top.compareKey, top.compareTo.compareKey)
    end;
}

abstract production dataType
top::Type ::= name::String
{
  top.compareKey = "example:dataType";
  top.compare =
    case top.compareTo of
    | dataType(name2) -> silver:core:compare(name, name2)
    | _ -> silver:core:compare(top.compareKey, top.compareTo.compareKey)
    end;
}

abstract production fnType
top::Type ::= inputType::Type outputType::Type
{
  top.compareKey = "example:fnType";
  top.compare =
    case top.compareTo of
    | fnType(_, _) -> if inputType.compare != 0 then inputType.compare else outputType.compare
    | _ -> silver:core:compare(top.compareKey, top.compareTo.compareKey)
    end;
}

If the compared productions do not match, then they are compared according to their names as determined by the key attribute, using the standard library function compare from the Ord type class. Otherwise the children of the matching production that have the attribute are compared via the attribute; any that lack the attribute are compared using the compare function.

Note for any nonterminal types that have the standard compareKey, compare and compareTo attributes defined in silver:core, the compare function itself (and other comparison operators) are overloaded to use the attributes for comparison. Thus propagating compareKey, compare and compareTo on a nonterminal type is comparable to writing deriving Ord in Haskell or similar languages.

Sometimes you want pairs of attributes to be threaded through the tree in a particular way. This might be useful if you’re doing a substitution context in Hindley Milner Type inference, or you want to assign ids to nodes in a tree ordered by their position in the tree structure.

You might setup a threaded attribute like so

threaded attribute inh, syn :: Context;

And use it by calling it in this way.

propagate inh, syn; generates child1.inh = top.inh; child2.inh = child1.syn; top.syn = child2.syn; on non-forwarding prods or child1.inh = top.inh; child2.inh = child1.syn; forward.inh = child2.syn; on forwarding prods.

By default the children of productions are traversed left-to-right, but the direction of threading can also be specified manually:

threaded attribute inh1, syn1 :: Context direction = left to right;
threaded attribute inh2, syn2 :: Context direction = right to left;

You can also do thread inh, syn on top, child1, child2, prodattr1, prodattr2, top; instead of propagate to more precisely specify the order of threading or include prod attrs/locals.

In some cases we wish to propagate an attribute on all productions of a nonterminal with no exceptions. Instead of adding propagate statements (and potentially aspects) for all productions, we can instead write

propagate attr1, attr2, ... on NT1, NT2, ...;

This generates an aspect production for all known non-forwarding productions of these nonterminals. Each of these aspect productions will contain propagate attr1, attr2, ...; in its body.

Sometimes one may wish to propagate on almost all productions of a nonterminal, but don’t want to write propagate on all but a few production bodies. This can be avoided by instead writing

propagate attr1, attr2, ... on NT1, NT2, ... excluding prod1, prod2, ...;

This will generate propagating aspect productions for all but the listed productions.

We generally do not wish to propagate on forwarding productions as doing so would often be interfering, and the host language does not know about all forwarding productions anyway. However if one does in fact wish to propagate on forwarding productions as well, they can simply add explicit propagate statements for each of these productions.

In some cases some non-forwarding propagate statements may not be exported by the definition of the nonterminal, such as with closed nonterminals or optioned grammars. In these cases explicit propagate statements are required as well, however the omission of these will be caught by the flow analysis.

For productions with shared children, one has a choice of whether inherited attributes should be supplied before or after forwarding. Thus when propagating inherited, destruct or threaded attributes, one can specify whether the attribute should be propagated for shared children by prefixing the names of the propagated attributes with @. For example

threaded attribute contextIn, contextOut :: TypingContext occurs on Expr;

production funCall implements Application
top::Expr ::= f::@Expr args::Exprs
{
  propagate contextIn, contextOut;
}

would produce the equations

  args.contextIn = top.contextIn;
  top.contextOut = args.contextOut;

while writing

  propagate @contextIn, @contextOut;

would produce

  f.contextIn = top.contextIn;
  args.contextIn = f.contextOut;
  top.contextOut = args.contextOut;