Tribe: a simple virtual class calculus

ABSTRACT

Beginning with BETA, a range of programming language mechanisms such as virtual classes (class-valued attributes of objects) have been developed to allow inheritance in the presence of mutually dependent classes. This paper presents Tribe, a type system which generalises and simplifies other formalisms of such mechanisms, by treating issues which are inessential for soundness, such as the precise details of dispatch and field initialisation, as orthogonal to the core formalism. Tribe can support path types dependent simultaneously on both classes and objects, which is useful for writing library code, and ubiquitous access to an object's family, which offers family polymorphism without the need to drag around family arguments. Languages based on Tribe will be both simpler and more expressive than existing designs, while having a simpler type system, serving as a useful basis for future language designs.

REFERENCES

• 1: Ivica Aracic, Vaidas Gasiunas, Mira Mezini, and Klaus Ostermann. An overview of Caesar J. Transactions on Aspect-Oriented Software Development, LNCS, 3880:135--173, February 2006.
• 2: David Aspinall and Martin Hofmann. Dependent types. Chapter in {26}.
• 3: Gilad Bracha, The programming language jigsaw: mixins, modularity and multiple inheritance, University of Utah, Salt Lake City, UT, 1992
• 4: David Gerard Clarke, Object ownership and containment, 2003
• 5: David Clarke. Nested classes, nested objects, and ownership. Invited talk at FOOL/WOOD, January 2006.
• 6: David Clarke, Sophia Drossopoulou, James Noble, and Tobias Wrigstad. Tribe: More types for virtual classes, available from http://slurp.doc.ic.ac.uk/pubs.html#tribe, December 2005.
• 7: David Clarke and Tobias Wrigstad. External uniqueness is unique enough. In Proceedings of the 17th European Conference on Object-Oriented Programming (ECOOP), Darmstadt, Germany, 2003.
• 8: Vincent Cremet, François Garillot, Sergueï Lenglet, and Martin Odersky. A core calculus for Scala type checking. In Rastislav Kralovic and Pawel Urzyezyn, editors, Mathematical Foundations of Computer Science 2006, 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings, volume 4162 of Lecture Notes in Computer Science, pages 1--23. Springer, 2006.
• 9: Robert DeLine and Manuel Fähndrich. The Fugue protocol checker: Is your software baroque? Technical Report MSR-TR-2004-07, Microsoft Research, 2003.
• 10: Erik Ernst. gBeta---A Language with Virtual Attributes, Block Structure, and Propagating, Dynamic Inheritiance. PhD thesis, University of Aarhus, Denmark, 1999.
• 11: Erik Ernst, Family Polymorphism, Proceedings of the 15th European Conference on Object-Oriented Programming, p.303-326, June 18-22, 2001
• 12: Erik Ernst , Klaus Ostermann , William R. Cook, A virtual class calculus, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.270-282, January 11-13, 2006, Charleston, South Carolina, USA
• 13: Martin Odersky et al. An overview of the Scala programming language. Technical Report IC/2004/64, EPFL Lausanne, Switzerland, 2004.
• 14: Manuel Fähndrich , K. Rustan M. Leino, Declaring and checking non-null types in an object-oriented language, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 15: Types Forum. Completeness of subtype judgments. Discussions April 25 and onwards, 2006. http://lists.seas.upenn.edu/pipermail/types-list.
• 16: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 17: Atsushi Igarashi, Chieri Saito, and Mirko Viroli. Lightweight family polymorphism. In Proceedings of the 3rd Asian Symposium on Programming Languages and Systems (APLAS'05), volume 3780 of LNCS, Tsukuba, Japan, 2005.
• 18: Paul Jolly, Sophia Drossopoulou, Christopher Anderson, and Klaus Ostermann. Simple dependent types: Concord. In 6th ECOOP Workshop on Formal Techniques for Java-like Languages, June 2004.
• 19: Kitt. Wikipedia Article. http://en.wikipedia.org/wiki/KITT.
• 20: 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
• 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: Jan-Willem Maessen , Xiaowei Shen, Improving the Java memory model using CRF, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-12, October 2000, Minneapolis, Minnesota, United States
• 23: Mira Mezini , Klaus Ostermann, Conquering aspects with Caesar, Proceedings of the 2nd international conference on Aspect-oriented software development, p.90-99, March 17-21, 2003, Boston, Massachusetts [doi>10.1145/643603.643613]
• 24: Nathaniel Nystrom , Stephen Chong , Andrew C. Myers, Scalable extensibility via nested inheritance, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 25: Martin Odersky, Vincent Cremet, Christine Röckl, and Matthias Zenger. A nominal theory of objects with dependent types. In Luca Cardelli, editor, ECOOP 2003 - Object-Oriented Programming, 17th European Conference, Darmstadt, Germany, July 21--25, 2003, Proceedings, volume 2743 of Lecture Notes in Computer Science, pages 201--224. Springer, 2003.
• 26: Benjamin C. Pierce, Advanced Topics in Types and Programming Languages, The MIT Press, 2004
• 27: Nathanael Schärli, Stéphane Ducasse, Oscar Nierstrasz, and Andrew P. Black. Traits: Composable units of behaviour. In Luca Cardelli, editor, ECOOP 2003 - Object-Oriented Programming: 17th European Conference, volume 2473 of Lecture Notes In Computer Science, pages 248--274. Springer-Verlag, July 2003.
• 28: Bjarne Stroustrup, The C++ Programming Language, Third Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 29: 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]
• 30: Tobias Wrigstad. Ownership-Based Alias Management. PhD thesis, Department of Computer and Systems Science, Royal Institute of Technology, Kista, Stockholm, May 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
      F.3.3 Studies of Program Constructs

General Terms:
Languages, Theory

Keywords:
subtyping, virtual classes