Accession Number:
ADA495129
Title:
Haskell-style Overloading is NP-hard
Descriptive Note:
Conference paper
Corporate Author:
NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF COMPUTER SCIENCE
Personal Author(s):
Report Date:
1994-05-01
Pagination or Media Count:
8.0
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 assertion CS is derivable Under arbitrary overloading, the problem is undecidable. Haskell limits overloading to a form similar to that proposed by Kaes 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.
Descriptors:
Subject Categories:
- Computer Programming and Software