4
Mathematical Aspects of Logic Programming Semantics
(2) Let X be a non-empty set, and let D denote the set of all pairs (I
+ , I
− ),
where I
+ and I
− are disjoint subsets of X. We define an ordering on D
by (I
+ , I
− ) [ (J
+ , J
− ) if and only if I
+ ⊆ J
+ and I
− ⊆ J
− . Then D
is a domain in which the bottom element is the pair (∅, ∅), the compact
elements of D are the pairs (I
+ , I
− ) in D in which I
+ and I
− are finite
sets, and the maximal elements are the pairs (I
+ , I
− ) which satisfy I
+ ∪
I
− = X. Note that D is not a complete lattice.
(3) Let D denote the set of all partial functions f : N
n → N ordered by graph
inclusion, that is, f [ g if and only if graph(f ) ⊆ graph(g), where f
and g are partial functions. (Thus, f [ g if and only if whenever f (x)
is defined, so is g(x) and f (x) = g(x).) Then D is a domain in which a
partial function f is a compact element if and only if graph(f ) is a finite
set and the bottom element is the empty function. Here, the maximal
elements of D are the total functions. Again, D is not a complete lattice.
1.1.6 Remark Mathematically speaking, the denotational semantics, or
mathematical semantics, approach to the theory of procedural and functional
programming languages is highly involved with providing a satisfactory framework within which to model constructs made in conventional programming
languages. Such frameworks must be closed under the formation of products,
sums, and function spaces and therefore are, simply, Cartesian closed categories. One of the most successful Cartesian closed categories to have arisen
out of these considerations is that of Scott domains,
3 as formulated in Definition 1.1.4. Moreover, most functions and operators encountered within domain
theory are order continuous, see Definition 1.1.7, and therefore the most useful
fixed-point theorem in domain theory is Theorem 1.1.9. On the other hand, as
we shall see in the next chapter and subsequent chapters, a logic program has
a well-defined and mathematically precise meaning inherent in its very nature,
namely, its semantics as a first-order logical theory. In addition, certain important operators arising in logic programming are not monotonic in general due
to the presence of negation, resulting in Theorems 1.1.9 and 1.1.10 often being inapplicable, and this has no direct parallel in conventional programming
language semantics. For these reasons, the semantics of logic programming
languages has developed rather differently from that of procedural programming languages. Nevertheless, we shall study domains in Chapter 4, in the
context of fixed-point theory.
4
If D is a set, A is a subset of D, and f : D → D is a function, then we
denote the image set {f (a) | a ∈ A} of A under f by f (A). We also define
3 See [Scott, 1982b].
4 Our basic references to domain theory are the book [Stoltenberg-Hansen et al., 1994]
and the book chapter [Abramsky and Jung, 1994], but the reader interested in domain
theory may also care to consult the notes of G.D. Plotkin [Plotkin, 1983] and also the
comprehensive treatment to be found in [Gierz et al., 2003].
Mathematical Aspects of Logic Programming Semantics
(2) Let X be a non-empty set, and let D denote the set of all pairs (I
+ , I
− ),
where I
+ and I
− are disjoint subsets of X. We define an ordering on D
by (I
+ , I
− ) [ (J
+ , J
− ) if and only if I
+ ⊆ J
+ and I
− ⊆ J
− . Then D
is a domain in which the bottom element is the pair (∅, ∅), the compact
elements of D are the pairs (I
+ , I
− ) in D in which I
+ and I
− are finite
sets, and the maximal elements are the pairs (I
+ , I
− ) which satisfy I
+ ∪
I
− = X. Note that D is not a complete lattice.
(3) Let D denote the set of all partial functions f : N
n → N ordered by graph
inclusion, that is, f [ g if and only if graph(f ) ⊆ graph(g), where f
and g are partial functions. (Thus, f [ g if and only if whenever f (x)
is defined, so is g(x) and f (x) = g(x).) Then D is a domain in which a
partial function f is a compact element if and only if graph(f ) is a finite
set and the bottom element is the empty function. Here, the maximal
elements of D are the total functions. Again, D is not a complete lattice.
1.1.6 Remark Mathematically speaking, the denotational semantics, or
mathematical semantics, approach to the theory of procedural and functional
programming languages is highly involved with providing a satisfactory framework within which to model constructs made in conventional programming
languages. Such frameworks must be closed under the formation of products,
sums, and function spaces and therefore are, simply, Cartesian closed categories. One of the most successful Cartesian closed categories to have arisen
out of these considerations is that of Scott domains,
3 as formulated in Definition 1.1.4. Moreover, most functions and operators encountered within domain
theory are order continuous, see Definition 1.1.7, and therefore the most useful
fixed-point theorem in domain theory is Theorem 1.1.9. On the other hand, as
we shall see in the next chapter and subsequent chapters, a logic program has
a well-defined and mathematically precise meaning inherent in its very nature,
namely, its semantics as a first-order logical theory. In addition, certain important operators arising in logic programming are not monotonic in general due
to the presence of negation, resulting in Theorems 1.1.9 and 1.1.10 often being inapplicable, and this has no direct parallel in conventional programming
language semantics. For these reasons, the semantics of logic programming
languages has developed rather differently from that of procedural programming languages. Nevertheless, we shall study domains in Chapter 4, in the
context of fixed-point theory.
4
If D is a set, A is a subset of D, and f : D → D is a function, then we
denote the image set {f (a) | a ∈ A} of A under f by f (A). We also define
3 See [Scott, 1982b].
4 Our basic references to domain theory are the book [Stoltenberg-Hansen et al., 1994]
and the book chapter [Abramsky and Jung, 1994], but the reader interested in domain
theory may also care to consult the notes of G.D. Plotkin [Plotkin, 1983] and also the
comprehensive treatment to be found in [Gierz et al., 2003].