\documentstyle{farticle}
\topmargin -1.5cm
\oddsidemargin 0cm
\evensidemargin 0cm
\textheight 25cm
\textwidth 17.0cm
\title{Examen final Prolog --- ESSI \\
	1993 }
\author{Michel Rueher}
\date{}

\begin{document}
\maketitle
\begin{center}
{\large Documents autoris\'es: {\bf Supports (et notes) de cours de TD}}
\end{center}	

\section{Expliquer ... ---  6 points }
Construire l'arbre de recherche pour les requ\^etes {\tt member(X,[a,b,c,d]},  {\tt member(e,[a,b,c,d]} et \\
{\tt reverse([a,b,c,d],L)}.
	{ \small
	\begin{verbatim}
member(X,[X|_]):-!.
member(X,[_|L]):-
    member(X,L).

reverse(L1,L2):- reverse(L1,[],L2).

reverse([],L,L).
reverse([T|Q],L_aux,L):-
    reverse(Q,[T|L_aux],L).
    \end{verbatim}	}


\section{Adapter ... ---  6 points }
	Modifier le programme {\tt simplify\_sum(Sum,Simplified)}, vu en TD et d\'ecrit dans l' annexe 1, pour qu'il puisse traiter une somme alg\'ebrique. \\
	Exemples :
	{ \small
	\begin{verbatim}
| ?-  simplify_sum(3+5+b-6-c,S).

S = 2+b-c
true
| ?-  simplify_sum(3-5+b-6+c,S).

S = -8+b+c
| ?- simplify_sum(11-5-6+x,S).

S = x

true
\end{verbatim}	}

\section{D\'efinir  ... ---  8 points}
\begin{itemize} 
\item	Les fameuses huit reines ---  4 points\\
	Ecrire un pr\'edicat {\tt reines(L)} qui calcule les diff\'erentes positions que peuvent prendre huits reines sur un \'echiquier sans \^etre en prise (rappel : deux reines sont en prise si elles sont sur la m\^eme ligne, la m\^eme colonne ou la m\^eme diagonale
	{ \small \begin{verbatim}	
| ?-   reines(L).

L = [1,5,8,6,3,7,2,4]

...
\end{verbatim}	}

\item	Le fameux 'self' ---  4 points\\
Ecrire un  pr\'edicat   {\tt self(X)}  qui unifie $X$ \`a la d\'efinition m\^eme de ce pr\'edicat (au renomage de variables pres). Pas d'exemple ... car il contiendrait le r\'esultat !!
\end{itemize}	

\section*{Annexe 1}
{ \small
\begin{verbatim} 
% Arithmetic expression simplifier - The Craft of Prolog/ R.A. O'Keefe

simplify_sum(Sum,Simplified) :-
    simplify_sum(Sum,TopOfTree,HoleAtBottom,0,N),
    simplify_sum1(Simplified,TopOfTree,HoleAtBottom,N).	
simplify_sum1(Simplified,TopOfTree,HoleAtBottom,N):-
    N \== 0,
    HoleAtBottom=N,
    Simplified=TopOfTree,
    !.
simplify_sum1(Simplified,TopOfTree,HoleAtBottom,N):-
    N == 0, 
    var(TopOfTree),
    Simplified=0,
    !.
simplify_sum1(Simplified,TopOfTree,HoleAtBottom,N):-
    N == 0,
    nonvar(TopOfTree),
    TopOfTree=Simplified+HoleAtBottom. 
simplify_sum(A+B,Hole0,Hole,N0,N):-!,
    simplify_sum(B,Hole0,Hole1,N0,N1),
    simplify_sum(A,Hole1,Hole,N1,N).
simplify_sum(C,Hole,Hole,N0,N):- number(C), !,
    N is N0 + C.
simplify_sum(X,Hole+X,Hole,N,N).


/* Exemples
| ?- simplify_sum(3+5,S).
  S = 8
| ?- simplify_sum(3+5+b+6+c,S).
  S = 14+b+c
| ?- simplify_sum((3+5)+b+6+c,14+b+c).
  true
| ?- simplify_sum(3+5+b+6+c,S).
S = 14+b+c


*/

\end{verbatim}}
\end{document} 