Typechecking and modules for multi-methods

ABSTRACT

Two major obstacles hindering the wider acceptance of multi-methods are concerns over the lack of encapsulation and modularity and the absence of static typechecking in existing multi-method-based languages. This paper addresses both of these problems. We present a polynomial-time static typechecking algorithm that checks the conformance, completeness, and consistency of a group of method implementations with respect to declared message signatures. This algorithm improves on previous algorithms by handling separate type and inheritance hierarchies, abstract classes, and graph-based method lookup semantics. We also present a module system that enables independently-developed code to be fully encapsulated and statically typechecked on a per-module basis. To guarantee that potential conflicts between independently-developed modules have been resolved, a simple well-formedness condition on the modules comprising a program is checked at link-time. The typechecking algorithm and module system are applicable to a range of multi-method-based languages, but the paper uses the Cecil language as a concrete example of how they can be applied.

REFERENCES

• Ada 83: Reference Manual for the Ada Progrcunming Language, ANSI/MIL-STD 1815A, 1983.
• Agrawal et al. 91: Rakesh Agrawal , Linda G. Demichiel , Bruce G. Lindsay, Static type checking of multi-methods, Conference proceedings on Object-oriented programming systems, languages, and applications, p.113-128, October 06-11, 1991, Phoenix, Arizona, United States
• America 87: Pierre America, Inheritance and subtyping in a parallel object-oriented language, European conference on object-oriented programming on ECOOP '87, p.234-242, October 1987, Paris, France
• America & van der Linden 90: Pierre America , Frank van der Linden, A parallel object-oriented language with inheritance and subtyping, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.161-168, September 1990, Ottawa, Canada
• Amiel et al. 94: 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
• Barnes 91: J. G. P. Barnes. Programming in Ada (third edition). Addison-Wesley, Wokingham, England, 1991.
• Bobrow et al. 88: Daniel G. Bobrow , Linda G. DeMichiel , Richard P. Gabriel , Sonya E. Keene , Gregor Kiczales , David A. Moon, Common Lisp Object System specification, ACM SIGPLAN Notices, v.23 n.SI, p.1-142, September 1988 [doi>10.1145/885631.885632]
• Bracha & Griswold 93: Gilad Bracha , David Griswold, Strongtalk: typechecking Smalltalk in a production environment, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.215-230, September 26-October 01, 1993, Washington, D.C., United States
• Bruce et al. 93: Kim B. Bruce , Jon Crabtree , Thomas P. Murtagh , Robert van Gent , Allyn Dimock , Robert Muller, Safe and decidable type checking in an object-oriented language, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.29-46, September 26-October 01, 1993, Washington, D.C., United States
• Canning et al. 89: P. S. Canning , W. R. Cook , W. L. Hill , W. G. Olthoff, Interfaces for strongly-typed object-oriented programming, Conference proceedings on Object-oriented programming systems, languages and applications, p.457-467, October 02-06, 1989, New Orleans, Louisiana, United States
• Cardelli & Wegner 85: Luca Cardelli , Peter Wegner, On understanding types, data abstraction, and polymorphism, ACM Computing Surveys (CSUR), v.17 n.4, p.471-523, Dec. 1985 [doi>10.1145/6041.6042]
• Cardelli & Mitchell 89: Luca Cardelli , John C. Mitchell, Operations on records, Proceedings of the fifth international conference on Mathematical foundations of programming semantics, p.22-52, July 1990, New Orleans, Louisiana, United States
• Castagna et al. 92: Giuseppe Castagna , Giorgio Ghelli , Giuseppe Longo, A calculus for overloaded functions with subtyping, Proceedings of the 1992 ACM conference on LISP and functional programming, p.182-192, June 22-24, 1992, San Francisco, California, United States
• Chambers 92: 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
• Chambers 93: Craig Chambers. The Cecil Language: Specification and Rationale. Technical report #93-03-05, Department of Computer Science and Engineering, University of Washington, March, 1993.
• Chambers & Leavens 94: Craig Chambers and Gary T. Leavens. Type.checking and Modules for Multi-Methods. Technical report #94-03-01, Department of Computer Science and Engineering, University of Washington, March, 1994.
• Chen & Turau 94: Weimin Chen , Volker Turau , Wolfgang Klas, Efficient Dynamic Look-Up Strategy for Multi-Methods, Proceedings of the 8th European Conference on Object-Oriented Programming, p.408-431, July 04-08, 1994
• Cook et al. 90: William R. Cook , Walter Hill , Peter S. Canning, Inheritance is not subtyping, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.125-135, December 1989, San Francisco, California, United States [doi>10.1145/96709.96721]
• Cook 90: William R. Cook, Object-Oriented Programming Versus Abstract Data Types, Proceedings of the REX School/Workshop on Foundations of Object-Oriented Languages, p.151-178, May 28-June 01, 1990
• Dean et al. 94: Jeffrey Dean, Craig Chambers, and David Grove. Identifying Profitable Specialization in Object-Oriented Languages. In Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, Orlando, FL, June, 1994. Available as Technical Report 94/9, Department of Computer Science, University of Melbourne, 1994.
• Ghelli 91: Giorgio Ghelli, A static type system for message passing, Conference proceedings on Object-oriented programming systems, languages, and applications, p.129-145, October 06-11, 1991, Phoenix, Arizona, United States
• Goldberg & Robson 83: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• Goguen 84: Joseph A. Goguen. Parameterized Programming. In IEEE Transactions on Software Engineering 10(5), pp. 528-543, September, 1984.
• Harrison & Ossher 93: William Harrison , Harold Ossher, Subject-oriented programming: a critique of pure objects, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.411-428, September 26-October 01, 1993, Washington, D.C., United States
• Hölzle 93: Urs Hölzle, Integrating Independently-Developed Components in Object-Oriented Languages, Proceedings of the 7th European Conference on Object-Oriented Programming, p.36-56, July 26-30, 1993
• Hudak et al. 92: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• Leavens 91: Gary T. Leavens, Modular Specification and Verification of Object-Oriented Programs, IEEE Software, v.8 n.4, p.72-80, July 1991 [doi>10.1109/52.300040]
• Leavens & Weihl 90: Gary T. Leavens , William E. Weihl, Reasoning about object-oriented programs that use subtypes, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.212-223, September 1990, Ottawa, Canada
• Liskov et al. 77: Barbara Liskov , Alan Snyder , Russell Atkinson , Craig Schaffert, Abstraction mechanisms in CLU, Communications of the ACM, v.20 n.8, p.564-576, Aug. 1977 [doi>10.1145/359763.359789]
• Liskov et al. 81: Barbara Liskov, Russell Atkinson, Toby Bloom, Eliot Moss, J. Craig Schaffert, Robert Scheifler, and Alan Snyder. CLU Reference Manual. Lecture Notes in Computer Science, volume 114, Springer-Verlag, New York, NY, 1981.
• Liskov & Zilles 74: Barbara Liskov , Stephen Zilles, Programming with abstract data types, Proceedings of the ACM SIGPLAN symposium on Very high level languages, p.50-59, March 28-29, 1974, Santa Monica, California, United States
• Meyer 88: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• Meyer 92: Bertrand Meyer, Eiffel: the language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• Milner et al. 90: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• Mössenböck & Wirth 91: H. M6ssenb6ck and Niklaus Wirth. The Programming Language Oberon-2. Structured Programming 12(4), 1991.
• Mugridge et al. 91: Warwick B. Mugridge , John Hamer , John G. Hosking, Multi-Methods in a Statically-Typed Programming Language, Proceedings of the European Conference on Object-Oriented Programming, p.307-324, July 15-19, 1991
• Nelson 91: Greg Nelson, Systems programming with Modula-3, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• Paepcke 93: Andreas Paepcke, Object-oriented programming: the CLOS perspective, MIT Press, Cambridge, MA, 1993
• Palsberg & Schwartzbach 94: Jens Palsberg , Michael I. Schwartzbach, Object-oriented type systems, John Wiley and Sons Ltd., Chichester, UK, 1994
• Parnas 71: D. L. Parnas. Information Distribution Aspects of Design Methodology. Proceedings of IFIP Congress 71. IFIP, 1971.
• Parnas 72: D. L. Parnas, A technique for software module specification with examples, Communications of the ACM, v.15 n.5, p.330-336, May 1972 [doi>10.1145/355602.361309]
• Paulson 91: Laurence C. Paulson, ML for the working programmer, Cambridge University Press, New York, NY, 1991
• Pierce & Turner 92: Benjamin C. Pierce and David N. Turner. Statically Typed Multi-Methods via Partially Abstract Types. Unpublished manuscript, October, 1992.
• Rouaix 90: Francois Rouaix, Safe run-time overloading, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.355-366, December 1989, San Francisco, California, United States [doi>10.1145/96709.96746]
• Schaffert et al. 86: Craig Schaffert , Topher Cooper , Bruce Bullis , Mike Kilian , Carrie Wilpolt, An introduction to Trellis/Owl, Conference proceedings on Object-oriented programming systems, languages and applications, p.9-16, September 29-October 02, 1986, Portland, Oregon, United States
• Snyder 86: Alan Snyder, Encapsulation and inheritance in object-oriented programming languages, Conference proceedings on Object-oriented programming systems, languages and applications, p.38-45, September 29-October 02, 1986, Portland, Oregon, United States
• Steele 90: Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
• Stroustrup 91: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• Szyperski 92: Clemens A. Szyperski, Import is Not Inheritance - Why We Need Both: Modules and Classes, Proceedings of the European Conference on Object-Oriented Programming, p.19-32, June 29-July 03, 1992
• Touretzky 86: David S. Touretzky, The mathematics of inheritance systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1986
• Wirfs-Brock & Wilkerson 88: Allen Wirfs-Brock , Brian Wilkerson, A overview of modular smalltalk, Conference proceedings on Object-oriented programming systems, languages and applications, p.123-134, September 25-30, 1988, San Diego, California, United States
• Wirth 88: Niklaus Wirth, Programming in MODULA-2 (3rd corrected ed.), Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Modules, packages

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Languages, Theory