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.