Safe run-time overloading

ABSTRACT

We present a functional language featuring a form of dynamic overloading akin to message passing in object oriented languages. We give a dynamic semantics describing a non-deterministic evaluation, as well as a type discipline (static semantics) supporting type inference. The type system ensures that a well-typed program has a correct execution, unique up to a semantic equivalence relation, and allows this execution to proceed deterministically, while resolving overloading at run-time.

REFERENCES

• BorIng 82: 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]
• CarWeg 86: 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]
• CleDDK 86: Dominique Clément , Thierry Despeyroux , Gilles Kahn , Joëlle Despeyroux, A simple applicative language: mini-ML, Proceedings of the 1986 ACM conference on LISP and functional programming, p.13-27, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319847]
• CooHC 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]
• DamMil 82: Luis Damas , Robin Milner, Principal type-schemes for functional programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-212, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582176]
• DeMGab 87: L.G. DeMichid, R.P. Gabriel: "CLOS Overview", Proceedings of ECOOP 87.
• HudWad 88: P. Hudak, P. Wadler et al.: "Report on the Functional Programming Language ttaskeU, Draft proposed standard", Research report, Yale University, Dec. 88.
• Huet 76: G. Huet: "R~solution d'~quations dans les langages d'ordre 1, 2,..., w", Th~se de doctorat d'~tat, Universit~ Paris 7, 1976.
• Johnson 86: Ralph E. Johnson, Type-checking Smalltalk, Conference proceedings on Object-oriented programming systems, languages and applications, p.315-321, September 29-October 02, 1986, Portland, Oregon, United States
• Kaes 88: Stefan Kaes, Parametric Overloading in Polymorphic Programming Languages, Proceedings of the 2nd European Symposium on Programming, p.131-144, March 21-24, 1988
• Lang 86: B. Lang "The Virtual Tree Processor" Esprit Project GIPE, Third review report,September 1986.
• Liskov 81: Barbara Liskov, CLU Reference Manual, Springer-Verlag New York, Inc., Secaucus, NJ, 1983
• MeyNM 87: Bertrand Meyer , Jean-Marc Nerson , Masanobu Matsuo, EIFFEL: object-oriented design for software engineering, Proc. of the 1st European Software Engineering Conference on ESEC '87, p.221-229, December 1987, Strasbourg, France
• Milner 78: R. Milner: "A Theory of Type Polymorphism in Programming", J. Cornput. Syst. Sci 17 (1978), pp.348-375.
• Lunau 89: C. Pii Lunau: "Separation of Hierarchies in Duo-Talk", Journal of Object- Oriented Programming Julia ug 1989.
• RajLev 89: R.K. Raj, H.M. Levy : "A Compositional Model for Software Reuse", Conf. Proceedings of BCOOP '89.
• Rémy 89: 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]
• SchaCoo 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
• Suzuki 81: 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]
• Tofte 87: M. Torte: "Operntional Semantics and Polymorphic Type Inference", Ph.D. Thesis University of Edinburgh, 1987.
• WadBlo 89: P. Wadler , S. Blott, How to make ad-hoc polymorphism less ad hoc, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-76, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75283]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics
      D.3.2 Language Classifications

          Nouns: ML

  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

General Terms:
Languages, Theory