Domains for Logic Programming

We construct Scott domains well suited to use in an abstract implementation of logic programming, and perhaps to the modelling of other first-order data structures. The domain elements, which we call ‘grafts’, are in effect a sort of directed graphs. The approximation order in the domains corresponds to the relation between tuples of terms, “has a substitution instance”; the price to be paid is that one equivalence class of (tuples of) terms under renaming of variables is represented by many grafts. Graft domains come in two flavors—plain and ‘acyclic’—for modelling on an equal footing logic programming without and with the ‘occur check’. The least-fixed-point semantics of logic programming re-emerges gracefully from our development in the form of an assignment to each predicate letter belonging to a logic program of an open subset of a graft domain as its denotation