Peter J. Stuckey
Martin Sulzmann
ABSTRACT
In this paper we illustrate the facilities for type debugging of Haskell programs in the Chameleon programming environment. Chameleon provides an extension to Haskell supporting advanced and programmable type extensions. Chameleon maps the typing problem for a program to a system of constraints each attached to program code that generates the constraints. We use reasoning about constraint satisfiability and implication to find minimal justifications of type errors, and to explain unexpected types that arise. Through an interactive process akin to declarative debugging, a user can track down exactly where a type error occurs. The approach handles Hindley/Milner types with Haskell-style overloading. The Chameleon system provides a full implementation of our flexible type debugging scheme which can be used as a front-end to any existing Haskell system.
- S. Abdennadher. Operational semantics and confluence of constraint propagation rules. In Proc. of CP'97, volume 1330 of LNCS, pages 252--266. Springer-Verlag, 1997.Google Scholar
- M. Beaven and R. Stansifer. Explaining type errors in polymorphic languages. In ACM Letters on Programming Languages, volume 2, pages 17--30, December 1993. Google ScholarDigital Library
- O. Chitil. Compositional explanation of types and algorithmic debugging of type errors. In Proc. of ICFP'01, pages 193--204. ACM Press, 2001. Google ScholarDigital Library
- B. Demoen, M. Garcia de la Banda, and P. J. Stuckey. Type constraint solving for parametric and ad-hoc polymorphism. In Proc. of the 22nd Australian Computer Science Conference, pages 217--228. Springer-Verlag, 1999.Google Scholar
- D. Duggan and F. Bent. Explaining type inference. Science of Computer Programming, 27(1):37--83, 1996. Google ScholarDigital Library
- T. Fruhwirth. Constraint handling rules. In Constraint Programming: Basics and Trends, volume 910 of LNCS. Springer-Verlag, 1995. Google ScholarDigital Library
- M. Garcia de la Banda, P.J. Stuckey, and J. Wazny. Finding all minimal unsatisfiable constraints. In Proc. of PPDP'03. ACM Press, 2003. To appear. Google ScholarDigital Library
- K. Glynn, P. J. Stuckey, and M. Sulzmann. Type classes and constraint handling rules. In Workshop on Rule-Based Constraint Reasoning and Programming, 2000. http://xxx.lanl.gov/abs/cs.PL/0006034.Google Scholar
- C. Haack and J. B. Wells. Type error slicing in implicitly typed, higher-order languages. In Proc. of ESOP'03, volume 2618 of LNCS, pages 284--301. Springer-Verlag, 2003. Google ScholarDigital Library
- Haskell 98 language report. http://research.microsoft.com/Users/simonpj/haskell98-revised/haskell98-report-html/.Google Scholar
- B. Heeren and J. Hage. Parametric type inferencing for Helium. Technical Report UU-CS-2002-035, Utrecht University, 2002.Google Scholar
- B. Heeren, J. Hage, and D. Swierstra. Generalizing Hindley-Milner type inference algorithms. Technical Report UU-CS-2002-031, Utrecht University, 2002.Google Scholar
- Helium home page. http://www.cs.uu.nl/~afie/helium/.Google Scholar
- F. Huch, O. Chitil, and A. Simon. Typeview: a tool for understanding type errors. In M. Mohnen and P. Koopman, editors, Proceedings of 12th International Workshop on Implementation of Functional Languages, pages 63--69. Aachner Informatik-Berichte,, 2000.Google Scholar
- Hugs home page. haskell.org/hugs/.Google Scholar
- M. P. Jones. Coherence for qualified types. Research Report YALEU/DCS/RR-989, Yale University, Department of Computer Science, September 1993.Google Scholar
- O. Lee and K. Yi. A generalized let-polymorphic type inference algorithm. Technical Memorandum ROPAS-2000-5, National Creative Research Center, Korea Advanced Institute of Science and Technology, March 2000.Google Scholar
- K. Marriott and P.J. Stuckey. Programming with Constraints: an Introduction. MIT Press, 1998.Google ScholarCross Ref
- B.J. McAdam. Graphs for recording type information. Technical Report ECS-LFCS-99-415, The University of Edinburgh, 1999.Google Scholar
- B.J. McAdam. Generalising techniques for type debugging. In Trends in Functional Programming, pages 49--57, March 2000. Google ScholarDigital Library
- R. Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348--375, Dec 1978.Google ScholarCross Ref
- 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
- E. Shapiro. Algorithmic Program Debugging. MIT Press, 1983. Google ScholarDigital Library
- P. J. Stuckey and M. Sulzmann. A theory of overloading. In Proc. of ICFP'02, pages 167--178. ACM Press, 2002. Google ScholarDigital Library
- M. Sulzmann. A General Framework for Hindley/Milner Type Systems with Constraints. PhD thesis, Yale University, Department of Computer Science, May 2000. Google ScholarDigital Library
- M. Sulzmann and J. Wazny. Chameleon. http://www.comp.nus.edu.sg/~sulzmann/chameleon.Google Scholar
- P. Wadler and S. Blott. How to make ad-hoc polymorphism less ad-hoc. In Proc. of POPL'89, pages 60--76. ACM Press, 1989. Google Scholar
- M. Wand. Finding the source of type errors. In Proc. of POPL'86, pages 38--43. ACM Press, 1986. Google Scholar
- J. Yang, J. Wells, P. Trinder, and G. Michaelson. Improved type error reporting. In Proceedings of 12th International Workshop on Implementation of Functional Languages, pages 71--86, 2000.Google Scholar
Index Terms
- Interactive type debugging in Haskell
Recommendations
Improving type error diagnosis
Haskell '04: Proceedings of the 2004 ACM SIGPLAN workshop on HaskellWe present a number of methods for providing improved type error reports in the Haskell and Chameleon programming languages. We build upon our previous work [19] where we first introduced the idea of discovering type errors by translating the typing ...
A theory of overloading
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 ...
A theory of overloading
We present a novel approach to allow for overloading of identifiers in the spirit of type classes. 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 ...
Comments