Open multi-methods for c++

ABSTRACT

Multiple dispatch - the selection of a function to be invoked based on the dynamic type of two or more arguments - is a solution to several classical problems in object-oriented programming. Open multi-methods generalize multiple dispatch towards open-class extensions, which improve separation of concerns and provisions for retroactive design. We present the rationale, design, implementation, and performance of a language feature, called open multi-methods, for C++. Our open multi-methods support both repeated and virtual inheritance. Our call resolution rules generalize both virtual function dispatch and overload resolution semantics. After using all information from argument types, these rules can resolve further ambiguities by using covariant return types. Great care was taken to integrate open multi-methods with existing C++ language features and rules. We describe a model implementation and compare its performance and space requirements to existing open multi-method extensions and workaround techniques for C++. Compared to these techniques, our approach is simpler to use, catches more user mistakes, and resolves more ambiguities through link-time analysis, runs significantly faster, and requires less memory. In particular, the runtime cost of calling an open multi method is constant and less than the cost of a double dispatch (two virtual function calls). Finally, we provide a sketch of a design for open multi-methods in the presence of dynamic loading and linking of libraries.

REFERENCES

• 1: Andrei Alexandrescu, Modern C++ design: generic programming and design patterns applied, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 2: Eric Amiel , Olivier Gruber , Eric Simon, Optimizing multi-method dispatch using compressed dispatch tables, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.244-258, October 23-28, 1994, Portland, Oregon, United States
• 3: Ken Arnold , James Gosling , David Holmes, The Java Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 4: Matthew H. Austern, Generic programming and the STL: using and extending the C++ Standard Template Library, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 5: Lorenzo Bettini , Sara Capecchi , Betti Venneri, Double dispatch in C++, Software—Practice & Experience, v.36 n.6, p.581-613, May 2006 [doi>10.1002/spe.v36:6]
• 6: G.M. Birtwhistle , O.J. Dahl , B. Myhrhaug , K. Nygaard, Simula Begin, Chartwell-Bratt Ltd, 1979
• 7: John Boyland , Giuseppe Castagna, Parasitic methods: an implementation of multi-methods for Java, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.66-76, October 05-09, 1997, Atlanta, Georgia, United States
• 8: Kim Bruce , Luca Cardelli , Giuseppe Castagna , Gary T. Leavens , Benjamin Pierce, On binary methods, Theory and Practice of Object Systems, v.1 n.3, p.221-242, Fall 1995
• 9: Craig Chambers, Object-Oriented Multi-Methods in Cecil, Proceedings of the European Conference on Object-Oriented Programming, p.33-56, June 29-July 03, 1992
• 10: C. Chambers. The Cecil language: Specification and rationale. 3.2. Technical report, Department of Computer Science and Engineering. University of Washington, 2004.
• 11: Craig Chambers , Weimin Chen, Efficient multiple and predicated dispatching, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.238-255, November 01-05, 1999, Denver, Colorado, United States
• 12: Curtis Clifton , Gary T. Leavens , Craig Chambers , Todd Millstein, MultiJava: modular open classes and symmetric multiple dispatch for Java, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.130-145, October 2000, Minneapolis, Minnesota, United States
• 13: Codesourcery.com. The Itanium C++ ABI. Technical report, 2001.
• 14: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 15: Edison Design Group. C++ Front End, March 2006.
• 16: C. B. Flynn and D. Wonnacott. Reconciling encapsulation and dynamic dispatch via accessory functions. Technical Report 387, Rutgers University Department of Computer Science, 1999.
• 17: B. Foote, R. Johnson, and J. Noble. Efficient Multimethods in a Single Dispatch Language. Proceedings of the European Conference on Object-Oriented Programming, Glasgow, Scotland, July, 2005.
• 18: 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
• 19: Michael Gibbs , Bjarne Stroustrup, Fast dynamic casting, Software—Practice & Experience, v.36 n.2, p.139-156, February 2006 [doi>10.1002/spe.v36:2]
• 20: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 21: Douglas Gregor , Jaakko Järvi , Jeremy Siek , Bjarne Stroustrup , Gabriel Dos Reis , Andrew Lumsdaine, Concepts: linguistic support for generic programming in C++, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 22: International Organization for Standardization. ISO/IEC 10918-1:1994: Information technology - Digital compression and coding of continuous-tone still images: Requirements and guidelines. 1994.
• 23: ISO/IEC 14882 International Standard. Programming languages C++. American National Standards Institute, September 1998.
• 24: Barbara Liskov, Keynote address - data abstraction and hierarchy, Addendum to the proceedings on Object-oriented programming systems, languages and applications (Addendum), p.17-34, October 04-08, 1987, Orlando, Florida, United States
• 25: Lockheed Martin. Joint Strike Fighter, Air Vehicle, C++ Coding Standard. Lockheed Martin, December 2005.
• 26: Bertrand Meyer, Eiffel: the language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 27: Todd Millstein , Mark Reay , Craig Chambers, Relaxed MultiJava: balancing extensibility and modular typechecking, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 28: Todd D. Millstein , Craig Chambers, Modular Statically Typed Multimethods, Proceedings of the 13th European Conference on Object-Oriented Programming, p.279-303, June 14-18, 1999
• 29: M. Schordan and D. Quinlan. A source-to-source architecture for user-defined optimizations. In JMLC'03, volume 2789 of LNCS, pages 214--223. Springer-Verlag, August 2003.
• 30: A. Shalit. The Dylan Reference Manual. 2nd edition. Apple Press, 1996.
• 31: J. Smith. Draft proposal for adding multimethods to C++. Technical Report N1463, JTC1/SC22/WG21 C++ Standards Committee, 2003.
• 32: Guy Steele, Common Lisp: The Language, Digital Press, Newton, MA, 1990
• 33: Bjarne Stroustrup, The design and evolution of C++, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 34: Bjarne Stroustrup, The C++ Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 35: B. Stroustrup and G. Dos Reis. Supporting SELL for high-performance computing. In LCPC'05, volume 4339 of LNCS, pages 458--465. Springer-Verlag, October 2005.
• 36: G. van Rossum. The Python Language Reference Manual. Network Theory Ltd., September 2003.
• 37: Joost Visser, Visitor combination and traversal control, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.270-282, October 14-18, 2001, Tampa Bay, FL, USA
• 38: Daniel Wasserrab , Tobias Nipkow , Gregor Snelting , Frank Tip, An operational semantics and type safety prooffor multiple inheritance in C++, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 39: David Wonnacott, Using accessory functions to generalize dynamic dispatch in single-dispatch object-oriented languages, Proceedings of the 6th conference on USENIX Conference on Object-Oriented Technologies and Systems, p.7-7, January 29-February 02, 2001, San Antonio, Texas
• 40: A. Wöß, M. Löberbauer, and H. Mössenböck. LL(1) conflict resolution in a recursive descent compiler generator. In JMLC'03, volume 2789 of LNCS, pages 192--201. Springer-Verlag, 2003.
• 41: www.fourcc.org. Video codec and pixel format definition, February 2007.

INDEX TERMS

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

General Terms:
Design, Languages, Performance

Keywords:
C++, generic programming, multi-methods, multiple dispatch, object oriented programming, open-methods