article

Precise static type analysis for object oriented programs

Authors:

Soham S. ChakrabortyAuthors Info & Claims

ACM SIGPLAN Notices, Volume 42, Issue 2

Pages 17 - 26

https://doi.org/10.1145/1241761.1241763

Published: 01 February 2007 Publication History

Abstract

A precise static type analysis is important to make available dynamic aspects of object-oriented programs (OOPs) approximately known at compile-time. Many techniques have been proposed for static type analysis depending upon the tradeoff of cost and precision; the techniques may generate spurious possible types for a particular dynamic dispatch which makes the static type analysis imprecise. In this paper, we propose a symbolic execution based type analysis technique that analyzes the dynamic type inter-procedurally by keeping the flow of the program in consideration. We analyze test cases with different class hierarchies. The proposed technique was capable to resolve the target method for most of the dynamic dispatches at reduced computational cost.

References

[1]

{ACG01} B. Alpern, A. Cocchi, and D. Grove. Dynamic type checking in Jalapeño. In Proc. The Usenix Java Virtual Machine Research and Technology Symposium, pp. 41--52, April 2001.

Digital Library

[2]

{Age95} O. Agesen. The Cartesian product algorithm: simple and precise type inference of parametric polymorphism. In Proc. ECOOP. LNCS: 2--26, 1995. Springer.

Digital Library

[3]

{AM95} M. Alt and F. Martin. Generation of efficient interprocedural analyzers with PAG. In Proc. Int. Symp. Static Analysis. LNCS 983: 33--50, Sep. 1995. Springer.

Digital Library

[4]

{Antlr06} T. Parr. ANTLR: ANother Tool for Language Recognition, Ver 3.0. {http://www.antlr.org/}

[5]

{ASU86} A. V Aho, R. Sethi and J. D. Ullman. Compilers: Principles, Techniques and Tools. Addison-Wesley, 1986.

Digital Library

[6]

{Bac97} D.F. Bacon. Fast and effective optimization of object oriented languages. PhD Thesis, Report No. UCB/CSD-98-1017, University of California, Berkeley, Dec. 1997.

Digital Library

[7]

{Ban00} J. C. Corbett, M. B. Dwyer, J. Hatcliff, S. Laubach, C. S. Pasareanu, Robby, and H. Zheng. Bandera: Extracting finite-state models from Java source code. In Proc. ICSE, pp. 439--448. 2000.

Digital Library

[8]

{BS96} D. F. Bacon and P. F. Sweeney. Fast static analysis of C++ virtual function calls. In Proc. OOPSLA. ACM SIGPLAN Notices 31: 324--341, 1996.

Digital Library

[9]

{Car97} L. Cardelli. Type Systems. In A. B. Tucker Jr. (Eds.), The Computer Science and Engineering Handbook, pp. 2208--2236, 1997. CRC Press.

[10]

{CCHK90} D. Callahan, A. Carle, M. W. Hall, and K. Kennedy. Constructing the procedure call multigraph. IEEE Transactions on Software Engineering 16(4):483--487, 1990.

Digital Library

[11]

{DC95} J. Dean and C. Chambers. Optimization of object oriented programs using static class hierarchy analysis. In Proc. ECOOP. LNCS 952: 77--101, 1995. Springer.

Digital Library

[12]

{EGH94} M. Emami, R. Ghiya, and L. J. Hendren. Context-sensitive interprocedural points to analysis in the presence of function pointers. In Proc. PLDI. ACM SIGPLAN Notices 29 (6): 242--256, June 1994.

Digital Library

[13]

{GC01} D. Grove and C Chambers. A framework for call graph construction algorithms. ACM Transactions on Programming Languages and Systems 23 (6):685--746, Nov. 2001.

Digital Library

[14]

{Gro98} D. Grove. Effective interprocedural optimization of object-oriented languages. PhD Thesis, University of Washington, 1998.

Digital Library

[15]

{Muc97} S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997.

Digital Library

[16]

{PC94} J. Plevyak and A. A. Chien. Precise concrete type inference for object-oriented languages. In Proc. OOPSLA. SIGPLAN Notices 29: 324--340, 1994.

Digital Library

[17]

{Ple96} J. Plevyak. Optimization of object-oriented and concurrent programs. PhD Thesis, University of Illinois at Urbana-Champaign, 1996.

Digital Library

[18]

{QH04} F. Qian and L. Hendren. Towards dynamic interprocedural analysis in JVMs. In Proc. Usenix 3rd Virtual Machine Research and Technology Symposium (VM-04), May 2004.

Digital Library

[19]

{Ran00} V. P. Ranganath. Object flow analysis for optimizing finite state models of Java. MS thesis, Kansas State University, 2000.

[20]

{Ryd79} B. Ryder. Constructing the call graph of a program. IEEE Transactions on Software Engineering 5(3): 216--225, 1979.

Digital Library

[21]

{SabCC98} É. Gagnon. SABLECC, An object-oriented compiler framework. MS Thesis. McGill University. March 1998.

Digital Library

[22]

{Shi88} O. Shivers. Control flow analysis in scheme. In Proc. PLDI. ACM SIGPLAN Notices 23 (7): 164--174, June 1988.

Digital Library

[23]

{Shi91} O. Shivers. Control-flow analysis of higher-order languages. Ph.D. thesis, Tech. Rep. CMUCS-91-145, Carnegie Mellon Univ., Pittsburgh, PA, 1991.

Digital Library

[24]

{SHR+00} V. Sundaresan, L. Hendren, C. Razafimahefa, R. Vallee-Rai, P. Lam, E Gagnon, and C. Godin. Practical virtual method calls resolution for Java. In Proc. OOPSLA. ACM SIGPLAN Notices 35: 264--280, 2000.

Digital Library

[25]

{Sri92} A. Srivastava. Unreachable procedures in object oriented programming. ACM Letters on Programming Languages and Systems 1: 355--364, Dec. 1992.

Digital Library

[26]

{TP00} F. Tip and J. Palsberg. Scalable propagation based call graph construction algorithms. In Proc. OOPSLA. ACM SIGPLAN Notices 35: 281--293. 2000.

Digital Library

Cited By

Kumar SKumar R(2012)Precise static analysis for generic programs in object oriented languagesACM SIGSOFT Software Engineering Notes10.1145/2180921.218093737:3(1-6)Online publication date: 16-May-2012
https://dl.acm.org/doi/10.1145/2180921.2180937
Ferrara P(2010)Static type analysis of pattern matching by abstract interpretationProceedings of the 12th IFIP WG 6.1 international conference and 30th IFIP WG 6.1 international conference on Formal Techniques for Distributed Systems10.1007/978-3-642-13464-7_15(186-200)Online publication date: 7-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-13464-7_15
Chakraborty SKumar RShroff GJalote PRajamani S(2008)Precise static type analysis in component based programming environmentProceedings of the 1st India software engineering conference10.1145/1342211.1342239(133-134)Online publication date: 19-Feb-2008
https://dl.acm.org/doi/10.1145/1342211.1342239

Index Terms

Precise static type analysis for object oriented programs
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Classes and objects
2. Theory of computation
  1. Semantics and reasoning

Recommendations

Static Type Analysis for Python
WISA '14: Proceedings of the 2014 11th Web Information System and Application Conference

Python is a kind of dynamic-typed language which provides flexibility but leaves the programmer without the benefits of static typing. This paper describes Type, a tool that works for static type annotation and inference for python. It could simulate ...
Improving precision of type analysis using non-discriminative union

This paper presents a new type analysis for logic programs. The analysis is performed with a priori type definitions; and type expressions are formed from a fixed alphabet of type constructors. Non-discriminative union is used to join type information ...
Type checking and type inference for object-oriented programming languages

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 42, Issue 2

February 2007

33 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1241761

Issue’s Table of Contents

Copyright © 2007 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 2007

Published in SIGPLAN Volume 42, Issue 2

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
442
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kumar SKumar R(2012)Precise static analysis for generic programs in object oriented languagesACM SIGSOFT Software Engineering Notes10.1145/2180921.218093737:3(1-6)Online publication date: 16-May-2012
https://dl.acm.org/doi/10.1145/2180921.2180937
Ferrara P(2010)Static type analysis of pattern matching by abstract interpretationProceedings of the 12th IFIP WG 6.1 international conference and 30th IFIP WG 6.1 international conference on Formal Techniques for Distributed Systems10.1007/978-3-642-13464-7_15(186-200)Online publication date: 7-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-13464-7_15
Chakraborty SKumar RShroff GJalote PRajamani S(2008)Precise static type analysis in component based programming environmentProceedings of the 1st India software engineering conference10.1145/1342211.1342239(133-134)Online publication date: 19-Feb-2008
https://dl.acm.org/doi/10.1145/1342211.1342239

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents