Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

definition of shadowing is inconsistent between variables and functions #19167

Closed
mppf opened this issue Feb 3, 2022 · 38 comments
Closed

definition of shadowing is inconsistent between variables and functions #19167

mppf opened this issue Feb 3, 2022 · 38 comments

Comments

@mppf
Copy link
Member

mppf commented Feb 3, 2022

I have been looking at this code in function resolution as part of porting it over to the new resolver. I have been scratching my head a bit. I am pretty sure that the current behavior is not reasonable. But, that might be a bug in function resolution or maybe it is a sign that we need to adjust the language design.

One thing to note about the current implementation is that it's pretty complicated and it does a traversal of all scopes visible from the call (including use/import), twice, in order to decide if one candidate is more specific than another candidate. I am worried that this contributes to performance problems. It would be much less worrisome if the consideration only needed to go up through the parent scopes (not counting use/import).

However a larger issue is that the behavior seems unnecessarily inconsistent between variables and functions. More details about that are in the next section.

Program to Explore the Current Behavior

Here is a program to explore the current behavior.

To summarize the current situation:

  • with UseA_UseUseB in the program below:

    • variables are resolved according to an idea of distance in terms of use/import statements - e.g. A.x is available with fewer hops through use statements than B.x, so A.x is shadowing B.x
    • for function disambiguation, the fact that A.f is available through fewer hops does not seem to matter, and it is ambiguous
  • with CUseA_ImportA

    • for variables, import A does not impact what could be defining x, so it has no effect on what x could refer to
    • for function disambiguation, import A is considered the same as use A and so is considered creating a path to A.f at the same number of hops as the path to C.f.
    • I am pretty sure that private uses, uses with renaming, or use only with an unrelated name will have the same problem for functions as the import here
module A {
  proc f() { writeln("A.f"); }
  var x = "A";
}
module B {
  proc f() { writeln("B.f"); }
  var x = "B";
}

module CUseA {
  public use A;
  proc f() { writeln("C.f"); }
  var x = "C";
}

module UseA_UseB {
  public use A;
  public use B;
}

module UseB {
  public use B;
}

module UseA_UseUseB {
  public use A;
  public use UseB;
}

module CUseA_UseA {
  public use CUseA;
  public use A;
}

module CUseA_ImportA {
  public use CUseA;
  import A;
}

module Program {
//use UseA_UseB;     // -> ambiguity between A.f and B.f
                     // -> x is multiply defined

//use UseA_UseUseB;  // -> ambiguity between A.f and B.f
                     // -> x refers to A.x

//use CUseA;         // -> f refers to C.f
                     // -> x refers to C.x

//use CUseA_UseA;    // -> ambiguity between A.f and C.f
                     // -> x is multiply defined
  
//use CUseA_ImportA; // -> ambiguity between A.f and C.f
                     // -> x refers to C.x
  proc main() {
    f();
    writeln(x);
  }
}

History and Related Issues

What does the spec say on the matter?

https://chapel-lang.org/docs/language/spec/procedures.html#determining-more-specific-functions

For functions X and Y, we have this rule about which is more specific (which is considered after things like formal argument types):

  • If X shadows Y, then X is more specific.
  • If Y shadows X, then Y is more specific.

However this section does not define shadows in any way.

https://chapel-lang.org/docs/language/spec/modules.html#conflicts

Describes shadowing in terms of a distance idea:

Because symbols brought into scope by a use or import statement are placed at a scope enclosing where the statement appears, such symbols will be shadowed by other symbols with the same name defined in the scope with the statement. The symbols that are shadowed will only be accessible via Qualified Naming of Module Symbols.

Symbols defined by public use or import statements can impact the scope they are inserted into in different ways (see Public and Private Use Statements and Re-exporting for more information on the public keyword). Symbols that are brought in by a public use for unqualified access are treated as at successive distances relative to how many public use statements were necessary to obtain them. For instance,

...

Symbols brought in directly by a public import are treated as though defined at the scope with the public import for the purpose of determining conflicts (see Re-exporting). This means that if the public use in module B of the previous example was instead replaced with a public import A.x, A’s x would conflict with C.x when resolving the main function’s body.

What should we do about it?

I think that at the very least, the language should have one definition of shadowing that is used for both resolving variables and for resolving functions.

Here are some ideas:

A. Consider the behavior with variables today to be correct and formalize it by describing a distance in number of hops. A symbol shadows another symbol if, in a given scope, it has a smaller distance. Have the new compiler code literally compute this distance and compare distances.

  • the module brought in by use and any symbol brought in by import adds 1 to the number of hops
  • the contents of a module brought in by a use adds 2 to the number of hops
  • an enclosing scope (e.g. going outside of { }) adds 3 to the number of hops

B. Simplify the rules about number of hops:

  • If a symbol is defined at an inner scope, or if it is defined in a module but that module use / imports something defining that symbol, then we have shadowing within that module. This can continue to consider 3 scopes: things defined directly in the module; modules used; and contents of modules brought in by use. This is the situation within CUseA in the example program.
  • However, something use / importing that module views the symbols defined in it as completely flat. So if you wanted use CUseA to find C.x and C.f (and not find them ambiguous with A.x and A.f) you would have to adjust CUseA to not publicly export A.x and A.f.
  • This design is simpler to implement (because the isMoreVisible operation can reuse other scope resolution ideas) and it's probably easier for users to predict what will happen with their programs.

C. Do not consider use / import to create additional scopes.

C'. Do not consider public use or public import to create additional scopes, but private use/import can do so

  • Note that public import is already documented as not creating an additional scope.
@lydia-duncan
Copy link
Member

  • or function disambiguation, import A is considered the same as use A and so is considered creating a path to A.f at the same number of hops as the path to C.f.

That shouldn't be true. import A should mean A.f can only be referred to in a qualified way. Anything else is a bug and should be fixed.

But that's a side issue. At a high level, the reason variable and function resolution is different is because functions don't necessarily conflict with each other unless they can be called in the same manner. This means that you can write a function at one scope that takes one set of arguments and a function at a different scope with a different set of arguments, and be able to call both of them from a third scope, no matter their relative distances - where your UseA_UseUseB is a problem with the same set of arguments (or in this case lack of arguments), adjust one of them to take an int and the conflict goes away. I think that's valuable behavior to preserve, but I agree that it's frustrating in the case where two functions have the same set of arguments and one could be considered to shadow the other. I think it would be reasonable to adjust function resolution to consider it shadowing in that situation, and doing so would be more consistent for users. But I want us to be careful not to discard overloads simply because we're only considering the function name when determining if shadowing can occur.

@mppf
Copy link
Member Author

mppf commented Feb 3, 2022

But I want us to be careful not to discard overloads simply because we're only considering the function name when determining if shadowing can occur.

We're talking about disambiguation, not finding candidates, so we're not discarding any overloads; just choosing among them. But anyway I'm not proposing here that we change where scoping/shadowing matters in function disambiguation -- only what the definition of shadowing is. (It is true one could argue that the definition of shadowing should ignore the argument types, but I'm not arguing for that).

@lydia-duncan
Copy link
Member

Okay, cool. As long as that's clear in whatever documentation we adjust as a result, I'm okay with A or B, then.

@bradcray
Copy link
Member

bradcray commented Feb 4, 2022

In:

  import A;

should this be a public import? (otherwise it won't affect anything outside of this module I think?). Should it be a public import A.{f, x}'? Or is the main goal of that example to show that imports, by nature, don't inject symbols?

@skaller
Copy link

skaller commented Feb 4, 2022

So here is what I do in Felix. My solution is not completely good. First principle is that "most specialised" has a single coherent definition. There are no complex rules. The algorithm determines if a polymorphic type A is a subtype of a polymorphic type P, and, the reverse. The algorithm is a stock-standard unification algorithm supporting subtyping in which the two sides of the inequality being tested are kept separated. We are seeking a set of equation which fix the values of all the type variables in P, in terms of type variables in A, such that P, after substitution, is a supertype of A.

This is all you need for overload resolution unless you also have additional constraints. Given a set of candidates, we try to find the most specialised. If we find one, we're done. If we find TWO we have an ambiguity, report an error and terminate.

Note: there are no "hops" or other rubbish. There are no conversions or other crap to think about. The algorithm asks only if a type is a subtype of another. If you have incoherent implicit conversions in your language, you have to fix them. The algorithm doesn't care about implicit conversions, but it needs to know subtyping rules, and subtyping is transitive (full stop, no arguments). C++ screws this up. It only allows one implicit conversion when overloading.

Note: the algorithm is fixed at being correct. Now fix the design faults in your language so it works. In this case
get rid of implicit conversions that are not subtyping relations. The algorithm consider both polymorphic subsumption and ordinary subtyping.

==========

Now there is one more case: there is no most specialised function. In this case, we search the parent scope for candidates and try again. Note that there can be two candidates that match, and we discard them both and proceed to look for a solution in the parent scope.

This algorithm is deliberately chosen because the C++ algorithm is really bad: in C++, you just give up. Here is an example I resolve which C++ would not:

fun f[T](x:T, y:T)=>...
{
  fun f[T] (x: int, y:T) => ...
  fun f[T] (x:T, y:int) => ...
  .. f(1,1) ... // picks the outer f
}

Here all the f's match the call. However neither of the inner f's is more specialised than the other. So we drop them both and chose the outer one. The equivalent C++ always halts when it find a symbol in a scope, and if resolution fails there that's the end. This is really bad. In C++ use declarations had to be introduced to fix this, especially in class scopes with inheritance.

In Felix, the name of a function is NOT just the identifier used, the type of the domain is part of the function name.

============

So now for the second issue. When you import modules into another exclusively for the implementation of that module and not for re-exportation, you need to be able to resolve conflicts, but only inside that module. In Felix open is used for that. In Chapel you WILL be implementing it for interfaces (because where clauses on every function is way too much boring work!)

What I do is open a shadow scope to put these things in. So for every scope, there is a shadow scope hiding behind it. If you cannot find a symbol in a scope, you look in the shadow scope first, before looking the in parent scope.

Now the important thing is this: if you have a problem in your shadow scope due to duplicate symbols or ambiguity, now you can resolve it easily with shadowing definition in the main scope. You can do this because, the main scope is searched before the shadow scope.

Note the client of the module never has an issue because the shadow scope is private to the module. No symbols in the shadow scope are ever exported. In Felix, I have another directive for that.

In the new C++ module system, you have import which is private to the module, and export import which also exports it to the current modules client. Thus you can chose if the operation is transitive or not.

Exporting modules is harder because you cannot easily resolve the conflicts. In Felix I use inherit to put a module into another for re-export. However this only works if the module is opened. In that case if there is a conflict, you can resort to explicit qualification which never refers to anything other than a symbol actually defined in the specified module. So explicit qualification is universally able to disambiguate all non function symbols (and if you throw in a domain type you can pick a particular function exactly too). In fact my system has a problem, I cannot construct a module from other modules so that say, a function defined in one appears to be defined in another, because explicit qualification will never find it. To do that I have to define a wrapper function. I'm not happy about that.

@mppf
Copy link
Member Author

mppf commented Feb 4, 2022

@bradcray

In:

  import A;

should this be a public import? (otherwise it won't affect anything outside of this module I think?). Should it be a public import A.{f, x}'? Or is the main goal of that example to show that imports, by nature, don't inject symbols?

It does not matter for the example - the behavior is the same (and x vs f differ). The point of the example is to show that the logic in function disambiguation is ignoring the details of what kind of use/import and just traverses everything assuming it is a public use including all symbols. And that this is inconsistent with what we are doing in scope resolve for variables.

@mppf
Copy link
Member Author

mppf commented Feb 4, 2022

@skaller - it is nice to know that at least one other language has the "shadow scope" idea. We do that today but have two shadow scopes for use.

If you have incoherent implicit conversions in your language, you have to fix them.

Can you say more about what you mean by "incoherent implicit conversions" here? Later you say:

get rid of implicit conversions that are not subtyping relations.

Is this exactly the implicit conversions you were calling "incoherent"?

I don't think we'll be willing to remove all non-subtyping implicit conversions from the language, and in any case that would be a massive change and is definitely off-topic for this issue.

@skaller
Copy link

skaller commented Feb 4, 2022

Two shadow scopes? Interesting!

So: removing some implicit conversions is a trivial change. It simply forces the user to write them explicitly. Since the compiler knows when one is used that will be removed it can simply tell the user to write one or their code will soon stop working. In fact, with some work, a tool can be written to automatically fix user code. So actually it is not a massive change although it is a breakage. I would argue breaking something is just fine, if it is needed to repair an even worse breakage.

So, there is a correspondence between implicit coercions and subtyping as explained in discourse post. Subtyping is used to select between candidates in overload resolution, to select the most specific function. I will note there are the usual subtyping rules but also we include a concrete type as a subtype of a type variable. One of these is called subsumption but i can never figure out which.

Subtyping relations are transitive.

Now, if you have say a coercion from real to int and a coercion from int to real and they're subtyping relations as well, then we can prove int is the same type as real. Note: I said PROVE. And then, we have just proven the type system is unsound, which is equivalent to being able to prove every statement in a logic system, including both A and not A for every A. So we simply cannot allow this.

Well, the way it works in Felix and will also work in Chapel I guess, is that if you have an argument of type A and a parameter of type P, and they're not equal types, the compiler fixes the discrepancy by magically inserting a conversion. This conversion is implicit by definition: the compiler put it in there, not the user. So ALL subtyping relations imply the existence of an implicit coercion. [In our kinds of languages]

So now, can we have an implicit conversion anywhere else? Remember, implicit conversions are inserted by the compiler. Where else could it insert one?

The answer is NOWHERE. There is ONLY one way for the compiler to insert the coercion implicitly and that is on a function call or any context where you have a target and source type. For example, in assignment: same deal. The RHS has to be a subtype of the LHS. Initialisation: same deal.

You see? You can have an implicit coercion that isn't a subtype but it is certain to be entirely useless. It will never get inserted by the compiler, so you might as well take it out of the documentation.

So now, lets consider real and int are equivalent and show where both conversions can be inserted:

proc f (x:int, y:real) ... f (1.0, 2)

The problem is, with the specialisation algorithm, unless both int->real and real->int are subtypes, this call will fail. There's no match. And if they are both subtypes, your type system is unsound. You simply cannot allow this, and you really DO have no choice but to overload based on the standard algorithm which depends entirely on a strict subtyping rule which must be transitive.

Otherwise you're polluting your overload resolution with a heap of special cases and that NEVER works, because such special cases almost universally fail to be recursive. Eg if you have nested tuples.

The reason this comes up is that when you import modules you're importing function sets. Even if you put all the imports in a shadow scope, you are still merging function sets from multiple imports. The original issue is how to handle the conflicts which arise here and that is directly related to overload resolution (so it is not really off topic :-)

@mppf
Copy link
Member Author

mppf commented Feb 4, 2022

@skaller - I will continue the conversation about subtyping and implicit conversions over on https://chapel.discourse.group/t/overload-resolution/10252 .

@mppf
Copy link
Member Author

mppf commented Feb 7, 2022

I've opened #19198 to describe a related problem with isMoreVisible.

@mppf
Copy link
Member Author

mppf commented Feb 8, 2022

Here is an even simpler program showing an inconsistency between scope resolution and function resolution:

module M {
  var X: int;
  proc f() { writeln("M.f"); }
}

module N {
  var X: real;
  proc f() { writeln("N.f"); }

  proc main() {
    use M;
    writeln(X); // prints out 0 so refers to M.X
    f(); // ambiguity error
  }
}

@mppf
Copy link
Member Author

mppf commented Feb 8, 2022

I've created #19219 about whether or not use should have two shadow scopes (or one, or none).

@mppf
Copy link
Member Author

mppf commented Feb 8, 2022

I think some of my previous comments might represent a misunderstanding of the current rules.

From #11262 (comment) :

The traditional definition has been more like: "use statements make symbols available as though they were in a scope just outside of the current lexical scope but closer in that its parent scope (and the module name that was used is in a scope just above that)."

So if I were to turn this in to a numeric distance, a regular enclosing scope would add 2, so that a use statement can create a distance between the symbols contained and the outer scope.

E.g.

module M {
  var x = ...;
}
module N {
  var y = ...;
  {
    // y is available here at distance 2
    use M; // x is available here at distance 1
    var z = ...; // z is available here at distance 0
  }
}

@lydia-duncan
Copy link
Member

I think that's a simplification. A use can bring in an arbitrary number of scopes, depending on if the module being used itself contains public use statements. I tend to think of scopes brought in by use and import statements as following a different dimension from the scopes defined with {}

@mppf
Copy link
Member Author

mppf commented Feb 8, 2022

Right but the compiler has this isMoreVisible element where it needs to be able to answer the question about visibility in function disambiguation. How can it do that with the scopes and the use statement things being in a different dimension? Maybe I am missing something but it seems it has to linearize it somehow in order to say if one thing is more visible than another thing. I could imagine that isMoreVisible could return "Incomparable" in some cases and maybe that would be OK but AFAIK our current scope resolver cannot do such a thing, so I don't understand how we could make variables and functions consistent with that approach.

@skaller
Copy link

skaller commented Feb 8, 2022

Hang on. If the rules are that complicated the compiler cannot figure it out in a simple way (meaning the algorithm is quite complex) then the rules are bad because the user has no hope of figuring it out. So perhaps the wrong question is being asked.

In my language, the rules for variables and functions are indeed different. It is an error to define the same non-function symbol in a scope. A function, on the other hand is identified by its name and domain type and duplicate definitions are allowed.

I use a single shadow scope, however there are two name maps, one for private use inside a module only, and one for public use from outside the module. Explicit qualification looks only in the specified module. It does not look in shadow scopes or in parent scopes. Each name map has two kinds of entry, a non-function entry and a function entry (a name map is a hash table). Function entry in the lookup table contains a set of functions. When I import two modules, the functions of the same name are merged into a single set. I had to do an experiment to see what happens to variables. To my dismay its a not exactly what I might have expected:

class X { var x = 3; }
class Y { var x = 2; }
class Z { inherit X; inherit Y; }
open Z;
println$ x;

Output:

~/felix>flx xx
3

I don't know if this is random or it just takes the first definition, but it is a design fault either way I think. The problem is, you cannot ban the importation or use of two modules just because they happen to contain duplicate variables. But it should be an error to use one (not silently picking one of them). The problem is, how can the compiler represent this? If it cannot bug out on constructing the scope, it would need to put an entry for the duplicate symbol which if found, would generate a diagnostic .. the only other option is to not put either symbol in the scope. However that is also bad because then, a symbol from the parent scope might be found instead of being hidden.

I would note also you need to think about Interfaces. In Felix, a module and and Interface are the same thing, a module is simply a non-generic Interface (i.e. with no type parameters). I used to have them separate, but it was too hard to figure out the differences and impossible to maintain two sets of complicated lookup rules.

So when you're trying to figure out rules for modules .. don't forget you will have to do it for interfaces as well.

@mppf
Copy link
Member Author

mppf commented Feb 8, 2022

In an off-issue discussion with @lydia-duncan I learned that one problem with Option B. is that it makes the rules for shadowing different within a module and when the module is used. I think that's a reasonable criticism of it. For what it's worth, Option C. doesn't have that problem. Arguably, Option C. is just making public use behave more like public import (where we already have public import working like Option C per the description in the last paragraph in https://chapel-lang.org/docs/language/spec/modules.html#conflicts ).

Another thing we talked about is that the current rules could lead to "hijacking" in this scenario:

We start with Library which publicly uses Dependency:

// this is Library v1.1
module Library {
  public use Dependency;
}

Let's suppose that when Library is developed, Dependency looks like this:

// this is Dependency v1.1
module Dependency {
  // other stuff unrelated to example
}

And the next thing that happens is that Dependency is improved to look like this:

// this is Dependency v1.2
module Dependency {
  proc foo();
}

Then, somebody makes an Application that uses Library v1.1 and Dependency v1.2:

module Application {
  use Library;
  foo(); // intended to call Dependency.foo
}

Now, suppose that the author of Library doesn't realize that the new version of Dependency has a foo and they add on of their own:

// this is Library v1.2
module Library {
  public use Dependency;
  proc foo() { }
}

They might test Library v1.2 using Dependency v1.1 and not notice any problem and then publish it. But, a user goes to try to build Application with Library v1.2 and Dependency v1.2. Then their call to foo starts running Library.foo where they expected it to run Dependency.foo, and they are surprised and confused.

(Vs in both Option B and Option C there would be a compilation error).

Edit:

Adding the foo functions in Dependency and Library ought to be a non-backwards-breaking change and in semantic versioning, so that can just increment the minor version as described above. That means that if mason is used for all of the modules involved, it would be reasonable for Library to depend on Dependency 1.* and for Application to depend on Dependency 1.2, so there is nothing about mason and version numbers that would prevent this problem.

One approach would be to point at the public use Dependency as something that is not a good idea to do with code from outside of a mason package -- i.e., in a mason package, it should only be used to re-export the contents of a submodule publicly. I suppose we could create a compilation warning for that scenario.

@skaller
Copy link

skaller commented Feb 8, 2022

BTW: if the module rules are complicated (and they usually are in any language) thing the user is going to need a psychiatrist to cope with POI lookup, because that has to look in at least THREE distinct places: the original point of definition, the module in which the instantiated type is defined, and the point of instantiation .. all of which can involve modules and imports and stuff.

@mppf
Copy link
Member Author

mppf commented Feb 10, 2022

I've edited #19167 (comment) a bit with some thoughts about how the "hijacking" scenario relates to semantic versioning and mason.

mppf added a commit that referenced this issue Feb 10, 2022
dyno: function disambiguation

This PR adds a port of the function disambiguation logic to the new
compiler rework effort, including some new tests. None of these changes
impact the production compiler at this point. The new code is primarily
porting the old logic and rules to work with uAST and the dyno type
system.

Reviewed by @vasslitvinov - thanks!

- [x] full local testing

Future Work:

* This implementation inherits the complexity of the language and the old
  implementation. The following issue asks if we can simplify the
  language in this area:
  * #19195

* This implementation uses a different approach for isMoreVisible than
  the production compiler and this issue discusses the specifics of the
  language design in that area:
  * #19167
@bradcray
Copy link
Member

Returning late to this issue and jumping into Michael's simpler example in the middle:

module M {
  var X: int;
  proc f() { writeln("M.f"); }
}

module N {
  var X: real;
  proc f() { writeln("N.f"); }

  proc main() {
    use M;
    writeln(X); // prints out 0 so refers to M.X
    f(); // ambiguity error
  }
}

I think the behavior of X here is appropriate and would be averse to changing it. If fear of hijacking were to cause us to change it, I think that'd be an argument that the user should've written import M; rather than use M;.

I also think that f() should probably call M.foo() rather than reporting the ambiguity, in part to act more symmetrically to X above, and also because in this example:

proc foo() {
  writeln("In outer foo");
}

{
  proc foo() {
    writeln("In inner foo");
  }

  foo();
}

we get a call to inner foo() rather than outer foo() (and given the shadow scope interpretation of use—which still matches my intuition—this seems similar to Michael's example.

I think the trick here is how far that shadowing goes. For example, if inner foo() had been declared to require arguments as in proc foo(x: int), would the call foo() invoke the outer routine, or would the outer routine be shadowed by inner foo()? And if "shadows" is the right answer, does this make it harder to add new overloads to a given function when you don't have access to the source code of the module that defined the original versions of the routine?

@mppf
Copy link
Member Author

mppf commented Feb 11, 2022

I think the trick here is how far that shadowing goes. For example, if inner foo() had been declared to require arguments as in proc foo(x: int), would the call foo() invoke the outer routine, or would the outer routine be shadowed by inner foo()? And if "shadows" is the right answer, does this make it harder to add new overloads to a given function when you don't have access to the source code of the module that defined the original versions of the routine?

A next step for me is to check to see if we have cases in the test system where more aggressive shadowing here would be a problem for non-method non-operator cases.

@bradcray
Copy link
Member

Catching up a bit more, I am generally in favor of something along the lines of approach B. Specifically, when I think about what a module logically does in Chapel, I think of it as making a set of symbols available to another piece of code via use or import statements, where those symbols may be defined by the module itself, or they may have the appearance of being defined by the module as a result of public use or public import statements that it contains. Generally speaking, once I'm outside the module (and maybe even when I'm within it?), I don't really want to have to worry about where those symbols came from or how they were implemented, simply that they're available or not. And from a compilation time/complexity standpoint, I'd like the compiler to see something more like a "flat bill of sale" for what a given module provides rather than for the module to expose all of the structure that led to its definition. Put another way, I think of a module as defining all the stuff that its documentation says it does (noting that chpldoc doesn't help with public use or public import today, but I think we all agree there should be a better story there) where ideally nobody would be the wiser how those symbols were implemented, and those implementations could change without changing behavior (e.g., pushing symbols into the module into a helper module that's publicly used/imported or vice-versa).

Where I might pause with option B (if I'm understanding it correctly) is with a concern that I think Lydia raised about having the resolution of a call foo() happen differently within a module vs. outside of it. But as I understand it, issue #19219 may propose a solution to that (?). Going to check that out now.

@mppf
Copy link
Member Author

mppf commented Feb 11, 2022

Right, if public use does not create a shadow scope, the inconsistency goes away for option B. (And at that point option B is more or less the same as option C' and the way I described the options above isn't that useful, FWIW).

@bradcray
Copy link
Member

Ah, I'd missed option C' earlier. Yeah, I think option C' makes the most sense to me: It keeps private use behaving as it does today; it makes the behavior for a call within a module and outside it (assuming all relevant symbols are equally visible in both cases) more consistent; it makes public use more interchangeable with defining a symbol directly within a module such that code can be refactored into or out of helper modules without changing the code's meaning; and it seems to support the "bill of sale" model

An example that came up in talking with Michael seems worth capturing here. Say I had:

module M {
  proc foo() { ... }
}
module N {
  public use M;
  proc foo() { ... }
  // foo();  // maybe I call foo here?
}
module O {
  use N;
  // foo();  // and/or maybe I call foo here?
}

Because we don't resolve overloads until a call is made—and because we generally can't very easily determine whether or not two functions do have overlapping signatures or not because of type inference, generics, and the like—while the code above effectively defines two foo() overloads at the same scope according to the rules of C', this would not be caught until someone tried to call foo(). And that's similar to what would happen today if the two foo() procedures were defined at the identical scope (no error until the call was made). Put another way, the "bill of sale" for N would be "I define two functions named foo() that take no arguments" which makes that routine useless, but consistent with what would happen if they were both defined within module N outright.

We discussed whether the compiler could try to consider certain function signatures to shadow others, but apart from some easy cases like 0-argument routines above, this felt pretty intractable to do in any way that felt like it wasn't a band-aid solution, covering some cases but letting others through.

@skaller
Copy link

skaller commented Feb 12, 2022

@bradcray wrote:

And if "shadows" is the right answer, does this make it harder to add new overloads to a given function when you don't have access to the source code of the module that defined the original versions of the routine?

Yes it does. When I face this issue in Felix, knowing in C++ if a name shadows an outer name, that's the end: if overload resolution in the inner scope fails there is no recourse to the outer scope. [In C++ you can put a using directive to pull extra overloads in, originally designed to pull in overloads from a base class]

It is important to understand the algebraic reason for this: in C++ a function set is identified by a name. In Felix, I changed the notion of identity: a function is Felix is identified by its name and the type of the domain. So if you are looking for a function with a given name, and arguments of some type T, then a function in the inner scope with a type X, where T is not a subtype of X, does not hide functions in the outer scope.

I'm not saying Chapel should do it my way or the C++ way or any other way, I'm saying that you have to step back and ask the right question: what identifies a function? Do you identify individual functions, or do you identify sets of functions?

The idea of a shadow scope is that you have the usual lookup rules for looking for a symbol by name in the current scope and if you fail, you go to the parent scope, etc all the way to the global scope. So with a shadow scope you would use the same rules, but just add an extra scope into the environment. The reason of course is simplicity: you can decouple the problem into the already implemented parent lookup rules and construction of the shadow scope.

So in Felix, I first search for an identifier, and find either a non-function or function set. If i'm looking for a function, the lookup routine must also accept the argument type being sought, not just the name. Which means there are two distinct lookup routines one for functions and one for everything else. It gets complicated because sometimes you don't know, and sometimes in Felix, a type can be a function, for example the name of a struct is also the name of its constructor, so sometimes, looking for a function, you find a non-function but its OK.

In fact in Felix lookup system, the shadow scope does not contain symbols, it contains the directives (use, import etc), which modify the lookup. So my system actually breaks the principle I cited above, so to re-establish it I have to encode the interpretation of lookup in spaces defined by directives, to work as if I had actually eagerly built the environment, instead of lazily waiting until i need to (performance is part of the reason but not the only one).

If you identify a function only by it's identifier name, then, an inner function of that name hides all functions in all enclosing scopes, including shadow scopes. This is the case in C++. It is not in Felix precisely because of the effect @bradcray noted above. The lookup algorithm should be derived from your concept of identity and environment.

@skaller
Copy link

skaller commented Feb 12, 2022

@bradcray wrote

We discussed whether the compiler could try to consider certain function signatures to shadow others, but apart from some easy cases like 0-argument routines above, this felt pretty intractable to do in any way that felt like it wasn't a band-aid solution, covering some cases but letting others through.

I don't follow. The way this is done is absolutely stock standard using a well known algorithm, namely (a modification of) unification. Generics do not cause a problem, nor do implicit conversions provided they're transitive. Furthermore you have to use precisely this algorithm to resolve overloads anyhow right now, and, you will have to use it again in a different way to resolve overloads mediated by Interfaces. Unification is a core algorithm used in almost every compiler one way or another. There's nothing band-aid here.

Whether or not a function domain type hides another or not is trivial to compute and is not an issue at all. The actual issue is what to do when you get either an ambiguity, or, no matches at all. Felix continues if there are no matches. C++ will not continue, unless there is no function with the given name, in which case unification is not done in the first place.

@skaller
Copy link

skaller commented Feb 12, 2022

@bradcray wroteL

Put another way, the "bill of sale" for N

I strongly support @bradcray concept here (never thought of it as a bill of sale but it's a nice analogy). The client of a module shouldn't care how the author of a module got a public symbol into the module. It's either in there or not.

Unfortunately, my own lookup rules do not support any way of doing this, I consider that a design fault in my system. In Felix, an open directive makes symbols available only for private use of the client performing the open, it is not transitive. An inherit directive, however, makes the symbols from the specified module available if the module doing the inherit is then opened, it is transitive. These rules apply exclusively to unqualified access. If a qualified access is made, lookup is restricted to the actual symbols defined in the module and both open and inherit are completely ignored. So in Felix it is not possible to synthesise a module from other modules (other than by using wrapper functions, typedefs, etc). The issue for me is that there should be a way to uniquely identify a function and a qualified name together with a function signature does that "up to functions with identical domain types" which cannot be disambiguated at all.

@brad is saying, the client of a module shouldn't care how a function got in there, and, there should be a way to bulk synthesise a module from other modules (module composition in other words). Indeed, with his view, it is still possible to pick the right function with a qualified name to its original location in case of ambiguity. The only real issue here is what to do about clashes: detecting them lazily seems the best way, but it has a downside: you don't find out about the problem until you try to use an ambiguous symbol, and generally, late error detection is contrary to the spirit of static typing: it means to be sure your module correctly implements a specification you have to run tests which cover all cases, the very problem static typing tries to solve.

But you can have your cake and eat it too: issue a warning if there is a possible clash, and an error only when it causes a problem.

@mppf
Copy link
Member Author

mppf commented Feb 18, 2022

From earlier comments:

I think the trick here is how far that shadowing goes. For example, if inner foo() had been declared to require arguments as in proc foo(x: int), would the call foo() invoke the outer routine, or would the outer routine be shadowed by inner foo()? And if "shadows" is the right answer, does this make it harder to add new overloads to a given function when you don't have access to the source code of the module that defined the original versions of the routine?

We discussed whether the compiler could try to consider certain function signatures to shadow others, but apart from some easy cases like 0-argument routines above, this felt pretty intractable to do in any way that felt like it wasn't a band-aid solution, covering some cases but letting others through.

The lookup algorithm should be derived from your concept of identity and environment.

It is interesting to consider how shadowing is related to overriding for child classes. There, we have the design that, basically, you can think of the combination of method name + argument names + types as the thing that determines what a method is, in terms of overriding. If we were to make the language design have overloads shadow more aggressively, would we would need to also change what we consider to be an override? In particular, if you are overidding something that has multiple overloads, you would have to override all of the overloads. In practice this is easy to do simply by copying the signatures from the parent class(es). But it is not required today.

Current checking is described here: https://chapel-lang.org/docs/language/spec/classes.html#overriding-base-class-methods

Here is an example:

class Parent {
  proc f(arg: int)    { writeln("Parent f(arg: int)"); }
  proc f(arg: string) { writeln("Parent f(arg: string)"); }
}

class Child : Parent {
  override proc f(arg: int)    { writeln("Child f(arg: int)"); }
}

var x: owned Parent = new owned Child();

x.f(1);     // Child f(arg: int)
x.f("hi");  // Parent f(arg: string)

In this case I think it would actually improve the clarity of the situation to require that the author of Child also write override proc f(arg: string). Especially since, when implicit conversions are involved, it may not be so obvious as in this example which f overload will be called.

Edit - Taking a completely different tack, what if we had two different record types that both wanted to define a method? If we were to consider defining anything named f to shadow all other things named f, we wouldn't be able to have methods with the same name on different record types. Here is an example:

module M1 {
  record R1 {
    proc f(arg: int)    { writeln("M1 R1.f(arg: int)"); }
  }
}

module M2 {
  use M1;

  record R2 {
    proc f(arg: int)    { writeln("M2 R2.f(arg: int)"); }
  }

  proc main() {
    var r1 = new R1();
    var r2 = new R2();

    r1.f(1); // is this a legal call? Is it shadowed by R2.f?
    r2.f(1);
  }
}

So, I think that if we were to have more shadow-y functions, we would have to also start to treat method receivers in more special ways than we do today. (It is already the case that methods can come from more scopes - the method-ness just does not impact the shadowing rules, and it would need to if we made shadowing of functions just based on the name, say).

@mppf
Copy link
Member Author

mppf commented Feb 20, 2022

I have been investigating option C': Do not consider public use or public import to create additional scopes, but private use/import can do so.

This design has two implications that were not obvious to me at the start.

One implication is that, if there is both a public use and a private use defining the same symbol within a module, mentions of that symbol within that module will refer to the public use.

E.g.

module M1 { var x: int; }
module M2 { var x: int; }
module Program {
  public use M1;
  private use M2;
  x; // this is M1.x because the public use did not introduce a shadow scope
     // but the private use did
}

I think that this is defensible on the argument that it makes the behavior of the code in the module better match what happens when you use it, but it is a bit odd.

The second implication is that, without adjustment, it's no longer possible to create a module that one can use in order to shadow a symbol defined in the automatically-used modules from the standard library. For example:

module ReplaceE { param e = 10; }
module Program {
  // use StandardLibrary; is effectively here but implicit
  use ReplaceE;
  e; // now ambiguous, because ReplaceE.e and StandardLibrary.e are
     // both in the same shadow scope
}

(But this pattern would work if it were public use ReplaceE).

I think this pattern is something that we probably want to support (e.g. if we want to have a module you can use to change what + does on numeric types, we would need it). I think that we could use the simple solution of placing that implicit "use StandardLibrary" in its own shadow scope just outside of the regular shadow scope.

@bradcray
Copy link
Member

I think that this is defensible on the argument that it makes the behavior of the code in the module better match what happens when you use it, but it is a bit odd.

I agree that this is defensible, but does it generate a new opportunity for hijacking? Say you wrote your code intending to refer to M2.x and at the time M1.x didn't exist, but is later added. Even if so, I'm also still OK with saying "If you want to avoid hijacking, use import rather than use. But I'm also wanting to make sure we're not just trading one source of confusion for another.

All that said, I still like the new interpretation of public use because of the fact that it supports the ability to refactor code from a scope into a module or vice-versa without changing its visibility, which seems like a major motivation for public use (i.e., it was more convenient for me to organize my code in another way, but I'd like it to behave the same).

The second implication is that, without adjustment, it's no longer possible to create a module that one can use in order to shadow a symbol defined in the automatically-used modules from the standard library.

This seems acceptable to me since there is actually an ambiguity (i.e., why should ReplaceE necessarily win? In this case, the name suggests it's what's desired, but maybe in another case, it's not, and would cause confusion? Or would be a case of a module hijacking something important without the user realizing?). Is there reason to believe that the user variable ought to win?

I agree we'll want a way to override such symbols, but I continue to imagine doing that through some way of opting out of auto-used modules/symbols (altogether, or maybe on a case-by-case basis). I'm also cautiously optimistic that as we continue to reduce the sizes of auto-used modules (like Math, ChapelEnv, etc.) this will be less of an issue, though your point about overriding built-in operators is well-taken—though also something that probably shouldn't be done lightly.

I was going to say something about import helping here, but it seems that's probably not the case since the auto-used modules aren't imported... That said, somehow import ReplaceE.e; feels like it ought to "win" over something obtained through a use without being named.

Of course, fully qualifying e at the use site would be a way to break the ambiguity while also making the code's intent clearer.

Maybe turning the question around: Can we rationalize why it's a good thing for the user module to "win" today? (given that the user module may not be a user module but some package module that they know nothing about which could be malicious). It seems to me that this ambiguity is making things better (?).

@mppf
Copy link
Member Author

mppf commented Feb 22, 2022

I think that this is defensible on the argument that it makes the behavior of the code in the module better match what happens when you use it, but it is a bit odd.

I agree that this is defensible, but does it generate a new opportunity for hijacking? Say you wrote your code intending to refer to M2.x and at the time M1.x didn't exist, but is later added. Even if so, I'm also still OK with saying "If you want to avoid hijacking, use import rather than use. But I'm also wanting to make sure we're not just trading one source of confusion for another.

That's true; however for public use to be relevant it is probably in a library (or something library-like) and at least this issue would be discovered if the library is independently compiled. It is an issue only within the library because the private use will not impact things using the library. So, it feels to me like we have an issue but the issue is a bit in a box.

In any case, I think it is reasonable to encourage library authors to prefer import since public use is such a big hammer.

All that said, I still like the new interpretation of public use because of the fact that it supports the ability to refactor code from a scope into a module or vice-versa without changing its visibility, which seems like a major motivation for public use (i.e., it was more convenient for me to organize my code in another way, but I'd like it to behave the same).

👍

The second implication is that, without adjustment, it's no longer possible to create a module that one can use in order to shadow a symbol defined in the automatically-used modules from the standard library.

This seems acceptable to me since there is actually an ambiguity (i.e., why should ReplaceE necessarily win? In this case, the name suggests it's what's desired, but maybe in another case, it's not, and would cause confusion? Or would be a case of a module hijacking something important without the user realizing?). Is there reason to believe that the user variable ought to win?

...

Maybe turning the question around: Can we rationalize why it's a good thing for the user module to "win" today? (given that the user module may not be a user module but some package module that they know nothing about which could be malicious). It seems to me that this ambiguity is making things better (?).

I've written about this a bit in this comment:

That comment talks about why I think we need for private use / use to introduce a shadow scope at all. Note that my argument about "we should be able to add functions without making breaking changes" could apply to the standard library or to a user library.

For the standard library, there I was arguing that private use needed a shadow scope; but an alternative could be to remove the shadow scope for private use but have the implicit standard library use have a further scope. That has the same effect for a different reason.

For a user library, we won't be able to handle it in that way. For example, if we have typical use cases of programs that need LinearAlgebra having a (private) use statement; we would like for those programs to be able to have top-level functions and for them to not break if LinearAlgebra has a theoretically-not-breaking change of adding a new function (which potentially has the same name as a function defined in the program).

Now, what is different in the current discussion is that the conflicting symbol is defined in something that is also used. E.g.

module DefinesFoo { var foo = 10; }
module Program {
  // use StandardLibrary; is effectively here but implicit
  use DefinesFoo;
  foo; // OK, at least until StandardLibrary adds a foo
}

Now suppose that in StandardLibrary, we add a const foo. That would cause ambiguity, but do we want the above program to continue to work? I would suppose so - because I'd think that adding a top-level variable to the standard library should be a non-breaking change.

Here is the similar case for a user module:

module DefinesFoo { var foo = 10; }
module Program {
  use LinearAlgebra;
  use DefinesFoo;
  foo; // OK, at least until LinearAlgebra defines a foo
}

I don't have a solution for this case and it would get the ambiguity error if LinearAlgebra added a foo. But, what is different in this case, is that the user can adjust how they are bringing in LinearAlgebra. They could use import exclusively, or they could write use LinearAlgebra except foo. These responses are not possible with the implicitly-used standard library.

I think another viewpoint on this issue is - suppose everybody were using import, what would happen? It would get the user's foo and not give an ambiguity error. Here is an example:

module DefinesFoo { var foo = 10; }
module Program {
  import LinearAlgebra;
  import DefinesFoo.foo;
  foo; // always refers to DefinesFoo.foo even if LinearAlgebra adds a foo
}

Similarly, if import never adds a shadow scope, code using import will not have problems if a symbol is added to the standard library. But that is because the user's foo will be preferred. My suggestion to give the standard library its own further scope just extends that behavior to use which I think is probably what we want to have.

@lydia-duncan
Copy link
Member

In this case I think it would actually improve the clarity of the situation to require that the author of Child also write override proc f(arg: string). Especially since, when implicit conversions are involved, it may not be so obvious as in this example which f overload will be called.

Is there precedent for this? My initial reaction is that sounds like a pain for implementers of Child classes.

Taking a completely different tack, what if we had two different record types that both wanted to define a method? If we were to consider defining anything named f to shadow all other things named f, we wouldn't be able to have methods with the same name on different record types.

That seems pretty obviously wrong to me.

One implication is that, if there is both a public use and a private use defining the same symbol within a module, mentions of that symbol within that module will refer to the public use.

E.g.

module M1 { var x: int; }
module M2 { var x: int; }
module Program {
  public use M1;
  private use M2;
  x; // this is M1.x because the public use did not introduce a shadow scope
     // but the private use did
}

I think that this is defensible on the argument that it makes the behavior of the code in the module better match what happens when you use it, but it is a bit odd.

This seems pretty subtle to me. Suddenly if you decide to make a use public that was private before, you may find you have conflicts that weren't present before. Which is very relevant because the default use is private - a user could very easily write use Bar and interact with it in their code without issue but then realize "oops, I meant for those symbols to be available outside my module as well" and suddenly their program breaks.

@mppf
Copy link
Member Author

mppf commented Feb 23, 2022

I agree it is subtle but I'm not sure what to do about it. It is something we already have today (at least in the behavior in the spec) for import. Also I think it is less bad than some of the alternative designs.

I suppose we could make this specific case of public use symbol shadowing a private use one an ambiguity (even though it would not be a general thing) but I'm not sure that makes the system more understandable.

@mppf
Copy link
Member Author

mppf commented Feb 24, 2022

Responding to a comment from here -- #19167 (comment)

I agree we'll want a way to override such symbols, but I continue to imagine doing that through some way of opting out of auto-used modules/symbols (altogether, or maybe on a case-by-case basis). I'm also cautiously optimistic that as we continue to reduce the sizes of auto-used modules (like Math, ChapelEnv, etc.) this will be less of an issue, though your point about overriding built-in operators is well-taken—though also something that probably shouldn't be done lightly.

Well, today we cannot do that at all, because the use ChapelStandard is implicit. I suppose though, we could allow people to write import ChapelStandard or use ChapelStandard except e etc and then have the compiler see that and leave out the implicit one.

@mppf
Copy link
Member Author

mppf commented Feb 25, 2022

I've made

To spin-off the discussion about shadowing an automatically used symbol (like Math.e) that started here: #19167 (comment)

@mppf
Copy link
Member Author

mppf commented Feb 25, 2022

I've made

To spin-off the idea described here #19167 (comment)

mppf added a commit that referenced this issue May 10, 2022
simplify use/import shadowing

This PR describes and implements some candidate language adjustments to
shadowing behavior for use and import statements. We need to do something
in this area because the definition of shadowing is currently
inconsistent between variables and functions (#19167). This PR attempts
to simplify the language design in this area.

The adjustments to the language design in this PR are as follows:
 * isMoreVisible in function disambiguation as well as scope resolution
   use the same rules for determining shadowing with use/import
   statements
 * isMoreVisible starts it search from the POI where the candidates were
   discovered (see issue #19198 -- not discussed further here)
 * private use statements still have two shadow scopes
 * public and private import statements now do not introduce a shadow
   scope
 * public use statements now do not introduce a shadow scope
 * `public use M` does not bring in `M` (but `public use M as M` does)
 * methods are no longer subject to shadowing
 
Note that the above design leads to less shadowing of symbols from the
automatic library (see the section "Less Shadowing of Symbols from the
Automatic Standard Library" in
#19306 (comment))


## Discussion

Elements of the language design direction are discussed in these issues:
 * #19167
 * #19160
 * #19219 and #13925
 * #19312
 * #19352
 
Please see also
#19306 (comment)
which discusses pros and cons of these language design choices.


### Testing and Review

Reviewed by @lydia-duncan - thanks!

This PR passes full local futures testing.

Resolves the future `test/modules/vass/use-depth.chpl`.
Also fixes #19198 and adds a test based on the case in that issue.

- [x] full local futures testing
- [x] gasnet testing

### Future Work

There are two areas of future work that we would like to address soon:
 * #19313 which relates to changes in this PR to the test
   `modules/bradc/userInsteadOfStandard/foo2`. The behavior for trying to
   replace a standard module has changed (presumably due to minor changes
   in how the usual standard modules are now available). I think that
   changing the compiler to separately list each standard module would
   bring the behavior back the way it was. (Or we could look for other
   implementation changes to support it).
 * #19780 to add warnings for cases where the difference between `public
   use M` and `private use M` might be surprising
@bradcray
Copy link
Member

@mppf: I'm looking through issues associated with #19306 to see what is open and what is closed. What needs to happen in order to resolve this issue currently?

@mppf
Copy link
Member Author

mppf commented May 12, 2022

I'm closing since the PR added tests from this issue (test/modules/shadowing/issue-19167) and these are now working as I would expect.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants