§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:

§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?

• We can expand (9) using (1), to give the new goal

• Since we are using the Standard Search Strategy, we must proceed by investigating b before we can use the simplification of (4), that c is true.

• There are two possibilities for b, using (2) or using (3).

• Applying (2) we get

• Applying to this clause (5), the first of the two possibilities for d, takes us on to

• Applying (8), that g is true, simplifies our goal to

• About which we can do nothing, since in the absence of a rule to the contrary our program must assume that e is false
  • We must backtrack, to the last point where we had the possibility of an alternative computational route

  • that is, to explore the alternative route computational route for d offered by (6)

• this particular computational route has failed

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):

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

• the name has nothing to do with Prolog, except in that Prolog uses the standard search strategy

• the trace is ordered simply because of the ordering in our search strategy

There is an important practical point which derives from this ordering

• Given (as in Prolog) a top-down, left-right search strategy, it is almost always wiser

  to place the simplest or exceptional relations first

• both in terms of clause ordering and in terms of goals within clause bodies.

• We will return to this point when we consider declarative semantics

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

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

• use b: - d, e. which leads us to ? - d, e, c.

• use b :-f. which leads us to ? - f, c.

• evaluate c first (through equation 4) to get ? - b.

We have encountered non-determinism, caused either

• by uncertainty over which of several possibilities to use to expand a sub-goal, or

• by uncertainty over which sub-goal to tackle first

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)

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

- and we can see why unless we have a defined search strategy our logic programs will (start of §4) "probably generate a load of rubbish"

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

• for example, "uniform call activation", defining which sub-goal to tackle first

• one such strategy being to tackle first the left-most goal, using the top-most expansion ... in other words, to use the standard search strategy.

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

- the standard computational tree is simply a sub-tree of the total computational tree

- in our example, only the green coloured paths appear in both diagrams

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

• this appears to conflict with our example tree; but it doesn't!

• the green solution in the standard tree is obtained by applying, in order,
  clauses 1 - 3 - 7 - 4.

• the purple solution below it in the total tree comes from, in order,
  clauses 1 - 3 - 4 - 7

• the purple, bottom solution in the total tree comes from, in order,
  clauses 1 - 4 - 3 - 7

• we are applying the same clauses, but in a different order ... all we are excluding are the purple replications of the solution

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

• by eliminating non-determinism we are not prohibiting trees of infinite depth

• such trees come from unwise use of recursion, for example

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