Haskell-style Overloading is NP Hard
MetadataShow full item record
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.
The article of record as published may be found at http://dx.doi.org/
Showing items related by title, author, creator and subject.
Bull, Bruce James (Monterey, California. Naval Postgraduate School, 1994-03);Interactive programming environment for language offer many advantages over traditional batch-oriented ones, such as immediate static analysis. One form of analysis is type checking, yet type checking in this setting for ...
Volpano, Dennis (1996-01);Smith has proposed an elegant extension of the ML type system for polymorphic functional languages with overloading. Type inference in his system requires solving a satisfiability problem that is undecidable if no restrictions ...
Volpano, Dennis M. (Monterey, California. Naval Postgraduate School, 1993-10); NPS-CS-94-006Proposed extensions of the ML type system to incorporate global overloading include the systems of Kae88, CD091, Smi9l, Kae92, Jon92 and those related to the design of the functional programming language Haskell WaB89, ...