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.

4 - Proving New Facts By Deduction

The power of prolog is not in finding simple matches to facts in a database. Prolog's power lies in its rather persistent search that can combine together several facts to, in effect, prove a new fact.

Let's explore at a minimal example of this power.

% Example 04 - Deduction

% facts
mammal(dog). 
mammal(cat).

% relation
animal(X) :- mammal(X). 

The first two lines of code establish simple facts, that a thing called dog has a property mammal, and that a thing called cat has a property mammal too. That is, a cat and a dog are mammals.

Relation Between Properties

The last line of code takes a form that is new to us, so let's break it down. It says that a thing X has a property animal if that same thing X has a property mammal. 

The symbol :- is equivalent to logical implication ← from right to left. Here mammal(X) being true implies animal(X) being true, but not the other way around. That is, animal(X) does not imply mammal(X). 

In plain English, this says that if a thing is a mammal, then it is also an animal. It does not say that if a thing is an animal, then it is also a mammal, which makes sense. A fish is an animal, but is not a mammal.

What this line of code establishes is a relation between two properties. These are also called rules, with a head to the left of the :- symbol, and a body to the right.

Deduction

A relationship between properties allows us to say something about one of the properties (the head) if we know something about the other (the body).

Let's try it.

?- animal(cat).

true

We're asking if a cat is an animal. The database has a fact that explicitly states a cat is a mammal, but none that says a cat is an animal.

Prolog has used the relationship between mammal and animal to deduce that a cat is also an animal.

Let's walk through how Prolog finds this answer. The query is animal(cat), and although there is no fact in the database that directly matches this query, Prolog does find it matches the head of the rule animal(X):-mammal(X) with X=cat. Prolog's task is then to see if can satisfy the body of this rule, mammal(cat). This is easily done because the database does contain mammal(cat). Therefore animal(cat) is provable.

We mighty ask why prolog's task was to satisfy the body of the rule animal(X):-mammal(X) once the head had matched the query animal(cat). The reason is because the body of a rule implies the head. To prove the head, all prolog needs to do is prove the body. So proving the body becomes its temporary goal.

If prolog wants to match with the head of a rule, where does this leave matching simple facts like mammal(dog) or tasty(apple)? The simple facts we first met are in fact rules with a head but an empty body. That is, the head is always true because the condition, the body, for the head to be true is empty.

Although this is example is small, what we've seen is pretty amazing. Prolog is not just searching for facts that match a query directly, but is using a relation between properties to deduce the truth of a new fact - a fact that was not explicitly stated in the database.

The following diagram visualises how prolog solves this query using deduction. We can see how combining the initial query goal with a rule leads to a new query goal.

 

Key Points

• In addition to simple facts, we can define relations between properties. These are called rules.
• Rules have the form head(X):-body(X). The symbol :- is equivalent to the logical implication ← from right to left. 
• animal(X):-mammal(X) says the property animal holds if property mammal holds for a thing X. It does not mean the property mammal holds if property animal holds for a thing X. 
• Prolog makes use of rules by matching a query to the head of a rule, then trying to satisfy the body. Satisfying the body of a rule is enough to prove the head.
• Simple facts are rules with a head but an empty body. The head is always true because the condition is empty.
• Prolog can use relations between properties to prove a statement that is not explicitly in its database by deduction. 

3 - Satisfying Multiple Properties

We've progressed from testing the truth of simple facts, to asking which things satisfy a single property. The next step is asking which things satisfy multiple properties.

The following program is simply both of our previous ones combined, creating a database of facts about tasty fruit and red fruit.

% Example 03 - Querying Multiple Properties

% simple facts
tasty(apple). 
tasty(banana). 
tasty(cherry).

% red fruit
red(apple). 
red(cherry). 
red(grape).

Querying With Multiple Properties

Let's ask which fruit are both tasty and red.

?- tasty(X), red(X).

The comma means “and”, or conjunction to be fancy. Prolog is being asked to find which X satisfy both tasty(X) and red(X) at the same time. 

Prolog works through each part of the query, progressing from left to right. Here it starts with tasty(X).

Finding tasty(apple) at the top of the database leaves prolog with X=apple. Prolog then tests to see if the next part of the query red(X) is true. Because X was set to apple by the first part of the query, this part becomes red(apple). Prolog finds this in the database, so X=apple is a valid answer.

After finding the first solution X=apple, prolog backtracks to the point where X is unbound and tries to search for other solutions. 

Prolog finds that tasty(X) unifies with the fact tasty(banana), which leaves X=banana. Prolog then has to test the second part of the query red(X), which is now red(banana). It can't prove red(banana) is true because this doesn't exist in the database, so it discards X=banana as a potential answer. To be clear, X=banana works for the first part of the query tasty(X), but it doesn't for the second part red(X), and this is why it is rejected.

Prolog backtracks and tries again. Following the same method, it finds X=cherry satisfies tasty(X) and red(X).

After this point there are no more facts in the database about things with the property tasty so the search ends.

In this way prolog finds all the fruit which are both tasty and red.

?- tasty(X), red(X).

X = apple
X = cherry 

The diagram below shows visually prolog's search for solutions for tasty(X),red(X). 

Key Points

• Queries with multiple properties separated by a comma are conjunctions. Prolog will try to see if all these properties can be true at the same time. 
• Prolog tries to satisfy each part of conjunctive query, progressing from left to right. Any variables that are set in one part retain their value into subsequent parts.

2 - Querying With Variables

Previously, we created a small database, against which we performed simple queries. Here we'll extend our querying a little further.

% Example 02 - Querying With Variables

% red fruit
red(apple). 
red(cherry). 
red(grape).

This program is very similar to our first one. We've created three facts saying that an apple, a cherry and a grape all satisfy a property called red. That is, apples, cherries and grapes are red.

All Things That Satisfy A Property

Instead of asking whether a cherry or grape is red, let's instead ask which things are red.

?- red(X).

Let's break this down. It looks like we are asking whether a thing called X satisfies the property red. However, X is not an ordinary thing. In fact, X is a variable. That means it is a thing which, at the time of making the query, is not set to any specific value. It is, however, ready to take any value it can, as soon as it can.

Prolog has a naming convention. Variables always start with a capital letter, like X or Fruit, whereas things and properties start with a lower case letter, like cherry and red.

The query is asking prolog, “which X satisfy red(X)?”

As always, prolog searches the database to see if the query matches any previously created facts.

? - red(X).

X = apple
X = cherry
X = grape 

Prolog has searched the database and come back with all the possible choices for X which would satisfy red(X). That is, it has found all the fruit that are red.

Most prolog implementations will give you one answer to such queries. You have to prompt to see if there are more, repeating the prompt until prolog tells you there are no more answers.

Which X Does Prolog Try?

We might wonder which values of X prolog tests to see if there is a match in its database of facts. Could it try X=pear or X=avocado? The options seem endless.

In fact, prolog doesn't come up with candidates for X. That would be a very unproductive way of finding matches. It actually compares the query red(X) with each fact in the database to see if it can be matched, property for property and thing for thing.

Because X is a variable, it is ready to take on any value. So when prolog compares red(X) with the first fact in our database red(apple), prolog finds they can match if X takes on the value apple. This is called unification, and gives us our first answer X=apple.

Prolog doesn't stop at the first match. It goes back to the point where X was a variable, not yet set to any value, and searches for more possible matches in the database. This is how it finds that red(X) unifies with red(cherry), meaning X=cherry is another answer. 

And yet again, prolog backtracks to the point where X is unbound, and finds that red(X) unifies with red(grape), giving X=grape as an answer. Prolog backtracks once more, but this time can't find any more facts to match with. Its job is done - phew!

The following diagram shows visually how prolog searches for solutions to the query red(X) by trying to match it with facts in the database.

Unification Examples

Unification is a really important mechanism in prolog, so it is worth making sure we're comfortable with it. The following are some informative examples.

Query	Fact	Unifies?
tasty(apple)	tasty(apple)	yes
tasty(apple)	tasty(banana)	no
tasty(apple)	red(apple)	no
tasty(X)	tasty(apple)	yes, X=apple
tasty(X)	red(apple)	no

Key Points

• A variable is a thing whose value has not been set, but is ready to take on values as soon as possible.
• Variable names start with an upper case letter, properties and things start with a lower case letter. 
• If a query contains a variable, prolog tries to find the values for that variable which result in the query being true. 
• If prolog finds a value for a variable, it can offer to search for more. Prolog does this by backtracking to the point where the variable is unbound, and continues its search for matches.
• Prolog doesn't invent values for variables. Instead, it uses unification with database facts to find values for variables.

1 - Simple Facts

Let's start with the simplest task, creating and querying facts.

Have a look at the following short prolog program.

% Example 01 - Creating & Querying Facts

% simple facts
tasty(apple).
tasty(banana).
tasty(cherry).

Lines beginning with % are comments for us to read, and are ignored by prolog.

Creating Facts

Let's look at the first real line of code.

tasty(apple).

This creates a simple fact, which then sits in prolog's database waiting to become useful later.

This fact consists of two parts, tasty() and apple. It is saying that a thing called apple, has a property called tasty.

Of course, calling the thing apple doesn't necessarily mean it is an apple. We could have typed elephant instead of apple. Similarly, the property tasty is just a word we've chosen.

Even so, it is useful to imagine we're describing real apples and genuine tastiness. We'll see later that this imagining becomes more useful the better we describe things and their properties in code.

The remaining two lines of code create new facts to sit in the database, tasty(banana), and tasty(cherry).

Querying The Database

Having established a small database of facts, we can query it.

?- tasty(apple).

Here we are asking “does the thing called apple satisfy the property called tasty?” Or more simply, “are apples tasty?”

Prolog tries to answer this question by searching the database. In our database it quickly finds the fact tasty(apple). This matches our query, and so prolog responds by saying true.

?- tasty(apple).

true

If we ask whether a banana is tasty, prolog will again respond with true, because tasty(banana) is a fact in our database.

?- tasty(banana).

true

What would happen if we asked whether a mango is tasty?

You and I might both agree that mangos are indeed tasty, but prolog can't say that because it isn't stated in the database. Prolog won't say “I think so”, or “maybe”. It will always say false, unless it can prove something is true.

?- tasty(mango).

false

Key Points

• The basis of a prolog program is a database of facts.
• Facts consist of two parts, a thing, and a property of that thing. 
• We interact with prolog through queries, asking whether a statement is true.
• Prolog determines the truth of a query statement by searching its database.