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
`X`

to`Y`

if they are**directly**connected, and the journey is a list of just one step`[(X,Y)]`

. - There is a journey from
`X`

to`Y`

if they are**indirectly**connected, that is, if`X`

and`A`

are directly connected, and there is a journey from that`A`

to`Y`

. The journey list of steps from`X`

to`Y`

has`(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 away`b`

→`c`

, and finally steps back`c`

→`b`

. Not as efficient. - The third solution is even less efficient,
`a`

→`b`

,`b`

→`c`

,`c`

→`b`

,`b`

→`c`

, and`c`

→`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.