Module 4

Non-determinism and recursion


The previous Module used a simple network to show how to write rules to traverse this network. This Module introduces a small change to the network to introduce non-determinism. This allows Prolog's search mechanism to be revealed in greater detail, which in turn allows a closer examination of the technique of recursion.

Breaking the network
The network used in Module 3 was deterministic in the sense that there are no dead ends. However, if there is a break in the network, it is possible to find routes that lead to dead ends. Prolog has a way of recovering from dead ends and finding alternative solutions. Prolog's ability of cope with non-determinism is one of its strengths.

Finding all possible solutions
It follows that if it is possible for Prolog to cope with non-deterministic situations, it is easy for it to deal with situations where there is more than one solution.

Prolog's data structure for non-determinism
Prolog's non-determinism is made possible by the use of a stack data structure to store alternative "paths" (or partial solutions). By the use of the stack, Prolog displays the symptom of backtracking.


Navigation Menu


These Pages are maintained by Dr Peter Hancox

Last updated October 1998