Logic Programs with Equational Type Specifications

by Michael Hanus

Proc. of the 2nd International Conference on Algebraic and Logic Programming (ALP'90), Springer LNCS 463, pp. 70-85, 1990
© Springer-Verlag
Revised and extended version

This paper proposes a framework for logic programming with different type systems. In this framework a typed logic program consists of a type specification and a Horn clause program which is well-typed with respect to the type specification. The type specification defines all types which can be used in the logic program. Relations between types are expressed by equations on the level of types. This permits the specification of many-sorted, order-sorted, polymorphic and polymorphically order-sorted type systems. We present the declarative semantics of our framework and a resolution procedure for typed logic programs. Resolution requires a unification procedure for typed terms which is based on a unification procedure for the type theory. An interesting application is a type system that combines parametric polymorphism with order-sorted typing and permits higher-order logic programming. Moreover, our framework sheds some new light on the role of types in logic programming.

Preprint (PDF) BibTeX-Entry Online