In this final example, we'll see how a meta-interpreter can change the way solutions are found for queries. This can be useful for some particularly challenging problem scenarios.
Prolog's own search strategy is depth-first. It will try to resolve a goal, following all deductions, until it succeeds or fails. A weakness of this strategy is that it can get trapped in an endless search loop, causing it to miss solutions to be found along different search paths.
Here we'll implement a fixed-depth strategy which can help in scenarios where there are such endless search traps.
% Example 20 - Meta-Interpreter With Fixed Depth Search
% maze locations and links
link(a,b). link(b,c). link(a,d).
link(d,e). link(e,f). link(d,g).
link(f,c). link(f,i).
% two rooms are connected if linked
connected(X,Y) :- link(X,Y).
connected(X,Y) :- link(Y,X).
% journey between two locations
journey(X, Y, [(X,Y)]) :- connected(X,Y).
journey(X, Y, J) :- [(X,A)|J1]=J, connected(X,A), journey(A,Y, J1).
% meta-interpreter with fixed depth search
prove(true, _) :- !.
prove(A=B, _) :- !, A=B.
prove((A,B), Depth):- !, prove(A, Depth), prove(B, Depth).
prove(H, Depth) :-
Depth > 0,
NextDepth is Depth-1,
clause(H,B), prove(B, NextDepth).
The example program defines a maze, illustrated below. There are nine rooms, labelled a to i, with links between some of them, but not all of them.
A link between two adjacent rooms is encoded by a property link/2. For example, link(a,b) states that we can walk from a to b in one step. There is no link between rooms e and h, and so there is no link(e,h) listed in the program.
Our challenge is to find journeys between any two distinct locations.
Journeys
Let's define a property journey(X,Y,J) where X is the starting location, Y is the target location, and J is a list of steps to get from X to Y.
The definition is naturally recursive:
- In the simplest case, there is a journey from
XtoYif they are directly connected, and the journey is a list of just one step[(X,Y)]. - There is a journey from
XtoYif they are indirectly connected, that is, ifXandAare directly connected, and there is a journey from thatAtoY. The journey list of steps fromXtoYhas(X,A)as its head.
We have to define a direct connection. Two rooms, X and Y, are directly connected no matter the direction of the link between them. That is, link(X,Y) is a fact, or link(Y,X) is a fact.
It is worth clarifying that J is a list of elements, each of which is a grouping of two adjacent rooms, for example (a,b). So J = [(a,b), (b,c), (c,f)] is a journey from a to f, taken in three steps, a → b, then b → c, and finally c → f.
The following definitions for connected/2 and journey/2 implement these ideas.
% two rooms are connected if linked
connected(X,Y) :- link(X,Y).
connected(X,Y) :- link(Y,X).
% journey between two locations
journey(X, Y, [(X,Y)]) :- connected(X,Y).
journey(X, Y, J) :- [(X,A)|J1]=J, connected(X,A), journey(A,Y, J1).
Basic Queries
Let's run some simple queries to check the basics are working.
?- connected(a,b).
true
false
?- connected(c,b).
true
connected(a,c).
false
Looking back at the maze illustration, we can see prolog has responded correctly to confirm that a and b are directly connected, as are c and b, but not a and c.
The first query connected(a,b) returns true, backtracks and then returns false. We could avoid this inefficient backtracking with a green cut in the definition of connected/2, but we'll tolerate it because we want to keep our meta-interpreter simple by not implementing the cut.
Journey Queries
The journey from a to b is one of the simplest, taking only one step. The query journey(a,b,[(a,b)]) is asking if there is a journey from a to b consisting of one step (a,b).
?- journey(a,b,[(a,b)]).
true
false
Prolog confirms the journey from a to b does indeed consist of one step (a,b).
Let's now ask “which journeys are possible from a to b?”
?- journey(a,b,J).
J = [(a,b)]
J = [(a,b), (b,c), (c,b)]
J = [(a,b), (b,c), (c,b), (b,c), (c,b)]
J = [(a,b), (b,c), (c,b), (b,c), (c,b), (b,c), (c,b)]
J = [(a,b), (b,c), (c,b), (b,c), (c,b), (b,c), (c,b), (b,c), (c,b)]
...
Prolog finds more than one journey is possible between a and b. In fact, we have to abort the query as the solutions appear to be endless.
Let's look more closely at the first few.
- The very first solution has a single step
a→b, clearly the most efficient journey. - The second solution moves
a→b, then steps awayb→c, and finally steps backc→b. Not as efficient. - The third solution is even less efficient,
a→b,b→c,c→b,b→c, andc→b.
We can see all of the further solutions simply add redundant steps b → c, c → b to the journey.
Prolog's search has fallen into a trap. The endless options for journeys which merely add the redundant steps b → c, c → b will prevent prolog from trying other journeys, such as those which start a → d.
A More Interesting Journey
Let's increase the challenge and ask about journeys from a to e. Looking back at the maze we can see there are two direct paths, clockwise a → b, b → c, c → f, f → e, and anti-clockwise a → d, d → e.
Let's see how our prolog program copes.
?- journey(a,e,J).
Stack limit (0.2Gb) exceeded
Stack sizes: local: 0.2Gb, global: 34.9Mb, trail: 11.6Mb
Stack depth: 762,019, last-call: 0%, Choice points: 762,000
Possible non-terminating recursion:
[762,017] journey(b, e, [length:1])
[762,016] journey(c, e, [length:2])
...
It seems this search is too challenging. Prolog has aborted the search after running out of memory.
We know journeys from a to e are possible, and we can ask prolog to confirm two specific journeys.
?- journey(a,e,[(a,b),(b,c),(c,f),(f,e)]).
true
false
?- journey(a,e,[(a,d),(d,e)]).
true
false
Let's see how a meta-interpreter can help.
Fixed Depth Search
How would we, with human brains, respond to being presented with long journeys like J=[(a,b), (b,c), (c,b), (b,c), (c,b), (b,c), (c,b)]? Our intuition would be to discard long journeys as good solutions because looking at the maze illustration suggests, visually, that shorter journeys should be sufficient.
Prolog's solution search strategy doesn't favour shorter solutions. However, with a meta-interpreter, we can gain control over the search strategy and change it. Changing it to only follow deductive paths up to a maximum given depth is fairly easy.
The following is an updated fixed-depth meta-interpreter prove/2.
% meta-interpreter with fixed depth search
prove(true, _) :- !.
prove(A=B, _) :- !, A=B.
prove((A,B), Depth):- !, prove(A, Depth), prove(B, Depth).
prove(H, Depth) :-
write("Depth = "), writeln(Depth),
Depth > 0,
NextDepth is Depth-1,
clause(H,B),
write(H), write(" ← "), writeln(B),
prove(B, NextDepth).
The first thing to notice is that the arity of prove has changed from 1 to 2. The first parameter remains the goal to be proved. The second parameter is the maximum permitted search depth. For example, prove(G, 5) asks prolog to prove the goal G with no more than 5 deductive resolution steps.
The core of the meta-interpreter remains the same as before. The rules to match true and A=B are the same, except for the additional depth parameter. Here the underscore is used for the depth, because the depth isn't used in the rule bodies.
The rule to pick off the first goal from a sequence (A,B) is also the same as before, and the additional depth parameter is simply passed onto the recursive calls to prove A and B.
The final rule prove(H,Depth) is where the maximum depth is enforced. The first condition Depth>0 ensures that the maximum depth has not been reduced to zero. A new variable NextDepth is assigned the arithmetic evaluation of Depth-1, and if the goal H does have a body B, that body is proved using prove(B, NextDepth), that is, with a maximum depth reduced by one.
This meta-interpreter prints out the current depth as well as the current goal and body. This is to help us see what it is doing when we run simple tests. We'll remove this printing when we use it for more complex queries.
For proofs that require longer chains of deduction, the value of NextDepth will reach zero, and the subsequent call to prove(B, 0) will fail because the condition Depth>0 will be enforced. This is how the meta-interpreter fails proofs that require longer chains of deduction.
Testing Fixed-Depth
Let's test our fixed-depth meta-interpreter works as intended.
We know that to prove connected(a,b) requires two deductive steps. First, connected(a,b) is resolved to link(a,b), and second, link(a,b) is resolved to true.
?- prove(connected(a,b),2).
Depth = 2
connected(a,b) ← link(a,b)
Depth = 1
link(a,b) ← true
true
connected(a,b) ← link(b,a)
Depth = 1
false
We can see the meta-interpreter starting with a maximum depth of 2, and reducing it to 1 for the final goal. We can also see the redundant backtracking and retrying of connected(X,Y).
Let's now try the same query but start with a maximum depth of 1.
?- prove(connected(a,b),1).
Depth = 1
connected(a,b) ← link(a,b)
Depth = 0
connected(a,b) ← link(b,a)
Depth = 0
false
The meta-interpreter failed to prove connected(a,b) within 1 deductive step. The printed messages show how the search was stopped before link(a,b) or link(b,a) could be resolved.
Our fixed-depth meta-interpreter seems to work.
Fixed-Depth Journey Search
Let's return to our problematic query journey(a,e,J) and try again with a fixed-depth search.
?- prove(journey(a,e,J), 3).
false
?- prove(journey(a,e,J), 4).
J = [(a,d), (d,e)]
false
We can see that allowing a search depth of 3 is insufficient to find any solutions. However, allowing a depth of 4 does return one solution, a → d, d → e, and it is the shortest journey from a to e.
Success! Our achievement is using a modified search strategy to find solutions where the default prolog strategy fails.
Let's extend the maximum depth.
?- prove(journey(a,e,J), 6).
J = [(a,b), (b,c), (c,f), (f,e)]
J = [(a,b), (b,a), (a,d), (d,e)]
J = [(a,d), (d,e)]
J = [(a,d), (d,e), (e,f), (f,e)]
J = [(a,d), (d,e), (e,d), (d,e)]
J = [(a,d), (d,g), (g,d), (d,e)]
J = [(a,d), (d,a), (a,d), (d,e)]
Our meta-interpreter has found seven solutions, including the shortest clockwise and anti-clockwise journeys.
Key Points
- A weakness of prolog's depth-first strategy for solutions is that it can get trapped in endless search loops.
- A meta-interpreter can enforce a maximum search depth. This avoids getting trapped in endless search loops, but will miss solutions that do require a deeper search.
- Iterative deepening is the technique of starting with a small maximum search depth, then progressively increasing it to reveal further solutions.