Implicit invocation meets safe, implicit concurrency

Abstract

Writing correct and efficient concurrent programs still remains a challenge. Explicit concurrency is difficult, error prone, and creates code which is hard to maintain and debug. This type of concurrency also treats modular program design and concurrency as separate goals, where modularity often suffers. To solve these problems, we are designing a new language that we call Panini. In this paper, we focus on Panini's asynchronous, typed events which reconcile the modularity goal promoted by the implicit invocation design style with the concurrency goal of exposing potential concurrency between the execution of subjects and observers.

Since modularity is improved and concurrency is implicit in Panini, programs are easier to reason about and maintain. The language incorporates a static analysis to determine potential conflicts between handlers and a dynamic analysis which uses the conflict information to determine a safe order for handler invocation. This mechanism avoids races and deadlocks entirely, yielding programs with a guaranteed deterministic semantics. To evaluate our language design and implementation we show several examples of its usage as well as an empirical study of program performance. We found that not only is developing and understanding Panini programs significantly easier compared to standard concurrent object-oriented programs, butt also performance of Panini programs is comparable to their equivalent hand-tuned versions written using Java's fork-join framework.

References

1. }}P. America. Issues in the design of a parallel object-oriented language. Formal Aspects of Computing, 1(4):366--411, 1989.
2. }}D. Ansaloni, W. Binder, A. Villazon, and P. Moret. Parallel dynamic analysis on multicores with aspect-oriented programming. In AOSD, pages 1--12, 2010.
3. }}J. Armstrong, R. Williams, M. Virding, and C. Wikstroem. Concurrent Programming in ERLANG. Prentice-Hal, 1996.
4. }}N. Benton, L. Cardelli, and C. Fournet. Modern concurrency abstractions for C\#. ACM Trans. Program. Lang. Syst., 26(5):769--804, 2004.
5. }}E. D. Berger, T. Yang, T. Liu, and G. Novark. Grace: safe multithreaded programming for C/C
6. }}. In the conference on Object oriented programming systems languages and applications (OOPSLA), pages 81--96, 2009.
7. }}R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, and Y. Zhou. Cilk: an efficient multithreaded runtime system. In PPOPP, pages 207--216, 1995.
8. }}R. Cunningham and E. Kohler. Making events less slippery with eel. In Conference on Hot Topics in Operating Systems, Berkeley, CA, USA, 2005.
9. }}David C. Luckham ηl. Specification and Analysis of System Architecture Using Rapide. IEEE Transactions on Software Engineering, 21(4):336--54, 1995.
10. }}T. Ekman and G. Hedin. The JastAdd Extensible Java Compiler. In OOPSLA, pages 1--18, 2007.
11. }}P. Eugster. Type-Based Publish/Subscribe: Concepts and Experiences. ACM Trans. Program. Lang. Syst., 29(1):6, 2007.
12. }}P. Eugster and K. R. Jayaram. EventJava: An Extension of Java for Event Correlation. In ECOOP, pages 570--584, 2009.
13. }}P. T. Eugster, R. Guerraoui, and C. H. Damm. On Objects and Events. In OOPSLA, pages 254--269, 2001.
14. }}J. Fischer, R. Majumdar, and T. Millstein. Tasks: language support for event-driven programming. In PEPM, pages 134--143, 2007.
15. }}E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Longman Publishing Co., Inc., 1995.
16. }}C. A. Glasbey. An analysis of histogram-based thresholding algorithms. CVGIP: Graphical Models and Image Processing, 55(6):532 -- 537, 1993.
17. }}J. Gosling, B. Joy, and G. L. Steele. The Java Language Specification. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1996.
18. }}Image Processing and Analysis in Java. ImageJ. http://rsbweb.nih.gov/ij/.
19. }}M. Krohn, E. Kohler, and M. F. Kaashoek. Events can make sense. In USENIX, 2007.
20. }}L. Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM, 21(7):558--565, 1978.
21. }}D. Lea. Concurrent Programming in Java. Second Edition: Design Principles and Patterns. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1999.
22. }}D. Lea. A Java Fork/Join Framework. In Java Grande, pages 36--43, 2000.
23. }}D. Leijen, W. Schulte, and S. Burckhardt. The design of a task parallel library. In the conference on Object oriented programming systems languages and applications (OOPSLA), pages 227--242, 2009.
24. }}P. Li and S. Zdancewic. Combining events and threads for scalable network services implementation and evaluation of monadic, application-level concurrency primitives. In PLDI, pages 189--199, 2007.
25. }}Y. Long, S. Mooney, T. Sondag, and H. Rajan. \panini: Separation of Concerns Meets Concurrency. Technical Report 09--28b, Iowa State U., Dept. of Computer Sc., 2010.
26. }}Mohsen Vakilian and Danny Dig and Robert Bocchino and Jeffrey Overbey and Vikram Adve and Ralph Johnson . Inferring method effect summaries for nested heap regions. In IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 421--432, 2009.
27. }}D. Notkin, D. Garlan, W. G. Griswold, and K. J. Sullivan. Adding Implicit Invocation to Languages: Three Approaches. In JSSST International Symposium on Object Technologies for Advanced Software, pages 489--510, 1993.
28. }}B. Oki, M. Pfluegl, A. Siegel, and D. Skeen. The Information Bus: An Architecture for Extensible Distributed Systems. In SOSP, pages 58--68, 1993.
29. }}J. Ousterhout. Why threads are a bad idea (for most purposes). In ATEC, January 1996.
30. }}P. Charles ηl. X10: an object-oriented approach to non-uniform cluster computing. In the conference on Object-oriented programming, systems, languages, and applications (OOPSLA), pages 519--538, 2005.
31. }}P. Pratikakis, J. Spacco, and M. Hicks. Transparent Proxies for Java Futures. In OOPSLA, pages 206--223, 2004.
32. }}R. Bocchino ηl. A type and effect system for deterministic parallel java. In the conference on Object oriented programming systems languages and applications (OOPSLA), pages 97--116, 2009.
33. }}H. Rajan, S. M. Kautz, and W. Rowcliffe. Concurrency by modularity: Design patterns, a case in point. In 2010 Onward! Conference, October 2010.
34. }}H. Rajan and G. T. Leavens. Ptolemy: A language with quantified, typed events. In ECOOP, pages 155--179, 2008.
35. }}H. Rajan and K. Sullivan. Eos: instance-level aspects for integrated system design. In the European software engineering conference and international symposium on Foundations of software engineering (ESEC/FSE), pages 297--306, 2003.
36. }}H. Rajan and K. Sullivan. Need for instance level aspect language with rich pointcut language. In L. Bergmans, J. Brichau, P. Tarr, and E. Ernst, editors, SPLAT: Software engineering Properties of Languages for Aspect Technologies, mar 2003.
37. }}M. C. Rinard and M. S. Lam. The design, implementation, and evaluation of Jade. ACM Trans. Program. Lang. Syst., 20(3):483--545, 1998.
38. }}J. Robert H. Halstead. Multilisp: A Language for Concurrent Symbolic Computation. ACM Trans. Program. Lang. Syst., 7(4):501--538, 1985.
39. }}S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 2nd edition, 2003.
40. }}D. C. Schmidt. Reactor: an object behavioral pattern for concurrent event demultiplexing and event handler dispatching. Pattern languages of program design, pages 529--545, 1995.
41. }}B. Shriver and P. Wegner. Research directions in object-oriented programming, 1987.
42. }}K. J. Sullivan and D. Notkin. Reconciling Environment Integration and Component Independence. SIGSOFT Software Engineering Notes, 15(6):22--33, December 1990.
43. }}H. Sutter and J. Larus. Software and the concurrency revolution. Queue, 3(7):54--62, 2005.
44. }}J.-P. Talpin and P. Jouvelot. The type and effect discipline. Inf. Comput., 111(2):245--296, 1994.
45. }}A. Welc, S. Jagannathan, and A. Hosking. Safe Futures for Java. In OOPSLA, pages 439--453, 2005.
46. }}A. Yonezawa. ABCL: An object-oriented concurrent system, 1990.
47. }}A. Yonezawa and M. Tokoro. Object-oriented concurrent programming, 1990.\endthebibliography

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Concurrent programming structures

        • Patterns

      • Language types

        • Concurrent programming languages

        • Distributed programming languages

        • Parallel programming languages