ITECH5403 Comparative Programming Languages

School of Science, Engineering and Information Technology

Lab 11 – Logic Programming Languages

Introduction

As this is an 'odd' week we'll be investigating the theory side of logic programming with regard to the
Prolog programming language (which is pretty much the only 'mainstream' programming language in
common use!)…

… but, it's also the last lab of the course (no week 12 lab!) – so
what the heck – let's go out with a bang and get our logic on like
Mr. Spock via the joys of Prolog! =D

Getting and Using Prolog

To start off, go and grab a copy of GNU Prolog from:

http://sourceforge.net/projects/gprolog/

Just hit the [Download] button and you should be happily

downloading setup-gprolog-1.4.4-mingw-x64.exe or a newer
version (if available). Once it's downloaded, install is just a few
clicks, and you should have a GNU Prolog shortcut on your
desktop like this one:

Double click it, and we're ready to go!

So what now?! Well… If you enter something like:

mortal(X) :- person(X).

CRICOS Provider No. 00103D Insert file name here Page 1 of 9

…then GNU Prolog will moan, because it wants all the facts placed in a file for it to read. However, let's
work around that for the moment by typing [user]. to put ourselves in user mode. We can then say that
if X is mortal, then X is a person – and we can say that Socrates is a person – therefore, we can use
logic (or really, we can get Prolog to use logic) to deduce that Socrates is mortal! Poor So-crates! ;-)

Rather than typing in facts and rules each time, it's far better to place them in a file with a .pl extension
and then open them with GNU Prolog – for example, we can enter the following into a file call
SiblingTest.pl:

% Facts
parent(bill, jake).
parent(bill, shelley).

% ----- Propositions -----

% X is a sibling of Y if P is the parent of X and P is the parent of Y and X is not

equal to Y
% Note: The X \== Y part is to stop someone from being their own sibling!
sibling(X, Y) :- parent(P, X), parent(P, Y), X \== Y.

% Queries to try:
% sibling(X,Y). % X = jake, Y = shelley
% sibling(bill, X). % No.
% sibling(jake, X). % X = shelley
% sibling(X, X). % no

Give it a go and try using some of the above queries (you have to type them in – including the full
stop!). Hit Ctrl+D if you get 'stuck' and can't enter any more commands (or restart GNU Prolog!)

CRICOS Provider No. 00103D Page 2 of 9

Let's try another example – put the following into a file called SolarSystem.pl and try out the queries
listed at the bottom of the code:

% ----- Facts -----

% Things that orbit the sun

orbits(mercury, sun).
orbits(venus, sun).
orbits(earth, sun).
orbits(mars, sun).

% Things that orbit the earth

orbits(moon, earth).

% Things that orbit mars

orbits(phobos, mars).
orbits(deimos, mars).

% ----- Propositions -----

% P is a planet if P orbits the sun

planet(P) :- orbits(P, sun).

% S is a satellite if S orbits P, and P is a planet

satellite(S) :- orbits(S, P), planet(P).

% ----- Queries -----

% Try:
% trace.
% satellite(phobos).
%
% Also try:
% satellite(S).

When tracing is enabled it steps through all the steps that occur in the deduction process – so we can
examine the truth of the deduction in detail and see why something is so, not just that it happens to be!

As a final example, try this – there's a sketch in Monty Python about deductive logic, where the
characters logically deduce that you can tell if someone is a witch by whether they weigh the same as a
duck or not!

It's a joke – it's funny, roll with it: https://www.youtube.com/watch?v=X2xlQaimsGg

CRICOS Provider No. 00103D Page 3 of 9

We can replicate this ground-breaking scientific breakthrough for ourselves with the following Prolog
code – place it into a file called WitchTest.pl or such and give it a shot!

% ----- Propositions -----

% X is a witch if X burns and X is female

witch(X) :- burns(X), female(X).

% X burns if X is wooden
burns(X) :- wooden(X).

% X is wooden if X floats
wooden(X) :- floats(X).

% X floats if X is the same weight as a duck

floats(X) :- sameweight(duck, X).

% ----- Facts -----

% girl is a female
female(girl).

% girl is the same weight as a duck

sameweight(duck,girl).

% Try:
% trace.
% witch(girl).

This is just some basic aspects of Prolog, there's a lot more to it than this – as a final task before we hit
the questions, take a look at the following 'quick 'n dirty' prolog tutorial:

http://www.cs.utexas.edu/~cannata/cs345/Class%20Notes/12%20prolog_intro.pdf

It guides you through some simple ancestry tests, but also, there's a great little section at the end
which ties in predicate calculus and explains why horn clauses are so important. The section is:
Connecting Prolog to Predicate Logic (page 5), and it's definitely worth reading if you want to get
better at computer science and climb the ranks of this here pyramid!

CRICOS Provider No. 00103D Page 4 of 9

Review Questions

1. In logic programming, what are the two parts of a compound term? Give at least one example.
[Q2-Mod]

A compound term is one element of a mathematical relationship, written in a form that has the appearance of
mathematical function notation. Compound terms are composed of two parts:

- A functor - which is the functional symbol that names the relation, and
- An ordered list of parameters - which together represent an element of the relation.

A compound term with a single parameter is a 1-tuple; one with two parameters is a 2-tuple, and so on. For
example, we might have the two propositions:

man(jake)
like(bob, steak)

These state that:

{jake} is a 1-tuple in the relation named man, and

{bob, steak} is a 2-tuple in the relation named like.

2. In logic programming, what is the general form of a proposition in clausal form? [Q4]

One problem with predicate calculus is that there are too many different ways of stating propositions that have
the same meaning; that is, there is a great deal of redundancy. To simplify matters, a standard form for
propositions is desirable - and this is called clausal form.

All propositions can be expressed in clausal form, which has the following general syntax:

B1 ∪ B2 ∪ … ∪ Bn ⊂ A1 ∩ A2 ∩ … ∩ Am
The meaning of this is: If all of the A's are true, then at least one of the B's is true.

3. In logic programming, what are antecedents and consequents? Give an example of each.
[Q5-Mod]

The right-hand side of a clausal form is called the antecedent. The left-hand side is called the consequent
(because it is the consequence of the truth of the antecedent).

Consider the following example:

likes(bob, trout) ⊂ likes(bob, fish) ∩ fish(trout)

This states: If bob likes fish and trout is a fish then bob likes trout

In this example likes(bob, trout) is the antecedent, and likes(bob,fish) ∩ fish(trout) are the consequents.

CRICOS Provider No. 00103D Page 5 of 9

 4. In logic programming, we can often replace two propositions with a single proposition via the
process of resolution. Explain the general process of resolution and give an example of it in
action. [Q6-Mod]

The concept of resolution is the following - suppose there are two propositions with the forms:

P1 ⊂ P2 // P2 implies P1
Q1 ⊂ Q2 // Q2 implies Q1

Their meaning is that P2 implies P1 and Q2 implies Q1. Now suppose that P1 is identical to Q2, so we could
rename P1 and Q2 as T. Then, we could rewrite the two propositions as:

T ⊂ P2 // P2 implies T
Q1 ⊂ T // T implies Q1

Now, because P2 implies T and T implies Q1, it is logically obvious that P2 implies Q1, which we could write as:

Q1 ⊂ P2 // P2 implies Q1

This is resolution! Looking at a concrete example:

older(joanne, jake) ⊂ mother(joanne, jake)

wiser(joanne, jake) ⊂ older(joanne, jake)

Their meaning is:

- If joanne is the mother of jake, then joanne is older than jake, AND
- If joanne is older than jake, then joanne is wiser than jake.

Remembering that we can re-write these via:

T ⊂ P2
Q1 ⊂ T

We can use resolution to simplify the propositions down to:

wiser(joanne, jake) ⊂ mother(joanne, jake)

Which means: If joanne is the mother of jake then joanne is wiser than jake.

5. What does it mean for a language to be nonprocedural? [Q9]

Programming in both imperative and functional languages is primarily procedural, which means that:

- The programmer knows what is to be accomplished by a program, and

- The programmer then instructs the computer on exactly how the computation is to be done.

In other words, the computer is treated as a simple device that obeys orders, and everything that is computed
must have every detail of that computation spelled out, step-by-step!

Programming in a logic programming language is nonprocedural - so programs in such languages do not state
exactly how a result is to be computed but rather describe the form of the result. Instead of providing exact
instructions, a set of rules are provided which may be applied to the data in order to infer a result.

CRICOS Provider No. 00103D Page 6 of 9

 6. Explain the closed-world assumption used by Prolog. Why is this a limitation? [Q20]

The nature of Prolog’s resolution sometimes creates misleading results, because the only truths, as far as Prolog
is concerned, are those that can be proved using its database, and it has no knowledge of the world other than its
database.

When the system receives a query and the database does not have information to prove the query absolutely, the
query is assumed to be false!

This is a limitation because Prolog can prove that a given goal is true…but it cannot prove that a given goal is
false. Instead, it simply assumes that something is false if it cannot prove it to be true.

In essence, Prolog is a true/fail system, rather than a true/false system.

Problem Set

1. Write a Prolog description of the Simpsons family tree as depicted below - be sure to include all
mother and father relationships. Add simple parent, sibling, grandparent and cousin rules
and experiment with the data set in Prolog to determine: [PS3-Mod]
- Which family members are siblings,
- Which family members are grandparents, and
- Which family members are cousins.

CRICOS Provider No. 00103D Page 7 of 9

% ----- Facts -----

% - Grandparents - Note: herb's mother is unknown

father(abraham,homer).
father(abraham,herb).
father(clancy,marge).
father(clancy,patty).
father(clancy,selma).
father(homer,bart).
father(homer,lisa).
father(homer,maggie).

mother(mona,homer).
mother(jackie,marge).
mother(jackie,patty).
mother(jackie,selma).
mother(marge,bart).
mother(marge,lisa).
mother(marge,maggie).
mother(selma, ling).

% ----- Propositions -----

% X is parent of Y if X is the mother of Y or X is the father of Y.

parent(X, Y) :- mother(X, Y); father(X, Y).

% X is a grandparent of Z if X is a parent of Y and Y is a parent of Z

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

% X and Y are siblings if Z is a parent of X and PARENT is a parent of Y

sibling(X, Y) :- parent(Z, X), parent(Z, Y).

% X and Y are cousins if A is a parent of X and B is a parent of Y and A and B are

siblings.
cousin(X,Y) :- parent(A,X), parent(B,Y), sibling(A, B).

% Try:
% trace.
%
% -- sibling tests --
% sibling(bart,lisa). -- answer should be yes
% sibling(marge,patty). -- answer should be yes
% sibling(homer,herb). -- answer should be yes
% sibling(homer,selma). -- answer should be no

% -- grandparent tests --
% grandparent(abraham,bart). -- answer should be yes
% grandparent(abraham,homer). -- answer should be no
% grandparent(jackie,ling). -- answer should be yes
% grandparent(mona,maggie). -- answer should be yes
% grandparent(clancy,marge). -- answer should be no

% -- cousin tests --
% cousin(ling,bart). -- answer should be yes
% cousin(homer,herb). -- answer should be no

CRICOS Provider No. 00103D Page 8 of 9

 2. Write the following English conditional statements as Prolog headed Horn clauses:
a. If Fred is the father of Mike, then Fred is an ancestor of Mike.
b. If Mike is the father of Joe and Mike is the father of Mary, then Mary is the sister of Joe.
c. If Mike is the brother of Fred and Fred is the father of Mary, then Mike is the uncle of Mary.

a. ancestor(Fred,Mike) :- father(Fred,Mike).

b. sister(Mary,Joe) :- father(Mike,Joe), father(Mike,Mary).

c. uncle(Mike,Mary) :- brother(Mike,Fred), father(Fred,Mary).

CRICOS Provider No. 00103D Page 9 of 9