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