A theory of overloading

ABSTRACT

We present a minimal extension of the Hindley/Milner system to allow for overloading of identifiers. Our approach relies on a combination of the HM(X) type system framework with Constraint Handling Rules (CHRs). CHRs are a declarative language for writing incremental constraint solvers. CHRs allow us to precisely describe the relationships among overloaded identifiers. Under some sufficient conditions on the CHRs we achieve decidable type inference and the semantic meaning of programs is unambiguous. Our approach allows us to combine open and closed world overloading. We also show how to deal with overlapping definitions.

REFERENCES

• 1: S. Abdennadher. Operational semantics and confluence of constraint propagation rules. In Proc. of CP'97, LNCS 1330, pages 252--266. Springer-Verlag, 1997.
• 2: Slim Abdennadher , Heribert Schütz, CHRv: A Flexible Query Language, Proceedings of the Third International Conference on Flexible Query Answering Systems, p.1-14, May 13-15, 1998
• 3: Lennart Augustsson, Cayenne—a language with dependent types, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.239-250, September 26-29, 1998, Baltimore, Maryland, United States
• 4: Carlos Camarão , Lucília Figueiredo, Type Inference for Overloading without Restrictions, Declarations or Annotations, Proceedings of the 4th Fuji International Symposium on Functional and Logic Programming, p.37-52, November 11-13, 1999
• 5: Kung Chen , Paul Hudak , Martin Odersky, Parametric type classes, Proceedings of the 1992 ACM conference on LISP and functional programming, p.170-181, June 22-24, 1992, San Francisco, California, United States
• 6: Bart Demoen , Maria J. García de la Banda , Warwick Harvey , Kim Marriott , Peter J. Stuckey, An Overview of HAL, Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming, p.174-188, October 11-14, 1999
• 7: T. Frühwirth. Constraint handling rules. In Constraint Programming: Basics and Trends, LNCS 910. Springer-Verlag, 1995.
• 8: T. Frühwirth. A declarative language for constraint systems: Theory and practice of constraint handling rules, 1998. Habilitation.
• 9: T. Frühwirth. Theory and practice of constraint handling rules. Journal of Logic Programming, 37(1--3):95--138, 1998.
• 10: Matthias Neubauer , Peter Thiemann , Martin Gasbichler , Michael Sperber, Functional logic overloading, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.233-244, January 16-18, 2002, Portland, Oregon
• 11: K. Glynn, P. Stuckey, and M. Sulzmann. Type classes and constraint handling rules. First Workshop on Rule-Based Constraint Reasoning and Programming, July 2000. http://xxx.lanl.gov/abs/cs.PL/0006034+.
• 12: M. Hanus. The integration of functions into logic programming: From theory to practice. Journal of Logic Programming, 19&20:583--628, 1994.
• 13: The Mercury language reference manual, 2001. http://www.cs.mu.oz.au/research/mercury/+.
• 14: D. Jeffery, F. Henderson, and Z. Somogyi. Type classes in Mercury. In Proc. of 23rd Australasian Computer Science Conf., pages 128--135. IEEE Press, 2000.
• 15: Mark Philip Jones, Qualified types: theory and practice (ordering relation), 1992
• 16: M. P. Jones. Coherence for qualified types. Research Report YALEU/DCS/RR-989, Yale University, Department of Computer Science, September 1993.
• 17: Mark P. Jones, A system of constructor classes: overloading and implicit higher-order polymorphism, Proceedings of the conference on Functional programming languages and computer architecture, p.52-61, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165190]
• 18: Mark P. Jones, Simplifying and improving qualified types, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.160-169, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224198]
• 19: Mark P. Jones, Type Classes with Functional Dependencies, Proceedings of the 9th European Symposium on Programming Languages and Systems, p.230-244, April 02, 2000
• 20: S. Peyton Jones, M. P. Jones, and E. Meijer. Type classes: an exploration of the design space. In Haskell Workshop, June 1997.
• 21: Stefan Kaes, Parametric Overloading in Polymorphic Programming Languages, Proceedings of the 2nd European Symposium on Programming, p.131-144, March 21-24, 1988
• 22: Jeffrey R. Lewis , John Launchbury , Erik Meijer , Mark B. Shields, Implicit parameters: dynamic scoping with static types, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.108-118, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325708]
• 23: R. Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348--375, Dec 1978.
• 24: T. Nipkow and C. Prehofer. Type reconstruction for type classes. Journal of Functional Programming, 5(2):201--224, 1995.
• 25: Martin Odersky , Martin Sulzmann , Martin Wehr, Type inference with constrained types, Theory and Practice of Object Systems, v.5 n.1, p.35-55, Jan. 1999 [doi>10.1002/(SICI)1096-9942(199901/03)5:1<35::AID-TAPO4>3.0.CO;2-4]
• 26: Martin Odersky , Philip Wadler , Martin Wehr, A second look at overloading, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.135-146, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224195]
• 27: S. Peyton Jones et al. Report on the programming language Haskell 98. http://haskell.org.
• 28: M.J. Plasmeijer and M.C.J.D. van Eekelen. Language report Concurrent Clean. Tech. Report CSI-R9816, University of Nijmegen, June 1998. ftp://ftp.cs.kun.nl/pub/Clean/Clean13/doc/refman13.ps.gz+.
• 29: M. Shields and S. Peyton Jones. Object-oriented overloading for Haskell. In Workshop on Multi-Language Infrastructure and Interoperability, September 2001.
• 30: P. J. Sulzmann and M. Sulzmann. A theory of overloading. Technical report 2002/2, The University of Melbourne, 2002. http://www.cs.mu.oz.au/~sulzmann/chr/+.
• 31: M. Sulzmann and A. Rossberg. A theory of overloading part II: semantics and coherence. Technical report 2002/1, The University of Melbourne, 2002. http://www.cs.mu.oz.au/~sulzmann/chr/+.
• 32: M. Sulzmann, A. Rossberg and J. Wazny. The Chameleon language manual. http://www.cs.mu.oz.au/~sulzmann/chameleon+.
• 33: M. Sulzmann and A. Rossberg. Beyond type classes. Working paper. www.cs.mu.oz.au/~sulzmann/chr/+.
• 34: Martin Franz Sulzmann , Paul Hudak, A general framework for hindley/milner type systems with constraints, 2000
• 35: 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]
• 36: Zhe Yang, Encoding types in ML-like languages, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.289-300, September 26-29, 1998, Baltimore, Maryland, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Polymorphism

  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

Keywords:
constraints, overloading, type classes, type inference