Type processing by constraint reasoning

Peter J. Stuckey, Martin Sulzmann, Jeremy Wazny

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

8 Citations (Scopus)

Abstract

Herbrand constraint solving or unification has long been understood as an efficient mechanism for type checking and inference for programs using Hindley/Milner types. If we step back from the particular solving mechanisms used for Hindley/Milner types, and understand type operations in terms of constraints we not only give a basis for handling Hindley/Milner extensions, but also gain insight into type reasoning even on pure Hindley/Milner types, particularly for type errors. In this paper we consider typing problems as constraint problems and show which constraint algorithms are required to support various typing questions. We use a light weight constraint reasoning formalism, Constraint Handling Rules, to generate suitable algorithms for many popular extensions to Hindley/Milner types. The algorithms we discuss are all implemented as part of the freely available Chameleon system.

Original languageEnglish
Title of host publicationProgramming Languages and Systems - 4th Asian Symposium, APLAS 2006, Proceedings
PublisherSpringer
Pages1-25
Number of pages25
ISBN (Print)3540489371, 9783540489375
Publication statusPublished - 1 Jan 2006
Externally publishedYes
Event4th Asian Symposium on Programming Languages and Systems, APLAS 2006 - Sydney, Australia
Duration: 8 Nov 200610 Nov 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4279 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th Asian Symposium on Programming Languages and Systems, APLAS 2006
CountryAustralia
CitySydney
Period8/11/0610/11/06

Cite this

Stuckey, P. J., Sulzmann, M., & Wazny, J. (2006). Type processing by constraint reasoning. In Programming Languages and Systems - 4th Asian Symposium, APLAS 2006, Proceedings (pp. 1-25). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4279 LNCS). Springer.