====== 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:
[[http://en.wikipedia.org/wiki/British_Royal_Family|wikipedia:British_Royal_Family]]

==== 2. Database ====

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.

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

**1 point**

==== 3. Basic definitions ====

  * 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**

==== 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 [[http://en.wikipedia.org/wiki/Inductive_logic_programming|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, [[http://www-ai.ijs.si/SasoDzeroski/ILPBook/|
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:

<code>
daughter(louise, edward).
daughter(elizabeth, george).
</code>

Next, tell Prolog, what predicate you want to learn.
<code>
target(daughter,2).
</code>
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:
<code>
language(parent,2).
language(female,1).
</code>

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.
<code>
daughter(X,Y) :- parent(Y,X), female(X).
</code>

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

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

If you find yourself lost, play with the ''functor'' predicate (see e.g. [[http://ktiml.mff.cuni.cz/~bartak/prolog/data_struct.html|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)'':

<code>
?- head_lit(X).
X = daughter(louise, edward) ;
X = daughter(elizabeth, george).
</code>

** 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.
<code>
?- findall(X, head_lit(X), HeadLits), findall(X, body_lit(X), BodyLits).
</code>

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

<code>
?- 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), ...])].
</code>
**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:
  * ''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 
<code>
?- lgg_term(parent(charles,harry),
            parent(charles,william), G, [],_).
</code>

\\
//Provided code://
<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).
</code>

==== 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''.
<code>
?- carthesian([a,b,c], [d,e], C).
C = [[a,d], [a,e], [b,d], [b,e], [c,d], [c,e]].
</code>
**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:
<code>
?- filter_compat([[a,a], [a,b], [f(a),f(b)], [f(a), f(a,b)]], Out).
Out = [[a,a], [f(a),f(b)]].
</code>
Again, you may find ''functor'' helpful.

**1 point**

Define LGG on clauses by using anti-unification on terms. For illustration, consider the two clauses:
  - ''cl(husband(charles,camilla),[wife(camilla,charles)]).''
  - ''cl(husband(philip,elizabeth),[wife(elizabeth,philip), wife(diana,charles)]).''

Your new predicate ''lgg_clause'' will generalize these two clauses into a new one.
  - First, the //heads// are anti-unified using ''lgg_term''.
  - 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:
    - (a) ''wife(camilla, charles)'' and ''wife(elizabeth,philip)''
    - (b) ''wife(camilla, charles)'' and ''wife(diana,charles)''
  - 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:
<code>
?- 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)]).
</code>

**1 point**

Finally, put everything together. Define a new predicate ''lgg(X)'', whose imperative pseudo-code can be described as follows:
  - Call ''all_clauses(Clauses)''.
  - When there is only one item in ''Clauses'', the procedure is stopped and the only item is returned.
  - Remove the first two items from ''Clauses'' and generalize them into a new clause ''General'' using ''lgg_clause''.
  - 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:

  - 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?
  - 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?
  - Name one or two real-world applications, where LGG might be useful.

**1 point**

====== Submission ======

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