Decorated vs undecorated

The distinction between decorated and undecorated types is one that some initially find confusing; this section aims to clear up such confusion.

Attribute grammars are a way of doing computations over trees, and there are two conceptually different types of trees for each nonterminal:

• The undecorated type, also referred to as a term, is a bare-bones data type that simply represents the tree itself. This is nearly identical to how the tree might be represented as a Haskell data type, for example.
• The decorated type, on the other hand, is the fully attributed tree. Decorated trees contain not just their (now decorated) children but also the values of all synthesized and inherited attributes that occur on the corresponding nonterminal.

There are a number of consequences to this distinction:

• An undecorated tree is quite space-efficient. Its decorated trees may not be.
• Attributes can only be accessed from decorated trees. (Some tricks may obscure this fact, see below.)
• Undecorated trees can be decorated any number of times, potentially with different inherited attributes each time. Each of these will produce a distinct decorated tree.

It comes from the two-stage form of application that attribute grammars have.

Stage 1 takes a production and applies it to its children. This yields an undecorated type.

Stage 2 takes an undecorated type, and applies it to a set of inherited attributes. This yields the decorated type.

Note that there are actually multiple decorated types possible for a nonterminal, depending on what inherited attributes have been provided to the referenced tree. For example we might have Decorated Expr with {env} or Decorated Expr with {env, frame, returnType} - the type specifies that the reference has been given at least these attributes. But for convenience we let just Decorated Expr refer to being decorated with all known inherited attributes, as a default. This default can be overridden.

From looking at simple examples of Silver code, one may not be aware of these distinctions between decorated and undecorated types. The reason is that Silver will hide this distinction in the common cases. Productions' (and functions') children and local attributes, despite having a declared undecorated type, are in fact treated as decorated when referenced. This is because these may be supplied with inherited attributes elsewhere within the production body.

Failing to define all the necessary inherited attributes is not currently detected by Silver at compile time, and will cause a runtime error.

Example: In the following production:

abstract production assignmentStmt
top::Stmt ::= l::Name '=' r::Expr
{
  local attribute lcopy :: Name;
  lcopy = l; -- Silver automatically undecorates l
  local attribute lref :: Decorated Name;
  lref = l;
}

The child l actually has type Decorated Name in the body of the production. Local attribute lcopy also has type Decorated Name for the same reason that the child l is decorated. However, the value of lcopy is a different decorated tree than l. These two trees may be assigned different values for inherited attributes, though that is not shown in the example.

Local lref has the same decorated type, but the value of lref is the same decorated tree as l. Inherited attributes cannot be given to lref.

assignmentStmt must be invoked with an undecorated name and expression. Attempting to pass it an already decorated name will result in a type error. Similarly, lcopy must be initialized with a value of undecorated type, though in the example above, l is automatically undecorated.

This “automatic undecoration” behavior only applies to names, not expressions. If you call a function that returns a value of type Decorated Foo, and you try to assign this to a local of type Foo, you will receive a type error. You will need to use the ^ operator to manually un-decorate the type. See the undecoration operator.

Whether a name is being referenced as decorated or undecorated is determined via type inference. However, if a name is passed into a polymorphic function, the “possibly decorated” type will be left unspecialized and will default to the decorated type. The undecorated type can be forced in these cases by calling new on the argument.

If a type class method is called with a possibly decorated type, and an instance exists for the undecorated but not the decorated form of the type (excluding typeError instances), the undecorated type will be used. This behavior is provided for convenience to avoid needing to call new.

For example in the following production:

instance Eq Name { eq = ...; }

abstract production nameAssignStmt
top::Stmt ::= l::Name '=' r::Name
{
  forwards to
    if l == r then nullStmt()
    else assignmentStmt(l, refExpr(r)); 
}

l == r is equivalent to eq(l, r); the type Name rather than Decorated Name with {} will be inferred for l and r, because an instance exists for Eq Name but not Eq Decorated Name with {}

In addition to this automatic undecoration of children and locals, attempting to access an attribute of an undecorated type will automatically decorate it with no inherited attributes, and then access the attribute from that resulting temporary decorated tree. This behavior is purely for convenience: there are many common synthesized attributes that do not depend on any inherited attributes (consider fst and snd of the Pair type.)

This behavior only applies to attribute accesses (and technically, also pattern matching), and not to any arbitrary expression that wants a decorated type. If you try to call a function that takes a Decorated parameter with an undecorated value, you will receive a type error. See the decorate operator for explicitly creating a decorate value from an undecorated one.

Consider the nonterminal type Expr from the Simple tutorial grammar. This nonterminal is decorated by the synthesized attribute errors which depends on the inherited attribute env. To compute errors on an expression such as “x + 3” we need contextual information indicating if x has been declared or not. This information is passed in as the inherited attribute env. Inside the production varRef the value of errors is based on the result of looking up the variable in the inherited attribute env.

The production add, below, in the abstract syntax computes the value of its errors attribute from that of its children. (The assignment operator := is described in the section on collections and can be read as the standard assignment = for our purposes here.)

abstract production add 
e::Expr ::= l::Expr r::Expr 
{
  l.env = e.env;
  r.env = e.env;
  e.errors := l.errors ++ r.errors ;
}

What may be initially confusing is that the declared type of child l is the undecorated type Expr yet this production clearly accesses the synthesized attribute errors on that node. The reason this is allowed is that inside the curly braces we are really working with decorated trees since inherited attributes of the children may be assigned here. And we see above that the env attribute is being assigned to the child l. In the body of the production l does have the type Decorated Expr. The production add does take an undecorated Expr as its first (and second) argument, thus the type given for l is accurate. The production assigns the necessary inherited attributes to its children in its body and thus, in the body, the synthesized attributes of its children can be accessed.

As mentioned previously, Decorated Expr is really just a shorthand for Decorated Expr with {env}, if {env} is the default reference set for Expr. References with different sets of attributes are different types - so a Decorated Expr with {env} cannot be passed into a function expecting a Decorated Expr with {env, frame}. Since extensions can introduce new inherited attributes, the ability to use references with a set that is different than the default is particularly useful developing extensions that use references.

Sometimes one wishes to write a function or type class instance that works over any type of reference, rather than just a particular set of inherited attributes. An example of this can be seen in Silver’s testing framework, for displaying values in failing tests:

class ShowTestValue a {
  showTestValue :: (String ::= a);
}
instance ShowTestValue a {
  showTestValue = \ x::a -> show(80, reflect(x).pp);
}
instance ShowTestValue a => ShowTestValue Decorated a with i {
  showTestValue = \ x::Decorated a with i -> showTestValue(^x);
}

We want to show ordinary nonterminal and primitive values using reflection, however this cannot handle references. Thus we have a more specific instance to undecorate any type of reference before it is printed. i in Decorated a with i is a type variable used in place of a set of inherited attributes - in fact, inherited attribute sets are themselves types! They are not the types of values, rather inherited attribute set types have a new kind, written InhSet.

Example: The InhSet kind can appear anywhere that non-* kinds are permitted, for example as a type parameter to a nonterminal:

nonterminal Foo<(i :: InhSet)>;
production foo
top::Foo<i> ::= ref::Decorated Expr with i
{ ... }

Sometimes we don’t want to require an exact set of inherited attributes, but we still want to be somewhat more specific than allowing any set. This can be achieved using subset type constraints; these are a built-in special type constraint similar to type class type constraints, of the form i1 subset i2, where i1 and i2 have kind InhSet.

Example: A helper function to access the typerep synthesized attribute on Expr references might have a subset constraint, if we know that computing typerep always requires the env inherited attribute. We can use a subset constraint to establish the minimum reference set:

function getTyperep
{env} subset i => Type ::= e::Decorated Expr with i
{
  return e.typerep;
}

Example: A helper function that decorates expressions with default values for any set of inherited attributes requires the resulting references to have only the known attributes. We can use a subset constraint to enforce a maximum reference set:

function getRef
i subset {env, frame, returnType} =>
Decorated Expr with i ::= e::Expr
{
  e.env = [];
  e.frame = defaultFrame();
  e.returnType = nothing();
  return e;
}

An attribute of undecorated type is called a higher-order attribute. Higher-order attributes are ideal for expressing transformations from one tree to another. See the Simple tutorial’s concrete syntax, and how it constructs abstract syntax using higher-order attributes.

An attribute of decorated type is called a reference attribute. Reference attributes are ideal for connecting variable uses with variable declarations. This can be seen in the production varRef in the Simple tutorial grammar and shown in an example on the Production Attribute page.

Since these attributes can also be viewed as records of the attribute values that occur on their nonterminal, it is sometimes also preferable to pass around more complex data structures using a reference attribute, rather than a higher order one, since this avoids creating many copies of the decorated tree everywhere the undecorated tree is used.

Forward clauses always take undecorated trees to forward to. However, the children of the root production of that tree may be of decorated type.

One of the potential drawbacks of forwarding is the exponential growth in the size of the decorated tree. Consider the case of an operator that forwards to a function, as one might expect to see in a simple extension.

concrete production twiddleOperator
top::Expr ::= foo::Expr '~~>' bar::Expr
{
  forwards to functionApp("ext:twiddle", exprsCons(foo, exprsSingle(bar)));
}

While the above code is perfectly fine by itself, one desired enhancement might be to do type checking on this operator, instead of on the function after the forward (for example, to give better error messages. Or, to determine which function to forward to, based on type.)

However, this would result in exponential runtime for nested uses of the operator. The reason is that foo and bar are both type checked here, and then again by the functionApp production. This means that the undecorated trees get decorated once here, and once again after the forward. With repeated nesting of the operator, the problem should be obvious.

A solution in this case is to introduce a new constructor for Exprs:

abstract production exprsDecorated
top::Exprs ::= exps :: [Decorated Expr]
  ...

concrete production twiddleOperator
top::Expr ::= foo::Expr '~~>' bar::Expr
{
  forwards to functionApp("ext:twiddle", exprsDecorated([foo, bar]));
}

With this change, the children are only decorated once. This eliminates the problem, but introduces a restriction: all inherited attributes the function application might wish to give to its children, must be given by the operator instead. It is possible to avoid this restriction by using tree sharing.