DocumentCode :
1833770
Title :
Haskell-style overloading is NP-hard
Author :
Volpano, Dennis M.
Author_Institution :
Dept. of Comput. Sci., Naval Postgraduate Sch., Monterey, CA, USA
fYear :
1994
fDate :
16-19 May 1994
Firstpage :
88
Lastpage :
94
Abstract :
Extensions of the ML type system, based on constrained type schemes, have been proposed for languages with overloading. Type inference in these systems requires solving the following satisfiability problem. Given a set of type assumptions C over finite types and a type basis A, is there is a substitution S that satisfies C in that A implies that CS is derivable? Under arbitrary overloading, the problem is undecidable. Haskell limits overloading to a form similar to that proposed by Kaes (1988) called parametric overloading. We formally characterize parametric overloading in terms of a regular tree language and prove that although decidable, satisfiability is NP-hard when overloading is parametric
Keywords :
computational complexity; decidability; trees (mathematics); type theory; Haskell-style overloading; ML type system; NP-hard; Type inference; constrained type schemes; decidable; parametric overloading; regular tree language; satisfiability problem; type assumptions; Computer science; Government; Protection;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Languages, 1994., Proceedings of the 1994 International Conference on
Conference_Location :
Toulouse
Print_ISBN :
0-8186-5640-X
Type :
conf
DOI :
10.1109/ICCL.1994.288390
Filename :
288390
Link To Document :
بازگشت