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.

The tasks in this assignment do not have to be completed in order. If you get stuck, try skipping to a next task.

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

0 points

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

Consider the following people:

• william: Prince William of Wales
• harry: Prince Henry of Wales
• charles: The Prince Charles, Prince of Wales
• diana: Diana, Princess of Wales
• camilla: Camilla, Duchess of Cornwall
• george: George VI of the United Kingdom
• elizabeth: Elizabeth II, HM The Queen
• philip: Prince Philip, Duke of Edinburgh
• edward: The Prince Edward, Earl of Wessex
• sophie: Sophie, Countess of Wessex
• louise: Princess Louise of Wessex
• james: Prince James of Wessex

and their relationships:

• male(X) means that X is a man.
• female(X) if X is a woman.
• parent(P,C) if P is the parent of C. E.g. P can be Lady Diana and C Prince William. Not the other way round!
• wife(W,H) if W is (or was) the wife of H.

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

• Define the predicate husband(Man,Woman) to be derivable from the database. Do not list all husbands of all wives as ground facts!
• Similarly define person(P) to be either a male or a female.
• Define mother(Mother,Child) and father(Father,Child). Be careful not to define a son or a daughter!

1 point

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 fail!

1 points

In this part you are asked to implement a basic technique from Inductive Logic Programming. ILP is a research area that 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). What do these facts have in common? Intuitively, both speak about “a child of Charles”, written in Prolog as parent(charles,_). The LGG seems to “remove differences”, which prevent unification. In case of simple terms, LGG is called “anti-unification”.

In the rest of the assignment, we will formalize such inductive 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.

The most difficult task, the anti-unification, has been done for you. Please read the documentation carefully, not to make mistakes when using the provided 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:

• X = parent(charles,harry)
• Y = parent(charles,william)

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, [],_).

How to keep the differences as small as possible? Notice that remembering pairs of terms (such as harry,william), we can reuse the variable X. In a silly example, two terms same_person(harry,harry) and same_person(william,william) can be generalized into the term same_person(X,X). The term same_person(_,_) is also a valid generalization, because it can unify with both input terms, but it is overly general, because same_person(X,X) is more specific. During the traversal of both terms, we have to keep track of the anti-unified terms. More info is described in the example below:

Provided code:

%
% Least General Generalization of two terms
% 
%   lgg_term(X,Y, G, In,Out)
%   X ..... first term to generalize (first input)
%   Y ..... second term to generalize (second input)
%   G ..... least general generalization of term (the result)
%   In .... list of already anti-unified terms for chaining
%   Out ... same as In, possibly 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).

Now you should have an idea on generalizing two terms. If we want to generalize whole clauses, Prolog must be told which predicates to use.

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 specific examples of daughters and their parents. Add the following lines to your code:

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

Next, tell Prolog the signature of the learned predicate.

target(daughter,2).

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

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

As you can already guess, we are aiming at finding the clause daughter(X,Y) :- parent(Y,X), female(X). But unlike the previous clauses, do not add it into your file! Let Prolog discover the clause by itself.

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 use a different syntax, but keep the semantics as before: cl(HeadLit,[BodyLit1,BodyLit2,…])

First, we 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) ;
...

Tip 1: Start from the functor predicate (see e.g. Roman Barták's Prolog introduction). Execute ?- functor(f(a,b,c), P,N). and ?- functor(X, predicate, 8) and study the results.

Tip 2: Apart from the functor, you will also need to use call(X). Execute ?- L = daughter(X,Y), call(L) and study the results.

Similarly, define the predicate head_lit(X), which uses target instead of language:

?- 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:

• Each clause will have one literal from HeadLits in its head.
• All clauses will share the same list of body literals, the BodyLits.

?- 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), ...])].

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]].

Take the result from carthesian and filter compatible terms using a new predicate filter_compat. Two terms are compatible iff they share the signature (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)]].

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).

Submit the file to cw.felk.cvut.cz/upload on the 28.4.2013 23:59 CEST the latest. The deadline is strict.