Abstract
Purity Analysis is the problem of determining whether or not a method may have side-effects. This has applications in automatic parallelisation, extended static checking, and more. We present a novel purity system for Java that employs purity annotations which can be checked modularly. This is done using a flow-sensitive, intraprocedural analysis. The system exploits two properties, called freshness and locality, to increase the range of methods that can be considered pure. JPure also includes an inference engine for annotating legacy code. We evaluate our system against several packages from the Java Standard Library. Our results indicate it is possible to uncover significant amounts of purity efficiently.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barnett, M., Naumann, D.A., Schulte, W., Sun, Q.: 99.44% pure: Useful abstractions in specification. In: Proc. FTFJP, pp. 11–19 (2004)
Benton, W.C., Fischer, C.N.: Mostly-functional behavior in Java programs. In: Jones, N.D., Müller-Olm, M. (eds.) VMCAI 2009. LNCS, vol. 5403, pp. 29–43. Springer, Heidelberg (2009)
Bierhoff, K., Aldrich, J.: Lightweight object specification with typestates. In: ESEC/SIGSOFT FSE, pp. 217–226. ACM Press, New York (2005)
Boyapati, C., Liskov, B., Shrira, L.: Ownership types for object encapsulation. In: Proc. POPL, pp. 213–223. ACM Press, New York (2003)
Cataño, N., Huisman, M.: CHASE: A static checker for JML’s Assignable clause. In: Zuck, L.D., Attie, P.C., Cortesi, A., Mukhopadhyay, S. (eds.) VMCAI 2003. LNCS, vol. 2575, pp. 26–40. Springer, Heidelberg (2002)
Cherem, S., Rugina, R.: A practical escape and effect analysis for building lightweight method summaries. In: Adsul, B., Vetta, A. (eds.) CC 2007. LNCS, vol. 4420, pp. 172–186. Springer, Heidelberg (2007)
Choi, J.-D., Burke, M., Carini, P.: Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In: Proc. POPL, pp. 232–245. ACM Press, New York (1993)
Clarke, D., Potter, J., Noble, J.: Ownership Types for Flexible Alias Protection. In: Proc. OOPSLA, pp. 48–64. ACM Press, New York (1998)
Clausen, L.R.: A Java bytecode optimizer using side-effect analysis. Concurrency - Practice and Experience 9(11), 1031–1045 (1997)
Darvas, Á., Leino, K.R.M.: Practical reasoning about invocations and implementations of pure methods. In: Dwyer, M.B., Lopes, A. (eds.) FASE 2007. LNCS, vol. 4422, pp. 336–351. Springer, Heidelberg (2007)
Dean, J., Grove, D., Chambers, C.: Optimization of object-oriented programs using static class hierarchy analysis. In: Olthoff, W. (ed.) ECOOP 1995. LNCS, vol. 952, pp. 77–101. Springer, Heidelberg (1995)
Finifter, M., Mettler, A., Sastry, N., Wagner, D.: Verifiable functional purity in Java. In: Proc. CCS, pp. 161–174. ACM Press, New York (2008)
Flanagan, C., Freund, S.N., Qadeer, S.: Exploiting purity for atomicity. In: Proc. ISSTA, pp. 221–231. ACM Press, New York (2004)
Flanagan, C., Leino, K.R.M., Lillibridge, M., Nelson, G., Saxe, J.B., Stata, R.: Extended static checking for Java. In: Proc. PLDI, pp. 234–245. ACM Press, New York (2002)
Heydon, A., Levin, R., Yu, Y.: Caching function calls using precise dependencies. In: Proc. PLDI, pp. 311–320 (2000)
Bocchino Jr., R.L., Adve, V.S., Dig, D., Adve, S.V., Heumann, S., Komuravelli, R., Overbey, J., Simmons, P., Sung, H., Vakilian, M.: A type and effect system for deterministic parallel Java. In: Proc. OOPSLA, pp. 97–116. ACM Press, New York (2009)
Landi, W., Ryder, B.G., Zhang, S.: Interprocedural side effect analysis with pointer aliasing. In: PLDI, pp. 56–67 (1993)
Le, A., Lhoték, O., Hendren, L.: Using inter-procedural side-effect information in JIT optimizations. In: Bodik, R. (ed.) CC 2005. LNCS, vol. 3443, pp. 287–304. Springer, Heidelberg (2005)
Leavens, G.T.: Advances and issues in JML. In: Presentation at Java Verification Workshop (2002)
Leavens, G.T., Leino, K.R.M., Poll, E., Ruby, C., Jacobs, B.: JML: notations and tools supporting detailed design in Java. In: OOPSLA Companion, pp. 105–106 (2000)
Lencevicius, R., Holzle, U., Singh, A.K.: Query-based debugging of object-oriented programs. In: Proc. OOPSLA, pp. 304–317. ACM Press, New York (1997)
Milanova, A., Rountev, A., Ryder, B.G.: Parameterized object sensitivity for points-to and side-effect analyses for Java. SIGSOFT Softw. Eng. Notes 27(4), 1–11 (2002)
Nguyen, P.H., Xue, J.: Interprocedural side-effect analysis and optimisation in the presence of dynamic class loading. In: Proc. ACSC, pp. 9–18 (2005)
Nordio, M., Calcagno, C., Meyer, B., Müller, P., Tschannen, J.: Reasoning about function objects. In: Vitek, J. (ed.) TOOLS 2010. LNCS, vol. 6141, pp. 79–96. Springer, Heidelberg (2010)
Pearce, D.J., Kelly, P.H.J., Hankin, C.: Efficient field-sensitive pointer analysis for C. ACM TOPLAS 30 (2007)
Rountev, A.: Precise identification of side-effect-free methods in Java. In: Proc. ICSM, pp. 82–91. IEEE Computer Society, Los Alamitos (2004)
Rountev, A., Milanova, A., Ryder, B.G.: Points-to analysis for Java using annotated constraints. In: Proc. OOPSLA, pp. 43–55 (2001)
Rountev, A., Milanova, A., Ryder, B.G.: Fragment class analysis for testing of polymorphism in Java software. In: Proc. ICSE, pp. 210–220 (2003)
Rountev, A., Ryder, B.G.: Points-to and side-effect analyses for programs built with precompiled libraries. In: Wilhelm, R. (ed.) CC 2001. LNCS, vol. 2027, pp. 20–36. Springer, Heidelberg (2001)
Salcianu, A., Rinard, M.: Purity and side effect analysis for Java programs. In: Cousot, R. (ed.) VMCAI 2005. LNCS, vol. 3385, pp. 199–215. Springer, Heidelberg (2005)
Tkachuk, O., Dwyer, M.B.: Adapting side effects analysis for modular program model checking. SIGSOFT Softw. Eng. Notes 28(5), 188–197 (2003)
Vakilian, M., Dig, D., Bocchino, R.L., Overbey, J., Adve, V.S., Johnson, R.: Inferring method effect summaries for nested heap regions. In: Proc. ASE, pp. 421–432 (2009)
Whaley, J., Lam, M.S.: Cloning-based context-sensitive pointer alias analysis using Binary Decision Diagrams. In: Proc. PLDI, pp. 131–144. ACM Press, New York (2004)
Willis, D., Pearce, D.J., Noble, J.: Caching and incrementalisation in the java query language. In: Proc. OOPSLA, pp. 1–18. ACM Press, New York (2008)
Xu, H., Pickett, C.J.F., Verbrugge, C.: Dynamic purity analysis for Java programs. In: Proc. PASTE, pp. 75–82. ACM Press, New York (2007)
Zhao, J., Rogers, I., Kirkham, C., Watson, I.: Pure method analysis within jikes rvm. In: Proc. ICOOOLPS (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pearce, D.J. (2011). JPure: A Modular Purity System for Java. In: Knoop, J. (eds) Compiler Construction. CC 2011. Lecture Notes in Computer Science, vol 6601. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19861-8_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-19861-8_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19860-1
Online ISBN: 978-3-642-19861-8
eBook Packages: Computer ScienceComputer Science (R0)