Previous    Next


One of the first "polymorphic" languages was Lisp [McCarthy 1960], which has no static (i.e., compile-time checkable) type system at all. Consequently, the fully boxed implementation of data was used, so that the data could describe itself to the run-time type-checker as well as to the garbage collector. The first coding language to use statically type-checked parametric polymorphism was ML, which was originally the MetaLanguage of the Edinburgh theorem prover [Gordon et al. 1978] but was later developed into a general-purpose coding language [Milner et al. 1990]. Cardelli [1984] describes a fully boxed implementation of ML. In the Ada coding language [Ada 1980], the generic mechanism allows a function (in fact, an entire package) to be parameterized over types; but full type-checking is done at each call site after the generic is applied to actual parameters, and the expansion technique of implementation must be used. In contrast, Algorithm 16.4 can check a generic class independent of how its formal type parameters will eventually be instantiated. Pierce [2002] provides a comprehensive survey of type systems, including polymorphic types, in the modern notation. Bracha et al. [1998] describe Generic Java (GJ) and its implementation. The type-checking algorithm in of this chapter is adapted from "Featherweight Generic Java" [Igarashi et al. 2001], which should be read by anyone planning to implement such a type-checker. Overloading Ada allows different functions with the same parameter types to be overloaded, as long as the result types are different. When the output of such a function is an argument to another overloaded identifier, then there may be zero, one, or many possible interpretations of the expression; the Ada semantics say that the expression is legal only if there is exactly one interpretation. Aho et al. [1986, ] discuss this issue and give a resolution algorithm. But Ada-style overloading has not been widely imitated in recent language designs, perhaps because it can confuse the programmer.

Dynamic overloading allows different implementations of a function to be chosen based on the run-time type of an actual parameter; it is a form of dynamic dispatch. Dynamic dispatch is also used to implement method overriding, a fundamental concept of object-oriented coding (see ) - overriding is a form of dynamic dispatch on the this parameter, while general dynamic overloading can depend on any or all parameters to a function. Type classes in the Haskell language allow overloading and parametric polymorphism to interact in a useful and expressive way [Hall et al. 1996].

JaVaScreenshot Previous    Next