Instantiation



next up previous
Next: Satisfying Where Clauses Up: Language Extensions Previous: Parameterized Definitions

Instantiation

A parameterized definition is used by providing actual types for each of its parameters; we call this an instantiation. The result of instantiation is a type; it has the constructors and methods listed in the definition, with signatures obtained from those in the definition by replacing occurrences of formal parameters with the corresponding actuals. We also use the term ``instantiation'' to refer to this type. Instantiations may be used wherever an ordinary type may be used.

When processing an instantiation, the compiler ensures that each actual parameter type satisfies the where clause for the associated parameter. This means that it has all the named methods and constructors, with compatible signatures. For example, the compiler rejects an instantiation such as SortedList[SortedList[int]], since the argument SortedList[int] does not have an lt method.

However, SortedList[int] is a valid instantiation, assuming that we can use existing primitive types such as int and char as actual type parameters even though these types do not have methods. We solve this problem in a simple and straightforward way: the various operations supported by these types are considered to be methods for the purpose of matching where clauses. For example, the == operator corresponds to the equals method, and lt corresponds to the lt method. (See Section 4.1 for further discussion of primitive types.)

The information in the where clause serves to isolate the implementation of a parameterized definition from its uses (i.e., instantiations). Thus, the correctness of an instantiation of SortedList can be checked without having access to a class that implements SortedList; in fact, there could be many such classes. Within such a class, the only operations of the parameter type that may be used are the methods and constructors listed in the where clause for that parameter. Furthermore, it must use the routines in accordance with the signature information given in the where clause. The compiler enforces these restrictions when it compiles the class; the checking is done just once, no matter how many times the class is instantiated.

A legal instantiation sets up a binding between a method or constructor of the actual type, and the corresponding where-routine, the code actually called at runtime. Since an instantiation is legal only if it provides the needed routines, we can be sure they will be available to the code when it runs. Thus, the where clauses permit separate compilation of parameterized implementations and their uses, which is impossible in C++ and Modula 3.



next up previous
Next: Satisfying Where Clauses Up: Language Extensions Previous: Parameterized Definitions

Andrew C. Myers, Joseph A. Bank, Barbara Liskov
Copyright © 1996 Association for Computing Machinery