John Plevyak
Andrew A. Chien
Abstract
Concrete type information is invaluable for program optimization. The determination of concrete types in object-oriented languages is a flow sensitive global data flow problem. It is made difficult by dynamic dispatch (virtual function invocation) and first class functions (and selectors)—the very program structures for whose optimization its results are most critical. Previous work has shown that constraint-based type inference systems can be used to safely approximate concrete types [15], but their use can be expensive and their results imprecise.
We present an incremental constraint-based type inference which produces precise concrete type information for a much larger class of programs at lower cost. Our algorithm extends the analysis in response to discovered imprecisions, guiding the analysis' effort to where it is most productive. This produces precise information at a cost proportional to the type complexity of the program. Many programs untypable by previous approaches or practically untypable due to computational expense, can be precisely analyzed by our new algorithm. Performance results, precision, and running time, are reported for a number of concurrent object-oriented programs. These results confirm the algorithm's precision and efficiency.
- 1 O. Agesen, J. Palsberg, and M. Schwartzbach. Type inference of SELF: Analysis of objects with dynamic and multiple inheritance. In Proceedings of ECOOP '93, 1993. Google Scholar
Digital Library
- 2 Ole Agesen. Personal communication, 1993.Google Scholar
- 3 Alexander Aiken, Edward L. Wimmers, and T. K. Lakshman. Soft typing with conditional types. In Twenty Firs~ Symposium on Principles of Programming Languages, pages 151-162, Portland, Oregon, January 1994. Google ScholarDigital Library
- 4 Kim B. Bruce, Jon Crabtree, Thomas P. Murtagh, and Robert van Gent. Safe and decidable type checking in an object-oriented language. In Proceedings of OOPSLA '93, pages 29-46, 1993. Google ScholarDigital Library
- 5 Robert Cartwright and Mike Fagan. Soft typing. In Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, pages 278-292, Ontario, Canada, June 1991. Google ScholarDigital Library
- 6 C. Chambers and D. Ungar. Customization: Optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language. In Proceedings of SIGPLAN Conference on Programming Language Design and Implementation, pages 146-60, 1989. Google ScholarDigital Library
- 7 C. Chambers and D. Ungar. Iterative type analysis and extended message splitting. In Proceedings of the SIGPI, AN Conference on Programming ;Language Design and Implementation, pages 150-60, 1990. Google ScholarDigital Library
- 8 C. Chambers and D. Ungar. Making pure objectoriented languages practical. In OOPSLA '91 Conference Proceedings, 1991. Google ScholarDigital Library
- 9 Andrew A. Chien. Concurrent Aggregates: Supporting Modularity in Massively.Parallel Programs. MIT Press, Cambridge, MA, 1993. Google ScholarDigital Library
- 10 Andrew A. Chien, Vijay Karamcheti, John Plevyak, and Xingbin Zhang. Concurrent aggregates language report 2.0. Available via anonymous ftp from cs.uiuc.edu in /pub/csag or from http://www-csag.cs.uiuc.edu/, September 1993.Google Scholar
- 11 J. Choi, R. Cytron, and J. Ferrante. Automatic construction of sparse dataflow evaluation graphs. In Proceedings of the A CM Symposium on Principles of Programming Languages, 1990. Google ScholarDigital Library
- 12 J. Graver and R. Johnson. A type system for smalltalk, in Proceedings of POPL, pages 136-150, 1990. Google ScholarDigital Library
- 13 Robin Milner, Marls Torte, and Robert Harper. The Definition of Standard ML. The MIT Press, 1990. Google ScholarDigital Library
- 14 John C. Mitchell, Furio Honsell, and Kathleen Fisher. A lambda calculus of objects and method specialization. In 1993 IEEE Symposium on Logic in Computer Science, pages 26-38, June 1993.Google ScholarCross Ref
- 15 N. Oxhoj, J. Palsberg, and M. Schwartzbach. Making type inference practical. In Proceedings of OOPSLA '92, 1992. Google ScholarDigital Library
- 16 J. Palsberg and M. Schwartzbach. Object-oriented type inference. In Proceedings of OOPSLA '91, pages 146-61, 1991. Google ScholarDigital Library
- 17 John Plevyak and Andrew Chien. Precise objectoriented type inference and its use in program optimization. To be issued as a technical report, 1994.Google Scholar
- 18 Bernhard Rytz and Marc Gengler. A polyvariant binding time analysis. Technical Report YALEU/DCS/RR-909, Yale University, Department of Computer Science, 1992. Proceedings of the 1992 ACM Symposium on Partial Evaluation and Semantics-Based Program Manipulation.Google Scholar
- 19 Olin Shivers. Topics in Advanced Language Implementation, chapter Data-Flow Analysis and Type Recovery in Scheme, pages 47-88. MIT Press, Cambridge, MA, 1991.Google Scholar
- 20 Norihisa Suzuki. Inferring types in Smalltalk. In Eighth Symposium on Principles of Programming Languages, pages 187-199, January 1981. Google ScholarDigital Library
- 21 Thinking Machines Corporation, Cambridge, Massachusetts. CM-5 Technical Summary, October 1991.Google Scholar
- 22 David Ungar and Randall B. Smith. SELF: The power of simplicity. In Proceedings of OOPSLA '87, pages 227-41. ACM SIGPLAN, ACM Press, 1987. Google ScholarDigital Library
Index Terms
- Precise concrete type inference for object-oriented languages
Recommendations
Precise concrete type inference for object-oriented languages
OOPSLA '94: Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applicationsConcrete type information is invaluable for program optimization. The determination of concrete types in object-oriented languages is a flow sensitive global data flow problem. It is made difficult by dynamic dispatch (virtual function invocation) and ...
Comments