New Issue: Can we simplify the function disambiguation rules?

mppf1 · February 8, 2022, 7:24pm

19195, "mppf", "Can we simplify the function disambiguation rules?", "2022-02-05T13:33:39Z"

https://github.com/chapel-lang/chapel/issues/19195

This issue is about the algorithm for function disambiguation / overload resolution / computing the most specific candidates.

What we have today is described in the language specification here:

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

These rules are fairly complex. The implementation of these rules is here: chapel/compiler/resolution/functionResolution.cpp at main · chapel-lang/chapel · GitHub .

This issue is asking a few questions about the algorithm and the related rules.

Does function disambiguation use a partial order? Should it?

This is especially related to Overload resolution and #19167.

We have a compareSpecificity function that returns -1/0/1 to indicate fn1 is more specific; they are the same level of specificity; or fn2 is more specific.

github.com/chapel-lang/chapel

compiler/resolution/functionResolution.cpp

bf9f12a25


      
          /** Determines if fn1 is a better match than fn2.
           *
           * This function implements the function comparison component of the
           * disambiguation procedure as detailed in section 13.13 of the Chapel
           * language specification.
           *
           * \param candidate1 The function on the left-hand side of the comparison.
           * \param candidate2 The function on the right-hand side of the comparison.
           * \param DC         The disambiguation context.
           * \param ignoreWhere Set to `true` to ignore `where` clauses when
           *                    deciding if one match is better than another.
           *                    This is important for resolving return intent
           *                    overloads.
           *
           * \return -1 if fn1 is a more specific function than f2
           * \return 0 if fn1 and fn2 are equally specific
           * \return 1 if fn2 is a more specific function than f1
           */
          static int compareSpecificity(ResolutionCandidate*         candidate1,

However we have seen some hints that there are problems in this area. Commit aebdceb23e28fd834ee2b071047aad8064240ca2 addressed one surprising behavior (where the order of candidates mattered). Additionally, while I was developing PR #7659, I remember encountering situations where compareSpecificity is not transitive and seeing unexpected ambiguity in that event.

One immediate question is this -- does 0 from compareSpecificity mean "the same specificity" or "these are incomparable"? If it means "these are incomparable" then probably the change in commit aebdceb23e28fd834ee2b071047aad8064240ca2 is not quite right.

See also this comment added in aebdceb23e28fd834ee2b071047aad8064240ca2:

github.com/chapel-lang/chapel

compiler/resolution/functionResolution.cpp

bf9f12a25


      
          // Inherit the notBest status of what we are comparing against
          //
          // If this candidate is equally as good as something that wasn't
          // the best, then it is also not the best (or else there is something
          // terribly wrong with our compareSpecificity function).

A further question is, suppose that compareSpecificity is not transitive. What harm will come of it? Is it always unexpected ambiguity? Or is it possible for the process to choose something that is a worse match than another candidate?

A next step here would be to add some experimental checking to the compiler to understand more about what cases are currently non-transitive, if any:

For a given set of candidates that we see in disambiguateByMatch, check that compareSpecificity is transitive, and report the non-transitive case if not (and bring it up here for discussion)
For all types at the end of function resolution, check that moreSpecific is transitive and report any cases that are not (and bring them up here for discussion) chapel/compiler/resolution/functionResolution.cpp at bf9f12a25b155e77c5f61b16b025a7761a83db26 · chapel-lang/chapel · GitHub

Could we remove some of the complexity of these?

IMO before PR #7659, the function disambiguation rules were already pretty complex, and that PR added the 3 levels of preference which made them even more so. Here we are considering what we might be able to do in order to make the rules less complex.

One idea is to remove most/all of the additional complexity in PR #7659 and instead have the compiler directly handle things like + on integers. At the moment, AFAIK it won't be possible for a user to add their own + on integers that participates in the same disambiguation process due to the overload sets checking. And the more complex disambiguation rules from PR #7659 exist so that we can determine an appropriate type for param expressions such as 1:uint(8) + 32 (with rules that effectively choose the overload that returns the type we want). But it might well be simpler for the language and for the implementation if these cases are handled directly by the compiler, since a user can't add more param types and can't currently add any more implicit conversions (but see #16729 for proposals in that area).

I have occasionally wondered if it would be possible to remove the "prefer int to uint" rule. Also, in my experience, the rules we need here to enable programs that we want to work depends on the set of implicit conversions allowed. For example in #19194 we are discussing removing int -> real implicit conversions. Perhaps we can simplify these rules more if we remove some implicit conversions.

Topic		Replies	Views
Overload resolution Developers	7	287	February 4, 2022
Overloading elementary function Users	15	436	December 5, 2023
Interfaces Users	12	520	January 19, 2022

New Issue: Can we simplify the function disambiguation rules?

Does function disambiguation use a partial order? Should it?

Could we remove some of the complexity of these?

Related topics