By Chieri Saito and Atsushi Igarashi. Proceedings of the ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA 2009), pages 263-282, Orlando, FL, October 2009.
Bruce and Foster proposed the language LOOJ, an extension of Java with the notion of MyType, which represents the type of a self reference and changes its meaning along with inheritance. MyType is useful to write extensible yet type-safe classes for objects with recursive interfaces, that is, ones with methods that take or return objects of the same type as the receiver.
Although LOOJ has also generics, MyType has been introduced as
a feature rather orthogonal to generics. As a result, LOOJ cannot
express an interface that refers to the same generic class recursively
but with different type arguments. This is a significant limitation
because such an interface naturally arises in practice, for example,
in a generic collection class with method map()
, which
converts a collection to the same kind of collection of different
elements. Altherr and Cremet and Moors, Piessens, and Odersky gave
solutions to this problem but they used a highly sophisticated
combination of advanced mechanisms such as abstract type members,
higher-order type constructors, and F-bounded polymorphism.
In this paper, we give another solution by introducing self type constructors, which integrate MyType and generics so that MyType can take type arguments in a generic class. Our solution is simpler---it uses only first-order type constructors and neither abstract type members nor F-bounds. We demonstrate the expressive power of self type constructors by means of examples, formalize a core language with self type constructors, and prove its type safety.