skip to main content
research-article

Precise static analysis for generic programs in object oriented languages

Published: 16 May 2012 Publication History

Abstract

Genericity enriched with multiple data types and classes is becoming a common feature of object oriented languages. Therefore, static analysis of such generic programs is gaining importance. Unfortunately such work does not exist. In this work, we statically analyse such generic programs for approximating the possible dynamic (run-time) types of objects. We propose a single pass technique for analyzing the generic programs inter-procedurally statement-wise following the control flow of the execution. The technique is able to resolve the covariance, contravariance and invariance relationship existing amongst different instances with type parameters as arguments to a class. We assess the performance of the proposed technique by carrying out experiments on a set of standard benchmark programs

References

[1]
O. Agesen. Constraint-based type inference and parametric polymorphism, 1994.
[2]
E. Allen, R. Cartwright, and B. Stoler. Efficient implementation of run-time generic types for java. In IFIP WG2.1 Working Conference On Generic Programming, pages 207--236. Kluwer, B.V, 2002.
[3]
J. Altidor, S.S. Huang, and Y. Smaragdakis. Taming the wildcards: combining definition- and use-site variance. SIGPLAN Not., 46:602--613, June 2011.
[4]
D.F. Bacon. Fast and effective optimization of statically typed object-oriented languages. Technical report, University of California, Berkeley, 1997.
[5]
G. Bracha, M. Odersky, D. Stoutamire, and P. Wadler. Making the future safe for the past: adding genericity to the Java programming language. SIGPLAN Not., 33:183--200, October 1998.
[6]
J. Gosling, B. Joy, G. Steele, and G. Bracha. The Java Language Specification Third Edition. Addison-Wesley, 2005.
[7]
D. Grove and C. Chambers. A framework for call graph construction algorithms. ACM Trans. Program. Lang. Syst., 23:685--746, November 2001.
[8]
L. Hubert, N. Barré, F. Besson, D. Demange, T. Jensen, V. Monfort, D. Pichardie, and T. Turpin. Sawja: static analysis workshop for java. In Proceedings of the 2010 international conference on Formal verification of object-oriented software, FoVeOOS'10, pages 92--106, Berlin, Heidelberg, 2011. Springer-Verlag.
[9]
A. Igarashi and M. Viroli. On variance-based subtyping for parametric types. In Proceedings of the 16th European Conference on Object-Oriented Programming, ECOOP '02, pages 441--469, London, UK, 2002. Springer-Verlag.
[10]
A. Igarashi and M. Viroli. Variant parametric types: A flexible subtyping scheme for generics. ACM Trans. Program. Lang. Syst., 28:795--847, September 2006.
[11]
International standard ISO/IEC 14882. programming languages C++, 2003.
[12]
D. Grove J. Dean and C. Chambers. Optimization of object-oriented programs using static class hierarchy analysis. In Proceedings of the 9th European Conference on Object-Oriented Programming, pages 77--101. Springer-Verlag, 1995.
[13]
R. Kumar and S.S. Chakraborty. Precise static type analysis for object oriented programs. SIGPLAN Not., 42:17--26, February 2007.
[14]
M. Méndez, J. Navas, and M.V. Hermenegildo. An efficient, parametric fixpoint algorithm for analysis of java bytecode. Electron. Notes Theor. Comput. Sci., 190:51--66, July 2007.
[15]
M. Méndez, J. Navas, and M.V. Hermenegildo. An efficient, parametric fixpoint algorithm for analysis of java bytecode. Electron. Notes Theor. Comput. Sci., 190:51--66, July 2007.
[16]
M.V. Hermenegildo N. Jorge, M. MÃl'ndez-lojo. A generic, context sensitive analysis framework for object oriented programs, 2007.
[17]
Jaime Niño. The cost of erasure in Java generics type system. J. Comput. Small Coll., 22:2--11, May 2007.
[18]
F. Nielson and H.R. Nielson. Interprocedural control flow analysis. In In Proc. European Symp. on Programming, vol. 1576 of LNCS, pages 20--39. Springer-Verlag, 1999.
[19]
Fausto Spoto. Julia: A generic static analyser for the java bytecode. In Part XXX, pages 363--369, 1982.
[20]
B. Stroustrup. The C++ Programming Language. Special 3rd Edition. Addison-Wesley Professional, 2000.
[21]
V. Sundaresan, L. Hendren, C. Razafimahefa, R. Vallee-Rai, P. Lam, E. Gagnon, and C. Godin. Practical virtual method call resolution for Java. In In Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 264--280. ACM Press, 2000.
[22]
Russell W. Quong Terence J. Parr. ANTLR: ANother tool for language recognition. ver 3.0. http://www.antlr.org, 1994

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGSOFT Software Engineering Notes
ACM SIGSOFT Software Engineering Notes  Volume 37, Issue 3
May 2012
129 pages
ISSN:0163-5948
DOI:10.1145/2180921
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 May 2012
Published in SIGSOFT Volume 37, Issue 3

Check for updates

Author Tags

  1. context sensitive
  2. generic program
  3. method call graph
  4. parametric polymorphism
  5. runtime type
  6. static analysis
  7. type safety

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 130
    Total Downloads
  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media