Overview

Some repetitive idioms exist in AG specifications that we would like to avoid writting 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.

Functor attributes

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.

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;
}

An example functor transformation is host in ableC, which transforms away ``injection’’ productions by lifting declarations to higher points in the tree. 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 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.

Monoid attributes

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.)

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")];
}

An example monoid attribute is errors in ableC. 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.

Global propagate

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, ... except 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 these will be caught by the flow analysis.

Note that global propagate is only permitted when the attribute should be propagated for all productions; attempting to also write an explicit equation will result in a duplicate equation flow error. This is not a particularly severe restriction, as requiring that a global propagate means that the attribute is indeed propagated for all productions will result in more maintainable specifications.

Strategy attributes

Functor attributes allow for a limited notion of rewriting on a tree. However, this only permits single-pass operations where changes are made throughout the tree without decorating intermediate results. This makes it difficult to express iterative transformations (such as expression evaluation) with only functor attributes.

Strategy attributes are a sort of generalization of functor attributes. Instead of a single simultaneous pass, they work incrementally, with the traversal order specified by a “strategy expression” DSL based on term rewriting systems such as Stratego. Application of a strategy attribute can succeed or fail; the type of a strategy attribute on a nonterminal of type a is Maybe<a>, rather than a with functor attributes. Generally a strategy attribute should be globally propagated for all productions and not defined directly. If desired the attribute can be manually propagated to preserve forwarding productions.

The following is an example strategy attribute for performing the optimization x + 0 -> x:

strategy attribute elimPlusZero =
  topDown(
    try(
      rule on Expr of
      | addExpr(x, intConst(0)) -> x
      end));
attribute elimPlusZero occurs on Stmt, Expr;
propagate elimPlusZero on Stmt, Expr;

function simplifyStmt
Stmt ::= s::Stmt
{
  return
    case s.elimPlusZero of
    | just(s1) -> s1
    | nothing() -> error("Should always succeed")
    end;
}

This forwards to the following:

strategy attribute elimPlusZero =
  rec s ->
    (rule on Expr of
     | addExpr(x, constExpr(0)) -> x
     end <+ id) <*
   all(s);
     
-- Optimization: s == elimPlusZero
strategy attribute elimPlusZero =
  (rule on Expr of
    | addExpr(x, constExpr(0)) -> x
    end <+ id) <*
  all(elimPlusZero);

attribute elimPlusZero occurs on Stmt, Expr;
   
aspect production addExpr
top::Expr ::= e1::Expr e2::Expr
{
  propagate elimPlusZero;
}
aspect production constExpr
top::Expr ::= i::Integer
{
  propagate elimPlusZero;
}

aspect production seqStmt
top::Stmt ::= s1::Stmt s2::Stmt
{
  propagate elimPlusZero;
}
aspect production assignStmt
top::Stmt ::= n::Name e::Expr
{
  propagate elimPlusZero;
}

Basic strategy expressions are rules, rec for recursive strategies, fail, id, <* (sequence), <+ (choice), all, some, and one. Synthesized attributes can be used as literals in a strategy expression. These are usually the names of other strategy attributes, but in principle any attribute of type Maybe can occur here. Strategy constructors such as topDown and try are “extensions” that forward to basic strategy combinators.

Since the rec occurs at the top level of the definition, as an optimization we can simply replace s with elimPlusZero and eliminate the rec. Otherwise the rec body would need to be lifted out as a separate strategy attribute.

The global propagate on generates an aspect production for all known Stmt and Expr productions. For this example we only examine 4 representative productions.

The definition, occurrence and propagation of the strategy forward to the following:

synthesized attribute elimPlusZero<a>::Maybe<a>;
strategy attribute elimPlusZero_cont = all(elimPlusZero);

attribute elimPlusZero<Stmt> occurs on Stmt
attribute elimPlusZero<Expr> occurs on Expr;
attribute elimPlusZero_cont occurs on Stmt, Expr;
   
aspect production addExpr
top::Expr ::= e1::Expr e2::Expr
{
  top.elimPlusZero =
    bindMaybe( -- <*
      orElse( -- <+
        case e1, e2 of -- rule
        | x, constExpr(0) -> just(x)
        | _, _ -> nothing()
        end,
        just(top)), -- id
      \ res::Expr -> decorate res with {env = top.env}.all_elimPlusZero);
  propagate elimPlusZero_cont;
}
aspect production constExpr
top::Expr ::= i::Integer
{
  -- Optimization: left operand to <* is effectively id for this production
  top.elimPlusZero = top.all_elimPlusZero;
  propagate elimPlusZero_cont;
}

aspect production seqStmt
top::Stmt ::= s1::Stmt s2::Stmt
{
  -- Optimization: left operand to <* is effectively id for this production
  top.elimPlusZero = top.all_elimPlusZero;
  propagate elimPlusZero_cont;
}
aspect production assignStmt
top::Stmt ::= n::Name e::Expr
{
  -- Optimization: left operand to <* is effectively id for this production
  top.elimPlusZero = top.all_elimPlusZero;
  propagate elimPlusZero_cont;
}

Here in the definition of the elimPlusZero strategy, the right side of the sequence operator is lifted out as a “continuation” strategy attribute elimPlusZero_cont, to be computed on any successful result of applying the left side.

The occurs on declaration forwards to the following 3 lines. elimPlusZero is provided with the nonterminal type as the type parameter for each nonterminal, and the elimPlusZero_cont continuation attribute automatically occurs on the same nonterminals.

The translation of the strategy’s body can be seen in the translation of propagating elimPlusZero on addExpr: the sequence operator becomes a monadic operation using bindMaybe, the choice operator becomes a call to orElse, id becomes just(top).

The rule is translated by statically analyzing the outermost pattern. Since this matches on addExpr, the rule becomes a pattern match of each of the child patterns on each of the children, failing if all clauses fail. If all patterns in a rule clause match, the right side rule expression is evaluated and wrapped in just.

When the left side of the sequence succeeds, we decorate the result with all known inherited attributes on the nonterminal and access the continuation. In reality only the attribute’s flow type is required, but this is done to avoid requiring the results of the flow analysis for translation. The MWDA guarantees that all inherited attributes that are dependencies of an attribute will be visible at the attribute’s definition site.

On the other productions, we can statically determine that the rule does not match. This means that the choice becomes equivalent to id, and thus the sequence becomes equivalent to its right side. As an optimization, we can avoid the monadic bind and just compute the continuation attribute on the current tree. Propagating a strategy attribute on a production will also automatically propagate any of its lifted continuation strategy attributes.

Expanding the forwarding of elimPlusZero_cont, we get

synthesized attribute elimPlusZero<a>::Maybe<a>;
synthesized attribute elimPlusZero_cont<a>::Maybe<a>;

attribute elimPlusZero<Stmt> occurs on Stmt
attribute elimPlusZero<Expr> occurs on Expr;
attribute elimPlusZero_cont<Stmt> occurs on Stmt
attribute elimPlusZero_cont<Expr> occurs on Expr;
   
aspect production addExpr
top::Expr ::= e1::Expr e2::Expr
{
  top.elimPlusZero =
    bindMaybe( -- <*
      orElse( -- <+
        case e1, e2 of -- rule
        | x, constExpr(0) -> just(x)
        | _, _ -> nothing()
        end,
        just(top)), -- id()
      \ res::Expr -> decorate res with {env = top.env}.all_elimPlusZero);
  top.elimPlusZero_cont =
    case e1.elimPlusZero, e2.elimPlusZero of -- all(elimPlusZero)
    | just(res1), just(res2) -> addExpr(res1, res2)
    | _ -> nothing()
    end;
}
aspect production constExpr
top::Expr ::= i::Integer
{
  top.elimPlusZero = top.all_elimPlusZero;
  top.elimPlusZero_cont = just(i); -- all(elimPlusZero)
}

aspect production seqStmt
top::Stmt ::= s1::Stmt s2::Stmt
{
  top.elimPlusZero = top.all_elimPlusZero;
  top.elimPlusZero_cont =
    case s1.elimPlusZero, s2.elimPlusZero of -- all(elimPlusZero)
    | just(res1), just(res2) -> seqStmt(res1, res2)
    | _ -> nothing()
    end;
}
aspect production assignStmt
top::Stmt ::= n::Name e::Expr
{
  top.elimPlusZero = top.all_elimPlusZero;
  top.elimPlusZero_cont =
    case e.elimPlusZero of -- all(elimPlusZero)
    | just(eRes) -> seqStmt(n, eRes)
    | _ -> nothing()
    end;
}

all is basically a monadic version of propagating an ordinary functor attribute. For all children on which the attribute occurs it is accessed, and if all succeed the results are used in reconstructing the same production. Note that the argument of the all combinator must be the name of a strategy attribute, otherwise the argument will be lifted as a separate strategy attribute.

Applications of strategy attributes

Remove this in the final version of this page

  • Strategy attributes would be a more elegant solution to the rewriting done by the Halide extension, as it would properly handle forwarding extension productions.
  • The template extension is probably still better off with the reflection-based version of rewriting. This could be done with attributes like before but would require explicit propagate on all extension productions.
  • We should compare performance between both versions for lambda calculus example.
  • Language extensions for compile-time expression evaluation or optimizations?
  • Anything we currently do with forwarding that might have a cleaner solution with strategy attributes?
  • Any other classic term rewriting problems?