Directional Type Inference for Logic Programs

We follow the set-based approach to directional types proposed by Aiken and Lakshman[1]. Their type checking algorithm works via set constraint solving and is sound and complete for given discriminative types. We characterize directional types in model-theoretic terms. We present an algorithm for inferring directional types. The directional type that we derive from a logic program P is uniformly at least as precise as any discriminative directional type of P , i.e., any directional type out of the class for which the type checking algorithm of Aiken and Lakshman is sound and complete. We improve their algorithm as well as their lower bound and thereby settle the complexity (DEXPTIME-complete) of the corresponding problem. 1 Introduction Directional types form a type system for logic programs which is based on the view of a predicate as a directional procedure which, when applied to a tuple of input terms, generates a tuple of output terms. There is a rich literature on types and dire..