Associated types and constraint propagation for mainstream object-oriented generics

Support for object-oriented programming has become an integral part of mainstream languages, and more recently generic programming has gained widespread acceptance as well. A natural question is how these two paradigms, and their underlying language mechanisms, should interact. One particular design option, that of using subtyping to constrain the type parameters of generic functions, has been chosen in the generics of Java and those planned for a future revision of C#. Certain shortcomings have previously been identified in using subtyping for constraining paranietric polymorphism in the context of generic programming. To address these, we propose extending object-oriented interfaces and subtyping to include associated types and constraint propagation. Associated types are type members of interfaces and classes. Constraint propagation allows certain constraints on type parameters to be inferred from other constraints on those parameters and their use in base class type expressions. The paper demonstrates these extensions in the context of C# (with generics), describes a, translation of the extended features to C#, and presents a formalism proving their safety. The formalism is applicable to other mainstream object-oriented languages supporting F-bounded polymorphism, such as Java.