AbstractThe combination of subtypings, conditional constraints and rows yields a powerful constraint-based type inference system. We illustrate this claim by propo sing solutions to three delicate type inference problems: ``accurate'' pattern matchings, record concatenation, and first-class messages. Previously known solutions involved a different technique in each case; our theoretical contribut ion is in using only a single set of tools. On the practical side, this allows all three problems to benefit from a c ommon set of constraint simplification techniques, a formal description of which is given in an appendix.
Categories and Subject Descriptors: F.3.3 [Logics and Meanings of Programs]: Studies of Program Constructs
Additional Key Words and Phrases: constraint-based type inference, subtyping, rows, conditional constraints
Selected references
- Alexander Aiken, Edward L. Wimmers, and T. K. Lakshman. Soft typing with conditional types. In Conference Record of POPL '94: 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 163-173, Portland, Oregon, January 1994.
- Cormac Flanagan and Matthias Felleisen. Componential set-based analysis. In Proceedings of the ACM SIGPLAN'97 Conference on Programming Language Design and Implementation (PLDI), pages 235-248, Las Vegas, Nevada, 15-18 June 1997. SIGPLAN Notices 32(5), May 1997.
- Robert Harper and Benjamin C. Pierce. A record calculus based on symmetric concatenation. In Conference Record of the Eighteenth Annual ACM Symposium on Principles of Programming Languages, pages 131-142, Orlando, Florida, January 1991.
- Susumu Nishimura. Static typing for dynamic messages. In Conference Record of POPL '98: The 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 266-278, San Diego, California, 19-21 January 1998.
- Atsushi Ohori. A polymorphic record calculus and its compilation. ACM Transactions on Programming Languages and Systems, 17(6):844-895, November 1995.
- Didier Rémy. From classes to objects via subtyping. In Chris Hankin, editor, Programming Languages and Systems -- ESOP'98, 7th European Symposium on Programming, volume 1381 of Lecture Notes in Computer Science, pages 200-220, Lisbon, Portugal, 28 March-4 April 1998. Springer.
- Mitchell Wand. Type inference for record concatenation and multiple inheritance. Information and Computation, 93(1):1-15, July 1991.