Parameterization and Bounded Parametric Polymorphism

---

Practical statically-typed languages need bounded parametric polymorphism. Without some mechanism for type parameterization, programmers must either resort to multiple similar implementations of the same abstraction that differ only in type annotations, or insert type casts, often at the client side, to indicate the more precise types of expressions than the type checker infers. For example, if parameterization is not available, several nearly identical implementations of list or array may be needed for lists or arrays of integers, strings, etc., and control structures such as if and map could not be reused for a variety of argument types. Accordingly, Cecil supports the definition of parameterized object representations, method and field implementations, types, signatures, and subtype and inheritance relations. The programmer is allowed to express the assumptions on the type parameters in such declarations using mixed subtype and signature type constraints. For example, a type parameter may be restricted to be a subtype of a certain type or to be any type such that a certain signature holds. Type constraints in Cecil generalize F-bounded polymorphism [Canning et al. 89] and Theta-style where clauses [Day et al. 95, Liskov et al. 94].

This section presents type parameterization and type constraints in Cecil. A more formal development, although in a simpler setting and using a slightly different notation, appears elsewhere [Litvinov 98]. The next subsection introduces parameterization. Subsection 4.2 adds constraints to achieve bounded polymorphism. Subsection 4.3 describes constraint solving and type inference. Subsection 4.4 describes an advanced use of the type system to express F-bounded polymorphism. The last subsection reviews related work.