A polymorphic record calculus and its compilation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A polymorphic record calculus and its compilation

Full text

Pdf (3.56 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 17 , Issue 6 (November 1995) table of contents

Pages: 844 - 895

Year of Publication: 1995

ISSN:0164-0925

Author

Atsushi Ohori

Kyoto University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 53, Citation Count: 27

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/218570.218572 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	APPEL, A. W. AND MACQUEEN, D. B. 1991. Standard ML of New Jersey. In Proceedings of the 3rd International Symposium on Programming Languages and Logic Programmzng. Lecture Notes in Computer Science, vol. 528. Springer-Verlag, Berlin, 1-13.
	2	BARENDREGT, H. 1984. The Lambda Calculus: Its Syntax and Semantics, rev. ed. Studies in Logic and the Foundations of Mathematics, vol. 103. North-Holland, Amsterdam.
	3	V. Breazu-Tannen , T. Coquand, Extensional models for polymorphism, Theoretical Computer Science, v.59 n.1-2, p.85-114, July 1988 [doi>10.1016/0304-3975(88)90097-7]
	4	Val Breazu-Tannen , Thierry Coquand , Carl A. Gunter , Andre Scedrov, Inheritance as implicit coercion, Information and Computation, v.93 n.1, p.172-221, July 1991 [doi>10.1016/0890-5401(91)90055-7]
	5	Kim B. Bruce , Albert R. Meyer , John C. Mitchell, The semantics of second-order lambda calculus, Information and Computation, v.85 n.1, p.76-134, March 1990 [doi>10.1016/0890-5401(90)90044-I]
	6	Peter Buneman , Achim Jung , Atsushi Ohori, Using powerdomains to generalize relational databases, Theoretical Computer Science, v.91 n.1, p.23-55, Dec. 9, 1991 [doi>10.1016/0304-3975(91)90266-5]
	7	Peter Buneman , Atsushi Ohori, Polymorphism and type inference in database programming, ACM Transactions on Database Systems (TODS), v.21 n.1, p.30-76, March 1996 [doi>10.1145/227604.227609]
	8	Luca Cardelli, A semantics of multiple inheritance, Information and Computation, v.76 n.2-3, p.138-164, February/March 1988 [doi>10.1016/0890-5401(88)90007-7]
	9	Luca Cardelli, Extensible records in a pure calculus of subtyping, Theoretical aspects of object-oriented programming: types, semantics, and language design, MIT Press, Cambridge, MA, 1994
	10	Luca Cardelli , John C. Mitchell, Operations on records, Proceedings of the fifth international conference on Mathematical foundations of programming semantics, p.22-52, July 1990, New Orleans, Louisiana, United States
	11	Luca Cardelli , Peter Wegner, On understanding types, data abstraction, and polymorphism, ACM Computing Surveys (CSUR), v.17 n.4, p.471-523, Dec. 1985 [doi>10.1145/6041.6042]
	12	Robert Cartwright , Mike Fagan, Soft typing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.278-292, June 24-28, 1991, Toronto, Ontario, Canada
	13	R. C. H. Conner , A. Dearle , R. Morrison , A. L. Brown, An object addressing mechanism for statically typed languages with multiple inheritance, Conference proceedings on Object-oriented programming systems, languages and applications, p.279-285, October 02-06, 1989, New Orleans, Louisiana, United States
	14	COURCELLE, B. 1983. Fundamental properties of infinite trees. Theor. Comput. Sci. 25, 95-169.
	15	Luis Damas , Robin Milner, Principal type-schemes for functional programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-212, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582176]
	16	Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
	17	M. Felleisen , D. P. Friedman , E. Kohlbecker , B. Duba, A syntactic theory of sequential control, Theoretical Computer Science, v.52 n.3, p.205-237, June 1987 [doi>10.1016/0304-3975(87)90109-5]
	18	You-Chin Fuh , Prateek Mishra, Type inference with subtypes, Proceedings of the Second European Symposium on Programming, p.155-175, January 1988, Nancy, France
	19	FURUSE, J.P. AND GARRIGUE, J. 1995. A label selective lambda calculus with optional argument and its compilation method. RIMS Preprint 1041, Research Instit. for Mathematical Sciences, Kyoto Univ., Kyoto, Japan.
	20	J. H. Gallier , W. Snyder, Complete sets of transformations for general E-unification, Theoretical Computer Science, v.67 n.2-3, p.203-260, Oct. 1989 [doi>10.1016/0304-3975(89)90004-2]
	21	Jacques Garrigue , Hassan Aït-Kaci, The typed polymorphic label-selective λ-calculus, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.35-47, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.174434]
	22	GIRARD, J.-Y 1971 Une extension de l'interpretation de gddel 5. l'analyse, et son apphcatlon l'61imination des coupures dans l'analyse et thdorm des types. In the 2nd Scandinavian Logic Symposium. North-Holland, Amsterdam
	23	Cordelia V. Hall, Using Hindley-Milner type inference to optimise list representation, Proceedings of the 1994 ACM conference on LISP and functional programming, p.162-172, June 27-29, 1994, Orlando, Florida, United States
	24	HALL, C , HAMMOND, K., PEYTON JONES, S., AND WADLER, P. 1994. Type class in Haskell Tech. rep., Univ. of Glasgow, Glasgow, Scotland.
	25	Robert Harper , John C. Mitchell, On the type structure of standard ML, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.2, p.211-252, April 1993 [doi>10.1145/169701.169696]
	26	Robert Harper , Greg Morrisett, Compiling polymorphism using intensional type analysis, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.130-141, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199475]
	27	Robert Harper , Benjamin Pierce, A record calculus based on symmetric concatenation, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.131-142, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99603]
	28	Lalita A. Jategaonkar , John C. Mitchell, Type inference with extended pattern matching and subtypes, Fundamenta Informaticae, v.19 n.1-2, p.127-165, Sept./Oct. 1993
	29	Xavier Leroy, Unboxed objects and polymorphic typing, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.177-188, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143205]
	30	MILNER, R. 1978 A theory of type polymorphism m programming. J. Comput. Syst. Scz 17, 348-375.
	31	Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
	32	John Mitchell, Type inference and type containment., Proc. of the international symposium on Semantics of data types, p.257-277, July 1984, Sophia-Antipolis, France
	33	John C. Mitchell, Type systems for programming languages, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	34	Atsushi Ohori, A simple semantics for ML polymorphism, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.281-292, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99393]
	35	Atsushi Ohori, Semantics of types for database objects, Theoretical Computer Science, v.76 n.1, p.53-91, Oct. 31, 1990 [doi>10.1016/0304-3975(90)90012-7]
	36	Atsushi Ohori, A compilation method for ML-style polymorphic record calculi, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.154-165, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143200]
	37	Atsushi Ohori , Peter Buneman, Type inference in a database programming language, Proceedings of the 1988 ACM conference on LISP and functional programming, p.174-183, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62700]
	38	A. Ohori , P. Buneman, Static type inference for parametric classes, Conference proceedings on Object-oriented programming systems, languages and applications, p.445-450, October 02-06, 1989, New Orleans, Louisiana, United States
	39	OHORI, A. AND TAKAMIZAWA, T 1995 A polymorphic unboxed calculus as an abstract machine for polymorphic languages. RIMS Prepnnt 1031, Research InstR. for Mathematmal Sciences, Kyoto Univ., Kyoto, Japan.
	40	John Peterson , Mark Jones, Implementing type classes, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.227-236, June 21-25, 1993, Albuquerque, New Mexico, United States
	41	D. Rémy, Type checking records and variants in a natural extension of ML, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.77-88, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75284]
	42	Didier Rémy, Typing record concatenation for free, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.166-176, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143202]
	43	Rt~MY, D. 1994a. Efficient representation of extensible records. In Proceedings o} the ACM SIGPLAN Workshop on ML and Its Applications. ACM, New York, 12-16.
	44	Didier Rémy, Type inference for records in natural extension of ML, Theoretical aspects of object-oriented programming: types, semantics, and language design, MIT Press, Cambridge, MA, 1994
	45	John C. Reynolds, Towards a theory of type structure, Programming Symposium, Proceedings Colloque sur la Programmation, p.408-423, April 09-11, 1974
	46	J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
	47	Zhong Shao , John H. Reppy , Andrew W. Appel, Unrolling lists, Proceedings of the 1994 ACM conference on LISP and functional programming, p.185-195, June 27-29, 1994, Orlando, Florida, United States
	48	R. Stansifer, Type inference with subtypes, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.88-97, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73568]
	49	Guy L. Steele, Jr., Common LISP: the language, Digital Press, Newton, MA, 1984
	50	Andrew Tolmach, Tag-free garbage collection using explicit type parameters, Proceedings of the 1994 ACM conference on LISP and functional programming, p.1-11, June 27-29, 1994, Orlando, Florida, United States
	51	VA$CONCELOS, V. 1994. A process-calculus approach to typed concurrent objects. Ph.D. thesis, Dept. of Computer Science, Keio Univ., Yokohama, Japan.
	52	P. Wadler , S. Blott, How to make ad-hoc polymorphism less ad hoc, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-76, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75283]
	53	WAND, M. 1987. Complete type inference for simple objects. In Proceedings of the 2nd IEEE Symposium on Logic in Computer Science (Ithaca, New York). IEEE, New York, 37-44.
	54	WAND, M. 1988. Corrigendum : Complete type inference for simple object. In Proceedings of the 3rd IEEE Symposium on Logic ~n Computer Science. IEEE, New York, 132.
	55	M. Wand, Type inference for record concatenatiOn and multiple inheritance, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.92-97, June 1989, Pacific Grove, California, United States
	56	Andrew K. Wright , Robert Cartwright, A practical soft type system for Scheme, Proceedings of the 1994 ACM conference on LISP and functional programming, p.250-262, June 27-29, 1994, Orlando, Florida, United States

CITED BY 27

	Mark Shields , Erik Meijer, Type-indexed rows, ACM SIGPLAN Notices, v.36 n.3, p.261-275, March 2001
	Atsushi Ohori , Nobuaki Yoshida, Type inference with rank 1 polymorphism for type-directed compilation of ML, ACM SIGPLAN Notices, v.34 n.9, p.160-171, Sept. 1999
	Micheal Kohlhase , Andreas Franke, MBase: representing knowledge and context for the intergration of mathematical software systems, Journal of Symbolic Computation, v.32 n.4, p.365-402, October 2001
	Didier Rémy , Jérôme Vouillon, Objective ML: a simple object-oriented extension of ML, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.40-53, January 15-17, 1997, Paris, France
	Peter Buneman , Atsushi Ohori, Polymorphism and type inference in database programming, ACM Transactions on Database Systems (TODS), v.21 n.1, p.30-76, March 1996
	Xavier Leroy , François Pessaux, Type-based analysis of uncaught exceptions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.340-377, March 2000
	Susumu Nishimura, Static typing for dynamic messages, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.266-278, January 19-21, 1998, San Diego, California, United States
	Susumu Nishimura , Atsushi Ohori , Keishi Tajima, An equational object-oriented data model and its data-parallel query language, ACM SIGPLAN Notices, v.31 n.10, p.1-17, Oct. 1996
	François Pessaux , Xavier Leroy, Type-based analysis of uncaught exceptions, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.276-290, January 20-22, 1999, San Antonio, Texas, United States
	Atsushi Ohori , Kiyoshi Yamatodani, An interoperable calculus for external object access, ACM SIGPLAN Notices, v.37 n.9, p.60-71, September 2002
	Yasuhiko Minamide, A functional representation of data structures with a hole, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.75-84, January 19-21, 1998, San Diego, California, United States
	François Pottier, A versatile constraint-based type inference system, Nordic Journal of Computing, v.7 n.4, p.312-347, Winter 2000
	Yasuhiko Minamide , Jacques Garrigue, On the runtime complexity of type-directed unboxing, ACM SIGPLAN Notices, v.34 n.1, p.1-12, Jan. 1999
	Atsushi Ohori , Tomonobu Takamizawa, An Unboxed Operational Semantics for ML Polymorphism, Lisp and Symbolic Computation, v.10 n.1, p.61-91, June 1997
	Manfred Pinkal , Michael Kohlhase, Feature logic for dotted types: a formalism for complex word meanings, Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, p.521-528, October 03-06, 2000, Hong Kong
	Atsushi Ohori, Register allocation by proof transformation, Science of Computer Programming, v.50 n.1-3, p.161-187, March 2004
	Christopher A. Stone, Extensible objects without labels, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.5, p.805-835, September 2004
	Oleg Kiselyov , Ralf Lämmel , Keean Schupke, Strongly typed heterogeneous collections, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, September 22-22, 2004, Snowbird, Utah, USA
	Eijiro Sumii, MinCaml: a simple and efficient compiler for a minimal functional language, Proceedings of the 2005 workshop on Functional and declarative programming in education, September 25-25, 2005, Tallinn, Estonia
	François Pottier , Nadji Gauthier, Polymorphic typed defunctionalization and concretization, Higher-Order and Symbolic Computation, v.19 n.1, p.125-162, March 2006
	Huu-Duc Nguyen , Atsushi Ohori, Compiling ML polymorphism with explicit layout bitmap, Proceedings of the 8th ACM SIGPLAN symposium on Principles and practice of declarative programming, July 10-12, 2006, Venice, Italy
	Jan Van den Bussche , Dirk Van Gucht , Stijn Vansummeren, A crash course on database queries, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	Koji Kagawa, Polymorphic variants in Haskell, Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, September 17-17, 2006, Portland, Oregon, USA
	Matthias Blume , Umut A. Acar , Wonseok Chae, Extensible programming with first-class cases, ACM SIGPLAN Notices, v.41 n.9, September 2006
	Paul Hudak , John Hughes , Simon Peyton Jones , Philip Wadler, A history of Haskell: being lazy with class, Proceedings of the third ACM SIGPLAN conference on History of programming languages, p.12-1-12-55, June 09-10, 2007, San Diego, California
	Martin Sulzmann , Gregory J. Duck , Simon Peyton-Jones , Peter J. Stuckey, Understanding functional dependencies via constraint handling rules, Journal of Functional Programming, v.17 n.1, p.83-129, January 2007
	Jan Van den Bussche , Stijn Vansummeren, Polymorphic type inference for the named nested relational calculus, ACM Transactions on Computational Logic (TOCL), v.9 n.1, p.3-es, December 2007