Region inference for an object-oriented language

ABSTRACT

Region-based memory management offers several important potential advantages over garbage collection, including real-time performance, better data locality, and more efficient use of limited memory. Researchers have advocated the use of regions for functional, imperative, and object-oriented languages. Lexically scoped regions are now a core feature of the Real-Time Specification for Java (RTSJ)[5].Recent research in region-based programming for Java has focused on region checking, which requires manual effort to augment the program with region annotations. In this paper, we propose an automatic region inference system for a core subset of Java. To provide an inference method that is both precise and practical, we support classes and methods that are region-polymorphic, with region-polymorphic recursion for methods. One challenging aspect is to ensure region safety in the presence of features such as class subtyping, method overriding, and downcast operations. Our region inference rules can handle these object-oriented features safely without creating dangling references.

References

1. A. Aiken, M. Fahndrich, and R. Levien. Better static memory management: Improving region-based analysis of higher-order languages. In ACM PLDI, pages 174--185, 1995.]]
2. J. Aldrich, V. Kostadinov, and C. Chambers. Alias Annotation for Program Understanding. In ACM OOPSLA, Seattle, Washington, November 2002.]]
3. W. Beebee and M. Rinard. An Implementation of Scoped Memory for Real-Time Java. In Proceedings of Embedded Software, First International Workshop (EMSOFT '01), Tahoe City, California, October 2001.]]
4. L. Birkedal, M. Tofte, and M. Vejlstrup. From region inference to von Neumann machines via region representation inference. In ACM POPL, pages 171--183. ACM Press, January 1996.]]
5. G. Bollella, B. Brosgol, P. Dibble, S. Furr, J. Gosling, D. Hardin, and M. Turnbull. The Real-Time Specification for Java. Addison-Wesley, 2000.]]
6. C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: Preventing data races and deadlocks. In ACM OOPSLA, Seattle, Washington, November 2002.]]
7. C. Boyapati, R. Lee, and M. Rinard. Safe runtime downcasts with ownership types. In Proceedings of the 2003 ECOOP Workshop on Aliasing, Confinement and Ownership in Object-Oriented Programming, Darmstadt, Germany, July 2003.]]
8. C. Boyapati, B. Liskov, and L. Shrira. Ownership Types for Object Encapsulation. In ACM POPL, New Orleans, Louisiana, January 2003.]]
9. C. Boyapati, A. Salcianu, W. Beebee, and M. Rinard. Ownership Types for Safe Region-Based Memory Management in Real-Time Java. In ACM PLDI, San Diego, California, June 2003.]]
10. G. Bracha, M. Odersky, D. Stoutamire, and P. Wadler. Making the future safe for the past: Adding Genericity to the Java Programming Language. In ACM OOPSLA, October 1998.]]
11. M. C. Carlisle and A. Rogers. Software caching and computation migration in Olden. In ACM PPoPP, pages 29--38, Santa Barbara, California (ACM Press), May 1993.]]
12. G. Castagna. Covariance and contravariance: Conflict without a cause. ACM Trans. on Programming Lang. and Systems, 17(3):431--447, May 1995.]]
13. S. Cherem and R. Rugina. Region Analysis and Transformation for Java Programs. Technical Report, Computer Science Dept, Cornell University, April 2004.]]
14. W.N. Chin, F. Craciun, S.C. Qin, and M. Rinard. Region Inference for an Object-Oriented Language. Technical report, School of Computing, National Univ. of Singapore, November 2003. avail. at http://www.comp.nus.edu.sg/.qinsc/papers/reginf.ps.gz.]]
15. M. V. Christiansen, F. Henglein, H. Niss, and P. Velschow. Safe Region-Based Memory Management for Objects. Technical Report D-397, DIKU, University of Copenhagen, October 1998.]]
16. M. V. Christiansen and P. Velschow. Region-Based Memory Management in Java. Master's Thesis, Department of Computer Science (DIKU), University of Copenhagen, 1998.]]
17. D. G. Clarke and S. Drossopoulou. Ownership, Encapsulation and Disjointness of Type and Effect. In ACM OOPSLA, Seattle, Washington, November 2002.]]
18. D. G. Clarke, J. M. Potter, and J. Noble. Ownership Types for Flexible Alias Protection. In ACM OOPSLA, October 1998.]]
19. K. Crary, D. Walker, and G. Morrisett. Typed Memory Management in a Calculus of Capabilities. In ACM POPL, January 1999.]]
20. R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. on Programming Lang. and Systems, 13(4):451--490, 1991.]]
21. M. Deters and R. Cytron. Automated Discovery of Scoped Memory Regions for Real-Time Java. In Proceedings of the International Symposium on Memory Management (ISMM'02), June 2002.]]
22. A. Deutsch. On the complexity of escape analysis. In ACM POPL, pages 358--371. ACM Press, 1997.]]
23. M. Fahndrich and R. Leino. Declaring and checking non-null types in an object-oriented language. In ACM OOPSLA, Anaheim, CA, October 2003.]]
24. D. Gay and A. Aiken. Memory Management with Explicit Regions. In ACM PLDI, June 1998.]]
25. D. Gay and A. Aiken. Language support for regions. In ACM PLDI, pages 70--80, 2001.]]
26. D. Grossman, G. Morrisett, T. Jim, M. Hicks, Y. Wang, and J. Cheney. Region-Based Memory Management in Cyclone. In ACM PLDI, June 2002.]]
27. J Gustavsson and J Svenningsson. Constraint abstractions. In Programs as Data Objects II, pages 63-83, Aarhus, Denmark, May 2001.]]
28. F. Henglein, H. Makholm, and H. Niss. A direct approach to control-flow sensitive region-based memory management. In Proceedings of the 3rd ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP), pages 175--186, Montréal, Canada, 2001. ACM.]]
29. P. N. Hilfinger, D. Bonachea, D. Gay, S. Graham, B. Liblit, G. Pike, and K. Yelick. Titanium Language Reference Manual v1.11. Computer Science Division (EECS), University of California Berkeley, California, Mar 2004.]]
30. A. Igarashi, B. Pierce, and P. Wadler. Featherweight Java: A Minimal Core Calculus for Java and GJ. In ACM OOPSLA, Denver, Colorado, November 1999.]]
31. S Peyton-Jones and et al. Glasgow Haskell Compiler. http://www.haskell.org/ghc.]]
32. M. Tofte and J. Talpin. Implementing the Call-By-Value λ-calculus Using a Stack of Regions. In ACM POPL, January 1994.]]
33. M. Tofte and J. Talpin. Region-based memory management. Information and Computation, 132(2), 1997.]]
34. D. Walker and K. Watkins. On regions and linear types (extended abstract). In ACM ICFP, pages 181--192. ACM Press, 2001.]]

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Metrics

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language features

• Theory of computation

  • Semantics and reasoning

    • Program semantics