John Peterson
ABSTRACT
We describe the implementation of a type checker for the functional programming language Haskell that supports the use of type classes. This extends the type system of ML to support overloading (ad-hoc polymorphism) and can be used to implement features such as equality types and numeric overloading in a simple and general way.
The theory of type classes is well understood, but the practical issues involved in the implementation of such systems have not received a great deal of attention. In addition to the basic type checking algorithm, an implmenentation of type classes also requires some form of program transformation. In all current Haskell compilers this takes the form of dictionary conversion, using functions as hidden parameters to overloaded values. We present efficient techniques for type checking and dictionary conversion. A number of optimizations and extensions to the basic type class sytems are also described.
- 1.A.W. Appel. A critique of Standard ML. Princeton University CS-TR-364-92, February 1992.Google Scholar
- 2.A.W. Appel. Compiling with continuations. Cambridge University Press, 1992. Google ScholarDigital Library
- 3.L. Augustsson. Implementing HaskeH overloading. To appear in Conference on Functional Programming Languages and Computer Architecture, Copenhagen, Denmark, June 1993. Google ScholarDigital Library
- 4.L. Damas and R. Milner. Principal type schemes for functional programs. In 8th Annual A CM Symposium on Principles of Programming languages, 1982. Google ScholarDigital Library
- 5.K. Hammond and S. Blott. Implementing Haskell type classes. Proceedings of the 1989 Glasgow Workshop on Functional Programming, Fraserburgh, Scotland. Workshops in computing series, Springer Verlag. Google ScholarDigital Library
- 6.P. Hudak, S.L. Peyton Jones and P. Wadler (eds.). Report on the programming language Haskell, version 1.2. A CM SIGPLAN notices, 27, 5, May 1992. Google ScholarDigital Library
- 7.M.P. Jones. Computing with lattices: An application of type classes. Journal of Functional Programming, Volume 2, Part 4, October 1992.Google ScholarCross Ref
- 8.M.P. Jones. Qualified types: Theory and Practice. D. Phil. Thesis. Programming Research Group, Oxford University Computing Laboratory. July 1992. Google ScholarDigital Library
- 9.S.L. Peyton Jones and D. Lester. A modular fully-lazy lambda lifter in HaskeU. Software - Practice and Experience, 21(5), May 1991. Google ScholarDigital Library
- 10.S.L. Peyton Jones and P. Wadler. A static semantics for Haskell (draft). Manuscript, Department of Computing Science, University of Glasgow, February 1992.Google Scholar
- 11.P. WacUer and S. Blott. How to make ad-hoc polymorphism less ad-hoc. In A CM Principles of Programming Languages, 1989. Google ScholarDigital Library
Index Terms
- Implementing type classes
Recommendations
Type checking type classes
POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesWe study the type inference problem for a system with type classes as in the functional programming language Haskell. Type classes are an extension of ML-style polymorphism with overloading. We generalize Milner's work on polymorphism by introducing a ...
Implementing type classes
We describe the implementation of a type checker for the functional programming language Haskell that supports the use of type classes. This extends the type system of ML to support overloading (ad-hoc polymorphism) and can be used to implement features ...
Comments