Matthias Neubauer
Michael Sperber
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.
- 1.A. V. Aho, R. Sethi, and J. D. Ullman. Compilers Principles, Techniques, and Tools. Addison-Wesley, 1986.]] Google Scholar
Digital Library
- 2.Arvind, editor. Functional Programming Languages and Computer Architecture, Copenhagen, Denmark, June 1993. ACM Press, New York.]]Google Scholar
- 3.L. Augustsson. Implementing Haskell overloading. In]] Google ScholarDigital Library
- 4.L. Augustsson. Cayenne-a language with dependent types. In Hudak {23}.]] Google ScholarDigital Library
- 5.K. Chen, P. Hudak, and M. Odersky. Parametric type classes. In Proc. 1992 ACM Conference on Lisp and Functional Programming, pages 170-181, San Francisco, California, USA, June 1992.]] Google ScholarDigital Library
- 6.K. Crary and S. Weirich. Flexible type analysis. In P. Lee, editor, Proc. International Conference on Functional Programming 1999, pages 233-248, Paris, France, Sept. 1999. ACM Press, New York.]] Google ScholarDigital Library
- 7.K. Crary, S. Weirich, and G. Morrisett. Intensional polymorphism in type-erasure semantics. In Hudak {23}, pages 301-312.]] Google ScholarDigital Library
- 8.L. Damas and R. Milner. Principal type-schemes for functional programs. In Proc. 9th Annual ACM Symposium on Principles of Programming Languages, pages 207-212. ACM, 1982.]] Google ScholarDigital Library
- 9.O. Danvy. Functional unparsing. Journal of Functional Programming, 8(6):621-625, Nov. 1998.]] Google ScholarDigital Library
- 10.D. Duggan, G. V. Cormack, and J. Ophel. Kinded type inference for parametric overloading. Acta Inf., 33(1):21-68, 1996.]] Google ScholarDigital Library
- 11.J. H. Gallier and W. Snyder. Complete sets of transformations for general E-unification. Theoretical Comput. Sci., 67((2+3)):203-260, 1989.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 13.E. Giovannetti, G. Levi, C. Moiso, and C. Palamidessi. Kernel-LEAF: A logic plus functional language. Journal of Computer and System Sciences, 42(2):139-185, 1991.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 15.C. Hall, K. Hammond, S. Peyton Jones, and P. Wadler. Type classes in Haskell. In D. Sannella, editor, Proc. 5th European Symposium on Programming, number 788 in Lecture Notes in Computer Science, pages 241-256, Edinburgh, UK, Apr. 1994. Springer-Verlag.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 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.]]Google Scholar
- 18.M. Hanus. The integration of functions into logic programming: From theory to practice. Journal of Logic Programming, 19,20:583-628, 1994.]]Google ScholarCross Ref
- 19.M. Hanus. A unified computation model for functional and logic programming. In Jones {32}, pages 80-93.]] Google ScholarDigital Library
- 20.M. Hanus. Curry - an integrated functional logic language. http: //www.informatik.uni-kiel.de/curry/report.html, June 2000. Version 0.7.1.]]Google Scholar
- 21.R. Harper and G. Morrisett. Compiling polymorphism using intensional type analysis. In Proc. 22nd Annual ACM Symposium on Principles of Programming Languages, pages 130-141, San Francisco, CA, Jan. 1995. ACM Press.]] Google ScholarDigital Library
- 22.R. Hinze. A new approach to generic functional programming. In Reps {44}, pages 119-132.]] Google ScholarDigital Library
- 23.P. Hudak, editor. International Conference on Functional Programming, Baltimore, USA, Sept. 1998. ACM Press, New York.]]Google Scholar
- 24.J.-M. Hullot. Canonical forms and unification. In R. Kowalski, editor, Proceedings of the Fifth International Conference on Automated Deduction (Les Arcs, France), number 87 in Lecture Notes in Computer Science, pages 318-334, Berlin, July 1980. Springer-Verlag.]] Google ScholarDigital Library
- 25.P. Jansson and J. Jeuring. PolyP - a polytypic programming language extension. In Jones {32}, pages 470-482.]] Google ScholarDigital Library
- 26.M. P. Jones. A system of constructor classes: Overloading and implicit higher-order polymorphism. In Arvind {2}, pages 52-61.]] Google ScholarDigital Library
- 27.M. P. Jones. Qualified Types: Theory and Practice. Cambridge University Press, Cambridge, UK, 1994.]] Google ScholarDigital Library
- 28.M. P. Jones. Functional programming with overloading and higher-order polymorphism. In Advanced Functional Programming, volume 925 of Lecture Notes in Computer Science, pages 97-136. Springer-Verlag, May 1995.]] Google ScholarDigital Library
- 29.M. P. Jones. Simplifying and improving qualified types. In S. Peyton Jones, editor, Proc. Functional Programming Languages and Computer Architecture 1995, pages 160-169, La Jolla, CA, June 1995. ACM Press, New York.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 31.M. P. Jones. Type classes with functional dependencies. In G. Smolka, editor, Proc. 9th European Symposium on Programming, number 1782 in Lecture Notes in Computer Science, pages 230-244, Berlin, Germany, Mar. 2000. Springer-Verlag.]] Google ScholarDigital Library
- 32.N. D. Jones, editor. Proc. 24th Annual ACM Symposium on Principles of Programming Languages, Paris, France, Jan. 1997. ACM Press.]] Google ScholarDigital Library
- 33.S. Kaes. Parametric overloading in polymorphic programming languages. In H. Ganzinger, editor, Proc. 2nd European Symposium on Programming 1988, number 300 in Lecture Notes in Computer Science, pages 131-144. Springer-Verlag, 1988.]] Google ScholarDigital Library
- 34.R. Kennaway. The specificity rule for lazy pattern-matching in ambiguous term rewrite systems. In N. D. Jones, editor, Proc. 3rd European Symposium on Programming 1990, number 432 in Lecture Notes in Computer Science, pages 256-270, Copenhagen, Denmark, 1990. Springer-Verlag.]] Google ScholarDigital Library
- 35.J. R. Lewis, J. Launchbury, E. Meijer, and M. B. Shields. Implicit parameters: Dynamic scoping with static types. In Reps {44}, pages 108-118.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 37.C. McBride. Faking it-simulating dependent types in Haskell. http://www.dur.ac.uk/~dcs1ctm/faking.ps, 2001.]]Google Scholar
- 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.]]Google Scholar
- 39.T. Nipkow and C. Prehofer. Type checking type classes. In Proc. 20th Annual ACM Symposium on Principles of Programming Languages, pages 409-418, Charleston, South Carolina, Jan. 1993. ACM Press.]] Google ScholarDigital Library
- 40.T. Nipkow and G. Snelting. Type classes and overloading resolution via order-sorted unification. In J. Hughes, editor, Proc. Functional Programming Languages and Computer Architecture 1991, number 523 in Lecture Notes in Computer Science, pages 1-14, Cambridge, MA, 1991. Springer-Verlag.]] Google ScholarDigital Library
- 41.M. Odersky, M. Sulzmann, and M. Wehr. Type inference with constrained types. Theory and Practice of Object Systems, 5(1):35-55, 1999.]] Google ScholarDigital Library
- 42.J. Peterson and M. Jones. Implementing type classes. In Proc. of the ACM SIGPLAN '93 Conference on Programming Language Design and Implementation, pages 227-236, Albuquerque, New Mexico, June 1993.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 44.T. Reps, editor. Proc. 27th Annual ACM Symposium on Principles of Programming Languages, Boston, MA, USA, Jan. 2000. ACM Press.]]Google Scholar
- 45.M. Shields and E. Meijer. Type-indexed rows. In H. R. Nielson, editor, Proc. 28th Annual ACM Symposium on Principles of Programming Languages, pages 261-275, London, Jan. 2001. ACM Press.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- 49.P. Wadler and S. Blott. How to make ad-hoc polymorphism less ad-hoc. In Proc. 16th Annual ACM Symposium on Principles of Programming Languages, pages 60-76, Austin, Texas, Jan. 1989. ACM Press.]] Google ScholarDigital Library
- 50.S. Weirich. Encoding intensional type analysis. In D. Sands, editor, Proc. 10th European Symposium on Programming, Lecture Notes in Computer Science, Genova, Italy, Apr. 2001. Springer-Verlag.]] Google ScholarDigital Library
- 51.H. Xi and F. Pfenning. Dependent types in practical programming. In A. Aiken, editor, Proc. 26th Annual ACM Symposium on Principles of Programming Languages, pages 214-227, San Antonio, Texas, USA, Jan. 1999. ACM Press.]] Google ScholarDigital Library
- Functional logic overloading
Recommendations
Functional logic overloading
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 ...
Liberal typing for functional logic programs
APLAS'10: Proceedings of the 8th Asian conference on Programming languages and systemsWe propose a new type system for functional logic programming which is more liberal than the classical Damas-Milner usually adopted, but it is also restrictive enough to ensure type soundness. Starting from Damas-Milner typing of expressions we propose ...
Comments