Home

Generics of a Higher Kind

Generics of a Higher Kind. Adriaan Moors, Frank Piessens, and Martin Odersky.

With Java 5 and C# 2.0, first-order parametric polymorphism was introduced in mainstream object-oriented programming languages under the name of generics. Although the first-order variant of generics is very useful, it also imposes some restrictions: it is possible to abstract over a type, but the resulting type constructor cannot be abstracted over. This can lead to code duplication. We removed this restriction in Scala, by allowing type constructors as type parameters and abstract types. This paper presents the design and implementation of the resulting type constructor polymorphism. It combines type constructor polymorphism with implicit parameters to yield constructs similar to, and at times more expressive than, Haskell’s constructor type classes. The paper also studies interactions with other object-oriented language constructs, and discusses the gains in expressiveness.

Many readers will already be aware that Scala has added support for higher-kinded generics, related to Haskell's type constructor classes. I believe Scala is the first language to provide this capability in an OO "generics" framework. This ECOOP submission presents this work, with many practical examples.

(Consider this penance for my last post...)

By Matt Hellige at 2007-12-20 19:54 | Object-Functional | Scala | other blogs | 46575 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Similar paper

Looks like the same team have written another very similar paper on the same topic.

Towards Equal Rights for Higher-kinded Types

By Ray Waterman at Tue, 2007-12-25 00:24 | login or register to post comments

The older version was never published

That's right, that's an older iteration of the same paper, which was never published. (It was presented at the MPOOL 2007 workshop, though.)
The newer ECOOP version is almost a complete rewrite.

By Adriaan Moors at Tue, 2007-12-25 15:47 | login or register to post comments

Generics

Ada had parametric polymorphism in the form of generic units from day one (the official release date of the language was 1983, but generic units existed in the specs well before that date). This model was extended to handle inheritance in Ada95, though poorly, and further evolved in Ada 2005. It is a shame that too many papers on these topics only mention recent languages (in this case C# and Java), and don't mention "prior art", such as Ada (and, indeed, C++).

Keep in mind that the Ada model is type safe, and not merely macro expansion.

By Ehud Lamm at Wed, 2008-01-09 06:39 | login or register to post comments