Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-13T12:30:24.853Z Has data issue: false hasContentIssue false
  • English
  • Français

Type classes with existential types

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

Konstantin Läufer
Konstantin Läufer
Affiliation:
Department of Mathematical and Computer Sciences, Loyola University of Chicago, 6525 North Sheridan Road, Chicago, IL 60626, USA (e-mail: laufer@math.luc.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.

We argue that the novel combination of type classes and existential types in a single language yields significant expressive power. We explore this combination in the context of higher-order functional languages with static typing, parametric polymorphism, algebraic data types and Hindley–Milner type inference. Adding existential types to an existing functional language that already features type classes requires only a minor syntactic extension. We first demonstrate how to provide existential quantification over type classes by extending the syntax of algebraic data type definitions, and give examples of possible uses. We then develop a type system and a type inference algorithm for the resulting language. Finally, we present a formal semantics by translation to an implicitly-typed second-order λ-calculus and show that the type system is semantically sound. Our extension has been implemented in the Chalmers Haskell B. system, and all examples from this paper have been developed using this system.

Type
Articles
Information
Journal of Functional Programming , Volume 6 , Issue 3 , May 1996 , pp. 485 - 518
Copyright
Copyright © Cambridge University Press 1996

References

Augustsson, L. (1993a) Haskell B. user manual. Distributed with the HBC compiler.Google Scholar
Augustsson, L. (1993b) Implementing Haskell overloading. Proc. Functional Programming Languages and Computer Architecture. ACM.Google Scholar
Baumgartner, G. and Russo, V. (1994) Signatures: A C ++ extension for type abstraction and subtype polymorphism. Software: Practice & Experience. To appear.Google Scholar
Blott, S. (1991) An Approach to Overloading with Polymorphism. PhD thesis, Department of Computing Science, University of Glasgow.Google Scholar
Cardelli, L. and Leroy, X. (1990) Abstract types and the dot notation. Proc. IFIP Working Conference on Programming Concepts and Methods, pp. 466–491, Sea of Galilee, Israel.Google Scholar
Cardelli, L. and Wegner, P. (1985) On understanding types, data abstraction and polymorphism. ACM Computing Surveys 17(4): 471–522.Google Scholar
Chen, K., Hudak, P. and Odersky, M. (1992) Parametric type classes. Proc. ACM Conf. Lisp and Functional Programming.Google Scholar
Damas, L. and Milner, R. (1982) Principal type schemes for functional programs. Proc. 9th ACM Symp. on Principles of Programming Languages, pp. 207–212.Google Scholar
Hall, C., Hammond, K., Peyton Jones, S. and Wadler, P. (1992) Type classes in Haskell. Technical report, Department of Computer Science, University of Glasgow.Google Scholar
Harper, R. and Lillibridge, M. (1994) A type-theoretic approach to higher-order modules with sharing. Proc. 21st ACM Symp. on Principles of Programming Languages, pp. 123–137.Google Scholar
Hudak, P., Peyton-Jones, S., Wadler, P., et al. (1992) Report on the programming language Haskell: A non-strict, purely functional language, Version 1.2. ACM SIGPLAN Notices, 27(5).CrossRefGoogle Scholar
Jones, M. (1993a) Coherence for qualified types. Technical Report YALEU/DCS/RR-989, Department of Computer Science, Yale University.Google Scholar
Jones, M. (1993b) A system of constructor classes: Overloading and implicit higher-order polymorphism. Proc. Functional Programming Languages and Computer Architecture. ACM.Google Scholar
Kaes, S. (1988) Parametric overloading in polymorphic programming languages. In Ganzinger, H., editor, Proc. 2nd European Symposium on Programming, pp. 131–144, Nancy, France.Lecture Notes in Computer Science 300, Springer-Verlag.CrossRefGoogle Scholar
Läufer, K. (1992) Polymorphic type inference and abstract data types. PhD thesis, New York University. (Available as Technical Report 622, December 1992, from New York University, Department of Computer Science.)Google Scholar
Läufer, K. and Odersky, M. (1991) Type classes are signatures of abstract types. Proc. Phoenix Seminar and Workshop on Declarative Programming, pp. 148–162. Workshops in Computing series, Springer-Verlag.Google Scholar
Läufer, K. and Odersky, M. (1994) Polymorphic type inference and abstract data types. ACM Trans. Programming Languages and Systems (TOPLAS), 16(5): 1411–1430.CrossRefGoogle Scholar
Leroy, X. (1994) Manifest types, modules, and separate compilation. Proc. 21st ACM Symp. on Principles of Programming Languages, pp. 109–123.CrossRefGoogle Scholar
Liskov, B. and Guttag, J. (1986) Abstraction and Specification in Program Development. MIT Press.Google Scholar
MacQueen, D., Plotkin, G. and Sethi, R. (1986) An ideal model for recursive polymorphic types. Information and Control (71): 95–130.Google Scholar
Mitchell, J., Meldal, S. and Madhav, N. (1991) An extension of Standard ML modules with subtyping and inheritance. Proc. 18th ACM Symp. on Principles of Programming Languages.CrossRefGoogle Scholar
Mitchell, J. and Plotkin, G. (1988) Abstract types have existential type. ACM Trans. Programming Languages and Systems 10(3): 470–502.CrossRefGoogle Scholar
Nipkow, T. and Prehofer, C. (1993) Type checking type classes. Proc. 20th ACM Symp. Principles of Programming Languages.CrossRefGoogle Scholar
Nipkow, T. and Snelting, G. (1991) Type classes and overloading resolution via order-sorted unification. Proc. Functional Programming Languages and Computer Architecture, pp. 1–14. Lecture Notes in Computer Science 523, Springer-Verlag.Google Scholar
Perry, N. (1990) The Implementation of Practical Functional Programming Languages. PhD thesis, Imperial College.Google Scholar
Pierce, B. and Turner, D. (1993) Simple type-theoretic foundations for object-oriented programming. Journal of Functional Programming.Google Scholar
Rémy, D. (1994) Programming objects with ML-ART: An extension to ML with abstract and record types. Proc. Intl. Symp. Theoretical Aspects of Computer Software (TACS). Lecture Notes in Computer Science, Springer-Verlag.Google Scholar
Stroustrup, B. (1986) The C++ Programming Language. Addison-Wesley.Google Scholar
Thatte, S. (1994) Semantics of type classes revisited. Proc. ACM Conf. Lisp and Functional Programming.Google Scholar
United States Department of Defense (1983) Reference Manual for the ADA Programming Language. Springer-Verlag.Google Scholar
Wadler, P. and Blott, S. (1989) How to make ad-hoc polymorphism less ad hoc. Proc. 16th ACM Symp. on Principles of Programming Languages, pp. 60–76.CrossRefGoogle Scholar
Wirth, N. (1985) Programming in Modula-2. Springer-Verlag. 3rd edition.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.