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

Article

Precise Constraint-Based Type Inference for Java

Authors:

Scott F. SmithAuthors Info & Claims

ECOOP '01: Proceedings of the 15th European Conference on Object-Oriented Programming

Pages 99 - 117

Published: 18 June 2001 Publication History

Abstract

Precise type information is invaluable for analysis and optimization of object-oriented programs. Some forms of polymorphism found in object-oriented languages pose significant difficulty for type inference, in particular data polymorphism. Agesen's Cartesian Product Algorithm (CPA) can analyze programs with parametric polymorphism in a reasonably precise and efficient manner, but CPAl oses precision for programs with data polymorphism. This paper presents a precise constraintbased type inference system for Java. It uses Data-Polymorphic CPA (DCPA), a novel constraint-based type inference algorithm which extends CPAwit h the ability to accurately and efficiently analyze data polymorphic programs. The system is implemented for the full Java language, and is used to statically verify the correctness of Java downcasts. Benchmark results are given which show that DCPAi s significantly more accurate than CPAan d the efficiency of DCPAis close to CPA.

References

[1]

Alexander Aiken, Manuel Fhndrich, Jeffrey S. Foster, and Zhendong Su. Partial online cycle elimination in inclusion constraint graphs. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) , 1998.

[2]

Ole Agesen. The cartesian product algorithm. In Proceedings ECOOP'95 , volume 952 of Lecture notes in Computer Science , 1995.

[3]

Ole Agesen. Concrete Type Inference: Delivering Object-Oriented Applications . PhD thesis, Stanford University, 1996. Available as Sun Labs Technical Report SMLI TR-96-52.

[4]

A. Aiken and E. L. Wimmers. Type inclusion constraints and type inference. In Proceedings of the International Conference on Functional Programming Languages and Computer Architecture , pages 31-41, 1993.

[5]

Robert O' Callahan. Optimizing a solver of polymorphism constraints: SEMI. Technical Report CMU-CS-99-136, CMU, June 1999.

[6]

Dominic Duggan. Modular type-based reverse engineering of parameterized types in java code. In ACM SIGPLAN Symposium on Object-Oriented Programming: Systems, Languages and Applications (OOPSLA) , 1999.

[7]

Jonathan Eifrig, Scott Smith, and Valery Trifonov. Sound polymorphic type inference for objects. In OOPSLA '95 , pages 169-184, 1995.

[8]

Cormac Flanagan and Matthias Felleisen. Componential set-based analysis. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI-97) , volume 32, 5 of ACM SIGPLAN Notices , pages 235-248, New York, June 15-18 1997. ACM Press.

[9]

David Grove, Greg DeFouw, Jeffrey Dean, and Craig Chambers. Call graph construction in object-oriented languages. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA) , 1997.

[10]

Suresh Jagannathan and Stephen Weeks. Auni fied treatment of flow analysis in higher-order languages. In Conference Record of the Twenty-Second Annual ACM Symposium on Principles of Programming Languages , pages 393-408, 1995.

[11]

John Plevyak and Andrew Chien. Precise concrete type inference for object-oriented languages. In Proceedings of the Ninth Annual ACM Conference on Object-Oriented Programming Systems, Languages, and Applications , pages 324-340, 1994.

[12]

François Pottier. Aframew ork for type inference with subtyping. In Proceedings of the third ACM SIGPLAN International Conference on Functional Programming (ICFP'98) , September 1998.

[13]

Jens Palsberg and Christina Pavlopoulou. From polyvariant flow information to intersection and union types. In POPL , 1998.

[14]

Olin Shivers. Control-Flow Analysis of Higher-Order Languages . PhD thesis, Carnegie-Mellon University, 1991. Available as CMU Technical Report CMU-CS-91-145.

[15]

V. Sundaresan, L. Hendren, C. Razafimahefa, R. Valee-Rai, P. Lam, E. Gagnon, and C. Godin. Practical virtual method call resolution for java. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA) , 2000.

[16]

Scott Smith and Tiejun Wang. Polyvariant flow analysis with constrained types. In Gert Smolka, editor, Proceedings of the 2000 European Symposium on Programming (ESOP'00) , volume 1782 of Lecture Notes in Computer Science , pages 382-396. Springer Verlag, March 2000.

[17]

F. Tip, C. Laffra, P. Sweeney, and D. Streeter. Practical experience with an application extractor for java. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA) , 1999.

[18]

F. Tip and J. Palsberg. Scalable propagation-based call graph construction. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA) , 2000.

Cited By

Milojković NGhafari MNierstrasz OScanniello GLo DSerebrenik A(2017)Exploiting type hints in method argument names to improve lightweight type inferenceProceedings of the 25th International Conference on Program Comprehension10.1109/ICPC.2017.33(77-87)Online publication date: 20-May-2017
https://dl.acm.org/doi/10.1109/ICPC.2017.33
Ancona DCorradi A(2016)Semantic subtyping for imperative object-oriented languagesACM SIGPLAN Notices10.1145/3022671.298399251:10(568-587)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/3022671.2983992
Milojković NNierstrasz OVisser EMurphy-Hill ELopes C(2016)Exploring cheap type inference heuristics in dynamically typed languagesProceedings of the 2016 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/2986012.2986017(43-56)Online publication date: 20-Oct-2016
https://dl.acm.org/doi/10.1145/2986012.2986017
Show More Cited By

Precise Constraint-Based Type Inference for Java
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
2. Theory of computation
  1. Semantics and reasoning

Recommendations

Constraint-based type inference for polymorphic programs
Type qualifier inference for java
Proceedings of the 2007 OOPSLA conference

Java's type system provides programmers with strong guarantees of type and memory safety, but there are many important properties not captured by standard Java types. We describe JQual, a tool that adds user-defined type qualifiers to Java, allowing ...
Type qualifier inference for java
OOPSLA '07: Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems, languages and applications

Java's type system provides programmers with strong guarantees of type and memory safety, but there are many important properties not captured by standard Java types. We describe JQual, a tool that adds user-defined type qualifiers to Java, allowing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ECOOP '01: Proceedings of the 15th European Conference on Object-Oriented Programming

June 2001

428 pages

ISBN:3540422064

Editor:
Jørgen Lindskov Knudsen

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 18 June 2001

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Milojković NGhafari MNierstrasz OScanniello GLo DSerebrenik A(2017)Exploiting type hints in method argument names to improve lightweight type inferenceProceedings of the 25th International Conference on Program Comprehension10.1109/ICPC.2017.33(77-87)Online publication date: 20-May-2017
https://dl.acm.org/doi/10.1109/ICPC.2017.33
Ancona DCorradi A(2016)Semantic subtyping for imperative object-oriented languagesACM SIGPLAN Notices10.1145/3022671.298399251:10(568-587)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/3022671.2983992
Milojković NNierstrasz OVisser EMurphy-Hill ELopes C(2016)Exploring cheap type inference heuristics in dynamically typed languagesProceedings of the 2016 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/2986012.2986017(43-56)Online publication date: 20-Oct-2016
https://dl.acm.org/doi/10.1145/2986012.2986017
Ancona DCorradi AVisser ESmaragdakis Y(2016)Semantic subtyping for imperative object-oriented languagesProceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2983990.2983992(568-587)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/2983990.2983992
Pearce DDietl W(2013)A calculus for constraint-based flow typingProceedings of the 15th Workshop on Formal Techniques for Java-like Programs10.1145/2489804.2489810(1-7)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1145/2489804.2489810
Zhao T(2011)Polymorphic type inference for scripting languages with object extensionsACM SIGPLAN Notices10.1145/2168696.204785547:2(37-50)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.1145/2168696.2047855
Zhao TD'Hondt T(2011)Polymorphic type inference for scripting languages with object extensionsProceedings of the 7th symposium on Dynamic languages10.1145/2047849.2047855(37-50)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.1145/2047849.2047855
Ducournau R(2011)Implementing statically typed object-oriented programming languagesACM Computing Surveys10.1145/1922649.192265543:3(1-48)Online publication date: 29-Apr-2011
https://dl.acm.org/doi/10.1145/1922649.1922655
Kulkarni ALiu YSmith S(2010)Task types for pervasive atomicityACM SIGPLAN Notices10.1145/1932682.186951445:10(671-690)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1932682.1869514
Ancona DLagorio G(2010)Complete coinductive subtyping for abstract compilation of object-oriented languagesProceedings of the 12th Workshop on Formal Techniques for Java-Like Programs10.1145/1924520.1924521(1-7)Online publication date: 22-Jun-2010
https://dl.acm.org/doi/10.1145/1924520.1924521
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents