dl@g.g.oswego.edu (Doug Lea) (10/20/90)
I'm considering submitting the following to X3J16 (ANSI C++). But before I do, I'd like to get more feedback. All comments would be welcome, in an attempt to make this as strong and useful a proposal as possible. Please email replies directly (dl@g.oswego.edu). Thanks! ----------------- % Format with latex \documentstyle{article} \begin{document} \title{{X3J16 Proposal:} \\ {Array References}} \author{Doug Lea} %\date{} \maketitle \section{The Problem} In C and C++, a {\tt T*} may ambiguously refer to either a pointer to a single object, or a pointer to the first of an array of objects. (Throughout this proposal {\tt T} is a stand-in for any first-class C++ type.) This ambiguity is alternately considered to be among C's major strengths, in that it allows the total integration of pointers and arrays, and as its greatest weakness in providing the infrastructure for C++, in that it compromises type safety and impedes optimizability of the kinds of high-level constructs that are much more characteristic of C++ than C programs. \subsection{Example 1} \samepage{\begin{verbatim} class B { public: int bvar; virtual int f() { return 0; } }; \end{verbatim}} \samepage{\begin{verbatim} class D : public B { public: int dvar; int f() { return 1; } }; \end{verbatim}} \samepage{\begin{verbatim} void useB(B* p) { int i = p[1].f() + p[1].bvar; } \end{verbatim}} \samepage{\begin{verbatim} main() { B single_b; useB(&single_b); // (1) B array_of_b[10]; useB(array_of_b); // (2) D single_d; useB(&single_d); // (3) D array_of_d[10]; useB(array_of_d); // (4) B* bp = 0; useB(bp); // (5) } \end{verbatim}} The safety problems are that a client (caller) of {\tt useB} cannot tell by {\tt useB}'s signature whether any or all of \begin{enumerate} \item A pointer to a single B \item An array of B's \item A pointer to a single D \item An array of D's \item A null pointer \end{enumerate} \noindent are legal arguments to {\tt useB}. As it turns out, only an array of B's is really supported: Calls (1) and (3) are unsupported because {\tt useB} attempts to treat the scalars {\tt single\_b} and {\tt single\_d} as arrays, and call (4) is unsupported because C++ arrays are necessarily {\em homogeneous}, (i.e., filled with elements all of the same exact class) requiring that the declared type ({\tt B}) be treated as an {\em exact} type when the compiler determines the byte offset (via {\tt sizeof(B)}) of the element {\tt p[1]}. Since {\tt sizeof(B) != sizeof(D)}, the computed offset is incorrect. Call (5) is unsupported since {\tt useB} does not check whether the pointer is null. Thus calls (1), (3), (4) and (5) are type-legal but wrong. There ought to be a way for programmers to express such intentions. This is a more serious type safety compromise in C++ than in C, since ambiguities due to subclassing are not present in C. \subsection{Example 2} \samepage{\begin{verbatim} class intVec { int sz; int* data; public: intVec(int s) :sz(s), data(new int[sz]) {} ~intVec() { delete [] data; } int& operator[] (int i) { return data[i]; } int length() { return sz; } }; \end{verbatim}} \samepage{\begin{verbatim} void clear(intVec& v) { for (int i = 0; i < v.length(); ++i) v[i] = 0; } \end{verbatim}} Any C++ compiler attempting to perform standard optimizations on {\tt clear} will be bothered by a fundamental obstacle. Even though {\tt length()} is inlined, because {\tt v.data} is allowed to point to {\em any} int, a compiler must conservatively assume that {\tt v.data} {\em could} point to {\tt v.sz}, that could in turn be set to zero within the assignment statement. This means that {\tt v.sz} must be retrieved from memory on each iteration rather than being kept in a register, or more importantly, being used as a loop constant that would allow this code to be transformed into the essentially optimal C-like \samepage{\begin{verbatim} { int* p = v.data; int* fence = &v.data[v.sz]; while (p != fence) *p++ = 0; } \end{verbatim}} \noindent or even a vectorization of this loop on a machine supporting such things. Among the basic efficiency differences between C and C++ programming is that C programmers who are interested in guaranteeing efficient performance can always manually rewrite functions like {\tt clear} in such a manner themselves. However, because of data encapsulation, C++ programmers cannot obtain low-level data access. Since only compilers are allowed to (safely) break encapsulation, programmers must rely on compilers to optimize functions much more than C programmers do. Thus, optimizability issues will continue to play a far greater role in C++ than they have in C. Programmers and libraries creating utility classes like {\tt intVec} will discover surprising and intractable efficiency losses for doing so unless these issues are addressed. This is an increasingly important issue for some users. Programmers will not always heed the standard advice (e.g., ARM, p 137) to create and use array-like classes instead of C constructs if they obtain noticeably slower code when doing so. It is easy to concoct larger examples where this kind of problem causes much more devastating optimization failures. This is not the sort of issue that can {\em always} be solved by merely creating cleverer compilers that attempt to discern for themselves whether a variable is serving as a pointer to a scalar versus an array. Moreover, even if compilers were to be able to handle the majority of such cases via advanced dataflow techniques, the programmer type safety issues remain: It is useful for the {\tt intVec} author to make crystal clear to other programmers, not just the compiler, that {\tt data} must point to an array, not a scalar. Programmers who desire greater type safety and optimizability need to have a mechanism to express the necessary constraints in a manner that does {\em not} require any other changes to C++, so that existing code continues to be accepted. \section{A Solution} Perhaps surprisingly, C++ already possesses the basic construct needed to solve many of these problems, the array reference. It is legal to declare references to arrays in either of two forms: \begin{itemize} \item ``Open array references'' that do not specify array capacity, denoted via {\tt T (\&open\_ref)[]} \item ``Closed array references'', that do specify capacity, denoted via {\tt T (\&closed\_ref)[N]}, where {\tt N} is a {\em compile-time} constant). \end{itemize} The fact that the syntax for declaring and using array references is very awkward may have somehow contributed to the fact that their basic semantics and properties have apparently never been fully spelled out.\footnote{Readers of the present proposal may find many syntactic constructs difficult to immediately grasp. My only defense is that I did not design this syntax.} The present proposal examines these issues and proposes answers in ways that maximally improve both type safety and optimizability, while also maintaining perfect back-compatibility. If these issues are settled, perhaps programmers will become accustomed to creating simple {\tt typedefs} that eliminate some of their awkwardness. This proposal does not go so far as to suggest particular wording changes of particular sections of the draft ARM. Instead, the basic issues are surveyed, and precise rules and their consequences are discussed. It should be a relatively easy matter to integrate these into the corresponding sections of the standard. In fact, with only a few (indicated) exceptions, there is nothing in this proposal that directly contradicts the ARM. Thus, it may be viewed as merely an interpretation of the utility of array references and their implementation. In other words, regardless of agreement on the details of this proposal, the semantics of array references probably need to be addressed by X3J16, since (1) they are not otherwise completely defined in the ARM, (2) current C++ compilers cannot be depended on to provide any consistent semantics for this construct, and (3) if, say, only one C++ compiler were to implement the interpretation discussed here, and programmers were to regularly exploit this support, serious incompatibilities could result. \section{Representational Properties} In C++, a reference is merely an ``alias''. As discussed, for example, in the ARM, p 153, declaration of a reference does not automatically entail the creation of a behind-the-scenes pointer requiring dereferencing. In fact array references {\em never} require extra indirection in order to access the base of the referenced array. Any {\tt T (\&)[]} or {\tt T (\&)[N]} may be internally represented in precisely the same fashion as a as {\tt T param[]} or {\tt T*}, i.e., via a pointer to the first cell of the array.\footnote{While it is not clear to me whether X3J16 can mandate this kind of economical representation of array references, an important aspect of the present proposal is that the advantages of array references may be obtained without additional overhead over other forms.} For example, all three of the following might generate precisely the same machine code: \samepage{\begin{verbatim} void strcpy1(char* s, const char* t) { for (int i = 0; t[i] != 0; ++i) s[i] = t[i]; } \end{verbatim}} \samepage{\begin{verbatim} void strcpy2(char s[], const char t[]) { for (int i = 0; t[i] != 0; ++i) s[i] = t[i]; } \end{verbatim}} \samepage{\begin{verbatim} void strcpy3(char (&s)[], const char (&t)[]) { for (int i = 0; t[i] != 0; ++i) s[i] = t[i]; } \end{verbatim}} The only programmer-visible difference is type safety. For example, it should be illegal to write {\tt char c; strcpy3(\&c, \&c);}. While (as discussed below) {\tt T param[]} and {\tt T* p} are often used interchangeably, the otherwise parallel constructs {\tt T (\&aref)[]} and {\tt T* (\&ptr)} are representationally distinct, and thus require stronger type enforcement. \section{First Class Status} Array references share many similarities with the C {\tt T param[]} construct (i.e., an array declared as a function parameter, as in {\tt strcpy2}). They differ in two important respects: While {\tt T param[]} is only legal in parameter declarations (and a few other miscellaneous spots), and can almost always be used interchangeably with {\tt T*}, array references are legal wherever any kind of reference is legal, and cannot be interpreted as equivalent to {\tt T*}. Use of array references clears up some problems encountered in the above examples: \subsection{Example 1, revisited} \samepage{\begin{verbatim} void useB2(B (&a)[]) { int i = a[1].f() + a[1].bvar; } \end{verbatim}} \samepage{\begin{verbatim} main() { B single_b; useB2(&single_b); // (1) ERROR B array_of_b[10]; useB2(array_of_b); // (2) D single_d; useB2(&single_d); // (3) ERROR D array_of_d[10]; useB2(array_of_d); // (4) ERROR B* bp = 0; useB(bp); // (5) ERROR } \end{verbatim}} Here, the calls that were previously legal but unsafe would be caught at compile time, assuming implementation of the declaration and matching rules to be described below. Additionally, an interesting minor optimization can be performed. Since C++ arrays are necessarily homogenous, the virtual call {\tt a[1].f()} can be resolved at compile time. It must be B's version of {\tt f()} being called, not any other. \subsection{Example 2, revisited} \samepage{\begin{verbatim} class intVec { int sz; int (&data)[]; public: intVec(int s) :sz(s), data((int(&)[])(new int[sz])){} ~intVec() { delete [] &(data[0]); } int& operator[] (int i) { return data[i]; } int length() { return sz; } }; \end{verbatim}} \samepage{\begin{verbatim} void clear(intVec& v) { for (int i = 0; i < v.length(); ++i) v[i] = 0; } \end{verbatim}} Since {\tt v.data} must {\em not} refer to a scalar, the optimization otherwise missed inside of {\tt clear} can be handled. (The odd mechanics of integrating array references with the {\tt new} and {\tt delete} operators are addressed below.) \section{Declaration and type-matching issues} Examples have so far only used open array references. However, closed array references are also occasionally useful. In fact, the two constructs differ enough that separate sets of rules must be created to handle them. By definition, an open array reference can serve as an alias for an array with any number of elements, with the actual number of elements often unknown to the programmer. Declaration of a closed array reference represents a stronger commitment on the part of the programmer. Since, to remain backwards compatibity, closed array references must only use compile-time constants for array bounds, they are less often usable.\footnote{Their utility could be marginally improved by extending the typesafe C++ {\em conformance} type matching rules to array references, so that a reference to, say 100 ints could be attached to an array of 200 ints. Unfortunately, this strategy conflicts with the assumptions of C matrix operations.} Since the little-used {\tt T param[]} construct represents a weaker version of array references, one could create rules to enable transformation from one form to the other in those cases where it is unambigously safe. However, because the {\tt T param[]} construct cannot currently be depended on be considered distinct from {\tt T*} (C and C++ compilers traditionally treat them as synonyms) a simpler strategy is to formalize this type equivalence (as is implicit in the ARM, p 138, as well as in ANSI C). This then allows simpler rules for dealing with array references, as opposed to either construct. \subsection{Rules} Given these considerations, the necessary rules for declaring array references should be clear: An open array reference, {\tt T (\&r)[]} may alias \begin{itemize} \item any array object {\tt T a[N]}, or \item an array object referenced by a closed array reference, {\tt T (\&cr)[N]}, or \item an array object referenced by another {\tt T (\&or)[]}; \end{itemize} \noindent where {\tt T} must be an {\em exact} type match, not a subclass, because of C++ homogeneity restrictions on arrays. A closed array reference, {\tt T (\&r)[N]} may alias \begin{itemize} \item an array object {\tt T a[N]}, or \item an array object referenced by another {\tt T (\&cr)[N]},; \end{itemize} \noindent again with the exactness restriction. No provision is made for implicitly coercing an open to a closed array reference. As is always the case, explicit coercions are available, and might even be useful by those who are aware of their inherent dangers. (Casts and coercions are, of course, dangerous, because compilers are generally allowed to {\em believe} in the veracity of declared types, which might lead to transformations and optimizations that fail to make sense for a casted object.) No additional rules are required to support multidimensional arrays or matrices. None of these rules are inconsistent with the ARM. Indeed, some are already implicit in other definitions and rules in the ARM, and appear consistent with at least some of the observed behavior of some C++ compilers. \subsection{Relation to {\tt T*}} C requires that a {\tt T*} pointer may be implicitly coerced into a {\tt T []}, and vice versa. But there is every reason to resist implicit coercions between {\tt T*} and array references. In passing, it may be noted that coercions may be used in order to create references to subarrays: \samepage{\begin{verbatim} T a[200]; T (&suba)[50] = (T (&r)[50])(&a[150]); \end{verbatim}} \subsection{Overloading} Overloading sensitivity and resolution rules, and type matching generally, should be governed by the above requirements. For example, function {\tt void f(int (\&a)[])} would be distinguishable from void {\tt f(int* p)} (which is, according to the ARM, p138, the same function as {\tt f(int param[])}). While sound, this has a surprising effect: \samepage{\vspace{-0.5pt}\begin{verbatim} extern void f(int*); extern void f(int (&)[]); int x[100]; f(x); // ambiguous int (&rx)[100] = x; f(rx); // call array reference version \end{verbatim}} Unless changes in the overload resolution policies are made, programmers will have to refrain from overloading pointer versions of functions in programs using array references. Such issues have interesting consequences for C++ library standardization. For example, should the C library version of {\tt strcpy} have a C++ prototype along the lines of {\tt strcpy1} or of {\tt strcpy3} above? \section{Assignment} In C++, reference assignment (as opposed to initialization) always entails {\em deep copy} semantics, which in the case of array references, imply the need for array copies. However, this conflicts with the set of C rules that prevent array copies from ever automatically occuring, even in those cases where the bounds of the copy are determinable at compile time. Hence, the most conservative strategy is to simply make array reference assignments illegal, in the same manner that array assignments are illegal. For example, \samepage{\vspace{-0.5pt}\begin{verbatim} T x[100]; T (&rx)[100] = x; T y[100]; T (&ry)[100] = y; x = y; // ERROR rx = y; // ERROR x = ry; // ERROR \end{verbatim}} \section{Array Pointers} Array references fail to clear up safety and efficiency issues in those cases where pointers are required instead of references. Just as it is legal to define a reference to an array, it is legal (and again, awkward) to define a pointer to an array via \begin{itemize} \item ``Open array pointers'' that do not specify array capacity, denoted via {\tt T (*open\_ptr)[]} \item ``Closed array pointers'' that do specify capacity, denoted via {\tt T (*closed\_ptr)[N]}, where {\tt N} is a {\em compile-time} constant). \end{itemize} These have similar representational properties as array references. They do not require additional indirection. The most important situation in which array pointers are required is in dealing with allocation and destruction of arrays of objects. The C++ definitions of the ``vector'' versions of {\tt new} and {\tt delete} operators accentuate the scalar versus array pointer ambiguity found in C. While {\tt vector\_new} actually returns a pointer to an array of objects ({\tt T (*)[]}), it is typed as returning a simple pointer ({\tt T*}). Similarly, the argument for {\tt vector\_delete} should be ({\tt T (*)[]} but is listed as {\tt T*}. This type laxity allows many common programming errors to remain uncaught by compilers. For example, in \samepage{\vspace{-5.0pt}\begin{verbatim} B* bp = new D[100]; /* ... */ delete [] bp; \end{verbatim}} \noindent the base ({\tt B}) element size step would be {\em incorrectly} used to traverse through the array of {\tt D}s while calling destructors, with indeterminate (but surely unpleasant) run time consequences. Additionally, current definitions require the kinds of machinations seen in the {\tt intVec} constructor and destructor in order to ``coerce'' arguments into their logically correct form. The solution to this is first solidify rules for array pointers, and then to correctly define the type of {\tt vector\_new} and {\tt vector\_delete}. \subsection{Rules} Rules for declaring and initializing array pointers should correspond exactly to those for references: \begin{itemize} \item An open array pointer {\tt T (*p)[]} may point to anything that an open array reference {\tt T (\&r)[]} may refer to. \item A closed array pointer {\tt T (*p)[N]} may point to anything that a closed array reference {\tt T (\&r)[N]} may refer to. \end{itemize} For example, \samepage{\vspace{-5.0pt}\begin{verbatim} T x[100]; T y[200]; T (*p)[] = &x; // p points to x *p = 17; // ERROR (*p)[0] = 17; // set x[0] = 17 T (*q)[100] = &x; // q points to x (*q)[1] = 2; // set x[1] = 2 T (&r)[] = y; // r refers to y p = &r; // repoint p to y (*p)[2] = 49; // set y[2] = 49 q = p; // ERROR p = q; // OK \end{verbatim}} Related issues, including overloading sensitivity and assignment, are also identical to those listed described for array references. \subsection{Relation to {\tt T*}} While, because of lack of existing precedent, there is no need to specially consider the intercoercibility of array references and simple pointers, there is a great deal of C++ code that relies on the representational equivalence and lack of type discernment between {\tt T*} and {\tt T (*)[]}. Requiring that these forms not freely intercoerce is clearly most defensible. The greatest impact would be on {\tt vector\_new} and {\tt vector\_delete}. A new set of rules, conflicting only in type details with the existing ARM (e.g., p60), are needed stating that \begin{itemize} \item The form {\tt new T[ expression ]} invokes {\tt vector\_new} and returns a {\tt T (*)[]}. \item The form {\tt delete[] arg} requires that {\tt arg} have exact type {\tt T (*)[]} and calls {\tt vector\_delete}, returning {\tt void}. \item {\tt vector\_new} and {\tt vector\_delete} are not overloadable. \end{itemize} For example, given this, the {\tt intVec} constructor and destructor could be rewritten intelligibly, in a manner perfectly analogous to those allocating and freeing scalars: \samepage{\begin{verbatim} class intVec { //... intVec(int s) :sz(s), data(*(new int[sz])) {} ~intVec() { delete [] &data); } //... }; \end{verbatim}} These changes would invalidate existing code of the form \samepage{\vspace{-5.0pt}\begin{verbatim} T* p = new T[100]; /* ... */ delete [] p; \end{verbatim}} \noindent There are two possible ways to deal with this: \begin{enumerate} \item Phase in the changes. \item Allow {\tt T*} and {\tt T(*)[]} to silently, ``trivially'' intercoerce. \end{enumerate} Choosing the second option negates {\em all} type safety advantages. \section{Homogeneity and type safety} As discussed in my (mainly unrelated) ``Customization in C++'' paper (1990 USENIX C++ conference), it is difficult in C++ to express the fact that a function is {\em intentionally} type-specific, properly working for a particular class, but not necessarily for subclasses. As noted above, this is among the issues successfully addressed by the the use of array references in the special case of functions requiring homogeneous array arguments. The most common and important examples are ``homogeneous object container classes'' like simple stacks, queues, sets, lists, etc., , in which {\em copies} of objects (created via {\tt X(const X\&)} or {\tt X::operator = (const X\&)}) passed by reference into an insertion member function are placed inside a container. Such methods are type-specific, since exact versions of the copy constructor and/or assignment operator must be hard-wired into implementations. It is almost always the class author's intention to disallow {\tt sub-T} arguments, in order to prevent suprising and undesirable ``chopped copies'' and unintentional insertion of objects without exact type {\tt T}. Such containers bear more than a passing similarity to C arrays. For both efficient implementability and type safety, these containers are strictly homogeneous, like C arrays. Array references can provide a modicum of help for expressing this correspondance. Since arrays are necessarily homogeneous, arguments for container methods can be declared as arrays of single elements. For example, a simple Stack could be declared via, {\samepage\vspace{-5.0pt}\begin{verbatim} class TStack100 { private: int sp; T data[100]; public: void push(const T (&a)[1]) { data[sp++] = a[0]; } //... }; \end{verbatim}} \noindent so as to disallow the use of {\tt sub-T}'s as arguments to {\tt push}. Note that, generally, this technique extends the kinds of optimization opportunities discussed above. Use of exact types in these contexts, as enabled by homogeneity restrictions, means that virtual function calls can be statically resolved. Of course, {\em using} such a class would not be especially simple or convenient, since arguments for methods like {\tt push} would either need to be framed as singleton arrays, or explicitly coerced into arrays, which, if done routinely via macros or the like, ends up defeating the safety goals. However, there is a way to accomodate simpler client usage via an ad hoc special case rule. Recall that allowing {\em implicit} coercions from scalar to array references and vice versa negates the optimizability goals discussed with respect to the {\tt intVec} example. However, if intercoercibility were allowed for the special case of {\em singleton} closed array references only, pragmatic attainment of both goals seems reachable. That is, declaration and matching rules could be extended to include: \begin{itemize} \item A {\tt T (\& singleton)[1]} may alias any object of exact type {\tt T}. \end{itemize} Overloading sensitivity and dispatch rules would have to be modified accordingly. This is an uncomfortable proposal because it yet further complicates matching, coercion, and overloading rules, which are difficult enough as it is. However, the resulting type safety enhancements seem well worth the trouble. An alternative proposal, that obtains the same effect without taking a backdoor approach, is briefly discussed in my ``customization'' paper. \section{Epilogue} The primary limitation of array references is that they, like any other references are not ``reseatable'': C++ references may only alias one object throughout their lifetimes. This makes the use of array references impossible in common cases involving resizing, copy-on-write, delayed allocation, sharing, etc., of referred-to arrays. Surely others have proposed to X3J16 that this restriction be removed. I would like to go on record as supporting any such change. Among the simplest possible mechanisms for doing so is to define a non-overloadable built-in polymorphic pseudofunction (i.e., with the same status of {\tt sizeof}), {\tt void reseat(ANY\& r, ANY\& newobj)} that makes {\tt r} refer to {\tt newobj} Any other constructs with the same effect would suffice. Of course {\tt const} references should not be reseatable. Allowing reseatable references would contribute to the battle to create safer, more optimizable subsets of C++. The utility of references in terms of type precision, inherent promises against performing pointer arithmetic, and simplicity of use should not be wasted because of quibbles about the most appropriate means for expressing things like reseating. \end{document} -- Doug Lea dl@g.oswego.edu || dl@cat.syr.edu || (315)341-2688 || (315)443-1060 || Computer Science Department, SUNY Oswego, Oswego, NY 13126 || Software Engineering Lab, NY CASE Center, Syracuse Univ., Syracuse NY 13244