Haskell-style Overloading is NP Hard

Volpano, Dennis

dc.contributor.author	Volpano, Dennis
dc.date	May 1994.
dc.date.accessioned	2013-08-20T16:44:14Z
dc.date.available	2013-08-20T16:44:14Z
dc.date.issued	1994-05
dc.identifier.citation	Proceedings 1994 Int'l Conference on Computer Languages, Toulouse, France, pp. 88-94, May 1994.
dc.identifier.uri	https://hdl.handle.net/10945/35271
dc.description	The article of record as published may be found at http://dx.doi.org/	en_US
dc.description.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 problems. 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 1- CS is derivable? Under arbitrary overloading, the problem is undecidable. Haskell limits overloading to a form similar to that proposed by Keas 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.	en_US
dc.rights	This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.	en_US
dc.title	Haskell-style Overloading is NP Hard	en_US
dc.contributor.department	Computer Science (CS)