Hygienic forwarding

[GoogleCodeExporter]

Provide an explanation of what the project should entail:

The essence of hygienic macros is passing around decorated trees, instead of 
undecorated ones.  Name binding happens in the environment provided lexically, 
instead of on the transformed tree.

We could claim to support hygiene in forwarding, but there are a couple of 
issues that make this a weakish claim:

1. We're far too happy to implicitly allow a child to be used as both a 
decorated and undecorated tree.  We should require that if a child is ever 
decorated at all, then you must use the 'new' operator to obtain the 
undecorated version.  Otherwise we are easily accused of having the wrong 
default.  (This might also have efficiency benefits as we current 
decorated-then-undecorate children that are only used undecorated, just in case 
they might be used decorated!)

2. We make it way too verbose to "use hygiene".  The idea is to produce an 
undecorated tree with decorated subtrees.  To do this we'd define something 
like:

abstract production wrapDecExpr
Expr ::= Decorated Expr

and instead of 'new' we'd use that production.  People have to look up the 
name, etc.  It might be nice to have a Hygienic type class and a prefix tick 
operator for
using the appropriate wrapper production.

3. There's an issue to consider with pattern matching and forwarding.  We'd 
*like* this wrapper production to be essentially invisible to pattern matching, 
but that would look like forwarding to a decorated tree!  Perhaps this requires 
baking into the language, then?

Provide a concrete example of a problem this project will fix:

production swap
Stmt ::= a::Expr  b::Expr
{
  -- error checking, e.g. ensure a&b are symbols
  forwards to seq(seq(seq(
    declare("temp", integer()),
    assign("temp", `a)),
    assign(`a, `b)),
    assign(`b, "temp"));
}

Works just fine even in the presence of a temp variable already in the code.  
Or swaping a variable named temp!

Provide a short guide on how to start this project:

Not even sure it's worth starting yet.  I just had the thought, wanted to write 
it up.

Provide a rough expectation of what the set of patches completing this
project might look like:



Probable challenges in completing this project:

Looks like we're missing:
1. type classes
2. decorated forwards (or building this feature in...)

to do it "right"

Additional Information:

Mostly this would just be one of those cool things to point at and say ``look 
how simple this is."

Original issue reported on code.google.com by [email protected] on 3 Jan 2013 at 2:20

[remexre]

Since we have typeclasses, is this now a good-first-issue? And/or should it wait until partial decoration is stable because we'd want the Hygenic/HasDecProd typeclass to use a UniqueDecorated reference instead of a PartiallyDecorated one?

[krame505]

The approach to "hygienic forwarding" that Ted proposed above needs to be considered carefully in relation to non-interference. By definition we are essentially constructing a tree where the attribute values in the forward tree don't match the equations in the forward tree, so we would need to consider for any host language what properties we care about preserving. In some languages, it might be okay for a child to be decorated with a value environment that is a subset of what it will actually receive through the forward, but this actually causes problem in ableC-templating for example, where we rely on generated names introduced via forwarding to avoid lifting duplicate template instantiations.

Note that in Ted's above example, he claims that this "Works just fine even in the presence of a temp variable already in the code.
Or swaping a variable named temp!" That is only true if the host language is translated in a way that assigns a unique identifier to every variable declaration. In the case of languages like ableC, this would result in erroneous C code being emitted. Thus the only degree of hygiene provided by this approach is in hiding generated names from the user, while we still must ensure generated names do not collide with user names.

Additionally, my goal with the UniqueDecorated work is to minimize the places where we must explicitly define attribute equations on the children of forwarding productions, by allowing children of a forwarding production to essentially receive their attributes through their place in the forward tree. That is incompatible with the above approach where we explicitly provide a different environment to the children in a forwarding production. (Also note that I am proposing to add features that are essentially equivalent to Ted's proposed "decorated forwards" and "wrap this decorated tree in an undecorated context" for the places where this actually is useful.)

For these reasons, I would say that hygiene is something that needs to be baked in to a host language, and not really just a feature of Silver. I would propose for languages like ableC, that we could add host-language productions for "hygienic declaration" and "hygienic reference" that would provide the desired semantics, essentially of appearing in a separate namespace, and ensuring that every one is translated to a unique name that does not collide with a user variable. This might also make use of origin tracking in some way to ensure that two extension productions that both introduce the hygienic name temp do not collide.

I don't know if we want to close this issue and open a new one, or keep this one around for discussion of topics related to hygiene and forwarding?

[ericvanwyk]

Something like this would be really nice. I think Lucas is right that the object language needs to define what hygiene means for it. But there may be some support we can add in Silver to facilitate this.