§5.0  Introduction: Specimen Program  §5.2  Total Computational space  
§5.1  Standard Computational Space 
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

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 subgoals, 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
There is an important practical point which derives from this ordering
to place the simplest or exceptional relations first
For now, let us see what happens when (in a more general language than Prolog) we leave the search strategy undefined.
Looking again at our example program, there is still no alternative to expanding the initial goal ?  a. so as to give the subgoals
?  b, c.
But now, lacking a defined search strategy, we have several choices for our next step
We have encountered nondeterminism, caused either
When constructing a display of the nondeterministic "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 topdown, then leftright)
In this wider context, a program is [potentially] nondeterministic whenever there is a branch in its total computational tree
Nondeterminism can be overcome, but only by defining a search strategy
Note that the use of any defined search strategy prunes 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
But do not confuse nondeterminism 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 