Proposed improvement for the Point of Instantiation (POI) semantics

[vasslitvinov]

This relates to #6252 and may simplify its resolution.

8077 contains relevant discussion.

Right now the POI rule in the spec, see here, always uses POI as a source of visible functions. The compiler, as of this writing, does that, and also prefers a function visible without POI over a function visible only at POI.

This proposal is to examine the visible functions at POI only if there are no applicable candidates that are visible from the current scope.

If POI is itself in an instantiation of a generic function, the instantiation's POI is to be consulted only when there are no applicable candidates visible from the current POI.

This is similar in spirit to how the pragma "last resort" works.

Motivation: this helps decouple a library from changes in user code. If a call in library code is intended to be implemented within the library, it will continue resolving to that implementation regardless of like-named functions in user code.

Examples

module M1 {
  use M2;
  ...
  genericFunction(1);
}
module M2 {
  ...
  proc genericFunction(param p) {
    helperFun(some args);
  }
}

In the above example, helperFun will be resolved first against functions defined in M2. If there are no visible candidates, then functions defined in M1 will be examined.

The example below adds a second generic-function call to the call stack:

module N1 {
  use N2;
  ...
  genFun2(1);
}
module N2 {
  use N3;
  ...
  proc genFun2(param p) {
    genFun3(p);
  }
}
module N3;
  ...
  proc genFun3(param p) {
    helperFun(some args);
  }
}

When resolving the call to helperFun, these sets of functions will be consulted in order: those visible from 'helperFun', then those visible from the call to genFun3, then those visible from the call to genFun2.

What about hijacking?

Consider this library evolution scenario. With Library v1:

module Application {
  use Library;
  proc helper(i:int(8)) { }
  libFunction(1);
}
module Library {
  proc libFunction(param p) {
    helper(p);
  }
}

the user expects the Application's helper to be invoked.

If Library gets its own proc helper in v2:

module Application {
  use Library;
  proc helper(i:int(8)) { }
  libFunction(1);
}
module Library {
  private proc helper(i:int(32)) { }
  proc libFunction(param p) {
    helper(p);
  }
}

then the user's helper will no longer be invoked.

We argue that this concern needs to be addressed by the developers of Library. When testing libFunction for v1, the test needs to provide a helper implementation and observe that it gets invoked. If so, v2 will fail this test because helper is no longer invoked.

[vasslitvinov]

How does this idea translate to constrained generics (CG) ?

In this example:

interface I {
  proc helper(...);
}
proc genericFunction(...) where ... implements I {
  helper(...);
}
proc helper(...) {
}

When resolving the call to helper in genericFunction(), what to do:

• (i1) attempt to resolve it against the interface I; if no applicable candidates, proceed to visibility from the current scope then from POI, or

• (i2) attempt to resolve it based on the current scope, then against the interface, then using POI, or

• (i3) combine visible functions in the interface and the current scope, before resorting to POI ?

Note that only interface functions can ever be applicable to a call when at least one actual's type is restricted by an interface. Or is an aggregate type that includes such a restricted type.

[mppf]

How does this idea translate to constrained generics (CG) ?

I'd probably do (i2) in order to keep constrained generics and POI behaving as similarly as possible, provided that the implementation process of (i2) and constrained generics does not give us an example that causes us to change our mind. Note that with constrained generics it is often possible to explicitly use something from the interface and we will probably need a syntactical way to do that.

However generally speaking I don't think that functions using constrained generics will use POI at all. They will entirely rely on interfaces. (If we had a constrained generics design where some arguments could be constrained and others could be unconstrained in the same function, then we would want POI for such functions. However I don't think this is a good design for other reasons).

[vasslitvinov]

Here is one example where this new rule goes against the Chapel developer's intention.

Consider the following extract from this test: test/studies/comd/elegant/arrayOfStructs/CoMD.chpl

module Simulation {
  use AccumStencilDist;

  record Box {}
  proc +=(ref A:Box, B:Box) {...}   // updates 'A' in place
  var Boxes: [...] Box;  //dmapped AccumStencil

  Boxes.updateFluff();
}

module AccumStencilDist {
  use ChapelBase; //along with others, implicitly

  proc _array.updateFluff() {
    // redirects to AccumStencilArr._unpackElements()
    // which does something like this:
    ref elm1 = some array element;
    ref elm2 = another array element;
    elm1 += elm2;         // <------------ the call to consider
  }
}

module ChapelBase {
  inline proc +=(ref lhs, rhs) {
    lhs = lhs + rhs;
  }
}

When resolving elm1 += elm2 in AccumStencilDist:

• First, functions visible from the current scope are gathered.

  += in ChapelBase is visible via a 'use'. It is the only applicable candidate that is visible from the current scope. Therefore, according to this proposal, the call is resolved to this overload of +=.

• The developer's intention, however, is for the call to resolve to += in Simulation. It is preferable because it is more efficient: it updates the LHS in place without creating an intermediate result of +.

  That overload is visible only from POI. It is arrived at with the current resolution rules. It is not considered as a candidate under this proposal.

[vasslitvinov]

Here is another example where this new rule goes against the Chapel developer's intention. The mechanism is similar to the CoMD example above, the setting is different.

Consider the following extract from this test: test/release/examples/benchmarks/shootout/meteor-fast.chpl

module Meteor {
  use ChapelReduce;  // implicit

  var coords: [...] 2*int;

  proc min((x1, y1), (x2, y2)) { ...custom definition... }

  var M = min reduce coords;
}

module ChapelReduce {
  use ChapelBase; // implicit

  // implementation of 'min reduce' includes this:
  proc accumulateOntoState(ref state, x) {
    state = min(state, x);     // <---------- the call to consider
  }
}

module ChapelBase {
  inline proc min(x, y) return if x < y then x else y;
}

When resolving the call min(state, x) within the implementation of min reduce, the overload in ChapelBase is the only applicable candidate that is visible in the lexical scope of the call. So it is chosen according to this proposal. Whereas the user wanted it to use the more specific overload in Meteor, which is visible only via POI.

[mppf]

Both of these cases seem to be a pattern of a "default" implementation of something and then replacing the "default" with something else. I think that the constrained generics design has a reasonable way to handle this (where you could put the "default" implementation in the interface itself).

Here, I still think it'd be a semantic improvement if these cases ran the scoped function (in ChapelBase). I think the main question is - is there a way to address the problem available to the user? Supposing that we went ahead with the language change - what would they do in these cases?

[vasslitvinov]

"what would they do in these cases?"

This is what I would like to work out as well.

8077, too, proposes this direction : "I think it'd be reasonable to "opt in" to having 1 2 consider both the existing operators and the new one."

For a reference, here is a hijacking pattern that this proposal would solve:

// test/functions/ferguson/hijacking/Application4.chpl

module Library {
  proc setup(x) { }
  proc run(x) {
    setup(x);  // <-------- the call to consider
  }
}
module Application {
  use Library;

  proc setup(x:string) { }  // "hijacking" definition
  proc main() {
    run("1");
  }
}

The call to setup in Library.run() would not "see" the definition of Application.setup and so will always resolve to Library.setup, regardless of what application code invokes Library. The program would compile and run successfully.

Today this scenario is flagged as an overload-sets error.

[bradcray]

Thanks for explaining these cases Vass. I agree that it seems preferable to have these cases use the default implementations that are immediately available to them rather than the specialized ones, and would argue that the fact that they use the specialized ones suggests that a hijacking of sorts has taken place (even if it was an intended one).

Practically speaking, for meteor-fast.chpl, it makes sense to me that one shouldn't be able to redefine min() for a well-defined type and have it apply to how min reductions work. E.g., if I defined my own min() on integers, it seems scary / dangerous / weird / indirect for min reduce on an array of integers to do something different than the typical thing one would expect in reading the code. Some options the author of this code has to keep it working under the new interpretation include: (a) writing the reduction manually (it's a serial reduction anyway, so the reduce expression gives some nice expressiveness, but isn't going to result in a big parallel implementation or anything like that); (b) defining a coord record type (either with two fields or wrapping the 2-tuple) and defining min()/< on it (c) reversing the order in which the tuples are stored

Practically speaking, meteor isn't a live benchmark in the CLBG anymore, so isn't of great interest to us (it ran so fast it essentially measured program startup time anyway).

The CoMD case is a little more concerning... On one hand, AccumStencilDist is part of this application, so arguably could be modified to use something other than += to do the accumulation, or to have the specific += overload immediately available to it. However, the intention is definitely that this might be a standard distribution someday, which would make the first approach less attractive and the second unworkable. This case (and POI decisions in general) takes me back to the age-old question about whether operators should optionally be able to be specified as methods. For example, if the default implementation of += was something like:

proc +=(lhs: ?t, rhs: t) {
  if canResolveMethod(lhs, "+=", rhs) then
    lhs.+=(rhs);
  else
    lhs = lhs + rhs;
}

Am I correct in thinking that this would permit a record author to define a += method on a pair of record types that they define and have it work?

[mppf]

@bradcray - thanks for your thoughts. I agree with what you are saying. I am not sure if the operators need to be methods or not; but either way I think in this case we'd want to consider += in a method-like manner. In particular, the module defining record Box should be the main place we should expect one to be created, and the version of += in ChapelBase is really a kind of default supported by the compiler. As a result we can solve the problem by implementing it differently. For example, one strategy would be to generate += for records that did not define their own += in buildDefaultFunctions.

[vasslitvinov]

The prototype implementation that I used is here: https://github.com/chapel-lang/chapel/compare/master...vasslitvinov:prototype-new-poi-rule

The only other failures I got in a paratest were of this kind:

[Executing diff err-in-insn.good err-in-insn.comp.out.tmp]
3,5c3
< err-in-insn.chpl:1: note: this candidate did not match: myadd(a: int, b: int)
< err-in-insn.chpl:6: note: because call actual argument #1 with type MyRecord
< err-in-insn.chpl:1: note: is passed to formal 'a: int(64)'
---
> err-in-insn.chpl:6: note: because no functions named myadd found in scope
[Error matching compiler output for functions/generic/err-in-insn]

[vasslitvinov]

Here are some ways to address the CoMD example above without constrained generics. Thinking both about that specific example, as well as the general pattern of "a library provides the default implementation of a particular operation, library user may override it for specific cases".

(A) Introduce syntax for the user to force the call consult POI first. This is along the lines of #15754 .

(B) Treat += like a method, meaning that the scope of the receiver type will be consulted for visible functions. See also typeHelperNames in the compiler.

(C) Use canResolve(); this requires giving a different name to this operation. That is, instead of:

elm1 += elm2;

AccumStencilDist would have:

// in AccumStencilArr._unpackElements()
accumWrapper(elm1, elm2);

// if user defined accum(), use that, otherwise use +=
private proc accumWrapper(elm1, elm2) {
  if canResolve("accum", elm1, elm2) then
    accum(elm1, elm2);   // if user provides a definition
  else
    elm1 += elm2;        // the default implementation
}

(D) Add an argument to AccumStencilDist that is either a first-class function (FCF) or an object providing an "accumulate" method. This argument would have a default value that executes +=.

(E) Mark the implementation of += in ChapelBase with pragma "last resort", ultimately changing this pragma into a user-facing feature.

(F) Use ChapelBase except +=. That way, AccumStencilDist can reason about availability of += in user code using canResolve. If not available, it can import += from ChapelBase.

(G) Add a where-clause to += in ChapelBase that checks whether + on the arguments is available. With this change, += will not be applicable for its use in CoMD AccumStencilDist.

[vasslitvinov]

Here is my take on the above alternatives:

(A), (C), (D) are the more general solutions.

(B) would apply to other op= operators, however would not cover the general scenario "a library provides the default implementation".

(E), (F), (F), (G) are geared towards the specifics of the CoMD use of =+ and its definition in ChapelBase.

[Added] Option (C) is implemented in 7440752073 .

[vasslitvinov]

Care needs to be taken with the behavior of pragma "last resort" in the following regard.

Consider the iterative process of gathering applicable candidates: (step1) those visible at the callsite; (step2) if none, those visible at the POI; (step3, if applicable) if none, visible at POI of POI, etc.

If (step1) yields only last-resort candidates and no regular candidates, what do we do?

• (LR-1) gathering is complete, use the last-resort candidates right away, or

• (LR-2) set them aside and proceed to (step2); use last-resort candidates only if none of the steps turned up regular candidates.

Likewise, if there are no candidates at all in (step1), (step2) yields only last-resort candidates, and more step(s) are available, do we (LR-1) use the last-resort candidates right away or (LR-2) set them aside and proceed to (step3) ?

(LR-1) is implemented as of this writing. This causes an unexpected overload of chpl_serialReadWriteRectangular to be chosen in one case, see below. I also suspect that Option (E) for fixing CoMD in the above comment would not work under (LR-1). I am working to implement (LR-2).

The problematic case is exposed when running this test on multiple locales:

test/distributions/replicated/testReplWrites.chpl

The relevant pieces of code are:

//user code
writeln(myReplicatedArray);

// writeln() invokes the following:
proc _array.writeThis(f) {
  _value.dsiSerialWrite(f);
}

module ArrayViewSlice {
  private use ChapelStandard;  // includes DefaultRectangular

  proc ArrayViewSliceArr.dsiSerialWrite(f) {
    chpl_serialReadWriteRectangular(f, arr, privDom);  // CALL-1
  }

}

module DefaultRectangular {

  pragma "last resort"
  proc chpl_serialReadWriteRectangular(f, arr, dom)    // IMPL-1
  { ... }

}

module ReplicatedDist {

  proc chpl_serialReadWriteRectangular(f, arr, dom)    // IMPL-2
    where isReplicatedArr(arr)
  { ... }

}

When resolving CALL-1, the overload IMPL-1 is immediately visible from the call -- without consulting its POI. So it is chosen as the best candidate.

The intention of the code is that the overload IMPL-2 is chosen. It is visible through POI and does not have the "last resort" pragma, so would be chosen by (LR-2).

[vasslitvinov]

@mppf, @bradcray - what are your thoughts on (LR-1) vs. (LR-2) from my previous comment with Replicated ?

I have implemented both options and testing passes. The only things that are holding this PR are choosing between (LR-1) and (LR-2) and among Options (A) through (G) to address CoMD . We might want to use the same approach to handle CoMD and the Replicated example.

[mppf]

I think LR-2 is the right way to handle "last resort". I think we should do (C) for CoMD but I am also comfortable with (G) in that specific case.

[bradcray]

Sorry for the late response here...

I think making "last resort" truly mean "last" (which is how I interpret LR-2) is definitely appealing. Specifically, I think of the += in ChapelBase as meaning "Only use me when there's no better match / nothing else to do." I don't view this approach (which is E, right?) as being particularly CoMD-specific.

Of the other solutions...

• w.r.t. B, I wonder frequently whether operators (generally) should be methods, or whether part of their implementation should be to use a method of a given name if it's available. But I think this is a big change we shouldn't jump into simply for CoMD. That said, this example does add more weight to having some sort of more method-like behavior for operators.

• I think C is definitely reasonable code to write, if a bit clunky. But I prefer the last resort approach.

• G is also intriguing to me, independent of this conversation, though I worry a little bit about (a) increased compile-time for evaluating the where-clause in a fairly common situation (unless we make a specialized += for types that we know have + like a bunch of the built-in types, and (b) making the error message clear. I guess I find it intriguing, but not as appealing as the other choices.

• Neither A, D, or F appeal to me very much

[vasslitvinov]

Turns out that pragma "last resort" does not work smoothly -- independently of this issue and #16158.

Last-resort functions are considered AFTER promotion is attempted. For example:

proc p(i:int) { writeln("p(int)"); }

pragma "last resort"
proc p(arg) { writeln("p(generic)"); }

var A = [1,22];
p(A);

will execute promoted p(int). I have bumped into this a couple of times in the past. Maybe we should look at last-resort functions before promotion?

The impact on this issue is that option (E) -- i.e. mark += with "last resort" -- does not work. Because when invoking += on two arrays of reals, the compiler will prefer promoting proc +=(a: [], b: _desync(a.eltType)) instead of invoking proc +=(lhs, rhs). We want the latter. Anecdotally, something breaks when doing the former.

[mppf]

It's not obvious to me how last resort should work with promotion. Can we make progress on the POI issue by choosing one of the other options? And then make a separate discussion about this question?

[vasslitvinov]

An issue on last resort: #16216