Generics of a higher kind

ABSTRACT

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 type members. This paper presents the design and implementation of the resulting type constructor polymorphism. Furthermore, we study how this feature interacts with existing object-oriented constructs, and show how it makes the language more expressive.

REFERENCES

• 1: Martín Abadi , Luca Cardelli, A theory of primitive objects: second-order systems, Science of Computer Programming, v.25 n.2-3, p.81-116, Dec. 1995
• 2: Martín Abadi , Luca Cardelli, A theory of primitive objects: untyped and first-order systems, Information and Computation, v.125 n.2, p.78-102, March 15, 1996 [doi>10.1006/inco.1996.0024]
• 3: P. Altherr and V. Cremet. Adding type constructor parameterization to Java. Accepted to the workshop on Formal Techniques for Java-like Programs (FTfJP'07) at the European Conference on Object-Oriented Programming (ECOOP), 2007.
• 4: David Aspinall , Adriana Compagnoni, Subtyping dependent types, Theoretical Computer Science, v.266 n.1-2, p.273-309, 09/06/2001 [doi>10.1016/S0304-3975(00)00175-4]
• 5: G. M. Bierman, E. Meijer, and W. Schulte. The essence of data access in Comega. In A. P. Black, editor, ECOOP, volume 3586 of Lecture Notes in Computer Science, pages 287--311. Springer, 2005.
• 6: Gilad Bracha, Executable Grammars in Newspeak, Electronic Notes in Theoretical Computer Science (ENTCS), 193, p.3-18, November, 2007 [doi>10.1016/j.entcs.2007.10.004]
• 7: Kim B. Bruce , Albert R. Meyer , John C. Mitchell, The semantics of second-order lambda calculus, Information and Computation, v.85 n.1, p.76-134, March 1990 [doi>10.1016/0890-5401(90)90044-I]
• 8: Kim B. Bruce , Martin Odersky , Philip Wadler, A Statically Safe Alternative to Virtual Types, Proceedings of the 12th European Conference on Object-Oriented Programming, p.523-549, July 20-24, 1998
• 9: Kim B. Bruce , Angela Schuett , Robert van Gent, PolyTOIL: A Type-Safe Polymorphic Object-Oriented Language, Proceedings of the 9th European Conference on Object-Oriented Programming, p.27-51, August 07-11, 1995
• 10: Peter Canning , William Cook , Walter Hill , Walter Olthoff , John C. Mitchell, F-bounded polymorphism for object-oriented programming, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.273-280, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99392]
• 11: L. Cardelli, Structural subtyping and the notion of power type, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.70-79, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73566]
• 12: Luca Cardelli, Types for Data-Oriented Languages, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.1-15, March 14-18, 1988
• 13: Luca Cardelli , Peter Wegner, On understanding types, data abstraction, and polymorphism, ACM Computing Surveys (CSUR), v.17 n.4, p.471-523, Dec. 1985 [doi>10.1145/6041.6042]
• 14: J. Carette, O. Kiselyov, and C. chieh Shan. Finally tagless, partially evaluated. In Z. Shao, editor, APLAS, volume 4807 of Lecture Notes in Computer Science, pages 222--238. Springer, 2007.
• 15: M. Chakravarty, S. L. P. Jones, M. Sulzmann, and T. Schrijvers. Class families, 2007. On the GHC Developer wiki, http://hackage.haskell.org/trac/ghc/wiki/TypeFunctions/ClassFamilies.
• 16: Manuel M. T. Chakravarty , Gabriele Keller , Simon Peyton Jones , Simon Marlow, Associated types with class, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-13, January 12-14, 2005, Long Beach, California, USA
• 17: Adriana Compagnoni , Healfdene Goguen, Typed operational semantics for higher-order subtyping, Information and Computation, v.184 n.2, p.242-297, August 01, 2003 [doi>10.1016/S0890-5401(03)00062-2]
• 18: V. Cremet and P. Altherr. Adding type constructor parameterization to Java. Journal of Object Technology, 7(5):25--65, June 2008. Special Issue: Workshop on FTfJP, ECOOP 07. http://www.jot.fm/issues/issue_2008_06/article2/.
• 19: B. Emir, A. Kennedy, C. V. Russo, and D. Yu. Variance and generalized constraints for C# generics. In D. Thomas, editor, ECOOP, volume 4067 of Lecture Notes in Computer Science, pages 279--303. Springer, 2006.
• 20: E. Ernst. gbeta -- a Language with Virtual Attributes, Block Structure, and Propagating, Dynamic Inheritance. PhD thesis, Department of Computer Science, University of Aarhus, Ú Arhus, Denmark, 1999.
• 21: Erik Ernst, Family Polymorphism, Proceedings of the 15th European Conference on Object-Oriented Programming, p.303-326, June 18-22, 2001
• 22: Jeremy Gibbons , Geraint Jones, The under-appreciated unfold, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.273-279, September 26-29, 1998, Baltimore, Maryland, United States
• 23: J. Girard. Interpretation fonctionelle et elimination des coupures de l'arithmetique d'ordre superieur. Thèse d'État, Paris VII, 1972.
• 24: James Gosling , Bill Joy , Guy Steele , Gilad Bracha, Java(TM) Language Specification, The (3rd Edition) (Java (Addison-Wesley)), Addison-Wesley Professional, 2005
• 25: Douglas Gregor , Jaakko Järvi , Jeremy Siek , Bjarne Stroustrup , Gabriel Dos Reis , Andrew Lumsdaine, Concepts: linguistic support for generic programming in C++, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 26: Christian Hofer , Klaus Ostermann , Tillmann Rendel , Adriaan Moors, Polymorphic embedding of dsls, Proceedings of the 7th international conference on Generative programming and component engineering, October 19-23, 2008, Nashville, TN, USA [doi>10.1145/1449913.1449935]
• 27: Paul Hudak , John Hughes , Simon Peyton Jones , Philip Wadler, A history of Haskell: being lazy with class, Proceedings of the third ACM SIGPLAN conference on History of programming languages, p.12-1-12-55, June 09-10, 2007, San Diego, California [doi>10.1145/1238844.1238856]
• 28: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• 29: J. Hughes. Restricted datatypes in Haskell. Technical Report UU-CS-1999-28, Department of Information and Computing Sciences, Utrecht University, 1999.
• 30: G. Hutton and E. Meijer. Monadic Parser Combinators. Technical Report NOTTCS-TR-96-4, Department of Computer Science, University of Nottingham, 1996.
• 31: Atsushi Igarashi , Benjamin C. Pierce , Philip Wadler, Featherweight Java: a minimal core calculus for Java and GJ, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.3, p.396-450, May 2001 [doi>10.1145/503502.503505]
• 32: M. P. Jones. constructor classes & 'set' monad?, 1994. http://groups.google.com/group/comp.lang.functional/msg/e10290b2511c65f0.
• 33: M. P. Jones. A system of constructor classes: Overloading and implicit higher--order polymorphism. J. Funct. Program., 5(1):1--35, 1995.
• 34: E. Kidd. How to make data.set a monad, 2007. http://www.randomhacks.net/articles/2007/03/15/data-set-monad-haskell-macros.
• 35: D. Leijen and E. Meijer. Parsec: Direct style monadic parser combinators for the real world. Technical Report UU-CS-2001-27, Department of Computer Science, Universiteit Utrecht, 2001.
• 36: Erik Meijer, There is no impedance mismatch: (language integrated query in visual basic 9), Companion to the 21st ACM SIGPLAN symposium on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA [doi>10.1145/1176617.1176686]
• 37: Erik Meijer, Confessions of a used programming language salesman, Proceedings of the 22nd annual ACM SIGPLAN conference on Object oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 38: A. Moors, F. Piessens, and M. Odersky. Towards equal rights for higher-kinded types. Accepted for the 6th International Workshop on Multiparadigm Programming with Object-Oriented Languages at the European Conference on Object-Oriented Programming (ECOOP), 2007.
• 39: A. Moors, F. Piessens, and M. Odersky. Parser combinators in Scala. Technical Report CW491, Department of Computer Science, K.U. Leuven, 2008. http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW491.abs.html.
• 40: A. Moors, F. Piessens, and M. Odersky. Safe type-level abstraction in Scala. In Proc. FOOL '08, Jan. 2008. http://fool08.kuis.kyoto-u.ac.jp/.
• 41: M. Odersky. Poor man's type classes, July 2006. Talk at IFIP WG 2.8, Boston.
• 42: M. Odersky. The Scala Language Specification, Version 2.6. EPFL, Nov. 2007. http://www.scala-lang.org/docu/files/ScalaReference.pdf.
• 43: M. Odersky, P. Altherr, V. Cremet, I. Dragos, G. Dubochet, B. Emir, S. McDirmid, S. Micheloud, N. Mihaylov, M. Schinz, L. Spoon, E. Stenman, and M. Zenger. An Overview of the Scala Programming Language (2. edition). Technical report, 2006.
• 44: M. Odersky, V. Cremet, C. Röckl, and M. Zenger. A nominal theory of objects with dependent types. In L. Cardelli, editor, ECOOP, volume 2743 of Lecture Notes in Computer Science, pages 201--224. Springer, 2003.
• 45: M. Odersky, L. Spoon, and B. Venners. Programming in Scala. Artima, 2008.
• 46: Martin Odersky , Christoph Zenger , Matthias Zenger, Colored local type inference, Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.41-53, January 2001, London, United Kingdom
• 47: Martin Odersky , Matthias Zenger, Scalable component abstractions, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 48: Harold Ossher , William Harrison, Combination of inheritance hierarchies, conference proceedings on Object-oriented programming systems, languages, and applications, p.25-40, October 18-22, 1992, Vancouver, British Columbia, Canada
• 49: Benjamin Pierce , Martin Steffen, Higher-order subtyping, Theoretical Computer Science, v.176 n.1-2, p.235-282, April 20, 1997 [doi>10.1016/S0304-3975(96)00096-5]
• 50: John C. Reynolds, Towards a theory of type structure, Programming Symposium, Proceedings Colloque sur la Programmation, p.408-423, April 09-11, 1974
• 51: Tim Sheard, Type-level Computation Using Narrowing in Ωmega, Electronic Notes in Theoretical Computer Science (ENTCS), v.174 n.7, p.105-128, June, 2007 [doi>10.1016/j.entcs.2006.10.040]
• 52: M. Steffen. Polarized Higher--Order Subtyping. PhD thesis, Universität Erlangen-Nürnberg, 1998.
• 53: Kresten Krab Thorup , Mads Torgersen, Unifying Genericity - Combining the Benefits of Virtual Types and Parameterized Classes, Proceedings of the 13th European Conference on Object-Oriented Programming, p.186-204, June 14-18, 1999
• 54: P. Wadler. Comprehending monads. Mathematical Structures in Computer Science, 2(4):461--493, 1992.
• 55: Philip Wadler, Monads for Functional Programming, Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques-Tutorial Text, p.24-52, May 24-30, 1995
• 56: P. Wadler , S. Blott, How to make ad-hoc polymorphism less ad hoc, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-76, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75283]
• 57: S. Wehr, R. Lämmel, and P. Thiemann. JavaGI: Generalized interfaces for Java. In E. Ernst, editor, ECOOP, volume 4609 of Lecture Notes in Computer Science, pages 347--372. Springer, 2007.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Polymorphism

General Terms:
Design, Experimentation, Languages

Keywords:
Scala, higher-kinded types, higher-order genericity, type constructor polymorphism