Toward a typed foundation for method specialization and inheritance

ABSTRACT

This paper discusses the phenomenon of method specialization in object-oriented programming languages. A typed function calculus of objects and classes is presented, featuring method specialization when methods are added or redefined. The soundness of the typing rules (without subtyping) is suggested by a translation into a more traditional calculus with recursively-defined record types. However, semantic questions regarding the subtype relation on classes remain open.

REFERENCES

• AR88: Norman Adams , Jonathan Rees, Object-oriented programming in scheme, Proceedings of the 1988 ACM conference on LISP and functional programming, p.277-288, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62720]
• BI82: Alan H. Borning , Daniel H. H. Ingalls, A type declaration and inference system for smalltalk, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-141, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582168]
• BL88: K. Bruce and G. Longo. A modest model of records, inheritance and bounded quantification. In Third IEEE Syrup'. Logic in Computer Science, pages 38-51, 1988:
• BMM89: Kim B. Bruce , Albert R. Meyer , John C. Mitchell, The semantics of second-order lambda calculus, Information and Computation, v.85 n.1, p.76-134, March 1990 [doi>10.1016/0890-5401(90)90044-I]
• Bor86: A. H. Borning, Classes versus prototypes in object-oriented languages, Proceedings of 1986 ACM Fall joint computer conference, p.36-40, November 1986, Dallas, Texas, United States
• BTCGS89: V. Breazu-Tannen , T. Coquand , C. Gunter , A. Scedrov, Inheritance and explicit coercion, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.112-129, June 1989, Pacific Grove, California, United States
• Car86: L Cardelli, Amber, Proc. of the thirteenth spring school of the LITP on Combinators and functional programming languages, p.21-47, October 1986, Val d'Ajol, France
• Car88: Luca Cardelli, A semantics of multiple inheritance, Information and Computation, v.76 n.2-3, p.138-164, February/March 1988 [doi>10.1016/0890-5401(88)90007-7]
• CCH+89: Peter Canning , William Cook , Walter Hill , Walter Olthoff , John C. Mitchell, F-bounded polymorphism for object-oriented programming, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.273-280, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99392]
• CDG+88: L. Cardelli, J. Donahue, L. Galssman, M. Jordan, B. Kalsow, and G. Nelson. Modula-3 report. Technical Report SRC-31, DEC systems Research Center, 1988.
• CDJ+89: L. Cardelli , J. Donahue , M. Jordan , B. Kalsow , G. Nelson, The Modula–3 type system, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.202-212, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75295]
• CM88: L. Cardelli and J.C. Mitchell. Semantic methods for object-oriented languages. Unpublished OOPSLA tutorial, 1988.
• CM89: 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
• Coo89a: William R. Cook, A denotational semantics of inheritance, 1989
• Coo89b: W.R. Cook. A proposal for making Eiffel type-safe. In European Conf. on Object-Oriented Programming, pages 57-72, 1989.
• CU89: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
• CW85: 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]
• DCBA89: A. DiMaio, C. Cardingno, R. Bayan, and C. Atkinson. Dragoon: an Ada-based object-oriented language. In Proc. Ada- Europe Conference, 1989. To appear.
• DT88: Scott Danforth , Chris Tomlinson, Type theories and object-oriented programmimg, ACM Computing Surveys (CSUR), v.20 n.1, p.29-72, March 1988 [doi>10.1145/62058.62060]
• Gir71: J.-Y. Girard. Une ext.ensi,)li tie l'interpretation de G6del h l'at~alyse, et son application ~t l'4lirnination des coupures dalls l'analyse et la thdorie des types. In J.E. Fenstad, editor, 2nd Scandinavian Logic Symposium, pages 63-92. North-IJolland, 1971.
• Gir72: j.-Y. Girard. Interpretatiol~ follctionelle et elimination des coupures de l'arithmetique d'ordre SUl)erieur. These D'Etat, Universite Paris VII, 1972.
• GR83: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• JM88: Lalita Jategaonkar , John Mitchell, ML with extended pattern matching and subtypes, Proceedings of the 1988 ACM conference on LISP and functional programming, p.198-211, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62702]
• Kam88: S. Kamin, Inheritance in smalltalk-80: a denotational definition, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.80-87, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73567]
• Lie86: Henry Lieberman, Using prototypical objects to implement shared behavior in object-oriented systems, Conference proceedings on Object-oriented programming systems, languages and applications, p.214-223, September 29-October 02, 1986, Portland, Oregon, United States
• LTP86: Wilf R. LaLonde , Dave A. Thomas , John R. Pugh, An exemplar based Smalltalk, Conference proceedings on Object-oriented programming systems, languages and applications, p.322-330, September 29-October 02, 1986, Portland, Oregon, United States
• Mey88: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• Mit84: John C. Mitchell, Coercion and type inference, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.175-185, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800529]
• MPS86: David MacQueen , Gordon Plotkin , Ravi Sethi, An ideal model for recursive polymorphic types, Information and Control, v.71 n.1-2, p.95-130, Oct/Nov. 1986 [doi>10.1016/S0019-9958(86)80019-5]
• MS89: J.C. Mitchell and P.J. Scott. Typed lambd~ calculus and cartesian closed categories. In Proc. Conf. Computer Science and Logic June 1~-20, 1987, Univ. Colorado Boulder, volume 92 of Contemporary Mathematics, pages 301-316. Amer. Math. Society, 1989.
• RA82: Jonathan A. Rees , Norman I. Adams IV, T: a dialect of Lisp or LAMBDA: The ultimate software tool, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.114-122, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802142]
• Red88: Uday Reddy, Objects as closures: abstract semantics of object-oriented languages, Proceedings of the 1988 ACM conference on LISP and functional programming, p.289-297, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62721]
• Rém89: D. Rémy, Type checking records and variants in a natural extension of ML, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.77-88, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75284]
• Rey84: J.C. Reynolds. Polymorphism is not settheoretic. In Proc. Int. Syrup. on ,%- mantics of Data Types, Sophia-Anlipolis (France), Springer LNCS 173, pages 145-156. Springer-Verlag, t984.
• RP89: John C. Reynolds , Gordon D. Plotkin, On functors expressible in the polymorphic typed lambda calculus, Information and Computation, v.105 n.1, p.1-29, July 1993 [doi>10.1006/inco.1993.1037]
• Sta88: R. Stansifer, Type inference with subtypes, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.88-97, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73568]
• Suz81: Norihisa Suzuki, Inferring types in Smalltalk, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.187-199, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567553]
• US87: David Ungar , Randall B. Smith, Self: The power of simplicity, Conference proceedings on Object-oriented programming systems, languages and applications, p.227-242, October 04-08, 1987, Orlando, Florida, United States
• Wan87: M. Wand. Complete type inferellce for simple objects. In Proc. 2-nd 1EEE Syrup. on Logic in Computer Science, pages 37-44, 1987. Corrigendunl in Prec. 3-rd IEEE Syrup. on Logic an Computer Science, page 132, 1988.
• Wan89: M. Wand, Type inference for record concatenatiOn and multiple inheritance, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.92-97, June 1989, Pacific Grove, California, United States
• Yel89: P.M. Yelland. First steps towards fullyabstract semantics for object-oriented languages. In European Conf. on Object- Orienled Programming, pages 347-367, 1989.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Lambda calculus and related systems

General Terms:
Languages