An Introduction to Prolog

9 min read CPSC3740, CPSC3750

The starwars way

Prolog stands for programming in logic. Prolog programs are specified as relations and rules around the relations defined by programming in logic. The programs can be queried to determine the veracity of facts or to infer new facts using the rules. The specification of the facts and rules will be illustrated using the STAR WARS family tree as per the end of episode 8 at the end of this post (obtained from google images). Please review the family tree before proceeding with the post. Two popular interpreters are gprolog, swipl.

The family tree will be specified in Prolog as a set of individuals and relationships between pairs of individuals. Basic facts that we encode are whether the individual (specified by the name) is a male or a female, and the child-of relationship between a pair of individuals.

Following unary and binary relations will be used.

  • male(X)/female(X)/neuter(X), encodes the gender of X.
  • child(X,Y), encodes that X is a child of Y.

The fact the_force is neuter in gender is stated as neuter(the_force). Note the use of lower-case letters. The basic units (called atoms) all being with lower-case letters. The basic facts about the family tree as below. The basic facts from the tree are encoded as below.


neuter(the_force).
male(cliegg_lars).
male(owen_lars).
female(shmi_skywalker).  
male(anakin_skywalker).
male(ruwee_naberrie).
female(jobal_naberrie).
female(padme_amidala).
male(luke_skywalker).
female(leia_organa).
male(han_solo).
male(kylo_ren).
female(rey).

child(anakin_skywalker, the_force).
child(anakin_skywalker, shmi_skywalker).
child(luke_skywalker, anakin_skywalker).
child(luke_skywalker, padme_amidala)
child(leia_organa, anakin_skywalker).
child(leia_organa, padme_amidala).
child(owen_lars, cleigg_lars). 
child(padme_amidala, ruwee_naberrie).
child(padme_amidala, jobal_naberrie).
child(kylo_ren, leia_organa).
child(kylo_ren, han_solo).

Given the database of related facts above, we already are in a position to query it. To know the children, we can ask child(X, han_solo). Prolog will evaluate the query below (queries are always prefixed with ?-) to find all X such that X is a child of han_solo;.

?- child(X, han_solo).

X = kylo_ren .

Both the children of anakin_skywalker can be queried using the query ?- child(X, anakin_skywalker)

?- child(X, anakin_skywalker).

X = luke_skywalker ;
X = leia_organa .

We can also query the parents of kylo_ren using the query child(kylo_ren, X).

?-child(kylo_ren, X).

X = leia_organa ;
X = han_solo .

The current facts in the prolog database do not support the fan theory that rey is a child of leia or luke. The query child(rey, X) fails to returns any parent of rey.

?- child(rey, X).

false.

So far, we have seen that we can use Prolog as a relational database and query for the existence of relations. Prolog can return all possible answers. Specialized versions of Prolog do exist for such data processing (see datalog).

The statements above are called facts and queries. It is also possible to describe rules of inference in Prolog. A rule is written q :- q, it means if p then q. Rules can be logically consistent but may not have any utility in computational reasoning. A rule p :- p (which says if p then p) is correct, but it does not help us derive a proof that p is true. The part before :- is called the head and the part after :- is called the body of the rule. Body of a rule can have multiple conditions (combined using and/or). Rule p :- a , b ; c means if (c or (a && b)) then p. , represents the && and ; represent the ||.

Let’s assume that X is a father of Y if X is a parent of Y and X is male or X is neuter. This knowledge can be described using the following rules. The body of the two rules can also be combined using the ; operator. Now we can ask Prolog, who is the father of anakin?

Similarly we can write a rule mother(X,Y) :- female(X), child(Y,x) to determine if X is mother of Y.

father(X,Y) :- male(X), child(Y,X).
father(X,Y) :- neuter(X), child(Y,X).

?-father(X,anakin_skywalker).

X = the_force .

Let us try to understand the way Prolog searches for answers. We can turn the trace on and see the order in which Prolog tries the rules and the clauses in the body.

?- trace.
?- father(X, anakin_skywalker).

true.
X = the_force .

Prolog has to find an X such that either the body of the first rule is true or the body of the second rule is true. The choice for X is again determined by the facts starting with male and then neuter. The clauses (parts of the body) that are proved to find X form the proof-tree. The proof tree for the query father(X, anakin_skywalker) is

                                  father(X,anakin_skywalker) 
                                             |
                                             |
                              -----------------------------------
                              |                                 |
                          neuter(X)                      child(anakin_skywalker,X)

This tree is a simplified representation of the process followed by Prolog. The choices in the tree are evaluated from top-down left to right. This ordering is determined by order of the facts in the program. The facts (and the rules) are tried in the order they are listed in the file. If X=clieg_lars then Prolog goes on to check the second part of the body, whether cleig is the father of anakin? using the rule child(anakin_skywalker, cleig_lars). The tree of choices for ‘X’ evaluated by Prolog is shown below

The actual process used by Prolog (SLD-resolution) can be observed by using the trace command. The complete trace for the query (in SWI-prolog) is shown below. Spend some time on understanding the trace below. This will significantly help you understand how Prolog searches for solutions.

 [trace]  ?- father(X, anakin_skywalker).
   Call: (8) father(_5874, anakin_skywalker) ? creep
   Call: (9) male(_5874) ? creep
   Exit: (9) male(cliegg_lars) ? creep
   Call: (9) child(anakin_skywalker, cliegg_lars) ? creep
   Fail: (9) child(anakin_skywalker, cliegg_lars) ? creep
   Redo: (9) male(_5874) ? creep
   Exit: (9) male(owen_lars) ? creep
   Call: (9) child(anakin_skywalker, owen_lars) ? creep
   Fail: (9) child(anakin_skywalker, owen_lars) ? creep
   Redo: (9) male(_5874) ? creep
   Exit: (9) male(anakin_skywalker) ? creep
   Call: (9) child(anakin_skywalker, anakin_skywalker) ? creep
   Fail: (9) child(anakin_skywalker, anakin_skywalker) ? creep
   Redo: (9) male(_5874) ? creep
   Exit: (9) male(ruwee_naberrie) ? creep
   Call: (9) child(anakin_skywalker, ruwee_naberrie) ? creep
   Fail: (9) child(anakin_skywalker, ruwee_naberrie) ? creep
   Redo: (9) male(_5874) ? creep
   Exit: (9) male(luke_skywalker) ? creep
   Call: (9) child(anakin_skywalker, luke_skywalker) ? creep
   Fail: (9) child(anakin_skywalker, luke_skywalker) ? creep
   Redo: (9) male(_5874) ? creep
   Exit: (9) male(han_solo) ? creep
   Call: (9) child(anakin_skywalker, han_solo) ? creep
   Fail: (9) child(anakin_skywalker, han_solo) ? creep
   Redo: (9) male(_5874) ? creep
   Exit: (9) male(kylo_ren) ? creep
   Call: (9) child(anakin_skywalker, kylo_ren) ? creep
   Fail: (9) child(anakin_skywalker, kylo_ren) ? creep
   Redo: (8) father(_5874, anakin_skywalker) ? creep
   Call: (9) neuter(_5874) ? creep
   Exit: (9) neuter(the_force) ? creep
   Call: (9) child(anakin_skywalker, the_force) ? creep
   Exit: (9) child(anakin_skywalker, the_force) ? creep
   Exit: (8) father(the_force, anakin_skywalker) ? creep
X = the_force.

Prolog uses depth-first search and matching of terms (unification, = operator) to determine the next goal to be tried. This process is slow and may not terminate. We will look at unification later. Consider the following program, X = f(X).

Is this a legitimate program? What do you think prolog would? To find the value of X prolog needs to use f(X). So,

X if f(X)
X if f(f(X))
X if f(f(f(X)))

gprolog sees this cyclic dependency readily and bars the specification of the program. However, SWI-prolog sees it only at the time of execution. Therefore it allows the program to be defined. There will be more on unification later.

For any free variable Z SWI-prolog says (see https://en.wikipedia.com/wiki/42_(number)) when the query ?-Z. is evaluated.

% … 1,000,000 ………… 10,000,000 years later

%

% >> 42 << (last release gives the question)

Let us finish with a brief introduction to recursive rules. A rule is called recursive if the head of the rules also appears in the body. This ability is the same as the recursive definition of the functions in traditional imperative programming, so one has to be careful about the specification of the base case. The base cases are themselves specified by rules. Thus, the base cases are typically defined earlier than the recursive definition.

See the following recursive definitions of the ancestor relation anc(X,Y).

  • Base Case: `X is an ancestor of Y if Y is a child of X.’
  • Recursive Definition X is an ancestor of Y if X has a child Z and Z is an ancestor of Y

An equivalent form in prolog is the two rules. Now, we can query the fact base for all the ancestors of kylo_ren.

anc(X,Y) :- child(Y,X).
anc(X,Y) :- child(Z,X), anc(Z,Y).

?- anc(X, kylo_ren).

X = leia_organa ;
X = han_solo ;
X = the_force ;
X = shmi_skywalker ;
X = anakin_skywalker ;
X = padme_amidala ;
X = ruwee_naberrie ;
X = jobal_naberrie .

If the rules were specified as below, then the left recursion in the rule (head) would cause the stack to overflow. The recursion will not terminate.

anc1(X,Y) :- anc1(Z,Y), child(Z,X).
anc1(X,Y) :- child(Y,X).

The program specifying anc1 does not terminate, however, it is “logically equivalent” to the program for anc. Thus, the prolog program has two meanings, i) the “logical” meaning, and ii) a “computational” meaning. Logical meaning can be thought of as the intended meaning, and computational meaning is the result that is obtained after the program is executed. These are known as declarative and the procedural meaning of the program respectively. So, two programs can have the same declarative meaning but different procedural meanings. Moreover, the declarative meaning of a program might not be the same as the procedural meaning of the program.

Exercise:

  • Write down the four different variants of the ancestor rules.
  • Trace the query anc(X, kylo_ren), draw the proof tree. Explain.
  • Modify the fact base above to capture the training relationships (master-student). Your model should capture the light and the dark side.
  • For X, a Jedi Y is a Jedi-ancestor, if Y trained X, or Y trained some Z, and Z is a Jedi-ancestor of X. Write a set of rules to identify Jedi-ancestors.
  • Using your rules (and the new fact base), write a query to determine all those individual who has some Jedi ancestor from the dark side and well as some from the light side.

Additional Resources:
Prolog Starwars COVID lecture