Soft typing with conditional types

ABSTRACT

We present a simple and powerful type inference method for dynamically typed languages where no type information is supplied by the user. Type inference is reduced to the problem of solvability of a system of type inclusion constraints over a type language that includes function types, constructor types, union, intersection, and recursive types, and conditional types. Conditional types enable us to analyze control flow using type inference, thus facilitating computation of accurate types. We demonstrate the power and practicality of the method with examples and performance results from an implementation.

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	Alexander Aiken , Brian R. Murphy, Implementing regular tree expressions, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.427-447, June 1991, Cambridge, Massachusetts, United States
	2	Alex Aiken , Brian Murphy, Static type inference in a dynamically typed language, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.279-290, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99621]
	3	Alexander Aiken , Edward L. Wimmers, Type inclusion constraints and type inference, Proceedings of the conference on Functional programming languages and computer architecture, p.31-41, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165188]
	4	John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
	5	BACKUS, J., WILLIAMS, J. H., WIMMERS, E. L., LU- CAS, P., AND AIKEN, A. The FL language manual parts I and 2. Tech. Rep. RJ 7100 (67163), IBM, 1989.
	6	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
	7	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]
	8	Tim Freeman , Frank Pfenning, Refinement types for ML, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.268-277, June 24-28, 1991, Toronto, Ontario, Canada
	9	You-Chin Fuh , Prateek Mishra, Type inference with subtypes, Proceedings of the Second European Symposium on Programming, p.155-175, January 1988, Nancy, France
	10	Carsten K. Gomard, Partial type inference for untyped functional programs, Proceedings of the 1990 ACM conference on LISP and functional programming, p.282-287, June 27-29, 1990, Nice, France [doi>10.1145/91556.91672]
	11	Nevin Charles Heintze, Set based program analysis, Carnegie Mellon University, Pittsburgh, PA, 1992
	12	Fritz Henglein, Global tagging optimization by type inference, Proceedings of the 1992 ACM conference on LISP and functional programming, p.205-215, June 22-24, 1992, San Francisco, California, United States
	13	Neil D. Jones , Steven S. Muchnick, Flow analysis and optimization of LISP-like structures, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.244-256, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567776]
	14	KOZEN, D., PALSBERG, J., AND SCHWARTZBACH, M. I. Efficient inference of partial types. In Foundations of Computer Science (Oct. 1992), pp. 363-371.
	15	David MacQueen , Gordon Plotkin , Ravi Sethi, An ideal model for recursive polymorphic types, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.165-174, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800528]
	16	MILNER, R. A theory of type polymorphism in programming. J. Comput. Syst. Sci. 17 (1978), 348-375.
	17	Prateek Mishra , Uday S. Reddy, Declaration-free type checking, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.7-21, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318603]
	18	John C. Mitchell, Coercion and type inference, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.175-185, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800529]
	19	REYNOLDS, J. C. Automatic Computation of Data Set Definitions. Information Processing 68. North-Holland, 1969, pp. 456-461.
	20	O. Shivers, Control flow analysis in scheme, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.164-174, June 20-24, 1988, Atlanta, Georgia, United States
	21	Satish Thatte, Type Inference with Partial Types, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.615-629, July 11-15, 1988
	22	TOFTE, M. Operational Semantics and Polymorphic Type Inference. PhD thesis, University of Edinburgh, 1987.
	23	Edward Wang , Paul N. Hilfinger, Analysis of recursive types in Lisp-like languages, Proceedings of the 1992 ACM conference on LISP and functional programming, p.216-225, June 22-24, 1992, San Francisco, California, United States