\documentstyle[fancyheadings,fancybox]{article}

\input{head}

\rhead{{\bf Assignment One}}

\begin{center} \large\bf 
Assignment One \bigskip \\
out February 2, due February 14, 1993
\end{center}

This assignment is intended to be a very simple one which will give
you an opportunity to get your feet wet with Prolog.  You should
review chapter eight in the {\em SICStus Prolog User's Manual} which
provides a terse introduction to Prolog as well as Chapters One (How
to run Prolog) and Two (Debugging).  You may want to consult the book
{\em Programming in Prolog} by Clocksin and Mellish, which provides a
good introduction to Prolog.  

\section{Append - Warm Up Exercise}

This is just to help those who are very new to Prolog get started.
Define the append predicate by typing the clauses directly into the
Prolog interpreter.  Figure \ref{fig:example} shows a sample session
with Sicstus Prolog.  The first line ({\em [user].}) tells Prolog to
{\em consult}, or read new clauses to be added to the database, the
user.  That is, clauses will be read from the terminal and added to
the database.  The next two lines are the two clauses that will define
{\em append/3} (i.e., a predicate named {\em append} with three
arguments).  The (control-D) is how one signals an {\em ``end of
file''} to the Prolog reader.  In this case it causes the Prolog
reader to stop {\em ``consulting the user''}.  Note that the periods
at the end of the first three lines are required.

Now try to append the list {\em [a,b,c]} to the list {\em [1,2,3]} by
typing in the goal {\em append([a,b,c],[1,2,3],X).}.  If this is
successful, the binding for the variable {\em X} will be displayed and
the interpreter will wait for you to type a carriage-return
(indicating that you want no more answers) or a semi-colon (indicating
you want to to seek another answer).  To help you understand how this
definition of {\em append} works, you can cause the interpreter to
trace the append predicate by issuing the command {\em
trace(append/3)}.  This will cause the interpreter to print
informative messages when it is executing append/3.  Note that it
pauses whenever the predicate is called, typing an $h$ will show the
possible responses and typing a carriage-return will cause it to
continue (``creep'').

Now try some other ways to use your append predicate. 

Show what happens when you ask Prolog to solve each of the following goals
\begin{enumerate}
\item append([a,b,c],X,[a,b,c,d,e,f]).          
\item append(X,[d,e,f],[a,b,c,d,e,f]).          
\item append(X,Y,[a,b,c,d,e,f]).
\item append(X,[d,e,f],Y).
\item append(X,Y,Z).
\end{enumerate}

\begin{figure} \small
\begin{boxed}
\begin{Verbatim}
SICStus 2.1 #6: Mon Dec 14 18:09:19 EST 1992
| ?- [user].
| append([],X,X).
| append([Head|Tail],X,[Head|Rest]) :- append(Tail,X,Rest).
| ^D {user consulted, 0 msec 480 bytes}

yes
| ?- append([a,b,c],[1,2,3],X).

X = [a,b,c,1,2,3] ? 

yes

| ?- trace.
{The debugger will first creep -- showing everything (trace)}

yes
{trace}
| ?-  append([a,b],[c,d],X)
     .
   1  1  Call: append([a,b],[c,d],_97) ? 
   2  2  Call: append([b],[c,d],_276) ? 
   3  3  Call: append([],[c,d],_405) ? 
   3  3  Exit: append([],[c,d],[c,d]) ? 
   2  2  Exit: append([b],[c,d],[b,c,d]) ? 
   1  1  Exit: append([a,b],[c,d],[a,b,c,d]) ? 

X = [a,b,c,d] ? 

yes
\end{Verbatim}
\end{boxed}
\label{fig:example}
\caption{A sample session using Sicstus Prolog}
\end{figure}

\newpage

\section{Set manipulations}

Suppose we chose to represent sets of objects in Prolog as lists.
We could define the predicate {\em union/3} as follows:
\begin{example}
union([],Set,Set).
union([X1|Rest1],Set2,Union) :-
  union(Rest1,Set2,Union),
  member(X1,Union).
union([X1|Rest1],Set2,[X1|Union]) :-
  union(Rest1,Set2,Union),
  \+ member(X1,Union).
\end{example}
For this definition,
\begin{enumerate} \compact
\item Does this program work correctly if the first two arguments are
instantiated and the third is not?
\item What happens if we try the goal {\em union(X,[1,2,3],[1,2,3,4,5])}?

\item Write a predicate {\em intersection(S1,S2,S3)} which is true if
the intersections of the two sets S1 and S2 is equal to the set S3.
You can assume that the arguments will be well formed sets (i.e. lists
of ground terms without duplicates) and that the first two arguments
will always be instantiated.
\end{enumerate}


\section{Kinship Relationships}

This problem will give you some experience designing a simple logic
programming database in terms of primitive facts and rules. The domain
is one we are all familiar with - kinship relations.

Our western-European culture considers a number of kinship relations
to be especially meaningful and gives them names.  Other cultures have
developed a much richer set of relationships.  Most of these relations
can be defined in terms of a small number of primitive relations and
attributes, such as those having to do parenthood, marriage, gender,
age, etc.  Your task is to: 

\cb

\bu Choose a set of primitive relationships to encode as facts that
will allow you to define the rest of the relations as rules.

\bu Test out your database design be entering the facts about your own
immediate family and trying out each of the relations.

\bu Hand in a listing of your database (facts and rules), and a sample
run showing a query for each predicate defines.
\eb

The relationships you must define are the following:
\cb \small
\bu {\em child(X,Y)} - true if X is a child of Y.
\bu {\em daughter(X,Y)} - true if X is a daughter of Y. 
\bu {\em parent(X,Y)} - true if X is a parent of Y. 
\bu {\em mother(X,Y)} - true if X is the mother of Y. 
\bu {\em sibling(X,Y)} - true if X and Y are siblings (i.e. have the same
biological parents).  Be sure your definition does not lead to one
being one's own sibling.
\bu {\em brother(X,Y)} - true if X is a brother of Y. 
\bu {\em grandparent(X,Y)} - true if X is a grandparent of Y. 
\bu {\em grandmother(X,Y)} - true if X is a grandmother of Y. 
\bu {\em uncle(X,Y)} - true if X is an uncle of Y. Be sure to include uncles
by marriage (e.g. your mother's  husband) as well as uncles
by blood (e.g. your mother's brother).
\bu {\em sister-in-law(X,Y)} - true if X is a sister-in-law of Y. 
\bu {\em mother-in-law(X,Y)} - true if X is a of Y. 
\bu {\em spouse(X,Y)} - true if X and Y are married.
\bu {\em wife(X,Y)} - true if X is the wife of Y.
\bu {\em ancestor(X,Y)} - true if X is a direct ancestor of Y (i.e. a parent
or an ancestor of a parent).
\bu {\em descendant(X,Y)} - true if X is a descendant of Y (i.e. a child or an
ancestor of a child).
 \bu {\em relative-by-blood(X,Y)} - true if X is a blood relative of Y
(i.e. related through some combination of offspring relations).  Hint:
your blood relatives are just those people with whom you share a
common ancestor.
\bu {\em relative(X,Y)} - true if X and Y are related somehow (i.e.
through some combination of offspring and marriage relations).  Hint:
this is easy to define in terms of relative-by-blood and spouse!
\bu {\em male(X,Y)} - true if X is male.
\eb 

The goal is to devise a good representation -- one that is intuitive
and natural and would be easy to extend.  You may need to (or want to)
define other relations, e.g., a gender/2 relation.  Watch out for
``loops'', or, more accurately, unterminating recursion.  For example,
you do not want a rule like {\tt spouse(X,Y) :- spouse(Y,X)}.

\section{Extra Credit}

This is an optional problem.  Study the following popular American (I
think) folk song.  Try to model it with the predicates you developed
in the previous problem and any extensions that are necessary.  Do you
reach reach the same conclusion as the singer?

\begin{quote} \small

Many, many years ago when I was seventeen,\\
I was married to a widow who was pretty as could be.\\
This widow had a grown up daughter who had hair of red.\\
My father fell in love with her and soon they, too, were wed.

\medskip

This made my dad my son-in-law and it changed my very life.\\
For my daughter was my mother though she was my father's wife.\\
To complicate the matter, even though it brought me joy,\\
I soon became the father of a bouncing baby boy.

\medskip

This little baby then became a brother-in-law to Dad.\\
And so became my uncle, though it made me very sad.\\
For if he was my uncle then it also made him brother.\\
To the widow's grown up daughter who, of course, was my stepmother.

\medskip

Father's wife then had a son who kept them on the run,\\
And he became my grandchild 'cause he was my daughter's son.\\
My wife is now my mother's mother and it makes me blue,\\
Because, although she is my wife, she's my grandmother, too.

\medskip

And if my wife is my grandmother, I am her grandchild,\\
And every time I think of it, oh, it nearly drives me wild.\\
For now I have become the strangest case you ever saw\\
As husband to my grandmother, I am my own grandpaw,... oh ...

\medskip

I am my own grandpaw.\\
Yes, I am my own grandpaw.\\
It sounds funny, I know,\\
But it really is so.\\
I am my own grandpaw.
\end{quote}

\end{document}
