Functional logic overloading

ABSTRACT

Functional logic overloading is a novel approach to user-defined overloading that extends Haskell's concept of type classes in significant ways. Whereas type classes are conceptually predicates on types in standard Haskell, they are type functions in our approach. Thus, we can base type inference on the evaluation of functional logic programs. Functional logic programming provides a solid theoretical foundation for type functions and, at the same time, allows for programmable overloading resolution strategies by choosing different evaluation strategies for functional logic programs. Type inference with type functions is an instance of type inference with constrained types, where the underlying constraint system is defined by a functional logic program. We have designed a variant of Haskell which supports our approach to overloading, and implemented a prototype front-end for the language.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Arvind, editor. Functional Programming Languages and Computer Architecture, Copenhagen, Denmark, June 1993. ACM Press, New York.
• 3: Lennart Augustsson, Implementing Haskell overloading, Proceedings of the conference on Functional programming languages and computer architecture, p.65-73, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165191]
• 4: 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
• 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: Karl Crary , Stephanie Weirich, Flexible type analysis, Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, p.233-248, September 27-29, 1999, Paris, France
• 7: Karl Crary , Stephanie Weirich , Greg Morrisett, Intensional polymorphism in type-erasure semantics, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.301-312, September 26-29, 1998, Baltimore, Maryland, United States
• 8: 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]
• 9: Olivier Danvy, Functional unparsing, Journal of Functional Programming, v.8 n.6, p.621-625, November 1998 [doi>10.1017/S0956796898003104]
• 10: Dominic Duggan , Gordon Cormack , John Ophel, Kinded type inference for parametric overloading, Acta Informatica, v.33 n.1, p.21-68, 1996 [doi>10.1007/s002360050035]
• 11: J. H. Gallier , W. Snyder, Complete sets of transformations for general E-unification, Theoretical Computer Science, v.67 n.2-3, p.203-260, Oct. 1989 [doi>10.1016/0304-3975(89)90004-2]
• 12: M. Gasbichler, M. Neubauer, M. Sperber, and P. Thiemann. Functional logic overloading. Technical Report 163, Institut fur Informatik, University of Freiburg, Germany, Nov. 2001. Available from ftp://ftp.informatik.uni-freiburg.de/documents/ reports/report163/report00163.ps.gz.
• 13: Elio Giovannetti , Giorgio Levi , Corrado Moiso , Catuscia Palamidessi, Kernel-LEAF: a logic plus functional language, Journal of Computer and System Sciences, v.42 n.2, p.139-185, April 1991 [doi>10.1016/0022-0000(91)90009-T]
• 14: K. Glynn, P. Stuckey, and M. Sulzmann. Type classes and constraint handling rules. In First Workshop on Rule-Based Constraint Reasoning and Programming, July 2000.
• 15: Cordelia V. Hall , Kevin Hammond , Simon L. Peyton Jones , Philip Wadler, Type Classes in Haskell, Proceedings of the 5th European Symposium on Programming: Programming Languages and Systems, p.241-256, April 11-13, 1994
• 16: T. Hallgren. Fun with functional dependencies. In Joint Winter Meeting of the Departments of Science and Computer Engineering, Chalmers University of Technology and Goteborg University, Varberg, Sweden, Jan. 2001. http: //www.cs.chalmers.se/hallgren/Papers/wm01.html.
• 17: M. Hanus. On the completeness of residuation. In Proc. of the 1992 Joint International Conference and Symposium on Logic Programming, pages 192-206. MIT Press, 1992.
• 18: M. Hanus. The integration of functions into logic programming: From theory to practice. Journal of Logic Programming, 19,20:583-628, 1994.
• 19: Michael Hanus, A unified computation model for functional and logic programming, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.80-93, January 15-17, 1997, Paris, France [doi>10.1145/263699.263710]
• 20: M. Hanus. Curry - an integrated functional logic language. http: //www.informatik.uni-kiel.de/curry/report.html, June 2000. Version 0.7.1.
• 21: Robert Harper , Greg Morrisett, Compiling polymorphism using intensional type analysis, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.130-141, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199475]
• 22: Ralf Hinze, A new approach to generic functional programming, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.119-132, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325709]
• 23: P. Hudak, editor. International Conference on Functional Programming, Baltimore, USA, Sept. 1998. ACM Press, New York.
• 24: Jean-Marie Hullot, Canonical Forms and Unification, Proceedings of the 5th Conference on Automated Deduction, p.318-334, July 08-11, 1980
• 25: Patrik Jansson , Johan Jeuring, PolyP—a polytypic programming language extension, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.470-482, January 15-17, 1997, Paris, France [doi>10.1145/263699.263763]
• 26: 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]
• 27: Mark P. Jones, Qualified types: theory and practice, Cambridge University Press, New York, NY, 1995
• 28: Mark P. Jones, Functional Programming with Overloading and Higher-Order Polymorphism, Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques-Tutorial Text, p.97-136, May 24-30, 1995
• 29: 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]
• 30: M. P. Jones. Typing Haskell in Haskell. In E. Meijer, editor, Proceedings of the 1999 Haskell Workshop, number UU-CS-1999-28 in Technical Reports, 1999. ftp://ftp.cs. uu.nl/pub/RUU/CS/techreps/CS-1999/1999-28.pdf.
• 31: 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
• 32: Mark P. Jones, First-class polymorphism with type inference, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.483-496, January 15-17, 1997, Paris, France [doi>10.1145/263699.263765]
• 33: Stefan Kaes, Parametric Overloading in Polymorphic Programming Languages, Proceedings of the 2nd European Symposium on Programming, p.131-144, March 21-24, 1988
• 34: R. Kennaway, The specificity rule for lazy pattern-matching in ambiguous term rewrite systems, Proceedings of the third European symposium on programming on ESOP '90, p.256-270, May 1990, Copenhagen, Denmark
• 35: 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]
• 36: S. Marlow, S. Panne, and N. Winstanley. hsparser: The 100% pure Haskell parser, 1998. http://www.pms.informatik.uni-muenchen.de/ mitarbeiter/panne/haskell_libs/hsparser.html.
• 37: C. McBride. Faking it-simulating dependent types in Haskell. http://www.dur.ac.uk/~dcs1ctm/faking.ps, 2001.
• 38: M. Neubauer, P. Thiemann, M. Gasbichler, and M. Sperber. A functional notation for functional dependencies. In R. Hinze, editor, Proceedings of the 2001 Haskell Workshop, 2001. to appear.
• 39: Tobias Nipkow , Christian Prehofer, Type checking type classes, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.409-418, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158698]
• 40: Tobias Nipkow , Gregor Snelting, Type classes and overloading resolution via order-sorted unification, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.1-14, June 1991, Cambridge, Massachusetts, United States
• 41: 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]
• 42: John Peterson , Mark Jones, Implementing type classes, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.227-236, June 21-25, 1993, Albuquerque, New Mexico, United States
• 43: S. Peyton Jones, M. Jones, and E. Meijer. Type classes: An exploration of the design space. In J. Launchbury, editor, Proc. of the Haskell Workshop, Amsterdam, The Netherlands, June 1997. Yale University Research Report YALEU/DCS/RR-1075.
• 44: T. Reps, editor. Proc. 27th Annual ACM Symposium on Principles of Programming Languages, Boston, MA, USA, Jan. 2000. ACM Press.
• 45: Mark Shields , Erik Meijer, Type-indexed rows, Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-275, January 2001, London, United Kingdom
• 46: M. Shields and S. Peyton Jones. Object-oriented style overloading for Haskell. In BABEL '01. First Workshop on Multi-Language Infrastructure and Interoperability, Florence, Italy, Sept. 2001.
• 47: P. A. Subrahmanyam and J.-H. You. FUNLOG: A computational model integrating logic programming and functional programming. In D. DeGroot and G. Lindstrom, editors, Logic Programming: Functions, Relations and Equations. Prentice Hall, Englewood Cliffs, NJ, 1986.
• 48: P. Thiemann and M. Sperber. Program generation with class. In M. Jarke, K. Pasedach, and K. Pohl, editors, Proceedings Informatik'97, Reihe Informatik aktuell, pages 582-592, Aachen, Sept. 1997. Springer-Verlag.
• 49: 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]
• 50: Stephanie Weirich, Encoding Intensional Type Analysis, Proceedings of the 10th European Symposium on Programming Languages and Systems, p.92-106, April 02-06, 2001
• 51: Hongwei Xi , Frank Pfenning, Dependent types in practical programming, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.214-227, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292560]