Domains for Logic Programming (1992)

Ivan Filippenko and F. Lockwood Morris
*Abstract*

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 as 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 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.