Doc Number: X3J16/94-0031 WG21/N0418 Date: January 25, 1994 Project: Programming Language C++ Ref Doc: 93-0148/N0355 Reply to: Sam Kendall Sam.Kendall@East.Sun.COM SMLI Doc Number: SMLI-94-0029 NOTES ON OVERLOADING RESOLUTION Sam Kendall Sun Microsystems Laboratories, Inc. (c)Copyright 1994, Sun Microsystems, Inc. All Rights Reserved. INTRODUCTION This paper consists of some notes on overloading resolution. It takes as a base the overloading resolution algorithm Jon Shopiro outlined in Munich. Section 1 is an outline of that algorithm, from which important details have been simplified. Section 2 discusses some of the simplifications made in section 1. Section 3 is several notes to prepare for section 4, which is a proposal for defining the calling of member functions and user-defined operators. Sections 1 and 2 are revised versions of my c++std-core-3257. Following Jon, I have used some elementary mathematical notation and language. I think the final description -- even in the WP -- must use some too in covering these topics. Otherwise it will be ambiguous. Much better that a reader has to look up a phrase like "partial order" than that we write something unclear. Thanks to Jon Shopiro for having the nice idea outlined in section 1 in the first place, and to several others (whose names are mentioned below) for commenting on parts of these notes. 1. OUTLINE OF SIMPLIFIED OVERLOADING RESOLUTION ALGORITHM We start with a call f(arg1, arg2, [...], argM) Each argi has a type; we aren't worrying about its other attributes here. For this reason we speak of argi and its type interchangeably. The sequence of argument types [type(arg1), type(arg2), [...], type(argM)] is called the _argument vector_. (The terms "vector" and "sequence" are synonyms.) f is an overloaded function name; the overloadings are f1(T11, T12, [...], T1M) f2(T21, T22, [...], T2M) ... fN(TN1, TN2, [...], TNM) Also assume that each fj has the same number of parameters as the call has arguments; here we ignore differing numbers of arguments, default arguments, and the ellipsis parameter. Each sequence of parameter types [Tj1, [...], TjM] is called a _parameter vector_. A _conversion_ is a conversion identifier and a pair of types [c, T1, T2]. The conversion identifier says what kind of conversion it is: trivial, promotion, etc., for purposes of enabling two conversion to be compared (see step 2). This algorithm is O(n^2) for n overloadings, since you have to compare all pairs of overloadings. The 13.2 algorithm is linear, I think. However, this algorithm is much easier to specify. We now list the steps of overloading resolution. Actually steps 1a through 3 are definitions rather than steps. Step 1a: UCS ------------ "Given a parameter type and an argument type, find a unique well-formed conversion sequence from the argument to the parameter." Step 1a defines an (abstract) function UCS(parameter_type, argument_type) UCS yields either a conversion sequence or an error; the error results if there is either zero or more than one well-formed conversion sequence. Jon felt that this step was best specified by an exhaustive specification of the possible conversion sequences between different categories of types; this would eliminate the need to talk about how to eliminate loops, etc. I disagreed (and still do); I felt that conversion sequences should still be built up out of primitive conversions (see my "Unifying Built-In Operators..." paper for one way to list all the conversions), and rules be written down for identifying a unique conversion sequence. Examples are written as initializations rather than as function calls; it's the same mechanism (and the WP can avoid redundancy by reflecting this: step 1 should be entirely documented in chapter 8 and omitted from chapter 13). struct B {}; struct D : B {}; D* p1; const B* p2 = p1; // #1 #1 seems to have two conversion sequences possible: D* --> const D* --> const B* D* --> B* --> const B* But of course this is not a real ambiguity. Some means must be found to prefer one to the other. char c = 5; // #2 #2 has an infinite number of possible sequences: int --> double --> char // overlong sequence int --> char --> int --> char // loop int --> char // the right answer How do we prefer the last sequence listed? This is the kind of thing addressed, somewhat unclearly, by 13.2/7-8. struct B; struct C; struct D; struct A { operator C*(); operator D*(); }; struct B {}; struct C : B {}; struct D : B {}; A a; B* bp = a; // #3 #3 is truly an ambiguity; that is, UCS yields an error and so the initialization is not well-formed. The possible conversion sequences are A --> C* --> B* and A --> D* --> B*. Step 1b: Eligible overloadings ------------------------------ "Select the eligible overloadings." Perform step 1a for each pair [argi, Tji]. The _eligible overloadings_ are all fj such that UCS(argi, Tji) yields a unique conversion. It's okay for UCS to yield an error for some overloadings; this just renders that overloading ineligible, rather than rendering the entire call expression ill-formed. Step 2a: A A --> T2 A --> T3 The reality is more complicated. I believe we get the following user-defined conversions T1 --> A const T1 --> A // if T1 is not a reference type volatile T1 --> A // if T1 is not a reference type const volatile T1 --> A // if T1 is not a reference type A& --> T2 const A& --> T3 This latter list is what results from considering A's constructor and its two operator conversions AS functions; in other words, we consider how those three functions can legally be called without any conversions on the arguments. S7) Calling of member functions and user-defined operators is not specified. See sections 3 and 4 below. S8) Deciding between a user-defined and a builtin operator is not defined. See my paper "Unifying Built-In Operators and User-Defined Functions, Revision 1", N0375R1 = 93-0168R1, for one possible scheme. 3. NOTES ON MEMBER FUNCTIONS AND USER-DEFINED OPERATORS 3.1 Function Call Syntaxes and Overloading Combinations Here is a table of what kind of (overloaded) functions can be called using the two syntaxes: Table 1: Function Call Syntaxes and Overloading Combinations a. Non-member function b. Nonstatic member function c. Static member function Syntax Combinations Explanation ------ ------------ ----------- E(args) a, bc In one call the overloadings may be non-member functions, or they may be (nonstatic and/or static) member functions; but not both. @E or E1@E2 ab Operators may not be static member functions. ("@" stands for any operator.) Caveats: - We ignore user-defined operator(), classes in the function position of a function call, and user-defined conversions at the function position of a function call. - Template-ness is orthogonal to the categories a, b, c. - The E(args) syntax covers explicit member function calls. 3.2 Lemma Here is a lemma I'm counting on: when you call overloaded member functions using the `E(args)' syntax, ALL THE OVERLOADINGS ARE DEFINED IN THE SAME CLASS. For example: struct A { void f(int); }; struct B { void f(double); }; struct C : A, B {}; C c; c.f(5); // Ill-formed; cannot inherit f's from two // different classes. In e-mail discussion three people (Scott Turner, Jon Shopiro, Frank Buschmann) said they thought this lemma was correct. However, Josee Lajoie and Frank B. were unhappy with it, feeling that perhaps the language should allow struct C to inherit both f's in the example. My sense is that the restriction -- struct C can define member functions "f", or it can inherit member functions "f" from at most one class, but not both -- was a very deliberate choice by Bjarne, and that lifting the restriction would make writing inherited classes error-prone. But if the restriction is lifted, this proposal will have to get more complicated. Note that the lemma does NOT hold for the @E or E1@E2 syntaxes. 3.3 Argument Vectors and Parameter Vectors In sections 1 and 4 I talk about argument vectors and parameter vectors. This notion must be made more precise. For example, what other attribute besides type are included in each? I think the argument vector must include all the expression attributes -- including the possibility of more than one type for an argument -- while the parameter vector is just types. 4. TYPE ANALYSIS OF EXPRESSIONS INVOLVING MEMBER FUNCTIONS 4.1. Introduction Here is a scheme for type analysis of expressions involving member functions. This builds upon my paper "Expression Attributes", N0365 = 93-0158. I am sorry to depend upon that paper in this discussion, but the topic is so complicated that I need a base of notation to build on. This scheme is either innovative in its simplicity or really odd, depending on your point of view. It is the first proposal I know of that has a rigorous division of responsibility between the . and () operators in the expression `a.f()'. 4.2. The Innovations Here come the example and attributes: void of(); // ordinary function struct A { static void sf(); void f(); void cf() const; }; A a; const A ca; void A::f() { // the following table shows expressions in this context } Line Expr Attributes ---- ---- ---------- 1 of Type: void (); Lvalue 2 sf Type: void (); Lvalue 3 f Type: void (); NS_member: A 4 cf Type: void () const; NS_member: A 5 a.sf Type: void (); Lvalue 6 ca.sf Type: void (); Lvalue 7 a.f Type: void () 8 a.cf Type: void () const 9 ca.f ***ill-formed*** 10 ca.cf Type: void () I think everyone will agree with the lines 1-6. Lines 7-8 contain the first innovation: the type of a.f and a.cf is exactly the same as that of f and cf, respectively. The only thing that the dot operator does is to strip off the "NS_member: A" attribute. And there is no hint of "member-ness" left, except that the expressions are not lvalues. Lines 9-10 contain the second innovation. Consider line 10 first. In the type of ca.cf, there is no const qualifier! The const on ca has "cancelled out" the const on cf. So ca.cf has the same type as a.f; this matches the reality that they behave identically. Now consider line 9. There is no const on f to be cancelled out, so we call the expression ill-formed. This is a slight C++ "contraction" I am proposing; in the WP, `ca.f' is allowed, although you can't call it or do anything else with it. The general rule is roughly this: Given an expression E . F E is an expression of type `cv1 C1' and C1 is a class type; F is a nonstatic member function of class C2, of type `T (argtypes) cv2'; then * if C2 is not an accessible, unambiguous base class of C1, or if it is not true that cv2 >= cv1, the expression is ill-formed; * otherwise, the expression is of type T (argtypes) cv3 where cv3 = cv2 - cv1. Subtraction of cv-qualifiers has the obvious meaning. Note that this rule is very similar to the rule for nonstatic data members. The difference is that for data members we ADD the two sets of cv-qualifiers, while for member functions we SUBTRACT one from the other. Also, of course, if F is an overloaded name, the rule is applied to each overloading. 4.3. Calling How do we call the result of the dot operator? We could call a.f and ca.cf (lines 7 and 10) exactly as if they were normal functions. But what do we do with the `const' hanging off of a.cf (line 8)? To explore this question we need a slightly more complicated example: struct B { void f(float); void f(double) const; }; B b; Line Expr Attributes ---- ---- ---------- 11 f { [ Type: void (float) ; NS_member: B ], [ Type: void (double) const; NS_member: B ] } 12 b.f { [ Type: void (float) ], [ Type: void (double) const ] } Now we have the following calls with their desired results: b.f(1.0f); // f(float) b.f(1.0); // f(double) const b.f(1); // f(float) Here's how we make our scheme get the desired results: Consider every call to have an extra argument of type `T'. Each function has a corresponding extra parameter of type `cv T', where `cv' is the cv-qualifier(s) of the function type. T can be almost any data type, because the result of the dot operator has "forgotten" the type of the left-hand operand. Think of it as an opaque object type, or think of it as "int" if you want something concrete. Given this scheme, we have: Argument type vectors (in each call, respectively): T, float T, double T, int Parameter type vectors (for f(float) and f(double) const, respectively): T, float const T, double Given these vectors, it is easy to see that we get the desired results. (If you work it out, note that int converts to float or double without preference.) How can we get away with ignoring the type of the class object in overloading resolution? The answer is that when we call a set of overloaded member functions, all the overloadings are defined in the same class. (This is my lemma above.) Because all the overloadings are members of the same class, for overloading resolution it doesn't matter what that class is. A solution to the problem of resolving calls to overloaded static vs. nonstatic member functions falls out of this scheme. This scheme applies to all uses of the `()' (function call) operator, not just uses involving member functions; but unless at least one cv-qualified member function is involved, the extra "T" argument has no effect. 4.4. Rationale This scheme is motivated by trying to find the simplest possible expression-attribute description for overloading resolution. I feel that this scheme is the natural one suggested by the syntax. Let me expand on this point. The syntax suggests that the result of the dot operator is *something*. When I say a.f() // A, a, and f as in section 2 what, in the abstract, is `a.f'? It is a _closure_, or more specifically a _curry_. That is to say, it is a function taking no arguments that, when called, will pass the object `a' to the member function `f'. In my scheme only the fact that this curry is an rvalue prevents us from taking its address, eg: void (*fp)() = a.f; // ill-formed and this would be darned useful -- ask any GUI toolkit designer. The basic decision one has to make in designing any callback scheme -- do I use ordinary functions or member functions? -- would become unnecessary. I am not proposing this extension. But it is a possibility for the future. My scheme permits it to be type-analyzed in the most straightforward possible way. As a general philosophy, I've come to feel that semantics must be rigorously syntax-driven to be completely clear. This means that we have to analyze `E.F' and say what its attributes are before we can analyze `E.F(args)'. Why? Because `E.F' isn't always called immediately. Here are several expressions involving E.F but not calling it: E.F; // expression statement (E.F) typeof (E.F) sizeof (E.F) &E.F E.F, 0 0, E.F If we specify the attributes of E.F clearly, then some general rules govern whether each of the above is ill-formed, and its meaning if it is well-formed. Otherwise, we'll have to write down lots and lots of special cases in the WP -- and we'll inevitably miss some. Two other simplicities are worth noting in this section. First, dotting of member functions works almost the same as dotting of data members; the difference is in the handling of cv-qualifiers on the member. And second, the open issue of static vs. nonstatic member function overloading is resolved. 4.5. Calls within a Member Function One thing I have not addressed is calls to a member function WITHOUT an explicit dot operator; informally, I'm talking about identifiers that have `this->' implicitly prepended. This actually has nothing to do with member FUNCTIONS in particular; it applies to all members. We need to say something like "expressions with the NS_member (nonstatic member) attribute are treated as though `this->' is prepended to them in such-and-such contexts." This happens to an expression M with any *except* the following operators: (M) E1.M E->M &M if the Class_qualifier attribute is also present This can be said more precisely. Maybe the WP already does; I can't remember where this is in the WP. 4.6. User-Defined Operators The method for calling a user-defined operator works differently than the method for explicit function calling. This is because, as we see from table 1, these two methods must solve different tough problems. `E(args)' allows the tough problem that static and nonstatic member functions will compete. @E or E1@E2, on the other hand, allows the tough problem that non-member and nonstatic member functions will compete. Luckily, static member functions cannot be operators. For user-defined operators, then, we use a method more like section 13.2. Operators that are member functions are considered to have an additional first element of their parameter vector, just like 13.2/4-5. This allows conflicts like the following to be resolved correctly: struct D; struct B { void operator+(D&); }; struct D : B {}; void operator+(D&, B&); B b; D d; void f() { d + d; // ambiguous } Here the argument vector is D, D and the parameter vectors are B&, D& // first parameter only allows some conversions D&, B& >From this the ambiguity is clear. It may appear odd that the following two calls: x.operator@(y) x@y are resolved using different schemes. Here is why: - The two schemes must solve different problems. The function call operator must deal with static vs. nonstatic member function conflict, while the x@y syntax must deal with nonmember function vs. nonstatic member function conflict. Furthermore, the x@y syntax must deal with conflicts between nonstatic member functions of different classes, while the function call operator doesn't have to. - The different syntaxes suggest different schemes. Note also that where both schemes apply, they get the same answer.