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.