self_study_answers.swinb

<div class="notebook">

<div class="nb-cell markdown">
# Prolog exercises for self-study
Below are some exercises designed to help you get up to scratch with Prolog. These exercises are for self-study, you won't get any marks for them. You are encouraged to work through them as soon as possible, to make the most out of the lectures. For those already familiar with Prolog, they should give you an idea of the basic level of Prolog programming required. Advanced programming techniques will be covered in the lectures. (NB. It would be trivial to look up the answers on the web or in a Prolog textbook, but this would entirely miss the point. A 3d year/4th year/MSc CS student should be able to work out the answers for themselves.)  

Before you start, make sure you have read the [Getting started with SWI-Prolog](https://github.com/COMS30106/prolog_intro/wiki/Getting-started) web page.
</div>

<div class="nb-cell markdown">
## Movie Database Queries
Load [ailp_movies.pl](ailp_movies.pl) file in SWISH using the **include/1** predicate. This file defines a database of facts of the following format (NB. Anything following '%' is treated as a comment in Prolog):

    % movie(M,Y) &lt;- movie M came out in year Y
    movie(american_beauty, 1999).

    % director(M,D) &lt;- movie M was directed by director D
    director(american_beauty, sam_mendes).

    % actor(M,A,R) &lt;- actor A played role R in movie M
    actor(american_beauty, kevin_spacey, lester_burnham).

    % actress(M,A,R) &lt;- actress A played role R in movie M
    actress(american_beauty, annette_bening, carolyn_burnham).
</div>

<div class="nb-cell program" data-background="true">
% include movies database
:- include(example(ailp_movies)).
</div>

<div class="nb-cell markdown">
### 1.
Write queries to answer the following questions (NB. Press **next**, **10**, **100**, **1,000** or **stop** after each answer to see if there are any more answers in the database):
</div>

<div class="nb-cell query">
% In which year was the movie American Beauty released?
movie(american_beauty,Y).
</div>

<div class="nb-cell query">
% Find a movie that was released in the year 2000?
movie(M,2000).
</div>

<div class="nb-cell query">
% Find a movie that was released before 2000?
movie(M,Y),Y&lt;2000.
</div>

<div class="nb-cell query">
% Find the name and year of a movie?
movie(M,Y).
</div>

<div class="nb-cell query">
% Find an actor who has appeared in more than one movie?
% or just M1\=M2.
actor(M1,A,_),actor(M2,A,_),M1@&lt;M2.
</div>

<div class="nb-cell query">
% Find a director who has directed a movie in which the actress Scarlett Johansson appeared?
actress(M,scarlett_johansson,_),director(M,D).
</div>

<div class="nb-cell query">
% Find an actor who has also directed a movie?
director(M,A),actor(M,A,_).
</div>

<div class="nb-cell query">
% Find an actor or actress who has also directed a movie?
% (Hint: to do this in a single query you will need to use disjunction
% (semicolon) as well as conjunction (comma).
director(M,A),(actor(M,A,_);actress(M,A,_)).
</div>

<div class="nb-cell markdown">
### 2.
Write a definition in Prolog for each of the following predicates.
</div>

<div class="nb-cell markdown">
(Test your definitions by checking all answers to the appropriate query relation(X,Y) in the *query boxes* below each *program box*. In some cases you will find unwanted answers of the form relation(X,X), but don't worry about these for now.)
</div>

<div class="nb-cell program">
% released_since(M,Y) &lt;- movie M was released after year X
released_since(M,Y) :-
    movie(M,X),
    X&gt;Y.
</div>

<div class="nb-cell query">
released_since(M, 2001).
</div>

<div class="nb-cell program">
% released_between(M,Y1,Y2) &lt;- movie M was released between year X and year Y inclusive
released_between(M,Y1,Y2) :-
    movie(M,Y),
    Y&gt;=Y1,
    Y=&lt;Y2.
</div>

<div class="nb-cell query">
released_between(M, 2002, 2004).
</div>

<div class="nb-cell program">
% same_year_as(M1,M2) &lt;- movie M1 was released in the same year as movie M2
same_year_as(M1,M2) :-
    movie(M1,Y),
    movie(M2,Y),
    M1\=M2.
</div>

<div class="nb-cell query">
same_year_as(M1, M2).
</div>

<div class="nb-cell program">
% newer(M1,M2) &lt;- movie M1 was released after movie M2
newer(M1,M2) :-
    movie(M1,Y1),
    movie(M2,Y2),
    Y1&gt;Y2.
</div>

<div class="nb-cell query">
newer(M1, M2).
</div>

<div class="nb-cell program" data-background="true">
% cast_member(A,M) &lt;- person A was an actor or actress in movie M
% (Give as a two predicates)
cast_member(A,M) :-
    actor(M,A,_).
cast_member(A,M) :-
    actress(M,A,_).
</div>

<div class="nb-cell query">
cast_member(A, M).
</div>

<div class="nb-cell program">
% cast_member2(A,M) &lt;- person A was an actor or actress in movie M
% (Give as a single predicate using the ; disjunction predicate)
cast_member2(A,M) :-
    actor(M,A,_);
    actress(M,A,_).
</div>

<div class="nb-cell query">
cast_member2(A, M).
</div>

<div class="nb-cell program">
% directed_by(X,Y) &lt;- person X has been in a movie directed by Y
% (Hint: re-use your cast_member/2 predicate)
directed_by(X,Y) :-
    director(M,Y),
    cast_member(X,M).
</div>

<div class="nb-cell query">
directed_by(A, B).
</div>

<div class="nb-cell markdown">
### 3.
What's the difference between these queries?

    ?- actor(M1,D,_),actor(M2,D,_).
    ?- actor(M1,D,_),actor(M2,D,_),M1\=M2.
    ?- actor(M1,D,_),actor(M2,D,_),M1@&lt;M2.
</div>

<div class="nb-cell query">
% you can test these queries in this box
</div>

<div class="nb-cell markdown">
#### Answer
1. returns every actor as M1 and M2 are not necessarily different
2. succeeds twice for every pair of different movies
3. succeeds once for every pair of different movies
</div>

<div class="nb-cell markdown">
### 4.
Why do these queries return answers multiple times?

    ?- director(_,D),actor(_,D,_).
    ?- director(_,D),actress(_,D,_).
</div>

<div class="nb-cell query">
% you can test these queries in this box
</div>

<div class="nb-cell markdown">
#### Answer
If D directed n movies and acted in m movies, the query succeeds n*m times. We will see later how to avoid this.
</div>

<div class="nb-cell markdown">
## List processing predicates
The task is to modify the behaviour of some standard list processing predicates. Make sure that you understand the given predicates first. Try to think in terms of minimal changes.
</div>

<div class="nb-cell markdown">
### 5.
The following predicate tests list membership:

    % element(X,Ys) &lt;- X is an element of the list Ys
    element(X,[X|Ys]).
    element(X,[_|Ys]):-
        element(X,Ys).
</div>

<div class="nb-cell markdown">
#### 1.
Extend it with a third argument that contains the list with X removed.
</div>

<div class="nb-cell program" data-background="true">
% remove_one(X,Ys,Zs) &lt;- list Zs is list Ys without one occurrence of X
remove_one(X,[X|Ys],Ys).
remove_one(X,[Y|Ys],[Y|Zs]) :- 
        remove_one(X,Ys,Zs).
</div>

<div class="nb-cell query">
remove_one(c, [a,d,c,b,g,r], Z).
</div>

<div class="nb-cell markdown">
#### 2.
Next, adapt the predicate such that it succeeds if X does not occur in the list, and returns the original list in its third argument in this case. Hint: add a second base case.
</div>

<div class="nb-cell program">
% remove_one2(X,Ys,Zs) &lt;- list Zs is list Ys without one occurrence of X
%                         if it occurs in Ys, and Zs is Ys otherwise
% NB. Not entirely correct as it will also succeed if X occurs in Ys and Zs=Ys
remove_one2(_X,[],[]).
remove_one2(X,[X|Ys],Ys).
remove_one2(X,[Y|Ys],[Y|Zs]) :- 
        remove_one2(X,Ys,Zs).
</div>

<div class="nb-cell query">
remove_one2(c, [a,b,d,g,r], Z).
</div>

<div class="nb-cell markdown">
#### 3.
Next, adapt the predicate such that it removes all occurrences (if any) of X.
</div>

<div class="nb-cell program">
% remove_all(X,Ys,Zs) &lt;- list Zs is list Ys without any occurrences of X
% NB. Not entirely correct as it will also succeed with some occurrences of X in Zs
remove_all(_X,[],[]).
remove_all(X,[X|Ys],Zs) :- 
        remove_all(X,Ys,Zs).
remove_all(X,[Y|Ys],[Y|Zs]) :- 
        remove_all(X,Ys,Zs).
</div>

<div class="nb-cell query">
remove_all(c, [a,c,b,d,c,f,g], Z).
</div>

<div class="nb-cell markdown">
### 6.
The following predicate tests for a subset:

    % subset(Xs,Ys) &lt;- every element of list Xs occurs in list Ys
    subset([],_).
    subset([X|Xs],Ys):-
        element(X,Ys),
        subset(Xs,Ys).
</div>

<div class="nb-cell markdown">
#### 1.
Adapt the predicate such that it only succeeds if Xs is a proper subset of Ys (i.e., Ys contains at least one element not in Xs). Hint: use one of the predicates of the previous question.
</div>

<div class="nb-cell program">
% proper_subset(Xs,Ys) &lt;- every element of list Xs occurs in list Ys, and 
%                         Ys has at least one element more than Xs
proper_subset([],[_|_]).
proper_subset([X|Xs],Ys) :- 
        remove_one(X,Ys,Zs),
        proper_subset(Xs,Zs).
</div>

<div class="nb-cell query">
proper_subset([a,c], [a,b,c]).
</div>

<div class="nb-cell markdown">
#### 2.
Adapt the original predicate such that it only succeeds if every element of Xs occurs in the same order (but not necessarily contiguously) in Ys. Hint: get rid of the **element/2** call, and add a second recursive clause.
</div>

<div class="nb-cell program">
% subset_ord(Xs,Ys) &lt;- every element of list Xs occurs in the same order in list Ys
subset_ord([],_).
subset_ord([X|Xs],[X|Ys]) :- 
        subset_ord(Xs,Ys).
subset_ord(Xs,[_|Ys]) :- 
        subset_ord(Xs,Ys).
</div>

<div class="nb-cell query">
subset_ord([a,c,f], [a,b,c,d,e,f,g]).
</div>

<div class="nb-cell markdown">
### 7.
The following predicates both test for a subsequence (a contiguous set of elements):

    % subseq1(Xs,Ys) &lt;- every element of list Xs occurs in the same order and contiguously in list Ys
    subseq1(B,ABC) :-
        append(_,BC,ABC),
        append(B,_,BC).

    % subseq2(Xs,Ys) &lt;- every element of list Xs occurs in the same order and contiguously in list Ys
    subseq2(Xs,Ys):-
        append(Xs,_,Ys).
    subseq2(Xs,[_|Ys]):-
        subseq2(Xs,Ys).

Both predicates succeed several times with the empty list for queries of the form **subseq(Xs,[1,2,3,4])**. Fix this. Hint: treat the empty list as a separate case and make sure the above clauses only apply if Xs is non-empty.
</div>

<div class="nb-cell program">
% subseq1(Xs,Ys) &lt;- every element of list Xs occurs in the same order and contiguously in list Ys
subseq1([],_).
subseq1([B|Bs],ABC) :-
        append(_,BC,ABC),
        append([B|Bs],_,BC).
% subseq2(Xs,Ys) &lt;- every element of list Xs occurs in the same order and contiguously in list Ys
% NB. The first two clauses can be combined into subseq2(Xs,Ys) :- append(Xs,_,Ys)
% i.e., the original base case
subseq2([],_).
subseq2([X|Xs],Ys) :- 
        append([X|Xs],_,Ys).
subseq2([X|Xs],[_|Ys]) :- 
        subseq2([X|Xs],Ys).
</div>

<div class="nb-cell query">
subseq1([1,3], [0,1,3,4,5]).
</div>

<div class="nb-cell query">
subseq2([1,3], [0,1,3,4,5]).
</div>

<div class="nb-cell markdown">
## Pattern matching
Pattern matching is used in virtually every predicate definition to distinguish between different cases, often (but not always) base case vs. recursive case.
</div>

<div class="nb-cell markdown">
### 8.
Consider the following rules for symbolic differentiation (U, V are mathematical expressions, x is a variable):

    dx/dx = 1
    d(-U)/dx = -(dU/dx)
    d(U+V)/dx = dU/dx + dV/dx
    d(U-V)/dx = dU/dx - dV/dx
    d(U*V)/dx = U*(dV/dx) + V*(dU/dx)

These rules can easily be translated into Prolog, for instance, the third rule can be defined as

    diff(plus(U,V),x,plus(RU,RV)):-diff(U,x,RU),diff(V,x,RV).

Write the remaining rules. Here is a test query:

    ?- diff(plus(times(x,x),x),x,Result).

    Result = plus(plus(times(x, 1), times(x, 1)), 1) ;

    No

Note: Prolog has built-in functors such as +, - and * that can be used in infix or prefix notation, so the given Prolog clause can also be written as

    diff(U+V,x,RU+RV):-diff(U,x,RU),diff(V,x,RV).

Keep in mind, though, that terms such as U+V are still trees with the functor at the root, and that evaluation of such terms requires additional processing (see the next question).
</div>

<div class="nb-cell program">
diff(x,x,1).
diff(minus(U),x,minus(RU)) :-
    diff(U,x,RU).
diff(plus(U,V),x,plus(RU,RV)) :-
    diff(U,x,RU),
    diff(V,x,RV).
diff(minus(U,V),x,minus(RU,RV)) :-
    diff(U,x,RU),
    diff(V,x,RV).
diff(times(U,V),x,plus(times(U,RV),times(V,RU))) :-
    diff(U,x,RU),
    diff(V,x,RV).
</div>

<div class="nb-cell query">
diff(plus(times(x,x),x),x,Result).
</div>

<div class="nb-cell markdown">
### 9.
Write a predicate that simplifies mathematical expressions as follows:

    U*1 = U
    U+0 = U
    U+U = 2*U
    U-U = 0

Hint: most of your clauses will need to be recursive. Also add a base case that leaves the expression untouched (in case none of the cases applies), and recursive clauses that take expressions of the form U+V and return X+Y, where X is the simplification of U and Y is the simplification of V.

Here is a test query:

    ?- simp(plus(plus(times(x,1),times(x,1)),1),Result).

    Result = plus(times(2, x), 1)

Note: Most likely, you will get a variety of answers, among which the desired one. This is because your clauses are not mutually exclusive. We will see later how to achieve that.
</div>

<div class="nb-cell program">
simp(times(U,1),V) :-
    simp(U,V).
simp(plus(U,0),V) :-
    simp(U,V).
simp(plus(U,U),times(2,V)) :-
    simp(U,V).
simp(minus(U,U),0).
% Some kind of base case is needed; multiple solutions could be avoided by demanding that U is atomic
simp(U,U).
% Keep top-level the same, simplify at lower level
simp(plus(U,X),plus(V,Y)) :-
    simp(U,V),
    simp(X,Y).
</div>

<div class="nb-cell query">
simp(plus(plus(times(x,1),times(x,1)),1),Result).
</div>

</div>