A lambda calculus of objects with self-inflicted extension

ABSTRACT

In this paper we investigate, in the context of functional prototype-based languages, objects which might extend themselves upon receiving a message. The possibility for an object of extending its own "self", referred to by Cardelli, as a self-inflicted operation, is novel in the context of typed object-based languages. We present a sound type system for this calculus which guarantees that evaluating a well-typed expression will never yield a message-not-found run-time error. We give several examples which illustrate the increased expressive power of our system with respect to existing calculi of objects. The new type system allows also for a flexible width-subtyping, still permitting sound method override, and a limited form of object extension. The resulting calculus appears to be a good starting point for a rigorous mathematical analysis of class-based languages.

REFERENCES

• 1: Martin Abadi , Luca Cardelli, A Theory of Objects, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 2: G. Bell~. Some Remarks on Lambda Calculus of Objects. Technical report, Dipartimento di Matematica ed Informatica, Universit~ di Udine, 1994.
• 3: Viviana Bono , Michele Bugliesi, Matching Constraints for the Lambda Calculus of Objects, Proceedings of the Third International Conference on Typed Lambda Calculi and Applications, p.46-62, April 02-04, 1997
• 4: Viviana Bono , Michele Bugliesi , Mariangiola Dezani-Ciancaglini , Luigi Liquori, Subtyping Constraints for Incomplete Objects (Extended Abstract), Proceedings of the 7th International Joint Conference CAAP/FASE on Theory and Practice of Software Development, p.465-477, April 14-18, 1997
• 5: Viviana Bono , Michele Bugliesi , Luigi Liquori, A Lambda Calculus of Incomplete Objects, Proceedings of the 21st International Symposium on Mathematical Foundations of Computer Science, p.218-229, September 02-06, 1996
• 6: Viviana Bono , Kathleen Fisher, An Imperative, First-Order Calculus with Object Extension, Proceedings of the 12th European Conference on Object-Oriented Programming, p.462-497, July 20-24, 1998
• 7: Viviana Bono , Luigi Liquori, A Subtyping for the Fisher-Honsell-Mitchell Lambda Calculus of Objects, Selected Papers from the 8th International Workshop on Computer Science Logic, p.16-30, September 25-30, 1994
• 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: Kim B. Bruce , Luca Cardelli , Benjamin C. Pierce, Comparing Object Encodings, Proceedings of the Third International Symposium on Theoretical Aspects of Computer Software, p.415-438, September 23-26, 1997
• 10: K. Bruce, L. Petersen, and A. Fiech. Subtyping Is Not a Good "Match" for Object-Oriented Languages. In Proc. of ECOOP, volume 1241 of Lecture Notes in Computer Science, pages 104-127. Springer-Verlag, 1997.
• 11: K.B. Bruce. A Paradigmatic Object-Oriented Programming Language: Design, Static Typing and Semantics. Journal of Functional Programming, 4(2):127- 206, 1994.
• 12: L. Cardelli. A Language with Distributed Scope. Computing System, 8(1):27-59, 1995.
• 13: Giuseppe Castagna, Covariance and contravariance: conflict without a cause, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.431-447, May 1995 [doi>10.1145/203095.203096]
• 14: Giuseppe Castagna, Object-oriented programming: a unified foundation, Birkhauser Boston Inc., Cambridge, MA, 1997
• 15: Kathleen Shanahan Fisher , John C. Mitchell, Type systems for object-oriented programming languages, 1996
• 16: Kathleen Fisher , Furio Honsell , John C. Mitchell, A lambda calculus of objects and method specialization, Nordic Journal of Computing, v.1 n.1, p.3-37, Spring 1994
• 17: Kathleen Fisher , John C. Mitchell, Notes on Typed Object-Oriented Programming, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.844-885, April 19-22, 1994
• 18: Kathleen Fisher , John C. Mitchell, A Delegation-based Object Calculus with Subtying, Proceedings of the 10th International Symposium on Fundamentals of Computation Theory, p.42-61, August 22-25, 1995
• 19: Kathleen Fisher , John C. Mitchell, On the relationship between classes, objects, and data abstraction, Theory and Practice of Object Systems, v.4 n.1, p.3-25, 1998 [doi>10.1002/(SICI)1096-9942(1998)4:1<3::AID-TAPO2>3.3.CO;2-2]
• 20: L. Liquori. An Extended Theory of Primitive Objects: First Order System. In Proc. of ECOOP, volume 1241 of Lecture Notes in Computer Science, pages 146-169. Springer-Verlag, 1997.
• 21: P. Paladin. Teoremi di Congruenza per Lambda-Calcoli Orientati agli Oggetti. Master's thesis, Dipartimento di Matematica ed Informatica, Universit~ di Udine, 1993. In Italian.
• 22: Gordon Plotkin. A Structural Approach to Operational Semantics. Technical Report DAIMI FN-19, Computer Science Department, Aarhus University, Denmark, 1981.
• 23: Didier Rémy, From Classes to Objects via Subtyping, Proceedings of the 7th European Symposium on Programming: Programming Languages and Systems, p.200-220, March 28-April 04, 1998
• 24: J.G. Riecke and C. Stone. Privacy via Subsumption. In Electronic proceedings of FOOL-98, 1998.
• 25: M. Wand. Complete Type inference for Simple Objects. In Proc. of LICS, pages 37-44. IEEE Press, 1987.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Lambda calculus and related systems

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

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Design, Languages, Performance, Theory, Verification