On the connection between functional programming languages and real-time Java scoped memory

ABSTRACT

Java has recently joined C and C++ as a relatively high-level language suitable for developing real-time applications. Java's garbage collection, while generally a useful feature, can be problematic for real-time applications if collection occurs with unpredictable frequency and latency.

The Real-Time Specification for Java™ (RTSJ) incorporates a scoped-memory model, akin to regions, that is not subject to garbage collection. However, applications are subject to strict rules concerning how objects can reference each other in scoped memory. Unfortunately, almost all extant Java code, including Java's vast and useful runtime libraries, will not execute properly in scoped-memory areas without significant modification.

In this paper, we show that programs written in a pure functional programming language can be executed in a provably safe manner using scoped memory in RTSJ. This new connection allows extant implementations of important abstract data types to migrate safely to RTSJ. We also explore the effect of RTSJ's referencing rules on the asymptotic, real-time behavior of some abstract data types.

REFERENCES

• 1: Ken Arnold , James Gosling , David Holmes, The Java Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 2: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 3: David F. Bacon , Perry Cheng , V. T. Rajan, Controlling fragmentation and space consumption in the metronome, a real-time garbage collector for Java, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 4: David F. Bacon, Perry Cheng, and V. T. Rajan. The Metronome: A simpler approach to garbage collection in real-time systems. In R. Meersman and Z. Tari, editors, Proceedings of the OTM Workshops: Workshop on Java Technologies for Real-Time and Embedded Systems, volume 2889 of Lecture Notes in Computer Science, pages 466--478, Catania, Sicily, November 2003. SpringerVerlag.
• 5: James Gosling , Greg Bollella, The Real-Time Specification for Java, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 6: Chandrasekhar Boyapati , Alexandru Salcianu , William Beebee, Jr. , Martin Rinard, Ownership types for safe region-based memory management in real-time Java, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 7: Dante J. Cannarozzi , Michael P. Plezbert , Ron K. Cytron, Contaminated garbage collection, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.264-273, June 18-21, 2000, Vancouver, British Columbia, Canada
• 8: Sigmund Cherem , Radu Rugina, Region analysis and transformation for Java programs, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029884]
• 9: Delvin Defoe, Rob LeGrand, and Ron K. Cytron. Cost analysis for real-time java scoped-memory areas. Journal of Systemics, Cybernetics and Informatics, 5, 2007, forthcoming.
• 10: Morgan Deters , Ron K. Cytron, Automated discovery of scoped memory regions for real-time Java, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 11: Max Goff. Celebrating 10 years of Java and our technological productivity: A look back on the last 10 years of the network age. http://www.javaworld.com, May 2005.
• 12: Tobias Mann , Morgan Deters , Rob LeGrand , Ron K. Cytron, Static determination of allocation rates to support real-time garbage collection, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 13: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 14: Kelvin Nilsen, A type system to assure scope safety within safety-critical Java modules, Proceedings of the 4th international workshop on Java technologies for real-time and embedded systems, October 11-13, 2006, Paris, France [doi>10.1145/1167999.1168017]
• 15: Chris Okasaki, Functional Data Structures, Advanced Functional Programming, Second International School-Tutorial Text, p.131-158, August 26-30, 1996
• 16: Chris Okasaki , Peter Lee, Purely functional data structures, Carnegie Mellon University, Pittsburgh, PA, 1996
• 17: F. Pizlo, J. M. Fox, D. Holmes, and J. Vitek. Real-time java scoped memory: Design patterns and semantics. In IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, pages 101--110, Vienna, Austria, May 2004. IEEE Computer Society.
• 18: Mads Tofte , Lars Birkedal, A region inference algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.4, p.724-767, July 1998 [doi>10.1145/291891.291894]
• 19: Mark Allen Weiss, Data structures and algorithm analysis in C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

General Terms:
Algorithms, Management

Keywords:
data structures, functional programming, memory, memory management, performance analysis, programming languages, real-time, real-time Java, scoped memory