Table of Contents

Prolog assignment 1: British Royal Family

In the first assignment you are going to revise basic syntax of Prolog, its search strategy and recursion. You are asked to save your work in a file called royal.pl and to submit it via the upload system.

Tasks in this assignment do not have to be completed sequentially. If you are not sure, try skipping to a next one.

I. Introduction

Your first task: Do not get scared by the length of this assignment! It is more verbose than usual.

0 points

II. The easy part

0. Introduction

Familiarize yourself with the royal family of the British Monarchy: wikipedia:British_Royal_Family

2. Database

Consider the following people:

and their relationships:

Your task is to encode the genealogy graph about the people above into ground facts in Prolog. Relations female, male and wife have already been done for you. You only have to add the missing facts in the parent relation. 

female(camilla).
female(diana).
female(elizabeth).
female(louise).
female(sophie).

male(charles).
male(edward).
male(george).
male(harry).
male(james).
male(philip).
male(william).

wife(camilla,charles).
wife(diana,charles).
wife(elizabeth,philip).
wife(sophie,edward).

parent(charles,harry).
parent(charles,william).
parent(diana,harry).
...

1 point

3. Basic definitions

1 point

4. Negation by failure

Using the course literature or Google, study the “negation as failure \+” technique or “non-unifiability predicate \=”.

Define the sibling(Sibling1,Sibling2,Parent) predicate: Sibling1 is the sibling of Sibling2 and Parent is their shared parent. Be careful, the person is not its own sibling, therefore sibling(william,william,P) must be false!

1 points

III. The hard part

In this part you are asked to implement a basic technique from Inductive Logic Programming. ILP is a state of the art research area, which combines machine learning and logic programming.

As you may know, machine learning is a branch of artificial intelligence, which develops algorithms making computers evolve their knowledge and behaviour. ILP adds the logic part, which allows computers to learn from complex and interlinked data, such as family relationships.

You will implement one particular technique called Least General Generalization. LGG enables you to have the predicate definitions learned, instead of encoding it by hand, as you did in the first half of the assignment. To guide the algorithm, you will only specify a few specific examples, which Prolog will transform into a general concept.

To illustrate the working of LGG, recall the facts about Charles' children: parent(charles,harry) and parent(charles,william). Intuitively, the generalization of these two tasks is “any child of Charles”, encoded as parent(charles,_). In the rest of the assignment, we will formalize such deductive inferences.

If you want to read more about ILP, Inductive Logic Programming: Techniques and Applications by Nada Lavrač and Sašo Džeroski is a good resource to start.

1. Specify the learning task

Suppose we want to deduce the definition of daughter(X,Y), where X is the daughter and Y is the parent. Firstly, we must tell Prolog some particular examples about daughters. Add the following lines to your code: 

daughter(louise, edward).
daughter(elizabeth, george).

Next, tell Prolog, what predicate you want to learn. 

target(daughter,2).
This line states, that we want to learn the definition of a predicate daughter, which has two arguments.

Next, tell Prolog, which predicates can be used in order to define the daughter predicate: 

language(parent,2).
language(female,1).

As you can already guess, we are aiming at finding the following clause. But unlike the previous lines in this section, do not add it into your file! Let Prolog discover the clause by itself. 

daughter(X,Y) :- parent(Y,X), female(X).

2. Convert atoms into clauses

As you know, a Prolog clause has a head, followed by the :- symbol, a list of literals called the body and a period at the end. For simplicity, we will store a clause in different syntax: cl(HeadLit,[BodyLit1,BodyLit2,…]), but its meaning will remain the same.

Before we start, let's load the complete program into a clause, using some basic meta-predicates. Define a predicate body_lit(X), which loads a fact specified by language(X,Y) into a list of terms. In our case, the implementation should work as follows: 

?- body_lit(X).
X = parent(charles, harry) ;
X = parent(charles, william) ;
X = parent(diana, harry) ;
...
X = female(camilla) ;
X = female(diana) ;
X = female(elizabeth) ;
...

If you find yourself lost, play with the functor predicate (see e.g. Roman Barták's Prolog introduction). Just play with ?- functor(f(a,b,c), P,N). or ?- functor(X, predicate, 8), which will guide you. Apart from the functor, you will also need to use call(X).

Similarly, define the predicate head_lit(X): 

?- head_lit(X).
X = daughter(louise, edward) ;
X = daughter(elizabeth, george).

1 point

Briefly study the following code, which puts all head and body literals into a list. Feel free to reuse it your code, where suitable. 

?- findall(X, head_lit(X), HeadLits), findall(X, body_lit(X), BodyLits).

Now your task is to combine the content of variables HeadLits and BodyLits into a list by defining the predicate all_clauses: 

?- all_clauses(X).
X = [cl(daughter(louise,edward), [parent(charles,harry),
          parent(charles,william), parent(diana,harry), ...,
          female(camilla), female(diana), ...]),
     cl(daughter(elizabeth,george), [parent(charles,harry),
          parent(charles,william), parent(diana,harry), ...,
          female(camilla), female(diana), ...])].
1 point

2. Anti-unification

The most difficult task, the anti-unification, has been done for you. Please read the documentation carefully, not to make mistakes when using the code.

In its essence, anti-unification finds the least general generalization of two terms. You can think of this algorithm as a “cautious” procedure: Differences between the two terms are removed, while keeping the modifications as small as possible.

For illustration, recall our running example:

As you can see, the only difference between X and Y is the second argument. Therefore anti-unification on the two terms yields parent(charles,_). Try it yourself by copy&pasting the code below and then, query Prolog for 

?- lgg_term(parent(charles,harry),
            parent(charles,william), G, [],_).


Provided code: 

%
% Least General Generalization of two terms
% 
%   lgg_term(X,Y, G, In,Out)
%   X ..... first term to generalize
%   Y ..... second term to generalize
%   G ..... least general generalization of term (the result)
%   In .... list of already anti-unified terms for chaining
%   Out ... same as In, possible enriched with new pairs
%
% Usage:
%
%   1) If two constants are equal, they are kept equal.
%      ?- lgg_term(a,a, G, [],Out).
%         G = a,
%         Out = [].
%
%  2) If two constants differ, they are lifted into a variable.
%      ?- lgg_term(a,b, G, [],Out).
%         Out = [s(a,b,G)].
%
%     Notice that G remains a free variable!
%
%  3) CHAINING: Variable G from the previous example appears inside the list
%     Out, which allows the next anti-unification to reuse the same variable:
%
%      ?- lgg_term(a,b, G, [],Mid), lgg_term(a,b, H, Mid,Out).
%         G = H,                    <-- THIS IS IMPORTANT
%         Mid = Out = [s(a, b, H)].
%
%     Intuitively, this makes sense. If you try to generalize the same pair
%     of constants twice, they should be replaced by the same variable.
%     
%     But lifting two different pairs of constants yields different variables:
%
%      ?- lgg_term(a,b, G, [],Mid), lgg_term(a,c, H, Mid,Out).
%         Mid = [s(a, b, G)],
%         Out = [s(a, c, H), s(a, b, G)].
%     
%     Notice that both G and H remain free, just as in case (1).
%     Also notice that the list Mid was extended by the new anti-unified pair.
%
%  5) You may treat different variables just as different constants,
%     no unification occurs.
%
%      ?- lgg_term(X,Y, G, [],Mid), lgg_term(X,Z, H, Mid,Out).
%         Mid = [s(X, Y, G)],
%         Out = [s(X, Z, H), s(X, Y, G)] 
%
%     Just as in case of (2), both G and H remain free variables.
%
%  6) Structured terms are crawled recursively:
%
%     ?- lgg_term( f(a,b,g(b),a), f(a,a,g(a),b), G, [],Out).
%        G = f(a, A, g(A), B),
%        Out = [s(a, b, B), s(b, a, A)].
%
%  7) Finally, see how chaining and recursion work together:
%
%     ?- lgg_term( f(a,b,g(b),a), f(a,a,g(a),b), G,  [],Mid),
%        lgg_term( g(b,a,g(a),b), g(b,b,g(b),a), H, Mid,Out).
%        G = f(a, A, g(A), B),
%        H = g(b, B, g(B), A),
%        Out = Mid = [s(a, b, B), s(b, a, A)].
%
%     Variables A and B are shared among the terms G and H, which
%     would not be the case, if the two calls were not "piped" via Mid.
%
lgg_term(X,Y, X, List,List) :- X == Y, !.
lgg_term(X,Y, G, List,[s(X,Y,G)|List]) :- var(X); var(Y).

lgg_term(X,Y, G, List,List) :-
  member(s(A,B,G), List),
  A == X, B == Y, !.

lgg_term(X,Y, G, In,Out) :-
  X =.. [P|Xa], Y =.. [P|Ya],
  lgg_list(Xa,Ya, Ga, In,Out),
  G =.. [P|Ga], !.

lgg_term(X,Y, G, List,[s(X,Y,G)|List]).

% LGG on lists of equal length
lgg_list([],     [],      [],       Lst,Lst).
lgg_list([H1|T1],[H2|T2], [G|Rest], Beg,End):-
  lgg_term(H1,    H2,      G,       Beg,Mid),
  lgg_list(  T1,     T2,     Rest,  Mid,End).

3. Generalization of clauses

At this point, you can generalize individual atoms. Now we will proceed to generalization of clauses.

Firstly create the predicate cartesian, which takes two lists L1 and L2 and creates a new list C of pairs of elements from L1 and L2. 

?- carthesian([a,b,c], [d,e], C).
C = [[a,d], [a,e], [b,d], [b,e], [c,d], [c,e]].
1 point

Take the result from carthesian and filter compatible terms using a new predicate filter_compat. Two terms are compatible iff they share the same symbol and arity: 

?- filter_compat([[a,a], [a,b], [f(a),f(b)], [f(a), f(a,b)]], Out).
Out = [[a,a], [f(a),f(b)]].
Again, you may find functor helpful.

1 point

Define LGG on clauses by using anti-unification on terms. For illustration, consider the two clauses:

  1. cl(husband(charles,camilla),[wife(camilla,charles)]).
  2. cl(husband(philip,elizabeth),[wife(elizabeth,philip), wife(diana,charles)]).

Your new predicate lgg_clause will generalize these two clauses into a new one.

  1. First, the heads are anti-unified using lgg_term.
  2. Then, take pairs of compatible body literals using filter_compat. Since clauses (1) and (2) contain literals of type wife/2 only, all their combinations are compatible:
    1. (a) wife(camilla, charles) and wife(elizabeth,philip)
    2. (b) wife(camilla, charles) and wife(diana,charles)
  3. Finally, the body literals of the generalized clause is created by sequentially anti-unifying the pair (a) and then (b) using lgg_term.

In the end, your code should produce results such as: 

?- lgg_clause(
     cl(husband(charles,camilla),[wife(camilla,charles)]),
     cl(husband(philip,elizabeth),[wife(elizabeth,philip), wife(diana,charles)]),
     ClauseLGG).
ClauseLGG = cl(husband(B, A), [wife(A, B), wife(_, charles)]).

1 point

Finally, put everything together. Define a new predicate lgg(X), whose imperative pseudo-code can be described as follows:

  1. Call all_clauses(Clauses).
  2. When there is only one item in Clauses, the procedure is stopped and the only item is returned.
  3. Remove the first two items from Clauses and generalize them into a new clause General using lgg_clause.
  4. Add General back to Clauses and the go back to step 2.

1 point

After you have obtained the single clause, print the clause. For your convenience, you can use a pretty-printer portray_clause(X).

Discussion

Write a short conclusion about your work in the first assignment. Aim at 300 words. Discuss the following topics:

  1. In the easy part of the assignment, you were asked to use Prolog as an intelligent database of facts. Briefly compare SQL databases and Prolog. Is there a use-case, where Prolog would be more suitable than a lightweight SQL database?
  2. In the hard part, you have defined a basic generalization technique, which learns from examples. What is the difference between clauses obtained by LGG and a clause manually encoded by hand? Are they logically equivalent (do they produce the same results)? What about efficienty of its execution?
  3. Name one or two real-world applications, where LGG might be useful.

1 point

Submission

Submit the file to cw.felk.cvut.cz/upload on the 1.5.2012 12:00 CEST the latest. The deadline is strict.