bertrand@eiffel.UUCP (Bertrand Meyer) (04/02/89)
The message posted after this one, entitled ``Eiffel types'' and numbered <>, is a draft of an article on the Eiffel type system, which will be adapted as a part of the 2.2 documentation. The present message explains the purpose of ``Eiffel types'', which is long. I hesitated before posting such a long note as ``Eiffel types'' but it seems that the potential benefits outweighed the standard objections. ``Eiffel types'' is NOT the article on ``The complete rules for type checking in Eiffel'' (``Type checking'' for short) which many people (something like 300) requested after I mentioned it on the net some time ago. ``Type checking'' complements ``Object-Oriented Software Construction'' and the Eiffel User's Manual by explaining the complete rules for Eiffel systems to be typewise correct. ``Type Checking'' is mostly of theoretical interest; the problems it addresses, although visible to people who look at Eiffel from an academic point of view, arise very seldom in practical Eiffel usage. In contrast, ``Eiffel types'' deals with very important improvements, both theoretical and practical, of the type system. These improvements are part of version 2.2. The main theoretical advance is to make the notion of type in Eiffel completely regular: all types are now classes; the basic types (INTEGER, REAL, CHARACTER, BOOLEAN) become fully normal classes of the Basic Eiffel Library. This approach contains the germ of a theory of types for which (as is appropriate for an area of applied mathematics having to do with automatic computing devices) the only predefined type is ``bit''. The practical advances are numerous: improvements in efficiency through avoidance of unneeded dynamic allocations and indirections; double precision reals (or, for that matter, arbitrary precision reals or integers); more flexible interface with C and other languages; a simple form of operator overloading; easier bit string manipulation; etc. Because ``Eiffel types'' has to do with the type system of Eiffel, I have decided to merge it with ``Type checking'' but this will take some time. This is the reason while I have not mailed ``Type checking'' yet to those who requested it. That will come. Sorry for the delay. Since ``Eiffel types'' opens possibilities of immediate interest for Eiffel users, it appeared appropriate to post it without delay. ``Eiffel types'' is posted in <> in nroff-ed form. This is less than perfect because the original uses italics, bold face, tables and other typographical niceties. I considered posting the original troff form but it depends to heavily on our local macro package. If there are any follow-ups they will be somehow forwarded to me but I won't be able to respond soon, since I will be roaming the world for the next few weeks with little likely access to news. Enough apologizing for one message. -- -- Bertrand Meyer bertrand@eiffel.com
bertrand@eiffel.UUCP (Bertrand Meyer) (04/02/89)
EIFFEL TYPES Bertrand Meyer DRAFT March 1989 This note presents a unified view of the Eiffel types. The language as described is what is available for version 2.2 and includes some extensions over the definition given by reference [1]. No incompatibility is introduced; any Eiffel class that was legal according to [1] remains legal, with the same semantics. The conceptual framework and extensions presented here introduce a remarkable number of benefits, both theoretical and practical: + Independently of any actual change to the language, the concept of type in Eiffel is presented in a clearer and more uniform way. All Eiffel types are now classes, and multiple inheritance is the basic mechanism for constructing new classes. This means in particular that basic types (integer, real, character and real) need no longer be treated according to special rules. In fact, the names INTEGER, REAL, CHARACTER and REAL need no longer be treated as reserved words in the language: instead, they are names of classes in the Basic Eiffel Library. (For practical reasons, however, these names will remain reserved in version 2.2.) + Double precision reals, which were not previously supported directly in Eiffel because of theoretical and practical problems relating in particular to genericity, are now available. In fact, any precision can be supported. + Limited support is offered for programmer-defined infix and prefix operators. + Programmers can improve the efficiency of their software by writing classes whose instances include other objects. Up to release 2.1, objects could refer to other objects through reference fields, but could not contain other objects. The new possibility avoids unneeded dynamic allocation and indirections. + Exchange of data between Eiffel software and external routines is made easier, particularly when the external routines are written in C. Eiffel objects may contain sub-objects which the C world views as C structures. + Operations on bit sequences of arbitrary length (previously supported by the library class BOOLEAN_SET) are handled simply within the base language. Throughout the rest of this note, ``Eiffel'' refers to version 2.2 Eiffel. The language defined by [1] and implemented as version 2.1 is called ``pre-2.2 Eiffel''. 1 THE TYPES The type system of Eiffel is entirely based on the notion of class: every Eiffel type is now defined as a class. Most classes will be defined by class declarations, under the syntax and semantics introduced in reference [1]. Since any non-empty class declaration must refer to other classes (to give the types of attributes, routine arguments, function results, and to list parents if an inheritance clause is present), some classes must be considered as predefined. Eiffel offers an unbounded set of predefined classes, written BITS M where M is any non-negative integer constant. For any M, the definition of class BITS M is that it describes objects whose representation will fit in M bits. In other words, by declaring an entity such as quadruple: BITS 128 the programmer is requiring the supporting Eiffel environment to devote at least 128 bits to the representation of any object that becomes associated with quadruple at run-time. Of course, the environment is free to allocate more space. Classes BITS M, for any M, are considered to export the boolean operations: and, or, not, and the constants true and false. This makes it possible to use these types for performing operations on bit strings of arbitrary length. In pre-2.2 Eiffel this was done through the library classes BOOLEAN_SET and INTEGER_SET, which remain available. A predefined inheritance structure exists on the set of BITS M classes: BITS M is heir to BITS M+1. No other inheritance relation is satisfied by these classes. 2 EXPANDED CLASSES In pre-2.2 Eiffel, any entity of a class type, for example an attribute declared as ref: CLASS_NAME where CLASS_NAME is the name of a class, represents not an object but a reference to a potential object. The object is ``potential'' because it is only allocated explicitly, through a Create operation. Until it becomes associated with an object, a reference is said to be ``void''. This remains true by default, but the situation will be different if CLASS_NAME has been declared under a newly provided mode, called ``expanded''. The syntax for declaring an expanded class is is expanded class CLASS_NAME ... The rest as before ... As will be seen below, an expanded class may not be deferred, so the problem of the respective order of the optional keywords expanded and deferred does not arise. The effect of declaring a class EXP as expanded is simple: any entity declared of type EXP will represent not a reference to potential objects of type EXP, but directly objects of type EXP. (Remember that ``entities'' in Eiffel cover class attributes, routine arguments, function results, local routine variables.) So if a class C contains an attribute declared as sub: EXP then any instance of C will contain a sub-object of type EXP, accessible through attribute sub. A class such as C having at least one attribute of expanded type is called a composite class; its instances are called composite objects. Figure 1 pictures a composite objects. By default, classes are unexpanded. If a class UNEXP is not explicitly declared as expanded, an entity declaration ref: UNEXP keeps its pre-2.2 meaning: ref denotes a reference to a potential object of type UNEXP, to be created dynamically. Assuming class C contains both of the above attribute declarations, the structure of an instance of this class is illustrated on figure 1. -------------------- ref | | ---> To dynamic instances -------------------- of UNEXP | | | | | Object | sub | of type | | EXP | | | | | -------------------- | | -------------------- Other | | -------------------- fields | | -------------------- | | -------------------- Figure 1: Composite object If EXP had not been declared as expanded, attribute sub would have denoted an attribute which, in any instance of C, represents a reference to potential instances of EXP. Composite objects serve to model external objects that have non-simple components. The modeling of such objects was, of course, possible in pre-2.2 Eiffel, but only by making the objects contain references to their components, not the components themselves. Now it is possible to specify that the objects are composite, so that they actually contain sub-objects. The improvement is not functional - no data structure can be described which could not have also be modeled in pre-2.2 - but is one of performance: useless indirections and dynamic object allocations may now be avoided. In most respects, expanded classes have the same properties as default (unexpanded) classes. An important difference is that instances of expanded classes do not need to be created explicitly. If the type of sub is an expanded class, the call sub.Create is still permitted; its sole effect, however, is to initialize the fields of the object associated with sub to their default values (based on their types) and then to call the specific Create procedure of the class, if present. (For unexpanded classes, Create also has these two effects, but it precedes them by allocating a new object of the appropriate type.) If C is a composite class (expanded or not) with an attribute sub of expanded type EXP, the application of Create to an instance of C implies that all fields of the instance will be initialized to their default values. This applies to field sub; when performing the default initializations, the Create of C will call the Create of EXP (default or specific) on this field. Two other predefined Eiffel features, Void and Forget, are also allowed on entities of expanded types. If sub is such an entity, sub.Void always returns false and sub.Forget has no effect. Three simple rules apply to expanded classes as a result of the above discussion. Violation of these rules will lead to compile-time errors. + As any other class, an expanded class may or may not have a specific Create procedure. If it has one, however, this procedure may not have any arguments. This clearly required in light of the rule for Create: in the above example, there is no way to initialize an instance of the composite class C if the initialization of its expanded sub component requires specific information. + Expanded classes may also be composite: in other words, an expanded class may itself have an attributed of expanded type. Among expanded classes, however, the relation ``A has an attribute of type B'' may not contain any cycles. The reason for this rule is obvious: we cannot implement A and B in such a way that an instance of any of these classes contains a sub-object which is an instance of the other. + An expanded class may not be deferred. (For one thing, its Create procedure could contain a call to a deferred routine. Create is disallowed for deferred classes anyway.) 3 ASSIGNMENT AND EQUALITY TESTING There are three ways of of assigning from b to a (the last one new): a := b a.Clone (b) a.Copy (b) The same type rule, described in [1], applies to all three forms: the type of a must be an ancestor of the type of b. The introduction of expanded classes brings in a further rule: Expanded class type rule: In an assignment from b to a, if the type of b is expanded, the type of a must also be expanded. The effect of assignment under its three forms depends on whether the type of the left-hand side, a, is expanded or not. For an unexpanded type, the rules are the same as in pre-2.2 Eiffel, with the addition of Copy: := denotes reference assignment. After the assignment a will refer to the same object as b, or will be void if b was. Clone represents object duplication. If b refers to an object, the Clone operation creates a new copy of this object, and makes a refer to it. If b was void, a becomes void. Copy represents copy without allocation. The contents of the object associated with b are copied onto the object associated with a. If either a or b is void, an exception is raised. The copies performed by both Clone and Copy are ``shallow'' copies; in other words they copy one entire object, but that object only, the reference fields being copied verbatim. For an expanded type, all three assignments have the effect just described for Copy. Because of the rules given, neither a nor b may be void in this case, so no exception will ever be raised. A similar semantics is defined for equality tests. For unexpanded types, the boolean expression a = b denotes a test for equality of references; the expression a.Equal (b) denotes a test for (shallow) field-by-field equality, returning true if only the contents of the corresponding objects are field-by-field identical, or both references are void. For expanded types, both tests have the semantic of Equal. 4 ENSURING CONSISTENT SEMANTICS FOR GENERIC CLASSES An important design guideline for generic classes follows from the preceding specification of assignment and equality operators. It is possible in Eiffel to write general-purpose classes describing ``container'' data structures (such as lists, trees etc.) containing objects of arbitrary types. These are written as generic classes. Genericity is essential to reconcile static typing with the need for reusable container classes. Consider, however, a routine of a generic class, acting on values of generic type; by generic type, we mean a type defined by a formal generic parameter of the class, for example T in a routine of class C [T]. The problem arises of how programmers can write such a routine and be assured that it has the same semantics regardless of the types used as actual generic parameters for practical uses of the class. In light of the above discussion, the answer is clear. Only copy semantics is available for both expanded and unexpanded types. (For expanded types reference semantics does not make sense.) Writers of generic classes may thus guarantee uniform semantics by making sure that: + All equality tests between expressions of generic type use Equal rather than =. + All assignments use either Copy rather than :=. Clone may also be used if, for generic parameters which are unexpanded classes, duplication is desired rather than mere copy; the difference between Clone and Copy is irrelevant for expanded classes. This rule is particularly important because, as will be seen below, basic types (INTEGER, REAL and others) are defined as expanded classes. Using Equal and Copy is thus the appropriate way to guarantee that a generic class will have uniform semantics for basic types and other class types. It is important to note that this was essentially already true in pre-2.2 Eiffel: as a first step towards the more general solution described here, Equal and Clone were already available on basic types, with the respective semantics of = and := on these types. (Copy did not exist in pre-2.2 Eiffel.) The rules described above simply generalize and systematize these conventions. Clearly, the above guidelines should only be followed if uniform semantics is desired; they do not mean that = and := should be banned from generic classes. One can conceive of perfectly valid generic classes for which reference semantics is desired when the actual generic parameter is an unexpanded class, and value semantics is desired when the generic parameter is an expanded class, in particular a basic type. Since field-by-field object comparison and object copy are the operations that make sense in all cases, it is legitimate to criticize the syntax retained: why are the simpler symbols (= and :=) used for operations whose semantics is not the same for expanded and unexpanded types, and more verbose notations (Equal, Copy) used for the operations which have consistent semantics and hence appear ``cleaner''? This is a valid criticism. Indeed, I seriously considered, during the initial design of Eiffel, making := denote copy assignment and = denote object equality. But this idea was rejected out of fear that such a clash with the tradition of all previous languages supporting reference semantics (Pascal, Ada, PL/I, and many others) would result in numerous mistakes on the part of new Eiffel programmers, not all of whom may yet be expected to learn Eiffel as their first programming language. The relative clumsiness of the syntax for the more uniform operations was deemed less unpleasant than the prospect of massive mistakes by the cohorts of new converts, still recovering from the influence of older programming languages. As explained in section 5.8.3 of [1], using variants of the same notation for copy and reference semantics (such as the traditional operators := and = for copy, and the Simula operators :- and == for reference) would have been the worst possible solution, implying that minor syntactical or typing oversights could result in drastic changes of meaning. The notations had to be visibly different. New reserved words (Clone, Copy, Equal) were deemed clearer than new operators. 5 INTERFACE WITH OTHER LANGUAGES [Readers who are not interested in detailed questions of Eiffel interface to other languages, particularly C, should skip to the next section.] The notion of expanded class also provides for a more flexible interface with the non-Eiffel world. In pre-2.2 Eiffel, Eiffel routines that needed to interface with routines written in other languages, such as C, could only pass them arguments of basic types or of class types; in the latter case the argument is actually a reference. This also applied to the types of the results of external functions. Furthermore, it was not possible for an Eiffel object to contain a sub-object modeled directly to a C structure type declaration, although this constraint was somewhat relieved by the presence of a routine copy_structure, in the basic library class INTERNAL, making it possible to copy the contents of a C structure into an Eiffel object. This concern is now addressed by composite classes. If each instance of C must contain a sub-object whose structure comes from external C software, then C should contain an attribute declaration of the form sub: EXP where EXP is an appropriate expanded class. Usually, EXP should simply be declared as expanded class EXP inherit BITS M end where M (an integer constant) is large enough to cover the size of instances of the required C structure type. It would usually be imprudent to give EXP a more precise Eiffel structure, since this would require making non-portable assumptions about the internal structure of both Eiffel and C objects. The above, however, will be sufficient in practice since entities of type EXP, such as sub, should only be used as arguments to external function calls. The purpose is not to have Eiffel do the job of C or the reverse, but only to facilitate communication between the two worlds. This facility is consistent with the Eiffel approach to interfacing with other languages, based on two observations. First, reusability implies that Eiffel software must be able to interface with existing software written in other languages, but not that the Eiffel language should be corrupted by compatibility with older, unrelated designs. A passage is provided through the border, but it remains a border. Second (for the special case of C): C plays with respect to Eiffel the role that assembly languages played for earlier high-level languages: that of a low-level vehicle to be used only when one cannot do otherwise. As an aside, note that release 2.2 provides further support for more powerful interaction between Eiffel and other languages. In particular, a simple syntactical extension makes it possible to pass the address of an Eiffel routine to an external routine. The notation is @f, where f is a routine of the enclosing class; such an expression is only valid as actual argument to an external routine. 6 ARGUMENT PASSING The rules for argument passing are a consequence of the above. When an Eiffel routine calls another Eiffel routine, the semantics of argument passing is the same as that of assignment from actual to formal argument: by copy for arguments of expanded types (including, as will be seen below, the basic types), and by reference for arguments of unexpanded types. [C-unfascinated readers, please skip to next section.] For arguments to external routines, the rule cannot be as systematic; they must of necessity be adapted to the target language. Current C, for example, does not support passing of structures or arrays as arguments; only pointers to such elements may be passed. (ANSI C may be more liberal, but has yet shown little relevance to the real world of C programming.) So for C all arguments, whether expanded or not, are normally passed by reference. It is the responsibility of the target C routine to copy any structure or array if needed. An exception is made, however, for arguments of basic types (integer, real, boolean, character and the new type ``long real'' described below), which are passed by value for compatibility with tradition. For the results of external functions, the Eiffel compiler can take care of ensuring the proper semantics (copy for expanded, reference for unexpanded); a language- dependent convention is needed, however, to determine what the function will return. In C, the answer is the only portable one: the C function is assumed to return a pointer to the result for non-basic types, expanded or not. The code generated by the Eiffel compiler then takes care of performing a copy in the expanded case. An important practical caveat governs the exchange of arguments and function results between Eiffel and C (or another language). We may usually assume that the basic types are common to both languages, and hence that values of these types may be manipulated by both sides. Both C and Eiffel routines, for example, may perform additions on a given integer value. For values of any other type, however, only one side may safely execute operations other than parameter passing; the other side will simply be used as repository for the values, or to pass them along to further elements. There are exceptions to this rule, but they apply to special cases and require that the programmer be well versed in the implementation techniques for both languages. 7 PREFIX AND INFIX OPERATORS We are now almost ready to explain how basic types can be interpreted as classes. A syntactical facility, although not essential, will prove convenient for this. To facilitate expressiveness, we allow some routines to be used in prefix or infix form. The standard grammar for the declaration of routines (see [1], appendix C) is as follows (brackets introduce optional components: Routine_declaration = Routine_name [Formal_arguments] [Type_mark] "is" Routine_text Formal_arguments = "(" Entity_declaration_list ")" Type_mark = ":" Type The optional ``Type_mark'' gives the type of the result when the routine is a function. In pre-2.2 Eiffel, ``Routine_name'' is simply an identifier. We now allow the two new forms prefix '"'Operator'"' infix '"'Operator'"' In this syntax, ``Operator'' may only be one of the following: +, -, *, /, <, >, <=, >=; only the first two in this list are permitted for a ``prefix'' declaration. So only a small group of common operators may be used in prefix or infix form. Routines declared in this way must all be functions. Infix routines must have exactly one argument; prefix routines must have none. Calls to such routines must use the corresponding operators, in prefix or infix form. Assume for example a class MATRIX with function declarations of the form infix ("+") (other: like Current): like Current is... prefix ("-"): like Current is... Then, for m1 and m2 of type MATRIX, the expressions m1 + m2 and -m1, respectively, will denote calls to the corresponding functions. The precedence of infix and prefix operators is fixed and given by the standard Eiffel precedence table (see section C.3 of [1]). It is important to note that the above possibility is not ``the introduction of overloading into Eiffel''. A powerful form of overloading has always been available in Eiffel, since any two classes can have different features of the same name, and dynamic binding makes it possible to obtain run-time discrimination. What is new is a simple syntactic extension, making it possible to use the standard arithmetic operators for any class, not just the basic types. 8 COMPARABLE and NUMERIC Two deferred classes are needed in the basic Eiffel library. Class COMPARABLE already existed in pre-2.2; its features now use the infix facility. Note that only "<=" needs to be deferred. deferred class COMPARABLE export infix "<", infix "<=", infix ">", infix ">=" feature infix "<=" (other: like Current): BOOLEAN is -- Is current element less than or equal to other? deferred end; -- "<=" infix "<" (other: like Current): BOOLEAN is -- Is current element less than other? do Result := Current < other and not Current.Equal (other) end; -- "<" infix ">" (other: like Current): BOOLEAN is -- Is current element greater than other? do Result := other < Current end; -- ">" infix ">=" (other: like Current): BOOLEAN is -- Is current element less than or equal to other? do Result := other <= Current end -- ">=" end -- class COMPARABLE Class NUMERIC describes any type with the basic arithmetic operations: deferred class COMPARABLE export infix "+", infix "-", infix "*", infix "/", prefix "+", prefix "-" feature infix "+" (other: NUMERIC): NUMERIC is -- Sum of other and current element deferred end; -- infix "+" prefix "-" BOOLEAN is -- Is current element less than other? deferred end; -- prefix "-" (etc.) end -- class COMPARABLE Any class that needs to manipulate elements connected by an order relation, or elements on which operations similar to the basic arithmetic operations are available, may inherit from COMPARABLE or NUMERIC and offer effective definitions for the above operations. A class may of course inherit from both. [Draft note: NUMERIC might inherit from COMPARABLE.] 9 BASIC TYPES AND DOUBLE PRECISION We can now introduce the basic types as classes. This definition is based on an assessment of the present state of computer hardware: on most platforms, an integer or (short) real will fit in 32 bits; a character will fit in 8 bits; a long real will fit in 64 bits. I believe it is preferable to explicitly incorporate these industry-standard lengths into the programming language definition, rather than to maintain a pretense of implementation-independence. In practice such a pretense can only prevent software developers from writing portable software that will perform in a (reasonably) consistent fashion across a range of platforms. (Another, more axiomatic approach has been followed by Ada, but its advantages over the policy of making simple assumptions about the minimum bit-size requirements of basic data types are not clear in the present state of hardware technology and software theory.) The basic types are defined as follows. expanded class REAL export infix "+", infix "-", infix "*", infix "/", prefix "+", prefix "-", infix "<", infix "<=", infix ">", infix ">=" inherit BITS 32; NUMERIC; COMPARABLE; REAL_CONVERTIBLE -- See below feature infix "+" (other: REAL_CONVERTIBLE): REAL is -- Sum of other and current element external short_real_addition (other: REAL): REAL language "..." do Result := short_real_addition (other.to_real) end; -- "+" ... And similarly for other prefix and infix operations ... to_real: REAL is -- Conversion to REAL type (here, identity) do Result := Current end; -- "+" end -- class REAL So we consider that a (short) real number is an expanded 32-bit object, which has the properties of both ``numeric'' and ``comparable'' objects. The operations are implemented through external routines, since these operations are to be carried out directly by the hardware (or through the lower-level implementation language used by the given implementation of Eiffel, such as assembly or C). The idea here is the same as with the way arrays are treated in pre-2.2 Eiffel. Arrays, and now real numbers, are viewed as instances of ``normal'' Eiffel classes in the Basic Library. From a practical standpoint, however, the implementation knows about these and implements the corresponding operations through shortcuts: no actual routine call is needed to access an array element, or to add two reals. So the usual efficiency of fundamental operations is achieved, but the conceptual framework (classes, objects, inheritance) remains consistent with the rest of the language. The class REAL_CONVERTIBLE is used to account for mixed arithmetic operations. What is added to a real number may be not just a real but also an integer. The class is simple: deferred class REAL_CONVERTIBLE export to_real feature to_real: REAL is -- Conversion of current element to a real value deferred end; -- to_real end -- class REAL_CONVERTIBLE This class is needed because it seems inappropriate to make INTEGER an heir of REAL; assignment, in particular, would not have its usual meaning. (In version 2.2, however, it will remain possible to assign an integer value to a real entity, with the expected effect of a conversion. This is an exception to the generality of the type scheme presented here, for compatibility with programmers' current habits.) Class INTEGER is declared in a way similar to REAL: expanded class INTEGER export infix "+", infix "-", infix "*", infix "/", prefix "+", prefix "-", infix "<", infix "<=", infix ">", infix ">=" inherit BITS 32; NUMERIC; COMPARABLE; REAL_CONVERTIBLE feature infix "+" (other: REAL_CONVERTIBLE): REAL is -- Sum of other and current element external integer_addition (other: REAL): REAL language "..." do Result := integer_addition (other) end; -- "+" ... And similarly for other prefix and infix operations ... to_real: REAL is -- Conversion to REAL type external integer_to_real: REAL language "..." do Result := Current.integer_to_real end -- to_real end -- class INTEGER Here no conversion is required for integer operations. The other basic types are defined similarly. CHARACTER is an expanded class that inherits from BITS 8. BOOLEAN is an expanded class that inherits from BITS 1. The type DOUBLE, new with 2.2, is formally a class, very similar to REAL, but inheriting from BITS 64 rather than BITS 32. Note that REAL is not an heir of DOUBLE. As with integers and reals, an explicit conversion mechanism is required; this does not, however, prevent the usual mixed- mode expressions. If longer precision reals or integers are needed, the technique is easily generalized: just define new classes that inherit from NUMERIC, COMPARABLE, and BITS M for the appropriate M. 10 UNEXPANDED CLASSES AND GENERICITY Two further conventions are needed to fully understand the Eiffel type system. + Any unexpanded class (this includes all classes of pre-2.2 Eiffel) is implicitly considered to inherit from BITS 32. This is a result of an assessment of the current state of hardware technology. Instances of unexpanded classes are accessible through references, that is to say, at the implementation level, pointers. We thus accept that, for still some time: (1) limiting Eiffel applications to manipulate 2**31 (about two billion) dynamic objects during a given session is acceptable; and (2) computer memory is not cheap enough that it would be preferable to raise this limitation to, say, 2**63, if this implied doubling the space occupied by the pointers of a session. Note that this convention is not really ``wired in'' and some future standardization committee might decide to raise the bound to 64 (for example) without major impact on existing applications, provided the same committee also decided that INTEGER and REAL now inherit from BITS 64 rather than 32. + Unconstrained genericity, as in a declaration of a class C [T], is taken as an abbreviation for constrained genericity of the form C [T -> BITS 32]. In other words, the default is 32; this covers both the short basic types and all unexpanded classes. Again, the value 32 might need to be adjusted in line with advances in technology. The last convention explains how generic classes may be written to support double precision reals (for example). A generic class declared as MATRIX [T] will be applicable to the actual generic types INTEGER, REAL, CHARACTER, BOOLEAN or any unexpanded class. It may not be used for the type DOUBLE, however, because this class is not a descendant of BITS 64. To make the class applicable to double precision reals, declare it as MATRIX [T -> BITS 64] This will work for DOUBLE, and will still work for the preceding types; remember that BITS M is heir to BITS M+1. As another consequence of the above rules, a generic class may usually not use an expanded class as actual generic parameter. More precisely, if EXP is an expanded class and C is generic, C [...EXP...] is legal if and only if C has been declared as MATRIX [...T -> EXP1...] where EXP1 is an expanded class, and EXP is a descendant of EXP. 11 CONCLUSION The mechanisms described above may at first appear as a significant extension of pre-2.2 Eiffel. They are not. Instead, the work reported here should primarily be viewed as a reorganization and cleanup of the theoretical framework, which makes important improvements available at the cost of very little actual extension. As a matter of fact the above discussion has introduced only five new reserved words: BITS Copy expanded infix prefix From a theoretical viewpoint, four have been removed: INTEGER, REAL, BOOLEAN, CHARACTER. If we accept that DOUBLE would have been needed anyway, the reserved word count is unchanged by this discussion. (The names of the basic types will, however, remain reserved in release 2.2 for practical reasons.) The starting point for this work was both practical and theoretical. From a practical viewpoint, I had known for a long time that it would be ultimately indispensable to support double precision; however double precision initially appeared extremely difficult in the presence of genericity. Clearly I did not want an implementation of genericity which would result (as most Ada compilers do for generic packages) in duplicating code for each separate use of a generic class; this was deemed unacceptable. At some point I realized that, from a practical perspective, the mechanism of constrained genericity (implemented for 2.1) contained the key. But then why stop at double precision? Eiffel strives for generality; what if someone wants, say, 128-bit reals? Another practical concern, which had been present for some time, was to avoid dynamic allocation whenever possible. In most applications, the overhead of pointers is acceptable; whether in Eiffel, Pascal, Ada or C, most non- trivial data structures are accessed through pointers anyway. Still, this overhead is annoying for applications that manipulate very large numbers of composite objects each of which contains several small but non-atomic components - say triangles, each containing three ``point'' attributes. Yet another motive was the desire to improve the flexibility of the interface of Eiffel with other languages, especially C. This requirement is not an internal one, since for our own developments the external interface of pre-2.2 Eiffel, based on external routines that essentially pass BITS 32 values to and from Eiffel, is more than enough. Eiffel users have increasingly requested support for more general interface mechanisms, however; the aim in particular is to facilitate cooperation between Eiffel software and existing packages (graphics, databases, expert systems etc.) The support for composite objects should be particularly useful here, since it covers a need often voiced by users, that of having Eiffel objects contain sub-objects described by C structures. Support for prefix and infix operators was never by itself a major concern. In fact I was (and remain) strongly against unbounded operator overloading, which opens the door to all kinds of notational abuses; I am much more interested in the semantically useful overloading permitted by redefinition and dynamic binding than by purely syntactical techniques which make it possible to call a two-argument routine under the form a @#$ b (say). The ability to define the precedence of new operators, in particular, has always struck me as a perfect example of programming language feature that is bad on all counts: it is difficult to find a good syntax for it (do you specify precedence by a number, forcing each program writer or reader to refer to the programming language reference manual each time, or do you say ``one less than the precedence of operator xxx''?); it makes it particularly easy to write tricky programs; it invites bugs; it makes the parser - normally the most trivial and worriless part of a modern compiler - considerably more difficult to implement (since each program may change the syntax); and to top the whole thing, it is only a superficial, syntactical, ``vanity'' extension. Not the most urgent feature to add to Eiffel. It was clear, however, that if we were to treat basic types formally as classes (see next), then we should be able to interpret the basic prefix and infix operators as denoting routines. Why not then make them available to writers of normal programmer-defined classes, such as MATRIX, VECTOR and the like? Since the concept would only apply to a few predefined operators, the extension would remain small and reasonable. I also had more theoretical concerns. The difference of treatment between basic types and class types in pre-2.2 Eiffel, explained in chapter 5 of [1], came directly from Simula. I knew that some difference was necessary: in most cases, class types need reference semantics, and usually they also need dynamic object creation, but no one would want to allocate integers dynamically. Still, this inconsistency was unpleasant in a language that emphasizes simplicity and uniformity. The concepts of class and multiple inheritance seemed to provide such a powerful basis for the discussion of types that it was sad to have to abandon them for a handful of basic types - the most fundamental at that. When I presented Eiffel concepts in public courses, listeners would often question the special treatment of basic types, asking why INTEGER, for example, was not a class. My answer usually included (among other arguments) that any theory of types needed to start somewhere, and thus to assume a few pre-existent, ``Bourbaki-given'' types. Why not, the argument would go, use for these the few types with which everybody is familiar, and which are readily available on all hardware? I would usually say something like ``In the most purist object-oriented approach, we would still need to take at least one type for granted: the bit''. In a way, the framework presented above implements this purist approach, although it considers not a single bit type, but an unbounded sequence of bit types, BITS M. Everything else is derived from these. Thanks to the notion of expanded class, which also addresses the problems that I have called ``practical concerns'', the basic types make perfect sense in this context; they cease to be special language elements with magical properties and become standard library classes. To make the solution clear and uniform, limited support for infix and prefix operators, useful in its own right, may be introduced. No loss in performance is implied because the compiler can be made smart enough to recognize these classes and apply special techniques to them; in fact, the pre-2.2 implementation of basic types remains entirely valid. Finally, the introduction of expanded classes makes it possible to tackle the dual-semantics issue in a much more explicit, complete, and (I hope) convincing fashion than ever before. I feel that the general cleanup of the Eiffel type system is almost complete with the discussion of this article (and the companion discussion [2], which addresses details of the rules making Eiffel fully statically typed through constraints on polymorphism, not well covered in [1] and not yet fully supported by the implementation). To make the basic type into fully ``ordinary'' citizens, we would also need to deal with manifest constants, which could be treated as ``zerofix'' operators. Example of such operators would be 0 and 1, now introduced as deferred functions in class NUMERIC, corresponding to the neutral elements for operations infix "+" and infix "*". The other integers would be interpreted as syntactical abbreviations for 1+1, 1+1+1 etc. Such an extension would require that we be more formal, separating what has been called NUMERIC into different inheritance levels (GROUP, RING, FIELD etc.) characterized by the proper assertions. This is worth exploring further; there may be the root of a full type theory, perhaps even of a general model for computation. This extension, however, will not be part of Eiffel release 2.2. References [1] B. Meyer, Object-Oriented Software Construction, Prentice-Hall, 1988. [2] B. Meyer, The complete rules for static typing in Eiffel, unpublished. -- -- Bertrand Meyer bertrand@eiffel.com