Refactor/expand binaryOpExpr and unaryOpExpr about ablec HOT 42 CLOSED

In general, I think we have the "op" approach for two reasons: 1. Clang did it. 2. Clang did it because there's a fair amount of shared code between each of the operators, and we don't want to copy & paste it all the time.

I know that Silver's style strongly encourages the addExpr approach, and things like the MWDA give us disadvantages for the addOp approach (references getting passed around). So I'm generally favorable to the idea of switching. But I also think we might want to seriously prioritize some kind of "traits" notion for Silver, to help deal with duplicated code, if we do go this route. It'd be nice if we could write down an "operator trait" and use that to share common implementation between all the operator expressions.

This would be a serious design problem to solve though, but it could probably be done afterwards. Duplicate code today, clean it up tomorrow.

from ablec.

I think some duplication of code is acceptable if overall it simplifies the code. Thus I support going with addExpr over the binaryOpExpr and addOp combo.

Much of the duplicated code is equations that collect errors or defs. Some form of monoid attributes would let us write propagate host, lifted, errors, defs perhaps.

from ablec.

I'm not fundamentally opposed to this change, but I have a couple concerns other than the obvious additional ones of (1) it would be a lot of work and (2) it would break everything.

One is that while duplicating host code is one thing, forcing extensions to write more code is another. Something to keep in mind is that we generally want to make it less painful for extensions to write transformations/analyses across the host language, and having allowing an extension to treat all binary operators the same is probably a plus. True, this could become less painful with proper monoid attributes, but explicitly needing to aspect more productions probably isn't a good thing. Actually this may just be an argument for doing monoid/functor attributes differently...

We would also lose the nice hierarchy of operators that we have right now, which allows us to handle categories of operators in a common way. I guess this is just another code duplication concern, though.

This would also require operator overloading to be refactored accordingly, but it would probably would actually make things cleaner (and easier in the future to modify if we were to implement my closed ExtType idea...)

So. yeah, I guess I am OK with this if someone is willing to fix pretty much every single extension being broken by this change. Also, Ted's idea of traits sounds interesting- could you expand on this?

from ablec.

OK, I'll work on this and include it in a pull request from the type qualifiers branch. I'll also update extensions that it breaks.

If we decide that the hierarchy of operators of useful, is there any reason we couldn't recreate it on Expr such as binExpr(numExpr(addExpr(lhs, rhs))) or binExpr(assignExpr(eqExpr(lhs, rhs)))?

from ablec.

from ablec.

I agree with Lucas that it is may not be worth the effort to have binExpr and numExpr.

@TravisCarlson can you make the changes you're thinking about for add by tomorrow afternoon? We could then spend some time discussing this at 1 or 2pm.

from ablec.

@ericvanwyk Sure, I'm free to meet until a little before 2:30pm again. The changes for add are already there. I suppose I'll wait to make similar changes to the other operators until after the discussion.

from ablec.

I took a quick look at this branch, addExpr and subtractExpr look reasonable. One small request - can we use the same base names for these productions as we currently have for operators (e.g. subExpr instead of subtractExpr?) It would make refactoring things quite a bit easier (and I kinda like having short names when doing lots of repetitive stuff), that's all.

One other side-note, I don't quite understand the purpose of having collectedTypeQualifiers as a synthesized attribute on Expr - This value isn't passed around the tree, only used internally by forwarding productions, and suggests that we can collect qualifiers on any production, even ones where this isn't doesn't make sense, such as qualifiedAddExpr. It would seem less confusing to have this as a collection production attribute on the productions where collecting qualifiers is actually valid.

from ablec.

Is there a reason we use addExpr and not add? Have we adopted some form of Hungarian notation for names? Do all/most production names end with the nonterminal type they construct? My preference would be to avoid this.

from ablec.

The reason I used subtractExpr is that there is a subExpr function in subtitution/Util.sv. Using add/sub sounds good to me.

Beyond this binaryOpExpr issue, there are more decisions about the organization of expressions / operators / overloading on the type qualifiers branch that need to be cleaned up, and your comment on collectedTypeQualifiers is probably one of them. Collection productions attributes runtimeChecks, lhs/rhsRuntimeChecks, lhs/rhsRuntimeInsertions, and lhs/rhsRuntimeConversions have been added only where needed for the examples in the paper. Productions in Expr.sv that use these now forward to a new production, e.g. dereferenceExpr now forwards to dereferenceHostExpr. This should probably all be done more consistently, but before spreading this further, comments are welcome.

from ablec.

Is there a reason we use addExpr and not add? Have we adopted some form of Hungarian notation for names? Do all/most production names end with the nonterminal type they construct? My preference would be to avoid this.

We really can't. It's much nicer to work with things named in a consistent way, and we really do have name collisions all the time otherwise.

Fixing this is my melt-umn/silver#31 issue with contextual name resolution. Without enhancements to the language, it's pretty necessary.

from ablec.

I am fine with renaming subExpr and similar functions to substExpr, etc. to fix that particular conflict. We should also have consistent naming for the for the forwarding and host productions. I like *Expr and *HostExpr, which appears to sometimes be used already.

I also just took a look at overloading in the type qualifiers branch. There are a few issues here, we shouldn't be collecting type qualifiers here, and for sure shouldn't be applying runtime conversions. Remember, overloading is just a tool for making host syntax mean something totally different, so any special handling of qualifiers should happen in the host production (which in turn will forward to the non-forwarding qualified production.)

Also, there is no need to decorate baseExpr in these overloading productions - you should just be able to forward directly to the new tree. In fact the existing overloading productions probably were fine as-is, we should just be adding new ones.

from ablec.

I just realized that there is an issue for how overloading works if we 'flatten out' binary operators as discussed. One way in which we were taking advantage of this operator 'hierarchy' is that we can know that an AssignOp represents some form of assignment operation, and when overloading complex constructs involving assignment, we use AssignOp in the overload production signatures (e.g. see getMemberAssignOverload in OpOverload.sv).

One way around this would be to replace places where we use AssignOp with functions of type (Expr ::= Expr Expr Location). This shouldn't be too bad to change, but could be hard to get right. There is also some code related to default overload generation for assignOp that would need to be de-generalized into the new individual assignment expression productions.

The best plan is probably to have Travis go ahead and change the core abstract syntax to add the new productions, and I can update overloading.

from ablec.

A few more random things, before I forget:

• Let's put all the unary expression productions in ExprUnaryOps.sv and all the binary ones in ExprBinaryOps.sv, to avoid filling up Expr.sv with lots of repetitive code.
• To be consistent, unaryExprOrTypeTraitExpr should probably also get refactored in the same way, with UnaryTypeOps replaced by Expr productions parameterized by ExprOrTypeName.
• I would prefer to name the productions that replace assignOp as assignExpr, mulAssignExpr, divAssignExpr, etc. instead of eqExpr, mulEqExpr, divEqExpr, since eqExpr sounds too much like the == operator. Any objections?

from ablec.

Hi Lucas,

Good points. We'll look closely at these. We do however want to collect type qualifiers on overloading productions - this allows one to do, for example, dimension analysis type qualifier checking on addition regardless of the type of the values being added. Putting runtime conversions there - that is maybe something to avoid. We'll consider that too.

Thanks,
Eric

from ablec.

The issue is that the + operator, for example, is used for more than just addition, it is also used for totally different things like vector append (or even rewriting strategy composition), where it very clearly doesn't make sense to have the same types of qualifiers. I do see how this could work if we were to check for the presence of the qualifier on both operands before adding it to the result, but I'm not sure that is what this extension does currently.

Anyway, if we do want to support collecting qualifiers on overloaded operators, the way this is being done currently in the branch is interfering - we should instead forward to something else that adds the qualifiers to the result. It occurred to me today that instead of having lots of Expr productions that have Qualifiers in the signature (e.g. qualifiedAddExpr), we could have one production

abstract production qualifiedExpr
top::Expr ::= q::Qualifiers e::Expr
{
  propagate lifted;
  top.host = e;
  top.typerep = addQualifiers(q.qualifiers, e.typerep);
  -- and everything else is the same as on e
  top.errors := e.errors;
}

that handles this in general. qualifiedAddExpr could then be replaced by addHostExpr that does not take collectedTypeQualifiers as a parameter, and addExpr could then just forward to qualifiedExpr(foldQualifer(...), addExpr(lhs, rhs, location=...), location=...) instead. This qualifiedExpr production could also be used by the overloading productions to resolve this interference issue.
Thoughts?

from ablec.

Why doesn't it make sense to require that a vector qualified with units(m) be appended to a vector also qualified as units(m), and that the result should be similarly qualified? Checking the presence of the same units qualifier on both operators before adding it to the result is exactly what the extension does. Unit conversions also make sense when appending a units(mm) vector with a units(m) vector if multiplication is overloaded in append(lhs, 1000*rhs) (though it's not).

Well, I've pushed a changed based on a discussion earlier today, before these latest suggestions gave us a lot more to think about.

from ablec.

The issue here is what does it really mean for a vector to have units? We would really want to have the units qualifier on the parameter type, not on the extension type itself. For example, in the case of a parametric interval type, you would have interval<units(m) float> and not units(m) interval<float>. When, for example, adding two of the former, you would end up generating code that performs host numeric operations on the type units(m) float, and the relevant qualifier inference would happen there instead.

It is important to remember that operator overloading is just a way of reusing syntax, there is really no underlying semantics of these operators that satisfies the standard mathematical identities assumed when inferring qualifiers. Trying to give, for example, the * operator a more general meaning fundamentally isn't sound. I could decide for some reason to overload this operator for a vector type to make x * y mean x.append(y). Then if a has type vector<units(m) float>, and b has type units(m) float, the expression a * b * b would end up with the type units(mm) vector<units(m) float>, if I am understanding correctly. This is obviously wrong, and comes from assuming that this syntax is tied to certain semantics, which just aren't there in this case.

I am somewhat concerned that we are trying to do too much at once in this branch, of simultaneously redoing the abstract syntax for expressions, and also adding a bunch of qualifier inference extension points. I would prefer that we split this into two steps, first refactoring ableC as it exists in the develop branch to 'flatten' the operator abstract syntax, and then look at where adding these extension points make sense. Thoughts?

from ablec.

OK, the feature/type_qualifiers branch has a few new changes that we'd like to get some feedback on before refactoring the rest of the binary op exprs in this way. I agree that the issues Lucas raised about collecting qualifiers / injecting code on overloaded operators is valid. Can we track that as a separate issue and move forward here?

The current branch has three levels of addExpr: an overloading addExpr which can also collect qualifiers and inject code, an "injectable" (suggestions for a better name are welcome) addExpr that collects qualifiers and injects code only on non-overloaded operators, and the final "host" / "standard C" addExpr. A new qualifierExpr has also been created to add the collected qualifiers.

abstractsyntax/overload/Expr.sv (move this to ExprBinOps.sv per Lucas' suggestion?)

abstract production addExpr
top::Expr ::= lhs::Expr  rhs::Expr
{
  top.pp = parens( ppConcat([lhs.pp, space(), text("+"), space(), rhs.pp]) );
  top.errors := [];

  production attribute runtimeMods::[LhsOrRhsRuntimeMod] with ++;
  runtimeMods := [];
  local modLhsRhs :: Pair<Expr Expr> = applyLhsRhsMods(runtimeMods, lhs, rhs);

  production attribute collectedTypeQualifiers :: [Qualifier] with ++;
  collectedTypeQualifiers := [];

  forwards to
    if null(top.errors)
    then qualifiedExpr(foldQualifier(collectedTypeQualifiers),
           case getAddOverload(lhs.typerep, rhs.typerep, top.env) of
             just(prod) -> prod(modLhsRhs.fst, modLhsRhs.snd, top.location)
           | nothing()  -> inj:addExpr(modLhsRhs.fst, modLhsRhs.snd, location=top.location)
           end,
           location=top.location)
    else errorExpr(top.errors, location=top.location);
}

abstractsyntax/injectable/Expr.sv

imports edu:umn:cs:melt:ableC:abstractsyntax with addExpr as addExprDefault,

abstract production addExpr
top::Expr ::= lhs::Expr rhs::Expr
{
  top.pp = parens( ppConcat([lhs.pp, space(), text("+"), space(), rhs.pp]) );
  top.errors := [];

  production attribute runtimeMods::[LhsOrRhsRuntimeMod] with ++;
  runtimeMods := [];
  local modLhsRhs :: Pair<Expr Expr> = applyLhsRhsMods(runtimeMods, lhs, rhs);

  production attribute collectedTypeQualifiers :: [Qualifier] with ++;
  collectedTypeQualifiers := [];

  forwards to
    if null(top.errors)
    then qualifiedExpr(foldQualifier(collectedTypeQualifiers),
           addExprDefault(modLhsRhs.fst, modLhsRhs.snd, location=top.location),
           location=top.location)
    else errorExpr(top.errors, location=top.location);
}

abstractsyntax/Expr.sv

abstract production addExpr
top::Expr ::= lhs::Expr rhs::Expr
{
  propagate host, lifted;
  top.pp = parens( ppConcat([lhs.pp, space(), text("+"), space(), rhs.pp]) );
  top.errors := lhs.errors ++ rhs.errors;
  top.globalDecls := lhs.globalDecls ++ rhs.globalDecls;
  top.defs := lhs.defs ++ rhs.defs;
  top.freeVariables =
    lhs.freeVariables ++
    removeDefsFromNames(lhs.defs, rhs.freeVariables);
  top.typerep = usualAdditiveConversionsOnTypes(lhs.typerep, rhs.typerep);
  rhs.env = addEnv(lhs.defs, lhs.env);
  top.isLValue = false;
}

from ablec.

@TravisCarlson - yes do start another issue on "semantic type qualifiers". The concerns about numeric-like qualifiers on containers need some thought. Right now we have syntactic qualifier, with some inherent problems so let's get these sorted out. Then we'll tackle the semantic issues.

Travis and I have been talking about how to organize all of this. We have a overload grammar for all 'dispatching' productions for overloadable constructs. So where to put the other 2 addExpr productions? I suggested another grammar - called injectable (I suggested this name but don't like - please offer better suggestions) - that contains these productions (that those in overload may forward to) that provide a place for aspect production to add type qualifiers or insert code. These forward to constructs in the new host grammar. @TravisCarlson - did we not decide on a host grammar`` as well?

Part of the thinking on the host grammar is that this contains the productions that need to eventually be forwarded to that, in terms of non-interference, are "in the host language". So things like injectGlobalDeclsExpr and the new qualifiedExpr live there. Also here are things like whileStmt that are not (currently) overloadable or injectable.

@TravisCarlson, If we do keep injectable then you might rename collectedTypeQualifiers to injectedTypeQualifiers and runTimeMods to injectedCode. But it would be nice to have a better term than inject for this.

Also, should errors not at least include the errors of the children for all of these?

from ablec.

I do like the idea of putting all these sets of productions in different grammars - that makes this much less ugly for extension developers to worry about. Presumably ...:ableC:abstractsyntax:host would be exported by ...:ableC:abstractsyntax?
I suggest the name qualification for the new grammar.

A few questions/comments:

• Why are you overriding errors in the forwarding addExpr productions?
• I'm still not convinced that injecting qualifiers on the overloading productions is really even needed, as I discussed before. All the examples with the units qualifiers right now are working with numeric types, and for extension numeric types, the inference should presumably happen on the forward, anyway. Is there any reason why we couldn't postpone this to a different pull request once this has been better explored?
• For addExpr in injectable, we probably don't want to wrap every single production in qualifiedExpr regardless of whether there are qualifiers being injected.
• addExpr in host looks good.
• qualifiedExpr looks good, although the pp for this should include q in some way - remember that this production is removed in the host AST. Also this belongs in the injectable (or whatever we call it) grammar, right?

from ablec.

I saw your latest commit, I don't understand why you are overriding errors at all on these forwarding productions - we want to include the errors from the forward translation, and this is interfering anyway.

from ablec.

The errors are there, for example, to specify on error on an aspect of dereferenceExpr if not qualified as nonnull, or on an aspect of addExpr if adding values qualified with incompatible dimensional units.

from ablec.

Yes, we just need a local attribute for errors on these forwarding productions so that errors can be injected here, but not override those on the forwards-to tree.

I believe that units on intervals needs to happen on the overloading production as the overloaded interval add production is not known to the units extension. Granted this is still syntactic, but that is a separate issue.

Yes, we could check the collectedTQs attribute and if it is empty then don't forward to qualifiedExpr

qualifiedExpr seems like it should be in the host grammar. It is part of the "host" language in terms of non-interference. Or are you thinking that since it is tied to the "injectable" that it should be in injectable?

from ablec.

Correct - collected errors should be a local production attribute, similar to collectedTypeQualifers or whatever.

My thought is that the interval type should really be parameterized with what type it is an interval of - for example, an interval of int or float or units(m) double. Operations on types external to an extension should forward to qualification:addExpr() (BTW, what do you think of that grammar name?), and so the qualifier inference would happen there.
In my understanding having the units be part of a type parameter actually makes more sense anyway then attaching the qualifier to the interval type, since we want to say 'an interval of (meters that are represented as doubles)' and not 'meters that are represented as (an interval of doubles)'.

Yeah, qualifiedExpr should be in host - forgot that it was non-forwarding for a second.

from ablec.

Another thing about collecting errors - you probably want to use warnExpr instead of errorExpr for forwarding, since there is still a perfectly valid forward to use even when errors are found, and not to mention extensions may very well want to inject warnings instead of errors.

from ablec.

The issue with interval is not if it is parameterized or not. It is just a new type that is in some sense numeric. Thus we, in this "syntactic" model, want to check some qualifiers - in this case units - on the overloading/dispatcing production.

Yes, @krame505 I agree warnError would be better.

from ablec.

Yes, we just need a local attribute for errors on these forwarding productions so that errors can be injected here, but not override those on the forwards-to tree.

Is there still a reason to contribute errors from the children into these local errors?

from ablec.

Sure - I don't think it matters.

from ablec.

@TravisCarlson No, that list would start out empty.

@ericvanwyk Right, but my point is that calling interval numeric is a bit of a stretch, although it does mostly act like such a type.

How about slightly less controversial example: integer, an arbitrary-precision int like in Haskell. We would have the same problem in this case as in the case of interval. It seems like operations on this type would want to use the same abstract syntax as for operations on host numeric operations, but we just need to perform a translation along with the host transformation. I propose adding a new production to the host:

abstract production hostExpr
top::Expr ::= directHost::Expr transHost::Expr
{
  propagate lifted;
  top.host = transHost;

  -- Error check directHost first and then transHost
  top.errors := if !null(directHost.errors) then directHost.errors else transHost.errors;

  -- Type checking comes from directHost
  top.typerep = directHost.typerep;
  top.isLValue = directHost.isLValue;

  -- Stuff not related to type checking comes from transHost
  top.defs := transHost.defs;
  top.globalDecls := transHost.globalDecls;
  top.freeVariables := transHost.freeVariables;
}

Then, for example, + on integer could be overloaded to hostExpr(qualification:addExpr(lhs, rhs), <whatever the translation for + is>). All the type checking then would happen the same as if it was an actual host int, including qualifier inference.
There would be interference issues for now with making integer act like a host numeric type (override equation for isIntegerType on Type, etc...), but this could be fixed eventually via #66.

from ablec.

@krame505 Yes, calling interval numeric is purely syntactic as you've called it. But this (important) issue is left for later.

This is an interesting proposal, but I think we delay what you've called "semantic" issues until later. We don't have the time (or for me the mental space) right now.

from ablec.

Note that this proposal would completely avoid needing to do things at the level of overloading.

My point is that I think we are adding an extension point to ableC that we don't actually need. AFAIK we don't have any examples depending on this right now (right?), so waiting to add this shouldn't break anything. If what I proposed or something similar doesn't work out, we can add this extension point in another PR.
On the other hand, I have been giving thought recently to some somewhat-significant changes/enhancements to how overloading works, and adding something such as this would make doing so more challenging.

from ablec.

Since adding these new production attributes, I realize I don't see how to use our new flowtype construct to seed the flow types on them. For example, the nonnull extension fails the MWDA with the error below. Do we have a way to seed these or do I need to create some kind of dummy expression in the host?

NonnullQualifier.sv:56:2: warning: Local contribution (runtimeMods <-) equation exceeds flow dependencies with: edu:umn:cs:melt:ableC:abstractsyntax:env:env, edu:umn:cs:melt:ableC:abstractsyntax:returnType

from ablec.

I don't think we have this type of flowspec implemented, you may need to use a dummy equation. Ask @tedinski if this would be easy to implement?

from ablec.

Doing it right might be annoyingly hard.

Doing it almost right should be easy. Almost right means we add the dependencies from a flowtype declaration inside a production, and then check to make sure that the equation doesn't exceed them as part of the mwda.

This is only almost right because it doesn't set the flowtype, it just checks to make sure the inference doesn't exceed what was declared. This means we don't get as good of an ability to raise errors. (We'd raise an error message on the flowtype declaration, not on the equation that causes it to be exceeded. This should only annoy host language developers, which may have a := and multiple <- and not know which caused the problem. Extensions will still see the fixed host languge's deps and raise errors on the equation.)

Thoughts on whether this approach would be okay?

from ablec.

I'm not sure I understand - the main reason we would want this is so that we could write a := []; initialization for a host collection attribute, but be able to set the flowtype that would be seen in aspects to be something non-empty. I don't see how the 'almost right' idea would gain us anything except checking that the host developer didn't mess up?

from ablec.

It adds those declared dependencies to what gets inferred, so it does that, too.

from ablec.

Ah, makes sense. I guess I don't really have any objections other than that it seems we are starting to add lots of hacky workarounds to implement new features (e.g. the shortcut we took to allow decorate to be used in flowtypes.) Do it that way I guess and leave a TODO or issue to come back and fix it the 'right' way?

from ablec.

Just out of curiosity though, what makes doing it the 'right' way so much harder?

from ablec.

It's a new type of information to add to the flow environment, that then needs to be checked for in a lot of places and adapted to accordingly.

from ablec.

After thinking about this proposed Silver enhancement a bit more, the 'hacky' way might actually be a little worse than at first thought. Having the error show up on the flowtype would be at odds with a not-unusual pattern where we have lots of aspects for a production attribute in the same or exported grammar, and would be very annoying to track down.
The hacky way would be better than nothing, if that is our choice, however.
@tedinski did you open a Silver issue for this? I don't want to keep discussing this on an ableC issue.

from ablec.

I haven't.

from ablec.