More Web Proxy on the site http://driver.im/

article

Type-checking multi-parameter type classes

Authors:

Dominic Duggan,

John OphelAuthors Info & Claims

Journal of Functional Programming, Volume 12, Issue 2

Pages 133 - 158

https://doi.org/10.1017/S0956796801004233

Published: 01 March 2002 Publication History

Abstract

Type classes are a novel combination of parametric polymorphism and constrained types. Although most implementations restrict type classes to be single-parameter, the generalization to multi-parameter type classes has gained increasing attention. A problem with multi-parameter type classes is the increased possibilities they introduce for ambiguity in inferred types, impacting their usefulness in many practical situations. A new type-checking strategy, domain-driven unifying resolution, is identified as an approach to solve these problems. Domain-driven unifying resolution is simple, efficient, and practically useful. However, even with severe restrictions on instance definitions, it is not possible to guarantee that type-checking with unifying resolution terminates. This is in contrast with the naive generalization of single parameter resolution strategies. Domain-driven unifying resolution is guaranteed to terminate if the type class constraints are satisfiable; however satisfiability is undecidable even with severe restrictions on instance definitions. These results shed some light on ambiguity problems with multi-parameter type classes.

References

[1]

Chen, K., Hudak, P. and Odersky, M. (1992) Parameteric type classes (extended abstract). Proceedings of ACM Symposium on Lisp and Functional Programming, pp. 170-181. ACM Press.

[2]

Cormack, G. and Wright, A. (1990) Type-dependent parameter inference. Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 127-136. ACM Press.

Digital Library

[3]

Dubois, C., Rouaix, F. and Weis, P. (1995) Extensional polymorphism. Proceedings of ACM Symposium on Principles of Programming Languages, ACM Press.

[4]

Hall, C., Hammond, K., Peyton-Jones, S. and Wadler, P. (1996) Type classes in Haskell. ACM Trans. Programming Langu. Syst. 18(2), 109-138.

Digital Library

[5]

Jones, M. (1991) An introduction to Gofer. Available via ftp from nebula.cs.yale.edu in pub/haskell/gofer.

[6]

Jones, M. (1992) Qualified Types: Theory and Practice. PhD thesis, Oxford University Computing Laboratory.

[7]

Jones, M. (1993) A system of constructor classes: Overloading and implicit higher-order polymorphism. Proceedings of ACM Symposium on Functional Programming and Computer Architecture: Lecture Notes in Computer Science 594, pp. 1-10. Springer-Verlag.

[8]

Jones, M. (1994) Re: Multiple parameter classes. E-mail message on Haskell mailing list.

[9]

Jones, M. (1995) Simplifying and improving qualified types Proceedings of ACM Symposium on Functional Programming and Computer Architecture. ACM Press.

[10]

Jones, M. (2000) Type classes with functional dependencies. European Symposium on Programming: Lecture Notes in Computer Science 1782. Springer-Verlag.

[11]

Kaes, S. (1988) Parametric overloading in polymorphic programming languages. In: D. Sannella, editor, European Symposium on Programming: Lecture Notes in Computer Science 300, pp. 131-144. Springer-Verlag.

[12]

Liang, S., Hudak, P. and Jones, M. (1995) Monad transformers and modular interpreters. Proceedings of ACM Symposium on Principles of Programming Languages, pp. 333-343. ACM Press.

[13]

Nipkow, T. and Prehofer, C. (1993) Type reconstruction for type classes. Proceedings of ACM Symposium on Principles of Programming Languages, pp. 409-418. ACM Press.

[14]

Nipkow, T. and Snelting, G. (1991) Type classes and overloading resolution via order-sorted unification. In: J. Hughes, editor, Proceedings of ACM Symposium on Functional Programming and Computer Architecture: Lecture Notes in Computer Science 523, pp. 1-14. Springer-Verlag.

[15]

Odersky, M., Wadler, P. and Wehr, M. (1995) A second look at overloading. Proc. ACM Conf. on Functional Programming and Computer Architecture, pp. 135-146.

Digital Library

[16]

Peyton-Jones, S. (1998) Multi-parameter type classes in GHC. URL: http:// research.microsoft.com/Users/simonpj/Haskell/multi-param.html.

[17]

Peyton-Jones, S., Jones, M. and Meijer, E. (1997) Type classes: an exploration of the design space. Haskell Workshop. Amsterdam, the Netherlands.

[18]

Volpano, D. and Smith, G. (1991) On the complexity of ML typability with overloading. In: J. Hughes, editor, Proceedings of ACM Symposium on Functional Programming and Computer Architecture: Lecture Notes in Computer Science 523, pp. 15-28. Springer-Verlag.

[19]

Wadler, P. and Blott, S. (1989) How to make ad-hoc polymorphism less ad-hoc. In: M. O'Donnell and S. Feldman, editors, Proceedings of ACM Symposium on Principles of Programming Languages, pp. 60-76. ACM Press.

Cited By

Lutze MMadsen M(2024)Associated Effects: Flexible Abstractions for Effectful ProgrammingProceedings of the ACM on Programming Languages10.1145/36563938:PLDI(394-416)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656393
Devriese DPiessens FChakravarty MHu ZDanvy O(2011)On the bright side of type classesProceedings of the 16th ACM SIGPLAN international conference on Functional programming10.1145/2034773.2034796(143-155)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.1145/2034773.2034796
Devriese DPiessens F(2011)On the bright side of type classesACM SIGPLAN Notices10.1145/2034574.203479646:9(143-155)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.1145/2034574.2034796
Show More Cited By

Recommendations

Type checking type classes
POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

We 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 ...
Modular type classes
Proceedings of the 2007 POPL Conference

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 ...
A parametric extension of Haskell's type classes

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Functional Programming

Journal of Functional Programming Volume 12, Issue 2

March 2002

92 pages

ISSN:0956-7968

Issue’s Table of Contents

Publisher

Cambridge University Press

United States

Publication History

Published: 01 March 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lutze MMadsen M(2024)Associated Effects: Flexible Abstractions for Effectful ProgrammingProceedings of the ACM on Programming Languages10.1145/36563938:PLDI(394-416)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656393
Devriese DPiessens FChakravarty MHu ZDanvy O(2011)On the bright side of type classesProceedings of the 16th ACM SIGPLAN international conference on Functional programming10.1145/2034773.2034796(143-155)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.1145/2034773.2034796
Devriese DPiessens F(2011)On the bright side of type classesACM SIGPLAN Notices10.1145/2034574.203479646:9(143-155)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.1145/2034574.2034796
Brunel JDoligez DHansen RLawall JMuller G(2009)A foundation for flow-based program matchingACM SIGPLAN Notices10.1145/1594834.148089744:1(114-126)Online publication date: 21-Jan-2009
https://dl.acm.org/doi/10.1145/1594834.1480897
Schrijvers TGuillemette LMonnier SAltenkirch TMillstein T(2009)Type invariants for HaskellProceedings of the 3rd workshop on Programming languages meets program verification10.1145/1481848.1481855(39-48)Online publication date: 20-Jan-2009
https://dl.acm.org/doi/10.1145/1481848.1481855
Brunel JDoligez DHansen RLawall JMuller GShao ZPierce B(2009)A foundation for flow-based program matchingProceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/1480881.1480897(114-126)Online publication date: 21-Jan-2009
https://dl.acm.org/doi/10.1145/1480881.1480897
Sulzmann MDuck GPeyton-Jones SStuckey P(2007)Understanding functional dependencies via constraint handling rulesJournal of Functional Programming10.1017/S095679680600613717:1(83-129)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.1017/S0956796806006137
Stuckey PSulzmann M(2005)A theory of overloadingACM Transactions on Programming Languages and Systems10.1145/1108970.110897427:6(1216-1269)Online publication date: 1-Nov-2005
https://dl.acm.org/doi/10.1145/1108970.1108974
Camarão CFigueiredo LVasconcellos CMoggi EWarren D(2004)Constraint-set satisfiability for overloadingProceedings of the 6th ACM SIGPLAN international conference on Principles and practice of declarative programming10.1145/1013963.1013974(67-77)Online publication date: 24-Aug-2004
https://dl.acm.org/doi/10.1145/1013963.1013974

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents