Abstract
We propose a modest conservative extension to ML that allows semi-explicit higher-order polymorphism while preserving the essential properties of ML. In our proposal, the introduction of polymorphic types remains fully explicit, that is, both the introduction and the exact polymorphic type must be specified. However, the elimination of polymorphic types is now semi-implicit: only the elimination itself must be specified as the polymorphic type is inferred. This extension is particularly useful in Objective ML where polymorphism replaces subtyping.
Preview
Unable to display preview. Download preview PDF.
References
Luca Cardelli. An implementation of FSub. Research Report 97, Digital Equipment Corporation Systems Research Center, 1993.
L. Damas and R. Milner. Principal type-schemes for functional programs. In Proc. ACM Symposium on Principles of Programming Languages, pages 207–212. ACM Press, January 1982.
Dominic Duggan. Polymorphic methods with self types for ML-like languages. Technical report cs-95-03, University of Waterloo, 1995.
J.-P. Jouannaud and C. Kirchner. Solving equations in abstract algebras: a rulebased survey of unification. In Jean-Louis Lassez and G. Plotkin, editors, Computational Logic. Essays in honor of Alan Robinson, chapter 8, pages 257–321. MIT-Press, Cambridge (MA, USA), 1991.
A. J. Kfoury and J. B. Wells. A direct algorithm for type inference in the rank-2 fragment of the second-order λ-calculus. In ACM conference on Lisp and functional programming, pages 196–207, Orlando, Florida, June 1994.
Konstantin Läufer and Martin Odersky. Polymorphic type inference and abstract data types. ACM Transactions on Programming Languages and Systems, 16(5):1411–1430, September 1994.
Xavier Leroy and Michel Mauny. Dynamics in ML. In John Hughes, editor, Conference on Functional Programming and Computer Achitecture, volume 523 of Lecture Notes in Computer Science, pages 406–426. Springer-Verlag, 1991.
John C. Mitchell. Polymorphic type inference and containment. In Proc. Int. Symp. on Semantics of Data Types, Sophia-Antipolis (France), pages 257–278, Berlin, June 1984. Springer LNCS 173. Full version in Information and Computation, vol. 76, no. 2/3, 1988, pp. 211–249. Reprinted in Logical Foundations of Functional Programming, ed. G. Huet, Addison-Wesley (1990) 153–194.
Martin Odersky and Konstantin Läufer. Putting type annotations to work. In Proceedings of the 23th ACM Conference on Principles of Programming Languages, pages 54–67, January 1996.
Frank Pfenning. Partial polymorphic type inference and higher-order unification. In Proceedings of the 1988 ACM Conference on Lisp and Functional Programming, pages 153–163, Snowbird, Utah, July 1988. ACM Press.
Frank Henning. On the undecidability of partial polymorphic type reconstruction. Fundamenta Informatique, 19(1,2):185–199, 1993. Preliminary version available as Technical Report CMU-CS-92-105, School of Computer Science, Carnegie Mellon University, January 1992.
Benjamin C. Pierce and David N. Turner. Pict: A programming language based on the pi-calculus. Technical report, Computer Science Department, Indiana University, 1997.
Didier Rémy. Extending ML type system with a sorted equational theory. Research Report 1766, Institut National de Recherche en Informatique et Automatisme, Rocquencourt, BP 105, 78 153 Le Chesnay Cedex, France, 1992.
Didier Rémy. Programming objects with ML-ART: An extension to ML with abstract and record types. In Masami Hagiya and John C. Mitchell, editors, Theoretical Aspects of Computer Software, volume 789 of Lecture Notes in Computer Science, pages 321–346. Springer-Verlag, April 1994.
Didier Rémy and Jerôme Vouillon. Objective ML: A simple object-oriented extension to ML. In Proc. 24th symposium Principles of Programming Languages, pages 40–53. ACM Press, January 1997.
J. B. Wells. Typability and type checking in the second order λ-calculus are equivalent and undecidable. In Ninth annual IEEE symposium on Logic in computer science, pages 176–185, Paris, France, July 1994.
Andrew K. Wright. Polymorphism for imperative languages without imperative types. Technical Report 93-200, Rice University, February 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Garrigue, J., Rémy, D. (1997). Extending ML with semi-explicit higher-order polymorphism. In: Abadi, M., Ito, T. (eds) Theoretical Aspects of Computer Software. TACS 1997. Lecture Notes in Computer Science, vol 1281. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014546
Download citation
DOI: https://doi.org/10.1007/BFb0014546
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63388-4
Online ISBN: 978-3-540-69530-1
eBook Packages: Springer Book Archive