The objective of this paper is to provide Scott domains in which a logic programming (LP) procedure can be regarded as denoting a continuous function. This approach is an alternative to the usual model-theoretic, least fixed point, and operational semantics, which interpret an LP procedure as a predicate among Herbrand terms, that is, a truth-valued function.
The proposed domain elements are rooted, directed, ordered, partially node-labeled graphs (calls “grafts”), which take the place of Herbrand terms. LP procedures, then, are continuous functions on domains of grafts. The approximation (partial) order in the domain is the “has a substitution instance” relation. The notion of “most general common instance” is then the least upper bound in the approximation order.
Term representation in this fashion is many-to-one: many grafts may represent a single term, exhibiting sharing--multiplicity of paths to a node--in different degrees. This allows the simplification of terms with multiple occurrences of variables, which are represented with many paths leading to the same unlabeled node.
The paper is technically self-contained, and researchers in LP and theory of computation will find it worth reading. It also suggests a novel approach to amalgamating LP to functionality. The background needed is standard denotational semantics and Scott’s information systems. The results appear to be original and technically sound.