52 349 Logic Programming

Chapter 5 - Computational Space & Non-Determinism

§5.0 Introduction: Specimen Program §5.2 Total Computational space
§5.1 Standard Computational Space

Previous Reading: Two Other Requirements

§5.0 Introduction

Let's apply these ideas to an example and see how we might move from a program to the solutions.

For simplicity, we retain Prolog style but we ignore variables and unification.

Consider the following program:

a :- b, c. % 1
b :- d, e. % 2
b :- f. % 3
c. % 4
d :- g. % 5
d :- h. % 6
f. % 7
g. % 8
?- a. % 9
% Omission of rules or facts for
% e, h is deliberate.

§5.1 Standard Computational Space

We will assume that the language used uses the Standard Search Strategy - which of course means that the language could be Prolog.

What possibilities do we have for moving to a solution?

? - b, c.

?- d, e, c.

?- g, e, c.

?- e, c.

Success in tracing a solution to our program only occurs when we reach an empty list of sub-goals, denoted by [ ].

If we proceed through the whole of the program on this basis, and then display the full pattern graphically we obtain the following (which should be read in the usual way, left to right, top to bottom):

Standard Computational Tree

What we have is an ordered trace of all possible computational paths for the program.

The diagram represents the "Standard Computational Tree"

- which is a display of the standard computational space for our given program

It is "standard" because of our choice of the standard search strategy

There is an important practical point which derives from this ordering

For now, let us see what happens when (in a more general language than Prolog) we leave the search strategy undefined.

§5.2 Total Computational Space

Looking again at our example program, there is still no alternative to expanding the initial goal ? - a. so as to give the sub-goals

? - b, c.

But now, lacking a defined search strategy, we have several choices for our next step

We have encountered non-determinism, caused either

When constructing a display of the non-deterministic "Total Computational Space", we must consider all the possibilities

- as in following diagram for the example program

- the diagram is itself unordered, but it has been constructed in an orderly manner (namely, expand top-down, then left-right)

Total Computational Tree

In this wider context, a program is [potentially] non-deterministic whenever there is a branch in its total computational tree

Non-determinism can be overcome, but only by defining a search strategy

Note that the use of any defined search strategy prunes the total computational tree

Note also that no valid solutions are lost by this pruning, only failing paths

But do not confuse non-determinism with the generation of trees of infinite depth

a :- a, b.

There are similar problems in grammar writing (class 52 348) ... and in functional languages such as Scheme and other forms of Lisp!

© Paul Goldfinch 1998 Next Chapter Return to 52 349 Menu