1999 · 584 citations · 45 references
ComputingComputer ScienceCompilersProgramming LanguagesSyntaxConstraint ProgrammingConstraint SatisfactionData TypesSpecification LanguagesType CheckingType SystemsConstraint-based Type CheckingDependent TypesHigher-order FunctionsLanguage DesignPolymorphic Type SystemsType ConstraintsType InferenceType Specification
We present an approach to enriching the type system of ML with a restricted form of dependent types, where type index objects are drawn from a constraint domain C, leading to the DML(C) language schema. This allows specification and inference of significantly more precise type information, facilitating program error detection and compiler optimization. A major complication resulting from introducing dependent types is that pure type inference for the enriched system is no longer possible, but we show that type-checking a sufficiently annotated program in DML(C) can be reduced to constraint satisfaction in the constraint domain C. We exhibit the unobtrusiveness of our approach through practical examples and prove that DML(C) is conservative over ML. The main contribution of the paper lies in our language design, including the formulation of type-checking rules which makes the approach practical. To our knowledge, no previous type system for a general purpose programming language such as ML has combined dependent types with features including datatype declarations, higher-order functions, general recursions, let-polymorphism, mutable references, and exceptions. In addition, we have finished a prototype implementation of DML(C) for an integer constraint domain C, where constraints are linear inequalities (Xi and Pfenning 1998).
45
A theory of type polymorphism in programming
Robin Milner · Journal of Computer and System Sciences · 1978 · 2.2K citations · Full text
George C. Necula · 1997 · 1.8K citations
An axiomatic basis for computer programming
C. A. R. Hoare · Communications of the ACM · 1983 · 1.5K citations
Constraint logic programming: a survey
Joxan Jaffar, Michael J. Maher · The Journal of Logic Programming · 1994 · 1.3K citations