Type Declarations as Subtype Constraints in Logic Programming

Abstract

This paper presents a type system for logic programs that supports parametric polymorphism and subtypes. This system follows most knowledge representation and object-oriented schemes in that subtyping is name-based, i.e., τ1 is considered to be a subtype of τ2 iff it is declared as such. We take this as a fundamental principle in the sense that type declarations have the form of subtype constraints. Types are assigned meaning by viewing such constraints as Horn clauses that, together with a few basic axioms, define a subtype predicate. This technique provides a (least) model for types and, at the same time, a sound and complete proof system for deriving subtypes. Using this proof system, we define well-typedness conditions which ensure that a logic program/query respects a set of predicate types. We prove that these conditions are consistent in the sense that every atom of every resolvent produced during the execution of a well-typed program is consistent with its type.