Scalable extensibility via nested inheritance

ABSTRACT

Inheritance is a useful mechanism for factoring and reusing code. However, it has limitations for building extensible systems. We describe <i>nested inheritance</i>, a mechanism that addresses some of the limitations of ordinary inheritance and other code reuse mechanisms. Using our experience with an extensible compiler framework, we show how nested inheritance can be used to construct highly extensible software frameworks. The essential aspects of nested inheritance are formalized in a simple object-oriented language with an operational semantics and type system. The type system of this language is sound, so no run-time type checking is required to implement it and no run-time type errors can occur. We describe our implementation of nested inheritance as an unobtrusive extension of the Java language, called Jx. Our prototype implementation translates Jx code to ordinary Java code, without duplicating inherited code.

REFERENCES

• 1: Davide Ancona , Giovanni Lagorio , Elena Zucca, Jam - A Smooth Extension of Java with Mixins, Proceedings of the 14th European Conference on Object-Oriented Programming, p.154-178, June 12-16, 2000
• 2: Gilad Bracha , William Cook, Mixin-based inheritance, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.303-311, September 1990, Ottawa, Canada
• 3: Kim B. Bruce, Adrian Fiech, and Leaf Petersen. Subtyping is not a good "match" for object-oriented languages. In Proceedings of 11th European Conference on Object-Oriented Programming (ECOOP'97), number 1241 in Lecture Notes in Computer Science, pages 104--127, Jyväskylä, Finland, June 1997. Springer-Verlag.
• 4: Kim B. Bruce , Martin Odersky , Philip Wadler, A Statically Safe Alternative to Virtual Types, Proceedings of the 12th European Conference on Object-Oriented Programming, p.523-549, July 20-24, 1998
• 5: Kim B. Bruce , Angela Schuett , Robert van Gent, PolyTOIL: A Type-Safe Polymorphic Object-Oriented Language, Proceedings of the 9th European Conference on Object-Oriented Programming, p.27-51, August 07-11, 1995
• 6: Curtis Clifton , Gary T. Leavens , Craig Chambers , Todd Millstein, MultiJava: modular open classes and symmetric multiple dispatch for Java, ACM SIGPLAN Notices, v.35 n.10, p.130-145, Oct. 2000
• 7: O.-J. Dahl et al. The Simula 67 common base language. Publication No. S-22, Norwegian Computing Center, Oslo, 1970.
• 8: 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.
• 9: Erik Ernst, Family Polymorphism, Proceedings of the 15th European Conference on Object-Oriented Programming, p.303-326, June 18-22, 2001
• 10: 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.
• 11: Matthew Flatt , Shriram Krishnamurthi , Matthias Felleisen, Classes and mixins, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.171-183, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268961]
• 12: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 13: James Gosling , Bill Joy , Guy Steele , Gilad Bracha, Java Language Specification, Second Edition: The Java Series, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 14: Carl A. Gunter , John C. Mitchell, Theoretical aspects of object-oriented programming: types, semantics, and language design, MIT Press, Cambridge, MA, 1994
• 15: Atsushi Igarashi , Benjamin C. Pierce, Foundations for Virtual Types, Proceedings of the 13th European Conference on Object-Oriented Programming, p.161-185, June 14-18, 1999
• 16: Atsushi Igarashi , Benjamin C. Pierce , Philip Wadler, Featherweight Java: a minimal core calculus for Java and GJ, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.3, p.396-450, May 2001 [doi>10.1145/503502.503505]
• 17: Atsushi Igarashi , Benjamin C. Pierce, On inner classes, Information and Computation, v.177 n.1, p.56-89, 25 August 2002 [doi>10.1006/inco.2002.3092]
• 18: Gregor Kiczales , Erik Hilsdale , Jim Hugunin , Mik Kersten , Jeffrey Palm , William G. Griswold, An Overview of AspectJ, Proceedings of the 15th European Conference on Object-Oriented Programming, p.327-353, June 18-22, 2001
• 19: Gregor Kiczales, John Lamping, Anurag Mendhekar, Chris Maeda, Cristina Videira Lopes, Jean-Marc Loingtier, and John Irwin. Aspect-oriented 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.
• 20: B Liskov , E Moss , A Snyder , R Atkinson , J C. Schaffert , T Bloom , R Scheifler, CLU reference manual, Springer-Verlag New York, Inc., New York, NY, 1984
• 21: Ole Lehrmann Madsen , Birger Mø-Pedersen , Kristen Nygaard, Object-oriented programming in the BETA programming language, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 22: O. L. Madsen , B. Moller-Pedersen, Virtual classes: a powerful mechanism in object-oriented programming, Conference proceedings on Object-oriented programming systems, languages and applications, p.397-406, October 02-06, 1989, New Orleans, Louisiana, United States
• 23: Sean McDirmid , Matthew Flatt , Wilson C. Hsieh, Jiazzi: new-age components for old-fasioned Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.211-222, October 14-18, 2001, Tampa Bay, FL, USA
• 24: Robin Milner , Mads Tofte , Robert Harper, The Definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 25: Andrew C. Myers, Lantian Zheng, Steve Zdancewic, Stephen Chong, and Nathaniel Nystrom. Jif: Java information flow. Software release. Located at http://www.cs.cornell.edu/jif, July 2001-2003.
• 26: Nathaniel Nystrom, Stephen Chong, and Andrew C. Myers. Scalable extensibility via nested inheritance. Technical Report 2004-1940, Computer Science Dept., Cornell University, June 2004.
• 27: Nathaniel Nystrom, Michael 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.
• 28: Martin Odersky, Philippe Altherr, Vincent Cremet, Burak Emir, Sebastian Maneth, Stephane Micheloud, Nikolay Mihaylov, Michel Schinz, Erik Stenman, and Matthias Zenger. An overview of the Scala programming language, June 2004. http://scala.epfl.ch/docu/files/-ScalaOverview.pdf.
• 29: Martin Odersky, Vincent Cremet, Christine Röckl, and Matthias Zenger. A nominal theory of objects with dependent types. In Proceedings of 17th European Conference on Object-Oriented Programming (ECOOP 2003), number 2743 in Lecture Notes in Computer Science, pages 201--224. Springer-Verlag, July 2003.
• 30: Martin Odersky and Christoph Zenger. Nested types. In 8th Workshop on Foundations of Object-Oriented Languages (FOOL), 2001.
• 31: Klaus Ostermann, Dynamically Composable Collaborations with Delegation Layers, Proceedings of the 16th European Conference on Object-Oriented Programming, p.89-110, June 10-14, 2002
• 32: 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 {14}, pages 13--23.
• 33: Yannis Smaragdakis , Don S. Batory, Implementing Layered Designs with Mixin Layers, Proceedings of the 12th European Conference on Object-Oriented Programming, p.550-570, July 20-24, 1998
• 34: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 35: Kresten Krab Thorup. Genericity in Java with virtual types. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP), number 1241 in Lecture Notes in Computer Science, pages 444--471. Springer-Verlag, 1997.
• 36: Mads Torgerson. Virtual types are statically safe. In 5th Workshop on Foundations of Object-Oriented Languages (FOOL), January 1998.
• 37: Andrew K. Wright , Matthias Felleisen, A syntactic approach to type soundness, Information and Computation, v.115 n.1, p.38-94, Nov. 15, 1994 [doi>10.1006/inco.1994.1093]
• 38: Matthias Zenger , Martin Odersky, Extensible algebraic datatypes with defaults, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 39: Matthias Zenger and Martin Odersky. Independently extensible solutions to the expression problem. Technical Report IC/2004/33, École Polytechnique Fédérale de Lausanne, March 2004.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Inheritance; Modules, packages; Frameworks; Classes and objects

General Terms:
Languages

Keywords:
inheritance, nested classes, object-oriented programming languages, virtual classes