Familia: Unifying Interfaces, Type Classes, and Family Polymorphism
Yizhou Zhang and Andrew C. Myers
Cornell University

October 2017, Vancouver, BC, Canada


Parametric polymorphism and inheritance are both important, extensively explored language mechanisms for providing code reuse and extensibility. We show that powerful recent forms of these apparently distinct mechanisms can be unified in a deep way, by generalizing the semantics of interfaces and classes. The payoff is a significant increase in expressive power without an increase in programmer-visible complexity. Salient features of the new programming language include retroactive constraint modeling, underpinning both object-oriented programming and generic programming, and module-level inheritance with further-binding, allowing family polymorphism to be deployed at large scale. The resulting mechanism is syntactically light, and the more advanced features are transparent to the novice programmer. We describe the design of a programming language that incorporates this mechanism; using a core calculus, we show that the type system is sound. We demonstrate that this language is highly expressive by illustrating how to use it to implement highly extensible software and by showing that it can not only concisely model state-of-the-art features for code reuse, but also go beyond them.