\documentstyle[fancyheadings,fancybox]{article}

\input{head}

\rhead{{\em Assignment Two}}


\rhead{{\bf Assignment Two}}

\begin{center} \large\bf 
Assignment Two -- The Countries of the World \smallskip \\
out February 14, due February 23, 1993
\end{center}

The file {\bf \~finin/worlddb.pl} contains assertions that make up a
simple database about the countries of the world.  For each country,
there are predicates which give its name, area, part of the world,
monetary unit, capital, population and neighboring countries. In
addition, there are predicates which link parts of the world to larger
geo-political regions (e.g. northAfrica is in Africa which is in the
oldWorld).  The following predicates define the database.

\begin{itemize}

\item {\bf country(C)} true if C is a country (e.g. {\em country(us)}).

\item {\bf capital(X,Y)} true if the capital of country X is Y 
(e.g.{\em capital(us,washington)}).

\item {\bf cPopulation(X,Y)} true if the population of country X is Y 
(e.g. {\em cPopulation(us,211210000)}).

\item {\bf cArea(C,A)} true if the area of country C is A 
(e.g. {\em cArea(us,3615122)}).

\item {\bf currency(C,U)} true if the monetary unit used by country C is U
(e.g. {\em currency(us,dollar)}).

\item {\bf part(X,Y)} true if geo-political region X is an immediate part of
geo-political region Y (e.g. {\em part(us,northAmerica)} and
{\em part(northAmerica,america)}).

\item {\bf cNeighbors(X,L)} true if country X has the neighboring countries
given by the list L (e.g. {\em neighbors(us,[canada,mexico])}).

\end{itemize}

Write prolog predicates to solve the problems by using this database.
Hand in your code and a sample session demonstrating that the
predicates work.
\begin{enumerate}

\item Show goals which will find the smallest country in the world and
the country with the most neighboring countries (show the answers,
too).

\item Write a predicate {\bf cIn(X,L)} which is true if X is a
geo-political region and L is a list of all of the countries in that
region.  For example:
\begin{Verbatim}
  cIn(northAmerica,[us,canada,mexico])
  cIn(us,[us])
\end{Verbatim}

\item Write a predicate {\bf in(X,Y)} which is true if X is contained within Y,
where both X and Y are geopolitical regions.

\item Write the prolog predicate {\bf numberIn(X,N)} which is true if
the number of countries in geo-political region X is N.

\item Write the predicate {\bf area(X,A)} which is true if the area of
geo-political region X (not necessarily a country) is P.  

\item Write a predicate {\bf smaller(X,Y)} which is true if X and Y are
geo-political region and X has a smaller area than Y.

\item Write the predicate {\bf cPath(X,Y,P)} which is true if X and
Y are countries and P is a list of countries on some path from 
X to Y.  For example, the following should be true:
\begin{Verbatim}
  cPath(us,us,[us])
  cPath(us,mexico,[us,mexico]).
  cPath(us,guatamala,[us,mexico,guatamala]).
\end{Verbatim}

Watch out for loops!

\end{enumerate}

You will find the predicate {\em findall(X,P,L)} useful.  This
predicate is true if the set of instances of {\em X} such that {\em P}
is provable is the list {\em L}.  In procedural terms, the prolog
interpreter attempts to prove the proposition {\em P} repeatedly.
Every time it succeeds in finding a new way to prove {\em P} it
records the current binding of the term {\em X}.  When its all done,
{\em L} is bound to a list of all of these bindings for {\em X}.

For example, suppose we have the following assertions in the database:
\begin{Verbatim}
  likes(tom,beer).         likes(tom,cider).
  likes(dick,beer).        likes(jan,cider).
  likes(harry,beer).       likes(bill,cider).
\end{Verbatim}
In order to get a list of all the things that {\em tom} likes, we
can do:
\begin{Verbatim}
  ?- findall(X,likes(tom,X),S).
  X = _5,
  S = [beer,cider]
  yes
\end{Verbatim}
If we want to get a list of all things that like something in the
database, we can try this:
\begin{Verbatim}
  ?- findall(X,likes(X,_),S).
  X = _5,
  S = [bill,jan,tom,harry,dick,tom]
  yes
\end{Verbatim}
If we want to get a list of tuples of likers and likees, we can do this:
\begin{Verbatim}
  ?- findall((X,Y),likes(X,Y),S).
  X = _17,
  Y = _18,
  S = [(bill,cider),(jan,cider),(tom,cider),
       (harry,beer),(dick,beer),(tom,beer)]
  yes
\end{Verbatim}
To find all of the liked things, we can do:
\begin{Verbatim}
  ?- findall(Y,likes(X,Y),S).
  Y = _29,
  X = _30,
  S = [cider,cider,cider,beer,beer,beer]
  yes
\end{Verbatim}

The goal we try to prove inside a {\em findall} can be any arbitrary
Prolog goal, including nested findall's, conjunctions, etc.  You
should investigate two closely related built-in Prolog predicates:
{\em bagof} and {\em setof}.  Bagof differs from findall in that it
fails if the goal cannot be proven and it also treats ``free
variables'' in the goal quite differently.  A free variable is on
which occurs in the goal to be proven but not in the instance
expression (i.e., a variable in the second argument but not the
first).  Setof is like bagof except the list returned will have no
duplicates and be sorted.

\end{document}
