Modular type classes

ABSTRACT

ML modules and Haskell type classes have proven to be highly effective tools for program structuring. Modules emphasize explicit configuration of program components and the use of data abstraction. Type classes emphasize implicit program construction and ad hoc polymorphism. In this paper, we show how the implicitly-typed style of type class programming may be supported within the framework of an explicitly-typed module language by viewing type classes as a particular mode of use of modules. This view offers a harmonious integration of modules and type classes, where type class features, such as class hierarchies and associated types, arise naturally as uses of existing module-language constructs, such as module hierarchies and type components. In addition, programmers have explicit control over which type class instances are available for use by type inference in a given scope. We formalize our approach as a Harper-Stone-style elaboration relation, and provide a sound type inference algorithm as a guide to implementation.

REFERENCES

• 1: Manuel M. T. Chakravarty , Gabriele Keller , Simon Peyton Jones, Associated type synonyms, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 2: 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
• 3: Luis Damas , Robin Milner, Principal type-schemes for functional programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-212, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582176]
• 4: Derek Dreyer , Robert Harper , Karl Crary, Understanding and evolving the ml module system, Carnegie Mellon University, Pittsburgh, PA, 2005
• 5: Derek Dreyer and Matthias Blume. Principal type schemes for modular programs. Technical Report TR-2006-08, University of Chicago Comp. Sci. Dept., October 2006.
• 6: Derek Dreyer , Karl Crary , Robert Harper, A type system for higher-order modules, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.236-249, January 15-17, 2003, New Orleans, Louisiana, USA
• 7: Derek Dreyer, Robert Harper, Manuel M.T. Chakravarty, and Gabriele Keller. Modular type classes. Technical Report TR-2006-09, University of Chicago Comp. Sci. Dept., October 2006.
• 8: Robert Harper , John C. Mitchell , Eugenio Moggi, Higher-order modules and the phase distinction, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.341-354, December 1989, San Francisco, California, United States [doi>10.1145/96709.96744]
• 9: Robert Harper , Christopher Stone, A type-theoretic interpretation of standard ML, Proof, language, and interaction: essays in honour of Robin Milner, MIT Press, Cambridge, MA, 2000
• 10: Mark P. Jones, Simplifying and improving qualified types, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.160-169, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224198]
• 11: Mark P. Jones, A theory of qualified types, Symposium proceedings on 4th European symposium on programming, p.287-306, January 1992, Rennes, France
• 12: Mark P. Jones, Type Classes with Functional Dependencies, Proceedings of the 9th European Symposium on Programming Languages and Systems, p.230-244, April 02, 2000
• 13: Mark P. Jones, Using parameterized signatures to express modular structure, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.68-78, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237731]
• 14: Mark P. Jones, Qualified types: theory and practice, Cambridge University Press, New York, NY, 1995
• 15: Mark P. Jones. A system of constructor classes: Overloading and implicit higher-order polymorphism. Journal of Functional Programming, 5(1), 1995.
• 16: Wolfram Kahl and Jan Scheffczyk. Named instances for Haskell type classes. In Haskell Workshop, 2001.
• 17: David MacQueen, Modules for standard ML, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.198-207, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802036]
• 18: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 19: Simon Peyton Jones et al. Haskell 98 language and libraries: the revised report. Journal of Functional Programming, 13(1), 2003.
• 20: Gerhard Schneider. ML mit Typklassen. Master's thesis, June 2000.
• 21: Jeremy G. Siek , Andrew Lumsdaine, A language for generic programming, Indiana University, Indianapolis, IN, 2005
• 22: Jeremy Siek , Jeremy G. Siek , Andrew Lumsdaine, Essential language support for generic programming, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 23: 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]
• 24: Stefan Wehr. ML modules and Haskell type classes: A constructive comparison. Master's thesis, Albert-Ludwigs-Universität Freiburg, Institut für Informatik, 2005.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Modules, packages; Polymorphism

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Design, Languages, Theory

Keywords:
modules, type classes, type inference, type systems