!topic LSN on Primitive Visibility, Beaujolais, etc. $Revision: 1.1 $ !reference MS-8.3 !from Tucker Taft $Date: 92/01/09 18:04:40 $ !discussion Bill Easton's section of the Technical Operating Report of the Language Precision Team (LPT) discusses the general issues relating to so-called "Beaujolais" effects, and more specifically how they relate to Ada 9X primitive visibility and preference rules. The 9X type model has been revised since this section was written (see MS version 4.0), and many of the problems identified in the LPT report have been resolved. However, we still have a primitive visibility rule with possible Beaujolais effects in some (relatively unlikely) cases. This LSN investigates slight modifications to the primitive visibility rules which might eliminate these remaining Beaujolais effects, from a semantic viewpoint, an upward compatibility and consistency viewpoint, and from an implementation viewpoint. First of all, here are the rules from MS-8.3;4.0 (slightly revised to distinguish "formal" operand type from "actual" operand type, and result type from result context); A) If a primitively visible operation of type T has a {formal} operand of type T, then it may be considered as a possible meaning of the operation's symbol if an interpretation of the corresponding actual operand has T as its root type (see 3.3). B) If a primitively visible operation of a type T has result type T (this includes all character literals), then it may be considered as a possible meaning of the operation's symbol if the context of the operation's symbol uniquely determines a type that has T as its root type. Rule (A) is pretty straightforward, and it does not introduce Beaujolais effects. Rule (B), which concerns the use of result context for primitive visibility, does have some subtle Beaujolais effects, largely because of the phrase "uniquely determines." To understand all of this, we need a little more background... For the purposes of discussion, let us divide "direct visibility" into three categories: 1) Immediate visibility (when within the immediate scope of an operation); 2) Use visibility (when the operation is declared immediately within the visible part of a package that has been "use"d); 3) Primitive visibility (for an operator or character literal that is a primitive operation of some type; plus all basic operations). A given (non-basic) operation is assigned to the first of these categories that it satisfies. [A SIDE NOTE ON BASIC OPERATIONS: To minimize special case overloading rules, our current intent is to include basic operations (like ":=" and "null") always in the third category (primitive visibility) even where the associated type declaration is immediately or use visible. This may simplify things because, even in Ada 83, such basic operations were always directly visible, even when not immediately or use visible. Furthermore, we expect that it will allow us to remove certain special cases that exist now for the overload resolution rules, to handle things like "null" and string literals (to prevent their being used as an operand of type conversion, for example). This approach may also allow us to say less about exactly "where" the declarations for these basic operations occur, since primitive visibility only depends on their "primitiveness." Finally, we expect that most implementors handle these basic operations as though they were "primitively visible," only considering a particular type's basic operation if an operand or the context demands that type. End of SIDE NOTE.] BEAUJOLAIS EFFECT The current rules can produce a Beaujolais effect as follows: Assume a primitively visible operator is only considered due to unique result context demanding its result type (i.e. it has no operands which allow it to be considered). Now add a use clause which makes the context no longer unique, but which also matches the expression involving the operator without using result-based primitive visibility. This new interpretation is chosen, and the result-based primitively visible one is ignored. For example: procedure P(X : Z.My_Int); -- Call this P.1 -- Assume package Z has not been "used" package Q is procedure P(Y : Integer); -- Call this P.2 end Q; P(1+2); -- Resolves to P.1; "+" on Z.My_Int is primitively visible P(3); -- Resolves to P.1 use Q; P(1+2); -- Resolves to P.2; "+" on Integer is immediately visible -- This is a "Beaujolais" effect. P(3); -- Ambiguous This Beaujolais effect will probably be rare in practice because most expressions have at least one operand which is not a literal. Note that this behavior is upward compatible (and upward "consistent") with Ada 83 because the call "P(1+2)" prior to the use clause would be illegal in Ada 83, and would resolve to P.2 after the "use" clause. The calls of the form "P(3)" would always "resolve" the same way in both Ada 83 and Ada 9X (since they don't involve any primitively-visible operators). POSSIBLE BEAUJOLAIS-FREE ALTERNATIVES The LPT has suggested a slight alteration to rule (B) given above, which simply removes the word "uniquely" from the rule. What this would mean in the example is that P(1+2) would now be ambiguous after the "use" clause, rather than resolving to P.2. This eliminates the Beaujolais effect, but at the expense of upward compatibility. Note however that it does retain upward "consistency," defined to mean that those programs that are legal in both Ada 83 and Ada 9X have the same interpretation. The degree of upward incompatibility introduced by this alteration to rule (B) depends on how much information from inside the expression may be used to resolve the result context. For example, with an aggregate, only the fact that it is an aggregate of some sort may be used to resolve the result context. With a result-based primitively visible operator, may we use the possible interpretations of the operands to help resolve the result context? Suppose we have the following example: procedure P(X : Z.My_Int); -- Call this P.1 package R is procedure P(Y : String); -- Call this P.3 end R; P("abc" & "def"); -- Does not resolve -- (Presuming Z.My_Int does not have a primitive "&"). use R; P("abc" & "def"); -- Does this resolve to P.3? If we use no information from the operands or even the identity of the operator to resolve the result context, then we must assume that could match Z.My_Int. If we use all the information available inside the expression, then we may have to do overload resolution twice. One possible compromise is to use the identity of the operator only to help resolve the result context. This would allow us to eliminate Z.My_Int as a possibility since (presumably) it has no "&" operator. However, the following would still be unresolvable: M : Integer; use Q; -- From first example P(M + 2); -- This does not resolve, since Z.My_Int has a primitive "+" -- so P.1 matches "M+2" (in fact it matches -- + ), and so the result context -- cannot be resolved. Note that Z.My_Int may in fact have a primitive "+" that would work with P(M+2) (e.g. function "+"(Left : Integer; Right : My_Int) return My_Int;) so this ambiguity may be legitimate. This compromise position is still upward consistent, meaning that the compiler will flag all such problems allowing them to be repaired by adding an appropriate qualification. ANOTHER ALTERNATIVE Another alternative is to give up on result-based primitive visibility for operators, and retain it only for character literals, string literals, null, aggregates, and allocators. This means that rule (A) would apply to operators only, and a simplified rule (B) would apply to the others only. This would produce a Beaujolais-free upward compatible situation for operators. For character literals, we will have some upward incompatibility anyway because we will now have two character types (CHARACTER and WIDE_CHARACTER) always in the immediate scope. The additional ambiguity due to making all character literals primitively visible is probably minor. Essentially, result context will be required, just like for null, string literals, and aggregates. Since string literals are probably more frequently used than character literals anyway, it seems unlikely that this will cause any additional problems. Here is a new version of rules A and B: A') If a primitively visible operator of type T has a formal parameter of type T, then it may be considered as a possible meaning of the operator's symbol if an interpretation of the corresponding actual parameter has T as its root type (see 3.3). B') The type of a character literal must be determinable from context, using only the fact that it is a "character type" (as defined in RM 3.5.2). The type of a string literal must be determinable from context, using only the fact that it is a one-dimensional array type whose component type is a character type. [Analagous rules, borrowed from Ada 83, for null, aggregates, and allocators...] [NOTE FOR OOP FANS: One way to view all of the subrules of (B') is to treat these literals as being of an appropriate class-wide type, but one whose root type is anonymous and has no primitive operators, and does not allow conversion. For example, imagine that all character types are implicitly derived from some anonymous root_character, which has no operators. A character literal would then be of type root_character'CLASS, which would match any character type, but would never "trigger" rule (A'), since the root character type has no primitive operators. Anonymous types root_access, root_string, root_type_with_aggregates, and root_access_to_T (for allocators) could be imagined. In any case, there is probably very little advantage in creating this extra semantic baggage just to explain result-based resolution of char/string/access literals, but it might be a useful implementation model. End of Note.] CONCLUSION Since result-based primitive visibility for operators was the place where essentially all of the implementation, Beaujolais, and upward incompatibility difficulties existed, eliminating result-based primitive visibility for operators seems to be a useful simplification. IMPLEMENTATION APPROACHES For the record, we include here a short discussion of overload resolution approaches. Since the conclusion of this LSN was to drop result-based primitive visibility for operators, we don't bother with any further implementation analysis other than this overview... There are two basic approaches to overload resolution (there are probably lots of others, as well as variations on these two, but lets stick with these two for now): 1) Bottom-up approach, where a bottom-up walk is performed, generating possible interpretations, and pruning them out by applying the overload resolution rules. If, upon reaching the top, there is not exactly one interpretation still "alive," the construct cannot be resolved. If there is exactly one, this interpretation is passed back down, and it may still be rejected due to other legality rules. 2) Top-down approach, where each possible meaning for the top of the construct is tried in a depth-first walk. If exactly one succeeds, then the "post-resolution" checks are performed to ensure legality. If more or less than one succeeds, then the construct cannot be resolved. Most implementations of which we are aware use the bottom-up approach (roughly), often with some kind of optimization to avoid generating all interpretations involving predefined operators. A notable exception is the RR implementation, which uses the top-down approach, and separately checks all predefined-operator interpretations.