14 - The Cut For Efficiency

Used carefully, the cut can improve the efficiency of a prolog program.

We'll explore this with a simple example of a property that relates the temperature of water to its state.

% Example 14 - The Cut For Efficiency

% water/2 relates temperature to state
water(Temp, solid) :- Temp =< 0.
water(Temp, liquid) :- Temp > 0, Temp < 100.
water(Temp, gas) :- Temp >= 100.

% h2o/2 uses the cut to be more efficient
h2o(Temp, solid) :- Temp =< 0, !.
h2o(Temp, liquid) :- Temp > 0, Temp < 100, !.
h2o(Temp, gas) :- Temp >= 100. 

The property water(Temp,solid) is true if Temp is less than or equal to 0. The property water(Temp,liquid) is true if Temp is more than 0, and also less than 100. Finally, water(Temp,gas) is true if Temp is more than or equal to 100. 

These three rules simply relate the temperature of water in degrees centigrade to its states. Water at or below 0°C is solid ice, between 0°C and 100°C is liquid, and at or above 100°C it is a gas, steam.

The numerical comparison operators =<, <, >, and >=, are just like most other programming languages. Notice that prolog uses =<, and not <= which looks too much like a logical implication arrow.

Inefficient Solution Search

Let's start with a simple query “is water at -10°C solid?”

?- water(-10, solid).

true
false 

Prolog reports true, confirming that water at -10°C is indeed solid ice. Perhaps surprisingly, prolog asks to search for other answers. Given the go-ahead, prolog returns false, indicating no other answers. 

Let's try another query, this time with a variable, and ask “what is the state of water at 50°C?”

?- water(50, X).

X = liquid
false

Prolog confirms water at 50°C is a liquid. But again, prolog asks to find additional answers. Given the go-ahead, prolog fails to find additional solutions, reporting false. To be clear, prolog isn't telling us X=liquid is false, it is telling us that X=liquid is a valid solution, and that other attempts to satisfy water(50,X) failed.

Why is prolog trying to find additional solutions after it has found one? It is because there are three rules for water and prolog must try each one just in case another one satisfies the query. Prolog doesn't know the additional rules for water won't be satisfied until it tries them.

Because we know water can only be in one state (solid, liquid or gas) we can say that prolog's search for additional solutions after finding one answer is inefficient. To be clear, prolog doesn't know water can only be in one state, so it is doing the right thing testing all of the three rules.

In our small example, there is no real harm from this inefficiency. In more complex projects, it is possible that testing the body of such rules is computationally expensive, and should be avoided where possible.

Efficient Search With The Cut

When one of the water rules is satisfied, we don't want prolog to try any others. This is a natural job for the cut. Remember, the cut commits prolog to the solution is has found at that point in the current rule, and prevents further backtracking across it. That's what we want - for prolog to commit to the water state it has found and not backtrack to check if it is in another state too.

The following are updated rules for a new h2o property, named after the chemical name for water, H₂O.

% h2o/2 uses the cut to be more efficient
h2o(Temp, solid) :- Temp =< 0, !.
h2o(Temp, liquid) :- Temp > 0, Temp < 100, !.
h2o(Temp, gas) :- Temp >= 100. 

A cut has been placed at the end of the rules. If prolog reaches a cut, it means the body of the rule has been satisfied (the state of the water has been confirmed) and no further backtracking is needed. 

Actually, the last rule doesn't have a cut at the end. There is no harm in adding one, but it isn't needed. This is because prolog works through these rules in order, and there are no more rules for h20 to try even if backtracking were enabled.

Let's test this new h2o with the first query again.

?- h2o(-10, solid).

true

This time prolog confirms true and terminates immediately. Let's try the second query.

?- h2o(50, X).

X = liquid

Again, prolog finds one answer and terminates immediately. 

Green Cut, Red Cut

The definitions of water and h2o lead to exactly the same answers to any given query. We say the two programs are logically equivalent, that they have the same logical meaning. The only difference is that h2o/2 is more efficient because it avoids unnecessary backtracking. 

A cut which doesn't change the logical meaning of a program is called a green cut. In contrast, the cuts we saw earlier in happy/1 and meal/2 are red cuts because their presence or absence changes the logical meaning of the program.

If we are going to use cuts, we should try to make them green cuts wherever possible.

Mutually Exclusive Rules

Our water example is an illustration of a more general pattern where green cuts can easily be applied to improve efficiency. 

The rules for water are mutually exclusive. At most, only one rule can be true for a given query. We've seen how adding a cut to the end of each mutually exclusive rule improves efficiency without changing the meaning of the definition. 

The following shows how any property with mutually exclusive rules can have a green cut appended to the end of each rule. 

% property with mutually exclusive rules
property(X,Y,Z) :- goal_1, goal_2, !.
property(X,Y,Z) :- goal_3, !.
property(X,Y,Z) :- goal_4, goal_5, goal_6.

As we've discussed, the final rule doesn't need a cut.

Key Points

• A cut at the end of a rule causes prolog to commit to any solution found up to that point, and prevents searching for more solutions.
• Two programs are logically equivalent, or have the same logical meaning, if they give the same answers to any given query.
• A green cut is a safe use of the cut because its presence or absence does not change logical meaning. 
• A property with mutually exclusive rules can easily benefit from green cuts applied to the end of each rule. The final rule doesn't need a cut as there are no further rules to try even if backtracking were enabled.

13 - Backtracking After The Cut

The cut is sometimes mistakenly thought of as stopping all backtracking in the rule it appears. 

The following example is designed to illustrate which backtracking can happen around a cut.

% Example 13 - The Cut With More Backtracking

% main meal
homemade(pizza). 
homemade(soup). 
homemade(fish).

% dessert
ripe(apple). 
ripe(orange). 
ripe(banana).

% meal has tasty dish and ripe fruit
meal(Main, Fruit) :- homemade(Main), !, ripe(Fruit).

The program establishes some facts and relations about what makes a nice meal. A meal consists of a homemade main dish, and fruit that is ripe. Pizza, soup and fish are homemade dishes. The apple, orange and banana are ripe.

We've placed a cut in the body of the rule defining a meal to explore its effect on backtracking. 

Most General Query

A query where every parameter is a fresh unbound variable is called a most general query. Such queries ask for all possible solutions, and are a good way to test the generality of our prolog definitions. 

Let's issue the most general query for meal/2.

?- meal(Main, Fruit).

Fruit = apple,
Main = pizza

Fruit = orange,
Main = pizza

Fruit = banana,
Main = pizza

Prolog has found three combinations that make a nice meal, pizza and apple, pizza and orange, pizza and banana. None of these has soup or fish as a main meal.

Clearly the cut had an effect on limiting the combinations to these three out of a possible nine. Let's find out how.

Backtracking and Not Backtracking

To find solutions for the query meal(Main,Fruit) prolog uses its definition homemade(Main),!,ripe(Fruit).

Working left to right, the first goal is homemade(Main). This is easy enough to resolve as the database has several facts for homemade dishes. The first is homemade(pizza), so Main=pizza is a candidate solution. 

Having found one potential solution for homemade(Main), prolog then moves right along the definition homemade(Main),!,ripe(Fruit). The next part is the cut. As we know, this always succeeds but has the side-effect of telling prolog to commit to any solutions found up to this point in the rule, and stop any backtracking back across it. That means prolog commits to Main=pizza.

Moving right again, prolog has to find solutions to ripe(Fruit). This is also straightforward because the database lists facts about ripe fruit. Prolog's answer above returns all three options for fruit. This shows that backtracking is enabled for ripe(Fruit). This is permitted because it takes place entirely to the right of the cut. That is, to find different solutions for ripe(Fruit), prolog does not need to backtrack across the cut.

The following search tree illustrates which backtracking is allowed, and which is prevented by the cut.

Key Points

• The most general query has all parameters as unbound variables. 
• Most general queries test the generality of a prolog definition.
• The cut does not prevent backtracking in a rule if it is entirely to the right of it.

12 - Introducing The Cut

There will come a point when we hear about the so-called cut. It is spoken of with words of caution, as if it were a forbidden power capable of great good and great evil.

We'll take our time learning about it, starting with a minimal example.

% Example 12 - The Cut

% who is happy
happy(john). 
happy(jane) :- !. 
happy(jill).

Setting aside the exclamation mark ! for now, this short prolog program creates three facts. John is happy, Jane is happy, and Jill is happy.

Who Is Happy?

Let's start by running some very basic queries to establish a firm and familiar foundation.

?- happy(john).

true

?- happy(jane).

true

?- happy(jill).

true

Everything is familiar, and as expected. The queries confirm John, Jane and Jill are happy.

Let's now ask “who is happy?” in the usual way using a variable.

?- happy(X).

X = john
X = jane

This isn't quite what we expected. Prolog didn't provide X=jill as an answer. It is as if prolog stopped trying to find additional answers after that ! symbol.

The Cut

The exclamation mark ! is called a cut. The following solution search tree illustrates the effect of the cut on our query.

Let's break it down. To find solutions to the query happy(X), prolog tries unifying with rules in its database. 

The first rule is happy(john) and this results in the first solution X=john. Prolog backtracks to the point where X is again unbound and tries to find another solution. 

This time prolog finds the rule happy(jane):-! and successfully unifies with its head. Before it can settle on X=jane as the next solution, the body of the rule needs to be true. That body is simply the cut !. The cut always succeeds, but also has the side-effect of telling prolog to stop any further backtracking. This stops prolog searching for more solutions. This is why prolog doesn't attempt to unify with the rule happy(jill), and why X=jill is not returned as a third solution.

So the effect of a cut is to stop prolog backtracking over it, and commit to whatever parts of a solution it has found up to the point the cut appears in a rule. It is called the cut because it cuts off part of the solution search tree, as illustrated above.

Looking back to our direct querying of facts, prolog did confirm that happy(jill) is true. This tells us the cut only takes effect when prolog is searching for solutions using the backtracking mechanism.

Cut With Caution

Even with this small example, we can see the cut introduces a logical inconsistency.

One the one hand, asking happy(jill) tells us Jill is happy, but on the other hand, asking happy(X) excludes Jill from the list of happy people. 

This breakdown of logical consistency is not ideal, and can be dangerous in higher risk applications. The larger and more complex our programs become, the harder it is to find such logical inconsistencies. Even worse, we may not even be aware inconsistencies are happening.

It is natural to ask why such something as dangerous as the cut even exists at all. We'll see later how the cut can be useful, if used carefully.

Key Points

• The exclamation mark symbol ! is called a cut.
• A cut always succeeds but stops prolog from backtracking over it, preventing prolog from searching for more possible solutions to a query.
• The cut only effects backtracking, which is why a specific query can return a solution, whereas a more general query using a variable might not.
• The cut can cause different, but logically consistent, queries to give logically inconsistent solutions.

11 - Queries That Don't Finish

A milestone on the journey of learning prolog is writing queries that don't complete. In some cases, this is the correct behaviour, but in others, it is undesirable. 

We'll take a first look at this phenomenon using the reversed/2 property we developed earlier.

% Example 11 - Bidirectional Termination

% recursive definition
step([], L2, L2). 
step([H1|T1], X, L2) :- step(T1, X, [H1|L2]).

% convenience property around step/3
reversed(X, Y) :- step(X, Y, []). 

% updated to terminate when first list is a variable
reversed2(X, Y) :- same_length(X,Y), step(X, Y, []).

The reversed(X,Y) property is true if the list Y is the list X but in reverse order. We previously asked “which Y is the reverse of the list [1,2,3]?”

?-  reversed([1, 2, 3], Y).

Y = [3, 2, 1]

Prolog tells us Y=[3,2,1] is a valid answer. In fact, prolog tells us it is the only answer because it doesn't ask to continue searching for more possible answers. The query terminates after the solution is found.

Termination

On several occasions we've pointedly commented that a prolog definition was written well enough for a question to be asked in both directions. For example, our earlier definition of ancestor/2 allows us to ask ancestor(X, sally), as well as ancestor(sally, Y). That is, “who are the ancestors of Sally?”, as well as “who is Sally an ancestor of?” 

?- ancestor(X, sally).

X = martha
X = deirdre
false

?- ancestor(sally, X).

X = jane
false

Prolog reports false when there are no more answers to be found. In both cases, the query terminates after all the answers have been found. 

Non-Termination

Back to our reversed/2 property. Let's query in the other direction by asking “which X, when reversed, is the list [1,2,3]?”

?-  reversed(X,[1, 2, 3]).

X = [3, 2, 1]

...  non-termination ...
** Execution aborted **

Prolog correctly finds X=[3,2,1] as a valid answer. It then asks to find more answers. Given the go-ahead, prolog ends up searching along a never-ending path, which will crash the entire program if left long enough. We have to manually intervene and cancel the query.

This is our first example of non-termination. Non-termination can be problematic because we can't determine whether or not there are more solutions yet to be found. In this particularly simple example, we know there can't be any other lists whose reverse is [1,2,3], but in more sophisticated scenarios we can't be so certain.

Non-Termination Isn't Always Wrong

In some cases, non-termination is the right behaviour. For example, we might define a property of lists such that every item in a list is cat. That definition is satisfied by an infinite set of lists, [cat], [cat, cat], [cat, cat, cat], and so on. It would be logically incorrect for a query asking “which lists satisfy this definition” to terminate.

In other cases, non-termination only happens when queries are made in one direction, as in our example reversed(X,[1,2,3]).

This kind of non-termination doesn't always have to be fixed. It's not unusual to find, even official, prolog properties intended to be used only in one direction. In such cases, the documentation makes clear which parameters are expected to be grounded and which can be left as variables. Because reversed(X,Y) is symmetric in X and Y, it is quite reasonable, and no real inconvenience, to require the first parameter be grounded. 

Fixing Non-Termination

If we do decide to fix non-termination, it is better to apply an additional logical constraint, than try to fix it with a procedural hack. This way, the property retains its logical meaning. This isn't always easy, especially when the non-termination is a direct result of prolog's procedural nature. 

Let's work out why the query reversed(X,[1,2,3]) fails to terminate. We need to remind ourselves of how reversed/2 works. 

Initially, nothing is known about X, and the accumulator starts as an empty list in step(X,Y,[]). With each application of the continuation rule, the accumulator is extended from its head. This extends the length of possible solution for X. When the length of the accumulator reaches the same length as the provided list [1,2,3], the termination rule lets prolog report X=[3,2,1] as an answer. But prolog doesn't stop there. It backtracks and keeps applying the continuation rule to extend the accumulator, in effect, trying to find solutions that are longer in length than [1,2,3]. 

We can prevent this undesirable backtracking by adding a logical constraint which asserts that a list and its reverse have the same length. 

% updated to terminate when first list is a variable
reversed2(X, Y) :- same_length(X,Y), step(X, Y, []).

This new reversed2/2 property uses same_length/2 provided by swi-prolog to assert that X and Y have the same length. Note that it needs to be placed before the recursive step/3 to ensure that X is created with a fixed length, albeit with currently unknown values.

?- reversed2(X,[1, 2, 3]).

X = [3, 2, 1]

This time the query returns the single correct answer and terminates immediately.

It may seem obvious that X and Y are of the same length, but it wasn't obvious that it needed asserting. Lots of thinking to make a small change is the norm when working in declarative and logic languages like prolog.

samelength/2

If same_length/2 isn't provided by your prolog, you can easily create your own, as follows.

% samelength/2 if same_length/2 isn't provided
samelength([], []). 
samelength([_H1|T1], [_H2|T2]) :- samelength(T1, T2).

It's a good idea to check you can read and understand this particularly simple recursive definition.

Testing For Termination

Imagine we want to test whether a query, let's call it q, terminates. 

We could run the query and manually prompt prolog to keep searching for more solutions until it tells us there are no more to be found. Ten prompts would be inconvenient. A hundred prompts would be impractical. Some queries might require millions of prompts.

Is there a way to exhaust the search for all possible solutions without manual prompting? Have a look at the following.

?- q, fail.

The fail is a goal that always fails. We could have used something like 1=2, which also always fails, but fail is easier to read and understand. 

Prolog works left to right, so it will first try to find a solution that satisfies the goal q. Having done this, it will encounter fail, which causes the query to fail, as if the solution found for the first part q did not satisfy the second part. This causes prolog to backtrack and try to find another solution for q. That second solution, if there is one, will be seen as unsatisfactory too because prolog will encounter fail again. This will repeat for all possible solutions to q. The test q,fail will terminate once all the possible solutions for q have been found.

So, if the test q,fail terminates, we know the query q also terminates. It is possible that q takes a long time to exhaust, and so the test appears not to terminate. This is why we can't say q doesn't terminate if the test is not observed to terminate.

Let's test if reversed2(X,[1,2,3]) terminates.

?- reversed2(X,[1,2,3]), fail.

false

The test terminates, confirming reversed2(X,[1,2,3]) does terminate. Prolog's reply false is not wrong, it is what we expect from a test that fails every solution to the goal being tested.

Key Points

• Non-termination happens when prolog follows an unending search path trying to resolve a query.
• Not all non-termination is wrong. Some queries should, logically, have an infinite number of answers,
• Some non-termination depends on which query parameters are ungrounded variables. It is not uncommon for prolog properties to require specific parameters to be grounded.
• Wherever possible, fixing undesirable non-termination should be done by adding logical constraints to a definition.
• We can test whether a query q does terminate. If q,fail terminates, then we can say q terminates. 
• If the test q,fail doesn't appear to terminate, we can't conclude definitively that q doesn't terminate.

10 - Recursion With Arithmetic

Prolog isn't designed for numeric computation, but sometimes simple calculations are unavoidable. Here we'll demonstrate prolog's ability to do arithmetic as well as explain some caveats.

% Example 10 - Arithmetic

% length of a list
len([], 0). 
len([_H|T], L) :- len(T, M), L is M+1.

The example program defines a property len/2 between a list and the length of that list. Before we can discuss it, we need to learn about arithmetic in prolog.

Simple Arithmetic

In most programming languages a statement like X=2+3 would result in the variable X being assigned the value 5. This is not the case in prolog because the symbol = means unify, not assign.

?- X=2+3.

X = 2+3

The variable X becomes 2+3, not 5. 

To nudge prolog to actually carry out an arithmetic calculation we replace = with is. 

?- X is 2+3.

X = 5

Different prolog implementations will differ in what kinds of numeric calculation they support. Some will support floating point calculations, like 2.3+5.1=7.4, and some will even support rational number calculations, like 1+1/3=4/3. Our own focus here is logic programming and simple calculations with whole numbers, also called integers, is sufficient.

Calculate With Caution

Prolog's ability to do numerical calculation should be used with care. Let's see why.

?- X=3, Y is X+2.

X = 3,
Y = 5

Prolog works left to right so the first thing it tries is the unification X=3. This leaves X with the value 3. After that it executes Y is X+2. To do that it needs to evaluate X+2. This is possible because X currently holds the value 3, so Y is given the value 5. The end result is the same as if Y were unified with 5.

Let's now swap the order of the query.

?- Y is X+2, X=3.

Arguments are not sufficiently instantiated

Logically this query is equivalent to the previous one, but procedurally it is different. Prolog first tries to execute Y is X+2, but at this point the value of X is not known, that is, X is unbound. Prolog throws an error. 

Prolog has done two things that are atypical. First, it didn't fail the query in the usual way which allows backtracking. The entire prolog program itself is stopped, arguably an overdramatic response. Second, prolog did not assign an internal variable to Y which would have left open the possibility of a value being found for it later. 

So we must take additional care when using numerical calculation in prolog. We must make sure that any variables used in an arithmetic expression are grounded at the time it is evaluated. 

Length Of A List

We can now think about calculating the length of a list. As always, it is a good habit to first explore the problem visually, with pen and paper, before trying to write prolog code. A first attempt might be as follows.

• The length of a list is calculated by visiting each item in a list, in order, incrementing a counter as we proceed.

Remembering that prolog only provides the [H|T] construct to get at the content of lists, we need an approach using heads and tails.

• The length of a list is one more than the length of its tail.

We can now write this as a recursive definition.

• Termination - length of an empty list is 0.
• Continuation - length of a list is 1 plus the length of its tail.

We can see the continuation rule performs its key job of reducing the size of the problem by one step.

len/2

Let's now look at the definition of the property len(List, L), which is true if L is the length of the given List. 

len([], 0). 
len([_H|T], L) :- len(T, M), L is M+1.

The first rule len([],0) is the familiar termination rule, which says the length of an empty list is 0. 

The second rule is the continuation rule which relates the length of a list with the length of its tail. We can see the length of the given list is unified with L, the length of its tail is unified with M, and the two are related by the arithmetic relation L is M+1. Logically, this is true, but we also need to understand how it works procedurally. This is best done with an example.

?- len([a,b,c], L). 

L=3

• len([a,b,c], L) is true if len([b,c], _M1) is true, and L is _M1+1.
• len([b,c], _M1) is true if len([c], _M2) is true, and _M1 is _M2+1.
• len([c], _M2) is true if len([], _M3) is true, and _M2 is _M3+1.
• len([], 0) is true by the termination rule, which means _M3=0.

Prolog can now calculate _M2 is _M3+1, leaving _M2=1. Similarly, _M1 is _M2+1 leaving _M1=2. Finally, L is _M1+1, leaving L=3, the length of the given list. 

Remember that prolog creates its own randomly chosen names for the internal variables, which we've called _M1, _M2 and _M3 for clarity.

Depth-First Resolution

You may be asking why the continuation rule doesn't cause the prolog program to dramatically stop because the variables L and M don't have values at the time this rule is first executed.

Remember that prolog works left to right along the parts of a rule, and it doesn't move right until it has completed the part it is working on. 

• To complete working on the first part len([b,c], _M1) it needs to apply the continuation rule again. 
• That rule has a first part len([c], _M2), and itself requires applying the continuation rule again. 
• The first part of that invocation is len([],_M3) which matches the termination rule. 

We can see why this method of searching for solutions, or resolving a rule, is called depth-first. Let's continue.

• The termination rule tells us _M3=0, which allows the calling continuation rule to complete, len([],0) is true and _M2 is _M3+1, leaving _M2=1.
• This allows the calling continuation rule to complete, len([c],1) is true and _M1 is _M2+1, leaving _M1=2.
• Finally, this allows the calling continuation rule to complete, len([b,c],2) is true and L is _M1+1, leaving L=3, the length of the given list [a,b,c].

Although this breakdown is quite detailed, it is beneficial to work through it once to understand how the query is executed, and to see in detail why the variables in the arithmetic expression are actually grounded when it is executed. 

Broken len/2

It is useful to see an incorrectly structured continuation rule. The following definition for len/2 has the two parts of the continuation rule swapped.

% broken version of len/2 continuation rule
len([_H|T], L) :- L is M+1,len(T, M).

Logically the continuation rule is the same as before, but procedurally it is different. The first part of the rule's body is L is M+1, and this will always cause the prolog program to stop because both L and M are ungrounded when the first part of the continuation rule is executed.

?- len([a,b,c], L). 

Arguments are not sufficiently instantiated

Even if we supply a value for L in the query, for example by asking “the length of [a,b,c] is 3?”, the variable M is ungrounded.

?- len([a,b,c], 3). 

Arguments are not sufficiently instantiated

Key Points

• The = symbol means unify, not assign. X=2+3 leaves X as 2+3.
• The is operator is used to assign the result of evaluating an arithmetic expression. X is 2+3 leaves X as 5.
• All variables in an arithmetic expression must have values assigned when an evaluation happens.
• If there are unbound variables at evaluation then the entire prolog program is stopped. This is not the usual prolog failure which results in backtracking or a false response.
• Prolog's strategy for executing multi-part rules is depth-first, then left to right. Understanding this is particularly important when writing recursive definitions.

9 - Recursion With An Accumulator

In this example we'll introduce the technique of recursion with an accumulator. We'll also walk through fixing a bug aided by tracing.

% Example 09 - Recursion With An Accumulator

% recursive definition
step([], L2, L2). 
step([H1|T1], Y, L2) :- step(T1, Y, [H1|L2]).

% convenience property around step
reversed(X, Y) :- step(X, Y, []).

The task of reversing a list, for example from [a,b,c] to [c,b,a], appears trivial. In many programming languages, there is either an instruction for doing this, or it is easy enough to work backwards along a list. In prolog, the only built in support for working with lists is the [H|T] construct which allows us to split the head from the rest of a list. Can we use this to reverse a list?

Reversing A List

The following diagram shows how we can grow a list L2 to be the reverse of a list L1 by taking the head of L1 at each step of a repeated process.

The list L2 starts empty and, with each step, grows towards the answer we want. The list L2 is an example of an accumulator.

Let's see how we can do this in prolog. We know how to get the head of a given list. Unifying L1 with [H|T] leaves H as the head of that list, as long as it is not empty. 

How do we add that item H to be the new head of an existing list? We use the construct [H|T] again. If we unify L2 with [H|L] then L2 is L with H added to it as a new head. 

Let's try it. The following uses the [H|T] construct to extend the list [1,4,1,5,9] with a new head 3 to give [3,1,4,1,5,9].

? - L2 = [3 | [1,4,1,5,9]].

L2 = [3, 1, 4, 1, 5, 9]

Recursive Definition

The diagram shows visually how, at each step, the size of the problem is reduced by one. This is a common feature of recursive systems. Step 1 reduces the length of the list L1 by one, and increases the length of the second list L2 by one. Step 2 does the same.

We should recognise the list L2 is not the reverse of the initial L1 until the end of the process. As such, we should avoid calling the property that relates L1 and L2 at each step reverse. Let's call it step.

Let's see if we can write a continuation rule.

• Continuation - the step property between (L1) and (L2) is true if the step property between (L1 without its head H) and (L2 extended with a new head H) is true.

If we keep applying this rule, the list L1 will keep reducing in length by one, and the list L2 will keep growing in length by one. It's clear our termination rule will need to deal with the case when L1 is empty.

• Termination - the step property between (an empty list) and (a list L2) is true.

From step/2 To step/3

Let's try turning this recursive definition into prolog code.

step([],L2). 
step([H1|T1], L2) :- step(T1, [H1|L2]).

Now let's try asking “which X is the reverse of [1,2,3]?”

?- step([1,2,3], X).

true

This didn't give us X=[3,2,1]. Let's find out what happened by tracing the query.

?- trace, step([1,2,3], X).

  Call:step([1, 2, 3],_4852)
  Call:step([2, 3],[1|_494])
  Call:step([3],[2, 1|_494])
  Call:step([],[3, 2, 1|_494])
  Exit:step([],[3, 2, 1|_494])
  Exit:step([3],[2, 1|_494])
  Exit:step([2, 3],[1|_494])
  Exit:step([1, 2, 3],_494)
true

We can see that at each step, the first list is being reduced from its head, and the second list is being extended from the front with the head from the first list. We can also see the second list starts as an anonymous variable. We should have initiated the second list as an empty list [].

Let's try again.

?- trace, step([1,2,3], []).

  Call:step([1, 2, 3],[])
  Call:step([2, 3],[1])
  Call:step([3],[2, 1])
  Call:step([],[3, 2, 1])
  Exit:step([],[3, 2, 1])
  Exit:step([3],[2, 1])
  Exit:step([2, 3],[1])
  Exit:step([1, 2, 3],[])
true

This time the second list correctly starts empty [] and grows to [3,2,1] as expected. 

The next challenge is working out why prolog is merely reporting back true, and not giving us the reversed second list. The main query step([1,2,3],[]) has no variable for prolog to try to find a value for. Prolog is merely being asked whether the property step is true or not. If we think about it, the property will always be true for a given list L1 of finite length, because the continuation rule can be applied a finite number of times and then the termination rule always succeeds. 

For prolog to give us an answer, our query needs to contain an unbound variable. That variable needs to be passed through the continuation rule, and only bound to the fully reversed list in the termination rule. This is a common pattern for recursion with an accumulator.

We see this idea in the following rules for step/3, which now has an arity of 3.

step([],L2,L2). 
step([H1|T1], X, L2) :- step(T1, X,[H1|L2]).

The variable X is passed through the continuation rule unchanged, and is only bound to the second list L2 in the termination rule. The termination rule step([],L2,L2) is the concise form for the longer step([],X,L2):-X=L2.

Let's check this step/3 works as expected.

?-  step([1,2,3], X, []).

X = [3, 2, 1]

reversed/2 Wraps step/3

If we're writing prolog code for others to use, we don't want to give them step/3, which takes one more parameter than really required, and a burdensome requirement to initialise the accumulator with an empty list [].

We can write a more intuitive reversed/2 property which wraps step/3 and hides of the implementation detail of initialising the accumulator as an empty list.

% convenience property around step/3
reversed(X, Y) :- step(X, Y, []).

This is much more intuitive. The property reversed(X,Y) is true if the list Y is the reverse of the list X. Let's try it.

?-  reversed([1, 2, 3],Y).

Y = [3, 2, 1]

Key Points

• The construct [H|T] can be used to extend a list with a new head. For example, L2=[H|L1] leaves L2 as the list L1 extended with a new head H.
• Some problems are solved by growing the solution through the repeated application of a process. The growing solution is called an accumulator.
• A common pattern is to pass a variable from the query, through the continuation rule, and only unify it with the accumulator in the termination rule.
• It is common to wrap a rule that uses an accumulator with a simpler rule that hides the initialisation of the accumulator.

8 - Recursion With Lists

With this example we'll practice the thinking required to develop a recursive definition. We'll also learn more about working with lists.

% Example 08 - Recursion With Lists

% are two lists the same?
same([],[]). 
same([H1|T1],[H2|T2]) :- H1=H2, same(T1,T2).

The example program defines a property same/2 which is only true if two lists, supplied as parameters, are the same. 

Before we can understand the code, we need to learn a little more about lists.

Working With Lists

Let's remind ourselves of prolog lists as a collection of things, for example [a,b,c]. The order of things in a list matters, so [a,b,c] is not the same as [c,b,a]. Repetition matters too, so [a,b,c] is not the same as [a,b,c,c].

If we want to work with the content of a list, we can unify it with variables. For example, [X,Y,Z]=[1,2,3] leaves X=1, Y=2 and Z=3. If we're only interested in the second item, we can use [_X,Y,_Z]=[1,2,3] which only reports Y=2. 

?- [_X,Y,_Z] = [1,2,3].

Y = 2

The underscores tell prolog that we're not interested the result of unifying _X and _Z. We can be even more frugal and just use underscores [_,Y,_]=[1,2,3].

?- [_,Y,_] = [1,2,3].

Y = 2

This only works if we know the length of the lists ahead of writing our code. If a list only has two things in it, then [X,Y,Z]=[1,2] will fail, as will [_,Y,_]=[1,2].

To work with lists of any length, prolog uses a special construct of the form [H|T]. The variable H unifies with the first thing in the list, the head, and the variable T unifies with the rest of the list, the tail. 

Let's look at an example.

?- [H|T] = [1,2,3].

H = 1
T = [2,3]

We can see H takes the value of the first item of the list [1,2,3], and T takes on the value [2,3], the rest of the list. 

Notice that T is a list, and this will always be the case. If the given list has only one item, then T will be the empty list.

?- [H|T] = [1].

H = 1
T = []

Unification with [H|T] only fails if the given list is empty.

?- [H|T] = [].

false

The following table presents the results of [H|T] unifying with an illustrative selection of lists.

[H|T]	H	T
[1,2,3]	1	[2,3]
[1,2,3,4]	1	[2,3,4]
[1,2]	1	[2]
[1]	1	[]
[]	fails
[[1], 2,3]	[1]	[2,3]
[[a,b,c], [d,e],[f,g]]	[a,b,c]	[[d,e],[f,g]]

The last two examples show that if the first item of the given list is itself a list, then H becomes that list.

We're now ready to explore our recursion example.

Are Two Lists The Same?

Let's think about what it means for two lists to be the same. If we explore some examples with a pen and paper, we'll likely make the following observation.

• Two lists are the same if the first items match, the second items match, the third items match, ... and so on until the end of the lists.

Let's see if we can reformulate this in terms of list heads and tails.

• Two lists are the same if their heads are the same, and their tails are the same too.

We're almost there. We can write this as the termination and continuation rules of a recursive definition.

• Termination - Two empty lists are the same.
• Continuation - Two lists are the same if their heads are the same, and their tails are the same.

The continuation rule needs to reduce the problem by one step. It does this by defining the similarity of two lists in terms of the similarity of their tails, which are shortener by one. Repeated application of the continuation rule will eventually lead to empty lists. This is when we need the termination rule to complete our definition.

same/2

The program defines a property same/2 with two rules.

same([],[]). 
same([H1|T1],[H2|T2]) :- H1=H2, same(T1,T2).

The first rule same([],[]) is the termination rule we just defined stating that two empty lists are the same.

The second rule is the continuation rule which says that two lists are the same if their heads are the same, and if their tails are the same. The rule head same([H1|T1],[H2|T2]) looks complicated so let's break it down. We could have written the head as same(L1, L2) where L1 and L2 are the given lists. We would then have to unify L1 with [H1|T1], and L2 with [H2|T2], in the body of the rule as follows.

same([],[]). 
same(L1, L2) :- L1=[H1|T1], L2=[H2|T2],H1=H2, same(T1,T2).

Putting [H1|T1] and [H2|T2] into the head immediately unifies the variables H1, H2, T1 and T2 with the heads and tails of the given lists. Logically the two approaches are the same. This way requires less code and is actually clearer once we get accustomed to how prolog is written.

The remainder of the rule's body asserts that the two heads are the same H1=H2, and that the tails are the same same(T1,T2).

The following five worked examples let us test same/2, and practise our understanding of recursion, unification, and prolog lists.

Example 1 - Equal Lists

Let's check same/2 confirms [1,2,3] and [1,2,3] are the same.

?- same([1,2,3],[1,2,3])

true

Let's talk through how this works.

• same([1,2,3],[1,2,3]) is true if the heads are the same 1=1, and same([2,3],[2,3]) is true.
• same([2,3],[2,3]) is true if the heads are the same 2=2, and same([3],[3]) is true.
• same([3],[3]) is true if the heads are the same 3=3, and same([],[]) is true. 
• same([],[]) is true by the termination rule.

Example 2 - Unequal Lists

Let's check same/2 confirms [1,2,3] and [1,2,4] are not the same.

?- same([1,2,3],[1,2,4])

false

Let's talk through this example.

• same([1,2,3],[1,2,4]) is true if the heads are the same 1=1, and same([2,3],[2,4]) is true.
• same([2,3],[2,4]) is true if the heads are the same 2=2, and same([3],[4]) is true.
• same([3],[4]) is true if the heads are the same 3=4, and same([],[]) is true. This fails because the heads are not the same.

Example 3 - Lists of Different Length

Let's check same/2 correctly handles lists of different length.

?- same([1,2,3],[1,2,3,4])

false

Let's break it down.

• same([1,2,3],[1,2,3,4]) is true if the heads are the same 1=1, and same([2,3],[2,3,4]) is true.
• same([2,3],[2,3,4]) is true if the heads are the same 2=2, and same([3],[3,4]) is true.
• same([3],[3,4]) is true if the heads are the same 3=3, and same([],[4]) is true. 
• same([],[4]) fails because it doesn't unify with any rule's head. It doesn't unify with the continuation rule because the first parameter [] doesn't unify with [H1|T1].

Example 4 - Lists With Variables

The definition for same/2 is good enough for us to use variables in our queries. In this example, we're asking “what values of A and B make [A,2,3] and [1,B,3] the same?”

?- same([A,2,3], [1,B,3]).

A = 1,
B = 2

Let's talk through this example.

• same([A,2,3],[1,B,3]) is true if the heads are the same A=1, and same([2,3],[B,3]) is true. This gives us A=1.
• same([2,3],[B,3]) is true if the heads are the same 2=B, and same([3],[3]) is true. This gives us B=2.
• A=1 and B=3 are only candidate solutions at this stage. If we continue the recursion and find it fails, we then can't say A=1 and B=3 are valid solutions.
• same([3],[3]) is true if the heads are the same 3=3, and same([],[]) is true. 
• same([],[]) is true by the termination rule.

Example 5 - List As Variable

A more interesting query is to ask “which X is the same as [1,2,3]?”

?- same([1,2,3], X).

X = [1,2,3]

The workings of this example are a little more involved, requiring us to track internal variables. Take your time to work through the following. 

• same([1,2,3],X) is true if the heads are the same 1=_H2, and same([2,3],_T2) is true, where _H2 is the head of X, and _T2 is the tail of X.
• same([2,3],_T2) is true if the heads are the same 2=_H3, and same([3],_T3) is true, where _H3 is the head of _T2, and _T3 is the tail of _T2.
• same([3],_T3) is true if the heads are the same 3=_H4, and same([],_T4) is true, where _H4 is the head of _T3, and _T4 is the tail of _T3.
• same([],_T4) is true by the termination rule if []=_T4.

This is enough information for prolog to build X.

• 1=_H2, _H2 is the head of X, and _T2 is the tail of X, so X=[1,_T2].
• 2=_H3, _H3 is the head of _T2, and _T3 is the tail of _T2, so X=[1,2,_T3].
• 3=_H4, _H4 is the head of _T3, and _T4 is the tail of _T3, so X=[1,2,3,_T4].
• []=_T4, so X=[1,2,3].

There is a lot going on here! The first phase is establishing the values of the internal variables and how they are related. The second phase is putting the information together to build X.

Prolog does all this work, normally unseen by us, even for seemingly innocent queries. It isn't necessary to think at this level of detail for most prolog programming, but it is important to have followed a few examples and understood the underlying mechanisms so that we can write better prolog, and more easily find bugs in code that isn't working as we want.

Key Points

• Prolog's built in mechanism for working with the content of arbitrary lists is the construct [H|T] which unifies H with a list's head (the first item), and T with the list's tail (the rest of the list).
• [H|T] fails to unify with an empty list. 
• When [H|T] does unify with a list, T is always a list.
• When [H|T] is used in the head of a rule, the variables H and T are immediately unified with the list supplied as a parameter.
• Prefixing a variable name with an underscore, like _X, tells prolog not to report its value. An underscore _ on its own has the same effect, however multiple uses of _ in a prolog rule don't refer to the same variable.

7 - Introducing Recursion

Recursion is an important technique in many programming languages, especially declarative languages like prolog. It enables elegant and concise ways to describe and solve problems. 

Recursion is sometimes perceived as difficult, so we'll use this example to introduce it gently.

% Example 07 - Introducing Recursion

% parent facts
parent(john, jane). 
parent(john, james). 
parent(sally, jane). 
parent(martha, sally). 
parent(deirdre, martha).

% grandparent
grandparent(X, Y) :- parent(X, A), parent(A,Y).

% ancestor recursive definition
ancestor(X,Y) :- parent(X,Y). 
ancestor(X,Y) :- parent(X,A), ancestor(A,Y).

The first part of the program establishes facts about how six people are related as parents and children. For example, John is the parent of Jane, and Sally is also the parent of Jane. In the code, the names don't start with an uppercase letter because we don't want prolog to treat them as variables.

The following diagram presents this information as a family tree, making it easier to see who is related to whom.

Just to warm up, we can ask basic questions like “who is the parent of Jane?”

?- parent(X, jane).

X = john
X = sally

As expected, prolog tells us both John and Sally are parents of Jane.

Grandparent

Let's turn our attention from parents to grandparents. The program defines a grandparent as follows.

% grandparent
grandparent(X, Y) :- parent(X, A), parent(A,Y).

If a person X is the parent of another person A, and that person A is the parent of someone else Y, then X is the grandparent of Y. That sounds complicated, but is just saying what we know, a grandparent is the parent of a parent.

Let's check it works as expected by asking “who is the grandparent of Jane?”

?- grandparent(X, jane).

X = martha
false

Prolog has found that Martha is indeed the grandparent of Jane. If we run this query, prolog will suggest searching for more solutions. This is because it hasn't completed trying all the combinations for X and A in the definition of grandparent. After we prompt for more solutions, prolog replies with a false because it finds the remaining combinations for X and A don't work.

We might have expected Jane to have the full set of four grandparents, not just Martha. Because they're not described in the database of facts, as far as prolog is concerned, they don't exist. This is called the closed world assumption. 

Recursive Definition of Ancestor

We could create similar definitions for great grandparents, great great grandparents, … but that would get boring pretty quickly. Instead, let's see if we can define a general property for all ancestors.

To get started, let's write down what some of these ancestors actually are.

• a grandparent is a parent of a parent,
• a great grandparent is a parent of a grandparent, 
• a great great grandparent is a parent of a great grandparent.

We can see a pattern here. Each statement is of the form:

• (ancestor) is a parent of (ancestor one level lower)

This insight isn't a surprise at all, but working out this kind of relationship is key to writing recursive programs in any language, not just prolog. 

Our definition of ancestor isn't quite complete. To see why, let's apply the pattern to great grandparent. A great grandparent is a parent of a grandparent. Applying the pattern again, a grandparent is a parent of a parent. We can't apply the pattern again because it looks like we don't have a rule defining parent. Actually, in our example, parents are defined as facts in the prolog database. This means the repeated application of the pattern will eventually terminate.

What we've arrived at is a recursive definition of ancestor. There are two key features of recursive definitions.

1. Continuation - a property defined in terms of itself, but reduced by one step. Here, an ancestor is a parent of an ancestor one level lower.
2. Termination - a base case which defines the property without referring to itself. Here, the lowest ancestor, a parent, is defined by database facts.

Don't worry if all of this is rather abstract. Recursion is best understood through practice, and we'll do that here, and in later chapters too.

Ancestor/2

Having talked about recursion, let's now look at the definition of ancestor/2 in the example program.

% ancestor recursive definition

ancestor(X,Y) :- parent(X,Y). 
ancestor(X,Y) :- parent(X,A), ancestor(A,Y).

The first thing we notice is that ancestor/2 appears to be defined twice. In a previous chapter we saw definitions using the same name for a property but with different arities, specifically sentence/3 and sentence/1. Here both definitions take the same parameters, X and Y, so they both have the same arity. They are both ancestor/2. Is there a clash?

There isn't a clash. Prolog will apply the first rule, and if that's not helpful, it then will try the second rule. This is actually no different to the simple facts we saw earlier, like hairy/1 or tasty/1.

Let's look at the first rule ancestor(X,Y):-parent(X,Y). A parent is the simplest case of being an ancestor, and because parents are defined in the database as facts, this is the termination rule of the recursive definition.

Let's now look at the second rule ancestor(X,Y):-parent(X,A), ancestor(A,Y). This is the pattern we found earlier, and is the continuation rule of the recursive definition. It defines an ancestor in terms of an ancestor one step down. That is, ancestor(A,Y) is one step down on the family tree from ancestor(X,Y) because X is required to be the parent of A.

Before we finish, we should think about the order of the two ancestor/2 rules. In prolog we write the termination rule first because we want prolog to end its search as soon as possible.

We've done a lot of thinking, and the end result is just two short lines of prolog code. That is the right way to do recursion!

Example 1 - Martha & Jane

Let's now talk through our recursive definition ancestor/2 with an example to see how it works in some detail. Let's ask whether Martha is an ancestor of Jane. 

The first rule says that if Martha is the parent of Jane, then she is an ancestor of Jane. This rule is not satisfied because the database doesn't tell us that Martha is the parent of Jane. 

So we move to the second rule which says that if Martha is the parent of someone A, and A is the ancestor of Jane, then Martha is an ancestor of Jane. Can we find an A that satisfies this rule?

The database tells us that Martha is a parent of A=sally. That's the first part of the rule satisfied. The second part is then asking whether A=sally is the ancestor of Jane. To answer this we apply the first rule again, because it defines ancestor as a parent. The database does indeed tell us that Sally is the parent of Jane, so Sally is an ancestor of Jane. The second rule has been satisfied. 

So Martha is indeed an ancestor of Jane.

?- ancestor(martha, jane).

true

The following diagram shows the search tree for this query. We can see how the first rule fails, but the second rule succeeds.

Example 2 - Deirdre & Jane

Let's see how the definition works for another example where the family lineage is a little longer. Let's ask whether Deirdre is an ancestor of Jane.

As usual, we'll apply the first rule. It says Deirdre is an ancestor of Jane if Deirdre is a parent of Jane. This rule is not satisfied because the database doesn't tell us that Deirdre is the parent of Jane. 

So we move to the second rule. This says that Deirdre is an ancestor of Jane if Deirdre is a parent of someone A, and A is an ancestor of Jane. Again, can we find an A that satisfies this rule?

The database tells us Deirdre is the parent of A=martha. So the first part of the second rule is satisfied. The second part of the rule is then asking whether A=martha is the ancestor of Jane.

That is the same question we just walked through. We showed that Martha is indeed an ancestor of Jane. So the second part of the rule is satisfied, and therefore Deirdre is an ancestor of Jane.

?- ancestor(deirdre, jane).

true

The key thing to notice is how this problem (Deirdre and Jane) is just the previous problem (Martha and Jane) extended by one parent. This is a feature of scenarios amenable to recursion.

Example 3 - All Jane's Ancestors

If we've defined a problem well enough, we can ask prolog to find answers for us, not just test whether given assertions are true. Let's ask “who are all the ancestors of Jane?”

?- ancestor(X, jane).

X = john
X = sally
X = martha
X = deirdre

Our recursive definition is indeed good enough to generate all the ancestors.

Key Points

• If something isn't provable in a prolog program, it is assumed to be false. This is the closed world assumption.
• Prolog is happy with multiple rules defining a property with the same name and the same arity. Prolog applies the rules in the order they are defined.
• A recursive definition has two key elements, a continuation rule and a termination rule.
• Continuation - a property defined in terms of itself, but with the size of the problem reduced by one step.
• Termination - a simple case which defines the property completely, without referring to the same property.
• In prolog we write the termination rule before the continuation rule because we want prolog to end its search as soon as possible.

6 - Query Order & Efficiency

Here we'll look at how two prolog queries can be logically equivalent, and yet have differences in how efficiently they work.

The following simple program establishes some facts about the hairiness and colour of cats and dogs.

% Example 06 - Query Order & Efficiency

% hairy facts
hairy(dog). 
hairy(cat).

% colour facts
colour(dog, brown). 
colour(dog, black).
colour(cat, grey). 
colour(cat, white). 

Cats and dogs are hairy. Dogs can be brown or black, and cats can be grey or white.

Logically Equivalent Queries

The following query asks which X is white and hairy.

?- colour(X, white), hairy(X).

X = cat

The next query asks which X is hairy and white.

?- hairy(X), colour(X, white).

X = cat

Even though the ordering of the two parts of the query is different, the two queries are logically equivalent. That is, they are not asking different questions. Unsurprisingly, X=cat is the answer to both.

Procedurally Different Queries

Like all computer code, these queries have to run on computer hardware which is not logical but procedural, ultimately carried out step by step, one after another.

Let's look at the first query. We already know that prolog works with conjunctive queries left to right, so it will first try to solve the goal colour(X,white). This is easily matched with the database fact colour(cat,white) leaving X=cat. There are no other rules that match this goal so there are no other options for X. Moving to the next part of the query hairy(X) means prolog has to test hairy(cat) because the first part set X=cat. This is straightforward because hairy(cat) is a simple fact in the database. So X=cat is the solution.

Now let's work through the second query. This time the left-most part of the query is hairy(X). As we've seen before, prolog works by trying to unify its current goal with facts in the database. The first one it finds is hairy(dog), leaving X=dog. Moving on to the second part of the query colour(X,white), which is now colour(dog,white), prolog finds there are no facts that confirm this. So X=dog is rejected as a solution. As we know, prolog backtracks to the point where X is unbound, and tries to unify hairy(X) again. This time prolog finds hairy(cat), leaving X=cat as a possible solution. It moves on to the second part of the query colour(X,white), which is now colour(cat,white). This second part is easily proven because it exists in the database. So X=cat is the solution to the full query.

We can see that, although both queries arrive at the same answer, the amount of work is different. The first query takes fewer steps. The second has more steps because it tries and then discards X=dog as a possible solution.

A Strategy For Efficient Queries

Our example, although simple, does show that logically equivalent queries can be procedurally different, with some more efficient than others. Our example also suggests a strategy for efficient queries. 

We should try to order the parts of our queries such that options for variables are closed down as soon as possible. 

That is, variables should be bound, or grounded, to the correct values as far left in a conjunctive query as possible. This reduces wasted effort testing, and backtracking from, later parts of a query with ultimately incorrect values.

Later we'll see queries where this difference makes a big impact on the efficiency, or even feasibility, of solving them.

Tracing

We can ask prolog to print out the steps it takes when trying to solve a query. This is called tracing. You might be asking why we didn't use tracing sooner as it seems like a very helpful thing to do. Reading and understanding traces needs some familiarity with how prolog solves queries, and we didn't have that before.

We can turn on tracing by adding trace/0 to the left of a query. Let's do this with the first version of our query. 

?- trace, colour(X, white), hairy(X).

 Call:colour(_3872,white)
 Exit:colour(cat,white)
 Call:hairy(cat)
 Exit:hairy(cat)
X = cat

Let's walk through what prolog is reporting. We can see the first goal prolog tries to solve is colour(_3872,white). The _3872 is prolog's name for a new variable temporarily taking the place of X. The actual number is random, and is different with every run of the query. That's because prolog wants to keep this variable for its own internal working, and is not something it normally shares with us. Once prolog is happy with the value this internal variable should have, it will report it back as the value of X.

The second line of the trace shows prolog immediately unified the goal with colour(cat,white). The next line shows prolog trying to solve the second part of the query, hairy(cat). Again, prolog succeeds quickly because hairy(cat) is in the database. We can think of this query taking four prolog steps.

Let's now do the same for the second version of the query.

?-  trace, hairy(X), colour(X, white).

 Call:hairy(_4086)
 Exit:hairy(dog)
 Call:colour(dog,white)
 Fail:colour(dog,white)
 Redo:hairy(_476)
 Exit:hairy(cat)
 Call:colour(cat,white)
 Exit:colour(cat,white)
X = cat

Compared to the previous trace with 4 lines, this one has 8 lines. Let's step through them.

The first goal is hairy(_4086), which is hairy(X) but with an internal variable for X. Prolog unifies this with hairy(dog) in the database, so the internal variable _4086 is set to dog. Prolog then moves on to the next part of the query, which means it tries to prove the goal colour(dog,white). The fourth line of the trace shows this goal fails because it doesn't match anything in the database. 

The fifth line of the trace makes clear prolog is backtracking to try other values for X in hairy(X). Notice how the internal variable for X is a new one _476. This is prolog's own way of managing how it keeps track of the different values it tries for X. The sixth line of the trace shows hairy(_476) immediately unifies with hairy(cat), leaving X=cat. After that, the trace shows prolog tests the second part of the query colour(cat,white), and succeeds immediately.

Tracing is a useful tool when trying to fix, or debug, prolog code that doesn't appear to be doing what we want it to do. Even if we're just curious, and not debugging, tracing lets us see how prolog actually works. 

Key Points

• Two prolog queries can be logically equivalent, because they ask the same question, but procedurally different, because the steps prolog takes to solve them are different.
• A good strategy for an efficient query is to order its parts so that variables are bound to the correct values as soon as possible, that is, as far left as possible.
• Prolog has a built in tracing capability to show the steps it takes trying to solve a query.
• When working with variables we've provided, prolog uses its own internal variables to keep track of its own search for possible solutions.
• These internal variables have the form _123, an underscore followed by a random number.

5 - Generating Simple Sentences

In this example we'll practice using the power of unification, and see how easy it is for prolog to generate simple grammatically correct English sentences.

% Example 05 - Generating Sentences

% subjects, verbs and objects
subject(john). 
subject(jane).
verb(eats). 
verb(washes).
object(apples). 
object(spinach).

% sentence = subject + verb + object
sentence(X,Y,Z) :- subject(X), verb(Y), object(Z). 

% sentence as a list
sentence(S) :- S=[X, Y, Z], subject(X), verb(Y), object(Z).

Before we talk about the code, let's see how simple English sentences are constructed.

Simple English Sentences

English sentences can be as simple as “Emma drives buses” or “James eats plums”. The grammatical structure is subject, verb and object. 

The first part of the code creates simple facts, establishing that john and jane are subjects, eats and washes are verbs, and apples and spinach are objects. 

Testing Sentences Are Well-Formed

The rule sentence(X,Y,Z):-subject(X),verb(Y),object(Z) says that X, Y and Z form a sentence if X is a subject, Y is a verb, and Z is an object. We recognise this as a conjunctive rule where the head is only true of all the three parts of the body are true.

We can use this rule to test if a sentence is well-formed. For example, “john eats apples”.

?- sentence(john, eats, apples).

true

Prolog uses this rule to check if john is a subject, eats is a verb, and apples is a subject. Because they are, the sentence conforms to the grammar we've defined. 

Let's try the sentence “john apples eats”.

?- sentence(john, apples, eats).

false

Prolog tells us this sentence isn't well-formed. Although subject(john) is true, verb(apples) is not, so the rule defining sentence can't be satisfied.

Generating Simple Sentences

One of the benefits of logic programming is that our definitions are often strong enough not just to test candidate solutions, but also to generate them. 

We can ask prolog which X, Y and Z result in a well-formed sentence.

?- sentence(X, Y, Z).

X = john
Y = eats
Z = apples

Just like our previous examples, Prolog uses unification with the database of facts and rules to find which values of X, Y and Z satisfy sentence(X,Y,Z).

The first combination it finds is X=john, Y=eats, and Z=apples, corresponding to the English sentence “john eats apples”. As you would expect, there are more combinations that also satisfy sentence(X,Y,Z). We need to prompt prolog to give them to us. 

The following table lists all eight combinations prolog finds.

X	Y	Z
john	eats	apples
john	eats	spinach
john	washes	apples
john	washes	spinach
jane	eats	apples
jane	eats	spinach
jane	washes	apples
jane	washes	spinach

With only a single rule to define a simple grammar, and a little bit of vocabulary, prolog can generate well-formed sentences. That's quite impressive.

What vs How

Notice how our prolog program defined what a grammatically correct sentence is. It didn't describe how to build a sentence step-by-step. That is, we didn't write detailed code to fetch an object from a list of objects, then a verb from another list, then a subject, and finally join them together to form a sentence.

Prolog is a declarative programming language, encouraging us to describe a problem, and letting the language solve it. In contrast, many popular languages like C or python are imperative, requiring us to write in code step-by-step instructions on how to build an answer to a problem. 

Chronological Backtracking

Before we move on, it is worth looking again at these combinations and recognising the process of search and backtracking at work. 

The very first combination matches the order of facts found in the database. The remaining combinations are found by backtracking and finding new values for the variables X, Y and Z.

Backtracking works by undoing the binding of variables, with the most recently set variable unbound first. This strategy is called chronological backtracking. 

Here, this means it is the variable Z, most recently bound to apples, which is backtracked to being unbound, and then bound to spinach. 

There are no more options to try for Z, so the next backtracking is for the middle part of subject(X),verb(Y),object(Z), unbinding Y from eats and setting it to the next option washes. Having set Y to washes, Z can again be matched to apples, backtracked and matched to spinach. This gives us the first four combinations.

The last four combinations are from prolog backtracking all the way back to the first part of subject(X),verb(Y),object(Z), unsetting X from john and binding it to jane.

Asking Questions

There is even more we can do with this simple program. We can ask “what can Jane do with apples?”

?- sentence(jane, Y, apples).

Y = eats
Y = washes

Jane can eat or wash apples. Although this example is trivially small, we can start to see the power of asking questions of a sufficiently well described system.

Another example, “who can wash spinach?”

?- sentence(X, washes, spinach).

X = john
Y = jane

Both John and Jane can wash spinach.

Sentences as Lists

Trying to read or write sentences as X=john, Y=eats, and Z=apples as not very comfortable. A more comfortable way is to use lists.

In prolog, like many other languages, a list is just a collection of things. In code these things are separated by commas, and enclosed in square brackets. For example, [john, eats, apples] is a list of three things.

In a list, the order of things is important. The list [john, eats, apples] is not the same as the list [apples, eats, john]. Repetition also matters, so the list [john, eats, apples] is not the same as [john, eats, apples, apples].

The last line of code in our program appears to create a conflicting rule for sentence. Let's look again at the two rules.

sentence(X,Y,Z) :- subject(X), verb(Y), object(Z). 
sentence(S) :- S=[X, Y, Z], subject(X), verb(Y), object(Z).

The two rules don't clash because prolog sees them as different. Let's see why.

The first definition for sentence takes three parameters, X, Y and Z. We say it has an arity of 3. Prolog experts write sentence/3 to make this clear.

The second definition for sentence takes just one parameter, S. Writing it as sentence/1 makes clear it has an arity of 1.

Prolog sees sentence/3 and sentence/1 as entirely different because they have different arities. They may as well be elephant/3 and giraffe/1.

The bodies of the two definitions look similar. They both say that X must be a subject, Y must be a verb and Z must be an object. But in addition, sentence/1 says that S must be a list consisting of X, Y and Z - in that order, and with no duplicates.

Let's test a sentence in a list.

?- sentence([john, washes, spinach]).

true

Prolog retains its ability to find values for variables when they are in a list.

?- sentence([john, Y, spinach]).

Y = eats
Y = washes

Finally, let's ask prolog to find all the valid sentences, this time as lists.

?- sentence(S).

S = [john, eats, apples]
S = [john, eats, spinach]
S = [john, washes, apples]
S = [john, washes, spinach]
S = [jane, eats, apples]
S = [jane, eats, spinach]
S = [jane, washes, apples]
S = [jane, washes, spinach]

Much better! Sentences as lists are much more comfortable to read and write.

Key Points

• Prolog tries to find multiple answers to conjunctive queries with chronological backtracking, from right to left.
• Prolog lists are written as [a,b,c]. Order and repetition matters, so [a,b,c] is not the same as [c,b,a], nor [a,a,b,c].
• Prolog sees rules with the same property name, but with different arity, as entirely different rules. Arity is the number of parameters a property takes. For example, sentence(X,Y,Z) is different from sentence(S).
• It is traditional for properties to be written with the arity, for example sentence/3.