Computer Science – Computation and Language
Scientific paper
1995-06-02
Computer Science
Computation and Language
Presented at CLNLP'95. An improved version is available under the name "A Type is a Type is a Type" from the Authors
Scientific paper
We introduce constraints necessary for type checking a higher-order concurrent constraint language, and solve them with an incremental algorithm. Our constraint system extends rational unification by constraints x$\subseteq$ y saying that ``$x$ has at least the structure of $y$'', modelled by a weak instance relation between trees. This notion of instance has been carefully chosen to be weaker than the usual one which renders semi-unification undecidable. Semi-unification has more than once served to link unification problems arising from type inference and those considered in computational linguistics. Just as polymorphic recursion corresponds to subsumption through the semi-unification problem, our type constraint problem corresponds to weak subsumption of feature graphs in linguistics. The decidability problem for \WhatsIt for feature graphs has been settled by D\"orre~\cite{Doerre:WeakSubsumption:94}. \nocite{RuppRosnerJohnson:94} In contrast to D\"orre's, our algorithm is fully incremental and does not refer to finite state automata. Our algorithm also is a lot more flexible. It allows a number of extensions (records, sorts, disjunctive types, type declarations, and others) which make it suitable for type inference of a full-fledged programming language.
Mueller Martin
Niehren Joachim
No associations
LandOfFree
Weak subsumption Constraints for Type Diagnosis: An Incremental Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Weak subsumption Constraints for Type Diagnosis: An Incremental Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Weak subsumption Constraints for Type Diagnosis: An Incremental Algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-611845