efficiency problems with forwarding

[krame505]

On Wed, Jul 13, 2016 at 5:15 PM, Lucas Kramer krame505@umn.edu wrote: One major problem with how we do forwarding at the moment is that it will cause trees to be decorated twice. A common pattern can yield an exponential blowup, in cases like this production foo top::Expr ::= e::Expr { forwards to if !null(e.errors) then errorExpr(e.errors) else add(e, const(1)); }

Accessing errors on the tree foo(foo(const(2)) would result in decorating const(2) 4 times, foo(foo(foo(const(2))) 8 times, etc. Something like this is happening with the closure extension (as well as a few others), thus the currently horrific compilation times for ableC, seemingly in line with an exponential increase based on nesting level.
This stems from our current method of forwarding being broken; in the original proposal of forwarding, the child asts are inserted into the forwards tree already decorated. But this is incompatible with how Silver does things, with its notions of decorated and undecorated trees.

I have been doing some thinking about how to circumvent this. What is basically needed is a way of including decorated children in new asts in a way where they appear undecorated, but when decorated are included directly. I can see a couple of ways of doing this simply; the issue is in ensuring non-interference.
The first (and simplest) way is to add an explicit wrapper production for a decorated tree to the host that would get the synthesized attributes off the decorated child. To ensure non-interference, we need to ensure that the values of all inherited attributes on the decorated child are effectively the same as the provided ones. This can't be done statically, but you could image that production performing checking and generating errors messages/warnings if any attribute values differ. For example:

abstract production decExpr top::Expr ::= e::Decorated Expr { top.pp = e.pp; top.defs = e.defs; ... top.errors := e.errors; top.errors <- if !envEqual(top.env, e.env) then [wrn("Interference!")] else []; ... }

This does however seem like something that should be automatically provided by Silver, and I could imagine it becoming tedious (you would have to aspect it for every new attribute on Expr, etc). Another (more difficult, but less hacky) option would be to implement something native to Silver, similar to new() although it would have the behavior I described above, of having its decoration be the provided decorated tree. Interference checking using this method would probably require typeclasses to be added (Eq), but it would be a much more seamless from a user perspective.

Finally, I don't want to rule out that maybe the way that Silver handles decorated, undecorated, and 'semi-decorated' (children in production bodies) trees is the best option - maybe a system in which decorated trees are implicitly converted to decorated ones, but when redecorated revert to the original tree would make sense. Or something else totally different.

Anyways, let me know what you think!
Lucas Kramer

On Wed, Jul 13, 2016 at 5:46 PM, Ted Kaminski tedinski@cs.umn.edu wrote: To start, we should probably open up a github issue about exponential forwarding, to keep the discussion somewhere accessible.

But, there's at least 3 ways to go to resolve the problem:

1. As you suggest an (Expr ::= Decorated Expr) production can be used. I suggested something similar in order to support something like what hygienic macros do. (https://github.com/melt-umn/silver/issues/27) And this is what Silver itself does (https://github.com/melt-umn/silver/blob/develop/grammars/silver/definition/core/Expr.sv#L1077) to solve this problem.

I'm not certain this necessarily has any interference issues, at least obvious ones. The hygienic example illustrates that we'd want a different environment in some use cases. However, I haven't thought about it.

This does have the drawback that the mwda doesn't let you introduce new inherited attributes across references, though.

1. Be clever in what you forward to. e.g. forward to "let x = child_tree in whatever_else" and use "var('x')" instead of child_tree inside whateverelse. Now, you can "case forward of let(, decorated_childtree, ) -> ..." and that child is being decorated exactly once--in the tree you forward to--and you're extracting what you want from there.
2. I seem to vaguely recall that there might have been an advantage to restricting where this can happen by only changing function application (Expr ::= Expr Decorated Expr) as the anchoring point for a reference instead of allowing it as any expression. However, I can't now recall what that might be, so perhaps I realized I was wrong...

And there's at least 2 ways to evade the problem:

1. Most attributes already are evaluated either 100% before forwarding (pp, typically) or 100% after forwarding (translation). Your example of checking errors is a bit contrived, since the same errors are in the sub-tree, no problem. But the example becomes good again if you're looking at a child's typerep, for example.
2. Change the host language. I'm not sure what's up with AbleC and closures that you mention, but this should be something that can be implemented without forwarding at all.

Ted

On Wed, Jul 13, 2016 at 8:47 PM, Eric Van Wyk evw@umn.edu wrote: Lucas,

This is indeed a performance issue. However, it is incorrect to say that "our current method of forwarding [is] broken". The semantics of this are correct, it was broken in Intentional Programming, where forwarding was originally proposed.

Since we now have a nice modular well-definedness analysis that computes the flow types for nonterminals, we should, with a significant effort, be able to implement something like the Ted's and your 'Expr::=Decorated Expr' production automatically.

For the sake of discussion, let's assume that 'errors' on 'Expr' depends on inh attr 'env' and nothing else. By analyzing the 'foo' and 'add' production an optimization can observe that the value of 'env' on top, the forwarded-to node, and the forwarded-to node's first child (first child of add) will have the same value. Thus, the value of 'errors' will be the same on both. We need then generate code that doesn't recompute 'errors' on the first child of this 'add' node but just copies it from the place where it may have already been computed.

Certainly there is plenty to flesh out here, but something like this would be the principled way to solve this problem.

It'd make a nice project for someone.

Cheers, Eric

P.S. Can you copy these emails into a new Silver issue? Thanks.

---

Melt mailing list Melt@cs.umn.edu https://wwws.cs.umn.edu/mm-cs/listinfo/melt

[krame505]

Ted- What I meant by interference was that abusing this mechanism (or simply making a mistake) could allow a tree to be 'glued in' with different inherited attributes than expected, potentially yielding an incorrect result. Simply put, forwarding to something in the host language could yield unexpected results with no warnings or errors.

Yes, the example I gave was slightly contrived. But this does come up, for example, in the rewriting extension, when checking for errors on a custom nonterminal with productions that involve expressions, then forwarding to a transform on that custom nonterminal. We want to still check for errors in both locations, since we are manually constructing the env.

I think this is actually the case for any extension that changes the env given to children. This is what is going on with closures, IIRC. But yes, as you mentioned, this is for sure an issue when checking the typerep of a child to get the local errors, then forwarding again to something involving that child. The second option you mention doesn't address this sort of thing.

[krame505]

Eric- You are right, it is not so much that forwarding is 'broken' as much as that our implementation fails to solve an important problem, of avoiding redecoration.

I am unsure about auto-generating this sort of production, at least in the near term. Generating the code that checks for equality for the provided attributes would probably require typeclasses. Otherwise we would need to live with the potential for strange behavior cropping up due to bugs caused by accidental interference that went undetected.

[ericvanwyk]

Lucas,

Just to be picky about your wording here, this is a missed optimization opportunity. If you want to call 'not taking advantage of an optimization opportunity' a 'problem', fine. Just as long as you understand that this is not an issue of semantics - forwarding doesn't do the wrong thing. It does the right thing, it just doesn't take advantage of some, perhaps important, optimizations.

Keep in mind that some attributes, like 'errors', will have the same value on 'top' and the first child of the forwards-to node. But some may be different. If 'add' sets an inherited attribute, say 'i', that is used to compute a syn attr, say 's', on its first child, then that value of 's' will be different than the value of 's' on the original node 'top'. So we must not reuse the entire 'Decorated Expr' under 'foo' as the child of 'add'.

Thus, we don't want to use production like this that would produce errors. Perhaps if users explicitly wrap 'e' under 'add' with some production like this, then generating errors would make sense. But this seems like a short term hack.

Much more interesting is to think of this as an optimization. What are the criteria that must be met to safely apply the optimization so that the behavior with it and without are the same? How is the optimization realized? Do we generate some production similar to your above but that has two children, an undecorated 'Expr' and a 'Decorated Expr' and then, based on some static analysis, can decide which one to pull attributes from?

The easy case is noticing that 'env' is autocopy and that 'add' doesn't have an explicit equation for it for its first child. So, use the value from the decorated child. In other cases, fall back to the safe option and use the computed value from the undecorated child.

Or maybe there are cases where the decision is made dynamically. But I'm leery of any runtime checks of equality for inherited attributes. Things get hairy quickly if the forwards to expressions is a simple pattern like in 'foo', but instead computes the tree into which we put 'e'.

Diving into this is something I've wanted to do for some time. Lots of interesting opportunities here.

In the short term, it might be reasonable to explicitly create this 2-child production for wrapping up 'e' under 'add' so that it reuses some attributes from the original decorated 'e' and some some not. Any extension to this grammar could then aspect this thing to and decide if its attributes are recomputed or not.

production foo
top::Expr ::= e::Expr
{
forwards to if !null(e.errors) then errorExpr(e.errors) else
add(decExpr_for_foo_for_first_child(e,e), const(1));
}

abstract production decExpr_for_foo_for_first_child
top::Expr ::= eu::Expr ed::Decorated Expr
{
top.pp = ed.pp;
top.defs = ed.defs;
top.errors := ed.errors;
}

this one written in the extension, not the same file as defining foo

aspect production decExpr_for_foo_for_first_child
top::Expr ::= eu::Expr ed::Decorated Expr
{
top.s = eu.s;
eu.i = top.i;
}

[krame505]

The time may have come to revisit this issue, as I have run headlong into some issues with exponential performance blow-up with involving the template extension while implementing my unification extension. For now I'll implement decExpr, decStmt and decDecl productions, each with a single Decorated child of the corresponding type, as described above. If this generally works we can look at some of Eric's suggested enhancements for this (such as special handling for extensions or auto-generating these productions) later on when I have more time.

[krame505]

I had a chat with Eric today about what this may look like in the future. The consensus for now was to stick with these explicit decorated wrapper productions and use them only were absolutely needed, but in the longer term to develop a way of performing the optimization automatically so that we can use it more widely.

Essentially the idea would amount to introducing new syntax to construct an undecorated tree from a decorated one using a "virtual wrapper production". For example, one may write something like

abstract production fooExpr
top::Expr ::= e::Expr
{
  local localErrors = ...;
  e.env = globalEnv(top.env);
  forwards to
    if !null(localErrors)
    then errorExpr(localErrors)
    else injectGlobalDeclsExpr(varDecl(..., e with {env}), ...);
}

The expression e with {env} would use a new "invisible" production to wrap the decorated form of e. When itself decorated, this production somehow would provide any additional inherited attributes to e that had not already provided, but without redecorating e "from scratch". Thus any attributes within e that had already been evaluated would not need to be computed a second time. This new production would also need to be invisible to reflection, pattern matching, etc. appearing just as the ordinary undecorated version of the tree.

Ensuring semantic correctness here would impose some challenges. When running the flow analysis we could check that the tree given to this decorated wrapper expression has actually been provided with all the attributes listed. But the harder part is ensuring that the wrapped tree has the same values of inherited attributes that it would have been given if it was re-decorated normally. Doing this constantly at runtime would probably be too expensive, but these asserts could be enabled as some sort of a debug mode or done as part of randomized property testing.

Note that we also probably don't want to enforce a strict equality in all cases; for example with env, we wouldn't care if the final environment contains extra items as long as all elements in the env given for the initial decoration are present identically. For this reason we would want some method of specifying an equality/equivalence test function to use, either as a part of this new expression or as a part of the attribute declaration.

[remexre]

Should this be closed now that partial decoration is merged? Or, should this be tied to some tracking issue or something like that?

[krame505]

I think this should stay open for now, but I will at some point open a new tracking issue for the further work of introducing the alternate patterns for forwarding that I proposed last week as a more general solution.