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.

SWI Prolog and SWISH

We'll be using a mature and open source Prolog called SWI-Prolog.

To avoid the complexity of installing and configuring the Prolog language, we'll be using than online service called SWISH accessed through any modern browser:

• https://swish.swi-prolog.org

If you have the technical experience, you can of course download and run SWI-Prolog locally, and even use your favourite code editor with a prolog or swi-prolog specific support, such as the add-on for Microsoft's Visual Studio Code.

We'll be putting all our prolog program examples on GitHub for convenient access:

• https://github.com/prologbyexample/prologbyexample

The files have a suffix .pl and are simply plain text files.

Welcome!

This blog will journey through learning logic programming and Prolog by working through small examples.

This is intentionally a different approach to learning about Prolog as a programming language, or learning about logic from a theoretical perspective.

The idea is that talking through examples helps to learn theoretical concepts by making them real, by seeing the mechanics of how they work, and by actively experimenting and playing ourselves. 

Doing, not just reading, is underestimated as a method for learning and understanding.

The examples will be kept small and focussed, and will progressively illustrate key concepts and themes.

We also won't cover topics which fall outside the core objective of learning to think like a logic programmer - for example, we won't cover how to read or write to files.