J&: nested intersection for scalable software composition

Abstract

This paper introduces a programming language that makes it convenient to compose large software systems, combining their features in a modular way. J& supports nested intersection, building on earlier work on nested inheritance in the language Jx. Nested inheritance permits modular, type-safe extension of a package (including nested packages and classes), while preserving existing type relationships. Nested intersection enables composition and extension of two or more packages, combining their types and behavior while resolving conflicts with a relatively small amount of code. The utility of J& is demonstrated by using it to construct two composable, extensible frameworks: a compiler framework for Java, and a peer-to-peer networking system. Both frameworks support composition of extensions. For example, two compilers adding different, domain-specific features to Java can be composed to obtain a compiler for a language that supports both sets of features.

References

1. Alexandre Bergel, Stéphane Ducasse, and Oscar Nierstrasz. Classbox/J: Controlling the scope of change in Java. In Proc. OOPSLA '05, pages 177--189, October 2005.]]
2. David Binkley, Susan Horwitz, and Thomas Reps. Program integration for languages with procedure calls. ACM Transactions on Software Engineering and Methodology (TOSEM), 4(1):3--35, January 1995.]]
3. Alan Borning and Daniel Ingalls. Multiple inheritance in Smalltalk-80. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 234--237, August 1982.]]
4. Gilad Bracha and William Cook. Mixin-based inheritance. In Norman Meyrowitz, editor, Proc. OOPSLA '90, pages 303--311, Ottawa, Canada, 1990. ACM Press.]]
5. Kim B. Bruce. Safe static type checking with systems of mutually recursive classes and inheritance. Technical report, Williams College, 1997. http://cs.williams.edu/~kim/ftp/RecJava.ps.gz.]]
6. Kim B. Bruce. Some challenging typing issues in object-oriented languages. Electronic Notes in Theoretical Computer Science, 82(8):1--29, October 2003.]]
7. Kim B. Bruce, Angela Schuett, and Robert van Gent. PolyTOIL: A type-safe polymorphic object-oriented language. In European Conference on Object-Oriented Programming (ECOOP), number 952 in Lecture Notes in Computer Science, pages 27--51. Springer-Verlag, 1995.]]
8. Kim B. Bruce and Joseph C. Vanderwaart. Semantics-driven language design: Statically type-safe virtual types in object-oriented languages. In Mathematical Foundations of Programming Semantics (MFPS), Fifteenth Conference, volume 20 of Electronic Notes in Theoretical Computer Science, pages 50--75, April 1999.]]
9. Luca Cardelli. A semantics of multiple inheritance. Information and Computation, 76:138--164, 1988. Also in Readings in Object-Oriented Database Systems, S. Zdonik and D. Maier, eds., Morgan Kaufmann, 1990.]]
10. Craig Chambers, David Ungar, Bay-Wei Chang, and Urs Hölzle. Parents are shared parts of objects: Inheritance and encapsulation in Self. Lisp and Symbolic Computation, 4(3):207--222, June 1991.]]
11. Dave Clarke, Sophia Drossopoulou, James Noble, and Tobias Wrigstad. Tribe: More types for virtual classes. Submitted for publication. Available at http://slurp.doc.ic.ac.uk/pubs.html, December 2005.]]
12. Curtis Clifton, Gary T. Leavens, Craig Chambers, and Todd Millstein. MultiJava: Modular open classes and symmetric multiple dispatch for Java. In OOPSLA 2000 Conference on Object-Oriented Programming, Systems, Languages, and Applications, Minneapolis, Minnesota, volume 35(10), pages 130--145, 2000.]]
13. Adriana B. Compagnoni and Benjamin C. Pierce. Higher order intersection types and multiple inheritance. Mathematical Structures in Computer Science, 6(5):469--501, 1996.]]
14. Robert DeLine and Manuel Fähndrich. Enforcing high-level protocols in low-level software. In Proceedings of the ACM Conference on Programming Language Design and Implementation, pages 59--69, June 2001.]]
15. Erik Ernst. gbeta -- a Language with Virtual Attributes, Block Structure, and Propagating, Dynamic Inheritance. PhD thesis, Department of Computer Science, University of Aarhus, Århus, Denmark, 1999.]]
16. Erik Ernst. Propagating class and method combination. In Proceedings of the Thirteenth European Conference on Object-Oriented Programming (ECOOP'99), number 1628 in Lecture Notes in Computer Science, pages 67--91. Springer-Verlag, June 1999.]]
17. Erik Ernst. Family polymorphism. In Proceedings of the 15th European Conference on Object-Oriented Programming (ECOOP), LNCS 2072, pages 303--326, Heidelberg, Germany, 2001. Springer-Verlag.]]
18. Erik Ernst. Higher-order hierarchies. In Proceedings of the 17th European Conference on Object-Oriented Programming (ECOOP), volume 2743 of Lecture Notes in Computer Science, pages 303--329, Heidelberg, Germany, July 2003. Springer-Verlag.]]
19. Erik Ernst, Klaus Ostermann, and William R. Cook. A virtual class calculus. In Proc. 33th ACM Symp. on Principles of Programming Languages (POPL), Charleston, South Carolina, January 2006. To appear.]]
20. Matthew Flatt, Shriram Krishnamurthi, and Matthias Felleisen. Classes and mixins. In Proc. 25th ACM Symp. on Principles of Programming Languages (POPL), pages 171--183, San Diego, California, 1998.]]
21. Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison Wesley, Reading, MA, 1994.]]
22. Carl Gunter and John C. Mitchell, editors. Theoretical aspects of object-oriented programming. MIT Press, 1994.]]
23. Susan Horwitz, Jan Prins, and Thomas Reps. Integrating noninterfering versions of programs. ACM Transactions on Programming Languages and Systems, 11(3):345--387, July 1989.]]
24. Scott E. Hudson, Frank Flannery, C. Scott Ananian, Dan Wang, and Andrew Appel. CUP LALR parser generator for Java, 1996. Software release. Located at http://www.cs.princeton.edu/~appel/-modern/java/CUP/.]]
25. Atsushi Igarashi and Benjamin Pierce. Foundations for virtual types. In Proceedings of the Thirteenth European Conference on Object-Oriented Programming (ECOOP'99), number 1628 in Lecture Notes in Computer Science, pages 161--185. Springer-Verlag, June 1999.]]
26. Paul Jolly, Sophia Drossopoulou, Christopher Anderson, and Klaus Ostermann. Simple dependent types: Concord. In ECOOP Workshop on Formal Techniques for Java Programs (FTfJP), June 2004.]]
27. Gregor Kiczales, John Lamping, Anurag Mendhekar, Chris Maeda, Cristina Videira Lopes, Jean-Marc Loingtier, and John Irwin. Aspectoriented programming. In Proceedings of 11th European Conference on Object-Oriented Programming (ECOOP'97), number 1241 in Lecture Notes in Computer Science, pages 220--242, Jyväskylä, Finland, June 1997. Springer-Verlag.]]
28. Jed Liu and Andrew C. Myers. JMatch: Abstract iterable pattern matching for Java. In Proc. 5th Int'l Symp. on Practical Aspects of Declarative Languages (PADL), pages 110--127, New Orleans, LA, January 2003.]]
29. O. Lehrmann Madsen, B. Müller-Pedersen, and K. Nygaard. Object Oriented Programming in the BETA Programming Language. Addison-Wesley, June 1993.]]
30. Ole Lehrmann Madsen and Birger Møller-Pedersen. Virtual classes: A powerful mechanism for object-oriented programming. In Proc. OOPSLA '89, pages 397--406, October 1989.]]
31. Katsuhisa Maruyama and Ken-Ichi Shima. An automatic class generation mechanism by using method integration. IEEE Transactions on Software Engineering, 26(5):425--440, May 2000.]]
32. Bertrand Meyer. Object-oriented Software Construction. Prentice Hall, New York, 1988.]]
33. M. Mezini and K. Ostermann. Conquering aspects with Caesar. In Proceedings of the 2nd International Conference on Aspect-Oriented Software Development (AOSD), pages 90--100, March 2003.]]
34. Todd Millstein. Practical predicate dispatch. In Proceedings of the 19th ACM Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA), October 2004.]]
35. Nathaniel Nystrom, Stephen Chong, and Andrew C. Myers. Scalable extensibility via nested inheritance. In Proceedings of the 19th ACM Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA), pages 99--115, October 2004.]]
36. Nathaniel Nystrom, Michael R. Clarkson, and Andrew C. Myers. Polyglot: An extensible compiler framework for Java. In Görel Hedin, editor, Compiler Construction, 12th International Conference, CC 2003, number 2622 in Lecture Notes in Computer Science, pages 138--152, Warsaw, Poland, April 2003. Springer-Verlag.]]
37. Nathaniel Nystrom, Xin Qi, and Andrew C. Myers. Nested intersection for scalable software extension, September 2006. http://www.cs.cornell.edu/nystrom/papers/jet-tr.pdf.]]
38. Martin Odersky and Matthias Zenger. Scalable component abstractions. In Proc. OOPSLA '05, pages 41--57, October 2005.]]
39. Harold Ossher and William Harrison. Combination of inheritance hierarchies. In Proc. OOPSLA '92, pages 25--40, October 1992.]]
40. Venugopalan Ramasubramanian, Ryan Peterson, and Emin Gün Sirer. Corona: A high performance publish-subscribe system for the World Wide Web. In Proceedings of Networked System Design and Implementation (NSDI), May 2006.]]
41. Venugopalan Ramasubramanian and Emin Gün Sirer. Beehive: O(1) lookup performance for power-law query distributions in peer-to-peer overlays. In USENIX Symposium on Networked Systems Design and Implementation (NSDI), March 2004.]]
42. John C. Reynolds. User-defined types and procedural data structures as complementary approaches to data abstraction. In Stephen A. Schuman, editor, New Directions in Algorithmic Languages, pages 157--168. Institut de Recherche d'Informatique et d'Automatique, Le Chesnay, France, 1975. Reprinted in 22., pages 13--23.]]
43. John C. Reynolds. Design of the programming language Forsythe. Technical Report CMU-CS-96-146, Carnegie Mellon University, June 1996.]]
44. Antony Rowstron and Peter Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), pages 329--350, November 2001.]]
45. Nathanael Schärli, Stéphane Ducasse, Oscar Nierstrasz, and Andrew P. Black. Traits: Composable units of behavior. In Luca Cardelli, editor, Proceedings of the 17th European Conference on Object-Oriented Programming (ECOOP 2003), number 2743 in Lecture Notes in Computer Science, pages 248--274, Darmstadt, Germany, July 2003. Springer-Verlag.]]
46. Gregor Snelting and Frank Tip. Semantics-based composition of class hierarchies. In Proceedings of the 16th European Conference on Object-Oriented Programming (ECOOP), volume 2374 of Lecture Notes in Computer Science, pages 562--584, Málaga, Spain, 2002. Springer-Verlag.]]
47. Bjarne Stroustrup. The C++ Programming Language. Addison-Wesley, 1987.]]
48. Peri Tarr, Harold Ossher, William Harrison, and Jr. Stanley M. Sutton. N degrees of separation: Multi-dimensional separation of concerns. In Proceedings of the 1999 International Conference on Software Engineering (ICSE), pages 107--119, May 1999.]]
49. Philip Wadler et al. The expression problem, December 1998. Discussion on Java-Genericity mailing list.]]
50. Alessandro Warth, Milan Stanojević, and Todd Millstein. Statically scoped object adaptation with expanders. In Proceedings of the 2006 Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA '06), October 2006.]]

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Classes and objects

        • Frameworks

        • Inheritance

        • Modules / packages

      • Language types

        • Object oriented languages