More Web Proxy on the site http://driver.im/

article

Free access

Precise concrete type inference for object-oriented languages

Authors:

Andrew A. ChienAuthors Info & Claims

ACM SIGPLAN Notices, Volume 29, Issue 10

Pages 324 - 340

https://doi.org/10.1145/191081.191130

Published: 01 October 1994 Publication History

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.

References

[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.

Digital Library

[2]

Ole Agesen. Personal communication, 1993.

[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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital Library

[8]

C. Chambers and D. Ungar. Making pure objectoriented languages practical. In OOPSLA '91 Conference Proceedings, 1991.

Digital Library

[9]

Andrew A. Chien. Concurrent Aggregates: Supporting Modularity in Massively.Parallel Programs. MIT Press, Cambridge, MA, 1993.

Digital 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.

[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.

Digital Library

[12]

J. Graver and R. Johnson. A type system for smalltalk, in Proceedings of POPL, pages 136-150, 1990.

Digital Library

[13]

Robin Milner, Marls Torte, and Robert Harper. The Definition of Standard ML. The MIT Press, 1990.

Digital 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.

[15]

N. Oxhoj, J. Palsberg, and M. Schwartzbach. Making type inference practical. In Proceedings of OOPSLA '92, 1992.

Digital Library

[16]

J. Palsberg and M. Schwartzbach. Object-oriented type inference. In Proceedings of OOPSLA '91, pages 146-61, 1991.

Digital 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.

[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.

[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.

[20]

Norihisa Suzuki. Inferring types in Smalltalk. In Eighth Symposium on Principles of Programming Languages, pages 187-199, January 1981.

Digital Library

[21]

Thinking Machines Corporation, Cambridge, Massachusetts. CM-5 Technical Summary, October 1991.

[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.

Digital Library

Cited By

Blizničenko JPergl R(2025)Combining type inference techniques for semi-automatic UML generation from Pharo codeJournal of Computer Languages10.1016/j.cola.2024.10130082(101300)Online publication date: Mar-2025
https://doi.org/10.1016/j.cola.2024.101300
Rubbo FPiveta ENunes D(2013)Inference rules for generic code migration of aspect-oriented programsScience of Computer Programming10.1016/j.scico.2012.09.00478:8(1157-1175)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.scico.2012.09.004
Ortin FGarcia M(2013)A Programming Language That Combines the Benefits of Static and Dynamic TypingSoftware and Data Technologies10.1007/978-3-642-29578-2_5(72-87)Online publication date: 2013
https://doi.org/10.1007/978-3-642-29578-2_5
Show More Cited By

Index Terms

Precise concrete type inference for object-oriented languages
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Object oriented languages
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
      1. Type structures

Recommendations

Precise concrete type inference for object-oriented languages
OOPSLA '94: Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications

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 ...
Type checking and type inference for object-oriented programming languages
Concrete type inference: delivering object-oriented applications

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 29, Issue 10

Oct. 1994

473 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/191081

Editor:
Richard L. Wexelblat

Issue’s Table of Contents

OOPSLA '94: Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications
October 1994
476 pages
ISBN:0897916883
DOI:10.1145/191080
Chairmen:
Jeff McKenna
McKenna consulting group
,
J. Eliot B. Moss
Univ. of Massachusetts, Amherst
,
Editor:
Richard L. Wexelblat

Copyright © 1994 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1994

Published in SIGPLAN Volume 29, Issue 10

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

190
Total Citations
View Citations
985
Total Downloads

Downloads (Last 12 months)103
Downloads (Last 6 weeks)9

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Blizničenko JPergl R(2025)Combining type inference techniques for semi-automatic UML generation from Pharo codeJournal of Computer Languages10.1016/j.cola.2024.10130082(101300)Online publication date: Mar-2025
https://doi.org/10.1016/j.cola.2024.101300
Rubbo FPiveta ENunes D(2013)Inference rules for generic code migration of aspect-oriented programsScience of Computer Programming10.1016/j.scico.2012.09.00478:8(1157-1175)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.scico.2012.09.004
Ortin FGarcia M(2013)A Programming Language That Combines the Benefits of Static and Dynamic TypingSoftware and Data Technologies10.1007/978-3-642-29578-2_5(72-87)Online publication date: 2013
https://doi.org/10.1007/978-3-642-29578-2_5
Ancona DLagorio G(2011)Idealized coinductive type systems for imperative object-oriented programsRAIRO - Theoretical Informatics and Applications10.1051/ita/201100945:1(3-33)Online publication date: 15-Mar-2011
https://doi.org/10.1051/ita/2011009
Ortin FZapico DPerez-Schofield JGarcia M(2010)Including both static and dynamic typing in the same programming languageIET Software10.1049/iet-sen.2009.00704:4(268)Online publication date: 2010
https://doi.org/10.1049/iet-sen.2009.0070
Fink SYahav EDor NRamalingam GGeay E(2008)Effective typestate verification in the presence of aliasingACM Transactions on Software Engineering and Methodology10.1145/1348250.134825517:2(1-34)Online publication date: 5-May-2008
https://dl.acm.org/doi/10.1145/1348250.1348255
Kumar RChakraborty S(2007)Precise static type analysis for object oriented programsACM SIGPLAN Notices10.1145/1241761.124176342:2(17-26)Online publication date: 1-Feb-2007
https://dl.acm.org/doi/10.1145/1241761.1241763
Hirzel MDincklage DDiwan AHind M(2007)Fast online pointer analysisACM Transactions on Programming Languages and Systems10.1145/1216374.121637929:2(11-es)Online publication date: 1-Apr-2007
https://dl.acm.org/doi/10.1145/1216374.1216379
Fink SYahav EDor NRamalingam GGeay EPollock LPezzè M(2006)Effective typestate verification in the presence of aliasingProceedings of the 2006 international symposium on Software testing and analysis10.1145/1146238.1146254(133-144)Online publication date: 21-Jul-2006
https://dl.acm.org/doi/10.1145/1146238.1146254
Aigner GHölzle U(2006)Eliminating virtual function calls in C++ programsECOOP ’96 — Object-Oriented Programming10.1007/BFb0053060(142-166)Online publication date: 21-May-2006
https://doi.org/10.1007/BFb0053060
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents