Partial Decoration
Partially decorated references are an extension to Silver’s notion of references to decorated trees.
NOTE: This feature is more experimental than average, and is subject to change!
Let’s take as an example, compiling a simple language with integers, booleans, and overloaded operators.
This language has an overloaded &
, so that:
> true & false // logical
false
> 12 & 5 // bitwise
4
One way to implement this operator might look something like:
production andExpr
top::Expr ::= lhs::Expr rhs::Expr
{
forwards to
case lhs.type, rhs.type of
 boolType(), boolType() > call(global("boolAnd"), exprsCons(lhs, exprsCons(rhs, exprsNil())))
 intType(), intType() > call(global( "intAnd"), exprsCons(lhs, exprsCons(rhs, exprsNil())))
 _, _ > errorExpr(...)
end;
}
However, this has a big performance problem hiding in it!
lhs
and rhs
must be undecorated terms in order to be passed to exprsCons
, so after decoration inference, the code is equivalent to:
production andExpr
top::Expr ::= lhs::Expr rhs::Expr
{
forwards to
case lhs.type, rhs.type of
 boolType(), boolType() > call(global("boolAnd"), exprsCons(new(lhs), exprsCons(new(rhs), exprsNil())))
 intType(), intType() > call(global( "intAnd"), exprsCons(new(lhs), exprsCons(new(rhs), exprsNil())))
 _, _ > errorExpr(...)
end;
}
This code may retypecheck an expression a number of times exponential in the nestedness of the expression!
To see why, let’s look at how the expression 1 & (2 & (3 & 4))
gets typechecked, and count how many times 4
gets typechecked.
 To typecheck
1 & (2 & (3 & 4))
, we need to evaluate its forward and typecheck that; to do that, we need to typecheck1
and2 & (3 & 4)
. Typechecking
1
is trivial.  To typecheck
2 & (3 & 4)
, we need to evaluate its forward and typecheck that; to do that, we need to typecheck2
and3 & 4
. Typechecking
2
is trivial.  To typecheck
3 & 4
, we need to evaluate its forward and typecheck that; to do that, we need to typecheck3
and4
. Typechecking
3
is trivial.  Typechecking
4
is trivial. (Typechecked 1 time) 3 & 4
forwards tointAnd(3, 4)
 To typecheck
intAnd(3, 4)
, we need to typecheck3
and4
. Typechecking
3
is trivial.  Typechecking
4
is trivial. (Typechecked 2 times)
 Typechecking
 Typechecking
2 & (3 & 4)
forwards tointAnd(2, 3 & 4)
. To typecheck
intAnd(2, 3 & 4)
, we need to typecheck2
and3 & 4
. Typechecking
2
is trivial.  To typecheck
3 & 4
, we need to evaluate its forward and typecheck that; to do that, we need to typecheck3
and4
. Typechecking
3
is trivial.  Typechecking
4
is trivial. (Typechecked 3 times) 3 & 4
forwards tointAnd(3, 4)
 To typecheck
intAnd(3, 4)
, we need to typecheck3
and4
. Typechecking
3
is trivial.  Typechecking
4
is trivial. (Typechecked 4 times)
 Typechecking
 Typechecking
 Typechecking
 Typechecking
1 & (2 & (3 & 4))
forwards tointAnd(1, (2 & (3 & 4)))
. To typecheck
intAnd(1, intAnd(2, intAnd(3, 4)))
, we need to typecheck1
andintAnd(2, intAnd(3, 4))
. Typechecking
1
is trivial.  To typecheck
2 & (3 & 4)
, we need to evaluate its forward and typecheck that; to do that, we need to typecheck2
and3 & 4
. Typechecking
2
is trivial.  To typecheck
3 & 4
, we need to evaluate its forward and typecheck that; to do that, we need to typecheck3
and4
. Typechecking
3
is trivial.  Typechecking
4
is trivial. (Typechecked 5 times) 3 & 4
forwards tointAnd(3, 4)
 To typecheck
intAnd(3, 4)
, we need to typecheck3
and4
. Typechecking
3
is trivial.  Typechecking
4
is trivial. (Typechecked 6 times)
 Typechecking
 Typechecking
2 & (3 & 4)
forwards tointAnd(2, 3 & 4)
. To typecheck
intAnd(2, 3 & 4)
, we need to typecheck2
and3 & 4
. Typechecking
2
is trivial.  To typecheck
3 & 4
, we need to evaluate its forward and typecheck that; to do that, we need to typecheck3
and4
. Typechecking
3
is trivial.  Typechecking
4
is trivial. (Typechecked 7 times) 3 & 4
forwards tointAnd(3, 4)
 To typecheck
intAnd(3, 4)
, we need to typecheck3
and4
. Typechecking
3
is trivial.  Typechecking
4
is trivial. (Typechecked 8 times)
 Typechecking
 Typechecking
 Typechecking
 Typechecking
 Typechecking
 Typechecking
The typical solution to this, colloquially called “decExpr
productions,” is to have a production like:
production decExpr
top::Expr ::= child::Decorated Expr
{
top.type = child.type;
 equations for any other hostlanguage synthesized attributes too
 since child is a reference, it already has all its inherited attributes
}
Then, instead of writing new
(or having it implicitly inserted for you), you write:
production andExpr
top::Expr ::= lhs::Expr rhs::Expr
{
forwards to
case lhs.type, rhs.type of
 boolType(), boolType() > call(global("boolAnd"), exprsCons(decExpr(lhs), exprsCons(decExpr(rhs), exprsNil())))
 intType(), intType() > call(global( "intAnd"), exprsCons(decExpr(lhs), exprsCons(decExpr(rhs), exprsNil())))
 _, _ > errorExpr(...)
end;
}
Now, when you typecheck 1 & (2 & (3 & 4))
, 4
gets typechecked only once (using { child }
as concrete syntax for decExpr
):
 To typecheck
1 & (2 & (3 & 4))
, we need to evaluate its forward and typecheck that; to do that, we need to typecheck1
and2 & (3 & 4)
. Typechecking
1
is trivial.  To typecheck
2 & (3 & 4)
, we need to evaluate its forward and typecheck that; to do that, we need to typecheck2
and3 & 4
. Typechecking
2
is trivial.  To typecheck
3 & 4
, we need to evaluate its forward and typecheck that; to do that, we need to typecheck3
and4
. Typechecking
3
is trivial.  Typechecking
4
is trivial. (Typechecked 1 time) 3 & 4
forwards tointAnd({ 3 }, { 4 })
 To typecheck
intAnd({ 3 }, { 4 })
, we need to typecheck{ 3 }
and{ 4 }
. Typechecking
{ 3 }
can use the alreadycomputed type, so it doesn’t need to do the actual work!  Typechecking
{ 4 }
can use the alreadycomputed type, so it doesn’t need to do the actual work!
 Typechecking
 Typechecking
2 & (3 & 4)
forwards tointAnd({ 2 }, { intAnd({ 3 }, { 4 }) })
 To typecheck
intAnd({ 2 }, { intAnd({ 3 }, { 4 }) })
, we need to typecheck{ 2 }
and{ intAnd({ 3 }, { 4 }) }
 Typechecking
{ 2 }
can use the alreadycomputed type, so it doesn’t need to do the actual work!  Typechecking
{ intAnd({ 3 }, { 4 }) }
can use the alreadycomputed type, so it doesn’t need to do the actual work!
 Typechecking
 Typechecking
1 & (2 & (3 & 4))
forwards tointAnd({ 1 }, { intAnd({ 2 }, { intAnd({ 3 }, { 4 }) }) })
 To typecheck
intAnd({ 2 }, { intAnd({ 3 }, { 4 }) })
, we need to typecheck{ 2 }
and{ intAnd({ 3 }, { 4 }) }
 Typechecking
{ 1 }
can use the alreadycomputed type, so it doesn’t need to do the actual work!  Typechecking
{ intAnd({ 2 }, { intAnd({ 3 }, { 4 }) }) }
can use the alreadycomputed type, so it doesn’t need to do the actual work!
 Typechecking
 Typechecking
Let’s say the compiler was structured so typechecking and most other semantic analyses are in the “core,” but actual translations are implemented as extensions. (Or if that feels a bit farfetched, pretend this is an extension that adds a new translation.)
To collect all the target language declarations, we have a threaded pair of attributes. (This might be done instead of using a monoid attribute to allow for pure generation of fresh names.)
inherited attribute transDeclsIn::[Decl];
synthesized attributes transDecls::[Decl];
What would the aspect for decExpr
look like?
It can’t simply add additional attributes to the reference, so there’s not really a better solution than:
aspect production decExpr
top::Expr ::= child::Decorated Expr
{
production transDeclsChild::Expr = child;
transDeclsChild.typeEnv = top.typeEnv;
 equations for any other hostlanguage inherited attributes in transDecls' flowtype
transDeclsChild.transDeclsIn = top.transDeclsIn;
top.transDecls = transDeclsChild.transDecls;
}
However, this has the exponential redecoration problem again, for the transDecls
attribute!
What we want is some way to write:
aspect production decExpr
top::Expr ::= child::Decorated Expr
{
child.transDeclsIn = top.transDeclsIn;
top.transDecls = child.transDecls;
}
However, this isn’t possible, since we don’t know that child
doesn’t already have an equation for transDeclsIn
.
For example, another extension could add:
production fooExpr
top::Expr ::=
{
local expr::Expr = litIntExpr(5);
expr.transDeclsIn = [];
forwards to
if expr.someSynThatDependsOnTransDeclsIn
then decExpr(expr)
else errorExpr(...);
}
In this case, the child.transDeclsIn
equation in decExpr
can’t work, since the process of computing someSynThatDependsOnTransDeclsIn
might have put the []
somewhere that it might need to be removed.^{1}
Partial Decoration makes it sound to write child.transDeclsIn
, under some conditions.
It introduces a new variety of type, PartiallyDecorated ... with ...
.
PartiallyDecorated Expr
is a tree that was originally decorated with only the reference set of attributes, rather than at least the reference set of attributes.
If you were to instead write:
aspect production decExpr
top::Expr ::= child::PartiallyDecorated Expr
{
child.transDeclsIn = top.transDeclsIn;
top.transDecls = child.transDecls;
}
This will reuse any thunks that are already present on child
, like the original decExpr
did.
However, transDecls
now works!
Decorating a partiallydecorated tree with additional attributes works by mutating the original tree to add the additional attribute equations. This means that we must be sure that any time we take a partially decorated reference to a tree, we must be sure never to decorate the original tree with more attributes!
These requirements are enforced with several restrictions in the flow analysis. First, if we take a partially decorated reference to some child or local (termed a decoration site), it is a flow error to supply any inherited equations that are not in the reference set:
production barExpr
top::Expr ::= child::Expr
{
child.barInh = true;
top.errors < if child.barSyn then [] else [err(child.location, "Not bar")];
forwards to barFwd(child);
}
production barFwd
top::Expr ::= child::PartiallyDecorated Expr with {env}
{ ... }
In the above, a flow error is raised on the equation for barInh
in the barExpr
production; this is potentially a duplicate equation, as we are taking a partially decorated reference to child
with only env
in the forward for barExpr
. The barFwd
production could have an equation child.barInh = false;
, which would conflict with this one.
Similarly, it is also illegal to take multiple partially decorated references to the same decoration site:
production bazExpr
top::Expr ::= child::Expr
{
production child1::PartiallyDecorated Expr = child;
child1.barInh = true;
production child2::PartiallyDecorated Expr = child;
child2.barInh = true;
top.barSyn = child1.barSyn  child2.barSyn;
}
However there are some situations where a partially decorated reference may be supplied with the same attributes twice, that are not caught by the flow analysis. For example:
production quxExpr
top::Expr ::= child::Expr
{
forwards to doubleExpr(decExpr(e));
}
production doubleExpr
top::Expr ::= e::Expr
{
forwards to mulExpr(e, e);
}
Here the (poorly implemented, but currently 100% legal!) doubleExpr
decorates its child twice by forwarding to mulExpr
. If doubleExpr
is passed a decExpr
, any inherited equations written on decExpr
will cause the PartiallyDecorated Expr
will be decorated twice. This currently results in a runtime error.
In the future, some sort of substructural type system (e.g. linear types) or other use analysis may be implemented to prevent these situations, however it is possible that such an analysis will be overly restrictive (for example, we may need to effectively ban new
.)
Alternatively, we may choose to silently ignore when a tree is decorated with the same attribute more than once, and implement some randomized testing approach to verify that subsequent decorations provided the same attribute values. However it is always best to avoid decorating a tree multiple times for performance reasons, as outlined above.

One might have the idea that we could just make a copy of the tree, and remove any attribute values that somehow depend on the attributes being supplied. However actually storing the needed dependency information at run time would add quite a bit of overhead and complexity, and we would still like to share the portions of the tree that don’t depend on the removed attributes  this is more difficult to achieve than it may appear. ↩︎