• invented early seventies by Alain Colmerauer in France and Robert Kowalski in Britain. 
• Prolog = Programmation en Logique (Programming in Logic).
• Prolog is a declarative programming language unlike most common programming languages.
• In a declarative language
• the programmer specifies a goal to be achieved
• the Prolog system works out how to achieve it
• relational databases owe something to Prolog

Let us assume we have a simple food chain where lions eat dogs, dogs eat cats, cats eat birds, birds eat spiders and spiders eat flies. 

In Prolog we write the following facts:

In Prolog eat is called a predicate; to be more precise it is a user defined predicate. We just made up the name eat; we could have used devour or almost any other name. The animal’s names are atoms. These are simple data items that are known in Prolog as atoms. Atoms must commence with a lower case character. A fact is a definite known item e.g. cats eat birds or in Prolog

Querying these facts is simple. Say we wish to determine if a spider can eat a dog. We enter the line ?-eat(spider,dog). When we run our program (or query), the Prolog inference engine responds with No, where as if we enter the query 

In Prolog a query is known as a goal, i.e. our goal was to find out if a dog could eat a cat. When we just have facts in our database and no rules then Prolog merely searches through the facts for a match. If a match occurs then our goal has been fulfilled and Yes is output. If no match is found then our goal fails and No is output.

Notice that A, B and C are in upper case so they are variables. Facts and rules combine to form a knowledge base. During execution of a goal Prolog interrogates the knowledge base in an attempt to fulfil the goal.

As an example, we wish to know if dogs eat spiders. 

So we execute the goal ?-eat(dog,spider) and it yields the result Yes as expected. How is Prolog executing this goal? 

• Firstly, the list of facts is examined in search of a direct match; none is found. 

• Next the rules are  examined. In our example, only one rule exists. 

• This rule allows us to reduce our goal into two sub-goals, eat(dog,X) and eat(X,spider). 

• We then examine eat(dog,X) and compare it to our facts. 

• The first, and in this case the only match is eat(dog,cat), 

• the sub-goal eat(dog,X) is fulfilled.

• For our original goal to be fulfilled we require the sub-goal eat(cat,spider) to be fulfilled.

• Breaking this goal down using our rule, we get eat(cat,Y) and eat(Y,spider). 

• Examining our facts, we find that eat(cat,bird) fulfils the first of these goals and eat(bird,spider) fulfils the second. 

• As a result of these inferences, the original goal is fulfilled and Yes is output.

The inference engine carries out this processing. The inference engine is the processing unit of logical programming languages. Inference engines apply the knowledge contained within the knowledge base to reach conclusions about goals. They do this in an organised and systematic manner.

GROUP TASK Activity

Draw a trace tree, like the one in Fig 9.7, for each of the following goals.

?-eat(lion,bird) ?-eat(cat,fly)

Case Study Part 2.

The goal ?-eat(bird,dog) should result in an output of No. 

Actually, Prolog reports a stack overflow error. 

Let us examine the way Prolog’s inference engine approaches the resolution of this goal. 

• As eat(bird,dog) is not a fact within the knowledge base we split it into sub-goals using our rule. 

• As a consequence we have 

• eat(bird,A) and eat(A,dog). 

• We need to fulfil eat(bird,A). 

• There is a fact eat(bird,spider) that fulfils this goal. 

• As A could be spider we now try to resolve

• eat(spider,dog). 

• This is not a fact so again we use our rule. We need to resolve

• eat(spider,B) and eat(B,dog). 

• We find a fact, 
• eat(spider,fly) 

• that fulfils the first of these sub-goals, so B could be fly. 

• We need to resolve eat(fly,dog) 

• which is not a fact so we once again use our rule resulting in 
• eat(fly,C) and eat(C,dog). 

• No fact exists

• for eat(fly,C) so again we use our rule which gives us the sub-goals eat(fly,D) and eat(D,C).

• Again, no facts for eat(fly,D) so we apply our rule giving us 
• eat(fly,E) and eat(E,D). 

• This process continues infinitely and eventually causes a stack overflow error.

This is a common problem encountered in Prolog when rules contain themselves. This is an example of a form of repetition called recursion. Some Prolog compilers and interpreters have mechanisms to detect these infinite inferences occurring, remember however, that logically they should occur.

The same problem can occur within imperative programs. A call to a procedure from within itself can often result in a stack error as the code attempts an infinite number of calls to itself. Care must be taken when using recursion.

The goal does not match any facts so we examine our two rules. 

Using the first rule we get eat(bird,dog). 

This is not a fact and cannot be broken down. 

Examining our second rule gives us eat(bird,X) and caneat(X,dog). 

The facts indicate that X could be spider, as eat(bird,spider) is a fact, in which case we need to resolve caneat(spider,dog). Again, this is not a fact and using our first rule neither is eat(spider,dog). Our second rule results in eat(spider,Y) and caneat(Y,dog). Y could be fly as spiders eat flies, so we try to resolve caneat(fly,dog). This goal expands to eat(fly,Z) and caneat(Z,dog). 

So far the operations of the inference engine have been similar to our original example above. 

This is the point at which the addition of our new rule affects the operation of the inference engine. 

No fact or rule exists in our knowledge base to resolve eat(fly,Z) any more. 

As a consequence, the output is the coveted result No. Which means birds cannot eat dogs. 

Phew! All that work for such an obvious result.

Inference Engine Worked Example

Prolog Case Study Notes Summary

Based on the Case Studies the following is a summary of the language rules.

• The percentage sign % is used to begin a comment within Prolog source code.
• In Prolog square brackets are used to denote a list. 
• A list is a data structure which simply groups a number of data items. The data items are separated using commas. 
• Unlike an array the data items in a list may be of different data types. 
• For example each of the following are legal Prolog lists [1, 2, 3, 4], [ant, 5, 6.87,wild, ‘Sam Davis’] and []. 
• The last example [] is known as the empty list.

• A vertical bar | is used to separate the head of a list from its tail. 
• The head of a list is simply its first item and the tail is the remaining list. 
• For example if we have the list [ant, bird, cat, dog] and we are matching a goal including [A|B] then A will match with the data item or atom ant and B will match with the list [bird, cat, dog]. 
• In many ways Prolog is simply attempting to match the pattern of variables in the goal with its known facts.
• dollar([A, B, C, D]):- 

• It is common practice in Prolog to begin a new line for each clause within a rule. 
• The commas between each clause are logical “and” operators hence all clauses within the rule must be true for the goal to be true.
• The Prolog keyword “is” is used to explicitly assign a value to a variable. 
• This is to distinguish between an equals sign which is used to compare two items. 
• 
  
• The inference engine works through the facts and rules sequentially from top to bottom as it attempts to prove a goal. For this reason the order in which facts and rules appear has a significant effect on the processing performed. It is best to list all facts first followed by the rules.
• 
  
• The operator \= means does not equal. Therefore C\=D is true when the variables C and D are not bound to the same data values.
• 
  
• The underscore character _ in Prolog is known as the anonymous variable. 
• It is similar to other Prolog variables however its value is not reported. 
• In addition if multiple anonymous variables are used within a Prolog statement then each is presumed to be distinct. 
• For example, we could develop a rule called super to find people who are both supervisors and who are also supervised. 
• We could write super(A):- supervises(A, _), supervises(_, A). 
• In this rule the two anonymous variables are not linked and hence can hold different values. 
• For instance super(fred) is true because supervises(fred, jack) and supervises(jeff, fred) are both true together despite jack and jeff being different. 
• In essence the rule super(A):- supervises(A, _), supervises(_, A). is logically the same as super(A):- supervises(A, B), supervises(C, A).