Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-15T05:39:00.959Z Has data issue: false hasContentIssue false
  • English
  • Français

A system of constructor classes: overloading and implicit higher-order polymorphism†

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

Mark P. Jones
Mark P. Jones
Affiliation:
Department of Computer Science, Yale University, PO Box 208285, New Haven, CT 06520-8285, USA (e-mail: jones-mark@cs.yale.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper describes a flexible type system that combines overloading and higher-order polymorphism in an implicitly typed language using a system of constructor classes—a natural generalization of type classes in Haskell. We present a range of examples to demonstrate the usefulness of such a system. In particular, we show how constructor classes can be used to support the use of monads in a functional language. The underlying type system permits higher-order polymorphism but retains many of the attractive features that have made Hindley/Milner type systems so popular. In particular, there is an effective algorithm that can be used to calculate principal types without the need for explicit type or kind annotations. A prototype implementation has been developed providing, amongst other things, the first concrete implementation of monad comprehensions known to us at the time of writing.

Type
Articles
Information
Journal of Functional Programming , Volume 5 , Issue 1 , January 1995 , pp. 1 - 35
Copyright
Copyright © Cambridge University Press 1995

References

Barendregt, H. (1991) Introduction to generalized type systems. Journal of Functional Programming, 1(2).CrossRefGoogle Scholar
Breazu-Tannen, V., Coquand, T., Gunter, C. A. and Scedrov, A. (1989) Inheritance and coercion. IEEE Symposium on Logic in Computer Science.Google Scholar
Chen, K., Hudak, P. and Odersky, M. (1992) Parametric type classes (Extended abstract). ACM Conf. LISP and Functional Programming,San Francisco, CA, June.CrossRefGoogle Scholar
Damas, L. and Milner, R. (1982) Principal type schemes for functional programs. 8th Ann. ACM Symposium on Principles of Programming languagesCrossRefGoogle Scholar
Hudak, P. and Fasel, J. (1992) A gentle introduction to Haskell. ACM SIGPLAN Notices, 27(5).CrossRefGoogle Scholar
Hudak, P., Peyton Jones, S. L. and Wadler, P. (eds.) (1992) Report on the programming language Haskell, version 1.2. ACM SIGPLAN Notices, 27(5).CrossRefGoogle Scholar
Jones, M. P. (1991) Introduction to Gofer—included as part of the Gofer distribution, available by anonymous ftp from nebula.cs.yale.edu in the directory pub/haskell/gofer.Google Scholar
Jones, M. P. (1992a) A theory of qualified types. European symposium on programming. Lecture Notes in Computer Science 582. Springer-Verlag.Google Scholar
Jones, M. P. (1992b) Qualified types: Theory and Practice. DPhil thesis, Oxford University Computing Laboratory.Google Scholar
Jones, M. P. (1992c) Programming with constructor classes (preliminary summary). Proc. Fifth Annual Glasgow Workshop on Functional Programming, Ayr, Scotland. Springer-Verlag.Google Scholar
Jones, M. P. and Duponcheel, L. (1993) Composing Monads. Yale University, Department of Computer Science, Research Report YALEU/DCS/RR-1004.Google Scholar
King, D. J. and Wadler, P. (1992) Combining monads. Proc. Fifth Annual Glasgow Workshop on Functional Programming, Ayr, Scotland. Springer-Verlag.Google Scholar
MacLane, S. (1971) Categories for the working mathematician. Graduate Texts in Mathematics 5. Springer-Verlag.Google Scholar
MacQueen, D. B. (1984) Modules for Standard ML. Conf. Record 1984 ACM Symposium on Lisp and Functional Programming.CrossRefGoogle Scholar
Milner, R. (1978) A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17(3).CrossRefGoogle Scholar
Milner, R., Tofte, M. and Harper, R. (1990) The definition of Standard ML. MIT Press.Google Scholar
Moggi, E. (1989) Computational lambda-calculus and monads. IEEE Symposium on Logic in Computer Science, Asilomar, CA.Google Scholar
Robinson, J. A. (1965) A machine-oriented logic based on the resolution principle. Journal ACM, 12.CrossRefGoogle Scholar
Spivey, M. (1990) A functional theory of exceptions. Science of Computer Programming, 14(1).CrossRefGoogle Scholar
Steele, G. L. Jr (1994) Building interpreters by composing monads. 21st Ann. ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages,Portland,Oregon.CrossRefGoogle Scholar
Wadler, P. and Blott, S. (1989) How to make ad-hoc polymorphism less ad-hoc. 16th Ann. ACM Symposium on Principles of Programming Languages,Austin, TX.CrossRefGoogle Scholar
Wadler, P. (1990) Comprehending Monads. ACM Conf. LISP and Functional Programming,Nice, France.CrossRefGoogle Scholar
Wadler, P. (1992) The essence of functional programming. 19th Ann. ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages,Santa Fe, NM.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.