66
Mathematical Aspects of Logic Programming Semantics
important properties in relation to logic programming semantics, namely, the
well-known Scott topology and a topology, called the Cantor topology by us,
2
which has connections with the Scott topology. Our goal is to establish the
basic facts about these two topologies and to consider continuity of semantic
operators in them. In fact, we deal with continuity in the Scott topology in this
chapter, but postpone our discussion of continuity in the Cantor topology until
Chapter 5. Later on, we will see how the results we establish can be employed
in studying acceptable programs and termination issues, and we will also see
that the topologies we discuss underlie the fixed-point structures we introduce
in later chapters.
In fact, in many ways it is the convergence properties of these topologies
which are most important, as already noted in the Introduction, and therefore
we take convergence as a fundamental notion and base our discussion upon
it. Nevertheless, we quite easily obtain descriptions of the topologies we study
in terms of more familiar notions such as basic open sets. Actually, convergence per se is formalized completely generally via the concept of convergence
spaces, and therefore we take convergence spaces as our starting point. In fact,
we focus mainly on the so-called convergence classes, which form a subclass
of the convergence spaces, because convergence classes correspond to conventional topologies, whereas convergence spaces give more general theories of
convergence than are needed here.
As can be seen from the results of Chapter 2, the notion of order is not
entirely satisfactory as a foundation for logic programming semantics due to
the failure in general of the immediate consequence operator to be monotonic
in the natural order present. However, order can be expressed through convergence, as we show here. Indeed, convergence spaces and convergence classes
are to a considerable extent appropriate structures with which to investigate
semantical questions in computer science in general and in logic programming
in particular.
3.1 Convergence Spaces and Convergence Classes
The theory of convergence can be based either on nets or on filters,
3 and
these two approaches are equivalent in that any result which can be established by the one can equally well be established by the other. We will work
exclusively with nets since they give rather intuitive descriptions of the sort
of conditions we want to consider in logic programming. The facts we need
2 The Cantor topology was introduced in [Batarekh and Subrahmanian, 1989a] and in
[Batarekh and Subrahmanian, 1989b], see also [Batarekh, 1989], under a restriction called
the matching condition and was treated in complete generality in [Seda, 1995].
3 Our basic references to the theory of nets and filters are the books [Kelley, 1975] and
[Willard, 1970].
Mathematical Aspects of Logic Programming Semantics
important properties in relation to logic programming semantics, namely, the
well-known Scott topology and a topology, called the Cantor topology by us,
2
which has connections with the Scott topology. Our goal is to establish the
basic facts about these two topologies and to consider continuity of semantic
operators in them. In fact, we deal with continuity in the Scott topology in this
chapter, but postpone our discussion of continuity in the Cantor topology until
Chapter 5. Later on, we will see how the results we establish can be employed
in studying acceptable programs and termination issues, and we will also see
that the topologies we discuss underlie the fixed-point structures we introduce
in later chapters.
In fact, in many ways it is the convergence properties of these topologies
which are most important, as already noted in the Introduction, and therefore
we take convergence as a fundamental notion and base our discussion upon
it. Nevertheless, we quite easily obtain descriptions of the topologies we study
in terms of more familiar notions such as basic open sets. Actually, convergence per se is formalized completely generally via the concept of convergence
spaces, and therefore we take convergence spaces as our starting point. In fact,
we focus mainly on the so-called convergence classes, which form a subclass
of the convergence spaces, because convergence classes correspond to conventional topologies, whereas convergence spaces give more general theories of
convergence than are needed here.
As can be seen from the results of Chapter 2, the notion of order is not
entirely satisfactory as a foundation for logic programming semantics due to
the failure in general of the immediate consequence operator to be monotonic
in the natural order present. However, order can be expressed through convergence, as we show here. Indeed, convergence spaces and convergence classes
are to a considerable extent appropriate structures with which to investigate
semantical questions in computer science in general and in logic programming
in particular.
3.1 Convergence Spaces and Convergence Classes
The theory of convergence can be based either on nets or on filters,
3 and
these two approaches are equivalent in that any result which can be established by the one can equally well be established by the other. We will work
exclusively with nets since they give rather intuitive descriptions of the sort
of conditions we want to consider in logic programming. The facts we need
2 The Cantor topology was introduced in [Batarekh and Subrahmanian, 1989a] and in
[Batarekh and Subrahmanian, 1989b], see also [Batarekh, 1989], under a restriction called
the matching condition and was treated in complete generality in [Seda, 1995].
3 Our basic references to the theory of nets and filters are the books [Kelley, 1975] and
[Willard, 1970].