\chapterimage{enrico}
\chaptertext{\og  Ah   c'qu'elles  sont  jolies  les   filles  de  mon
  pays\fg{}  chantait  \href{http://youtu.be/JIyzddijozw}{Enrico  Macias}.  Comme  lui,  vous  allez  être
  subjugué(e) par  la beauté de Haskell,  qui est un des  langages les
  plus  célèbres de  la  programmation fonctionnelle.  Il  ne sera  pas
  gênant de  l'explorer en parallèle  de votre apprentissage du  C car
  les  concepts   sont  extrêmement  différents  et   il  faudra  bien
  cloisonner ces deux langages: rien de pire que d'essayer de traduire
  du  C en  Haskell  ou  vice-versa. Nous  allons  apprendre à  penser
  différemment en nous plongeant dans un monde pur et élégant...} 

\chapter{Compter sur Haskell}



\begin{quote}
  {\large  \itshape  The  main  idea  is to  regard  a  program  as  a
    communication to human beings rather than as a set of instructions
    to a computer.}
  \begin{flushright}
    {\small
D. E. \textsc{Knuth}. "Literate Programming (1984)" in Literate Programming. CSLI, 1992, p. 99
}
  \end{flushright}
\end{quote}



\vspace{-1cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{curry}
\caption{Haskell \textsc{Curry}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


Haskell  Brooks  \textsc{Curry}  (1900-1982) est  un  mathématicien
  américain dont l'influence  en informatique a été telle que  trois langages de
  programmation portent son nom: Haskell, Brooks et Curry...

  Il a fait partie de cette génération  qui a lancé les fondements de la logique
  et  de l'informatique:  Alonzo \textsc{Church},  Alan \textsc{Turing},  Steven
  \textsc{Kleene}.




  Ses travaux  sur la logique combinatoire  sont les fondements du  langage de
  programmation fonctionnel   Haskell   créé dans les  années 1990 et qui  nous servira
  de support à  nos travaux informatiques qui vous permettront  tout au long des
  deux années à  venir de vous familiariser avec  la programmation fonctionnelle
  dont  le  rôle  est  de  plus   en  plus  important  dans  le  monde
  informatique.


\vspace{-0.7cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{turing}
\caption{Alan \textsc{Turing}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}

Puisque nous sommes à l'Université,  nous pourrions commencer ce cours
en disant que  les langages \og à la  V\textsc{on Neumann}\fg{} (comme
C, Python, Java, etc.) sont basés sur les concepts de
variable  et   d'instruction.  Ces  concepts   sont  assez  intuitifs   car  ils
correspondent à de  nombreuses situations \og de la vie  de tous les jours\fg{}:
nous agissons sur et en fonction de notre environnement immédiat.
Nous portons le même nom mais nous changeons d'aspect, de taille, de poids,...Ce modèle
dérive des  travaux de  \textsc{Turing} et  de sa  machine universelle  dans les
années 1930.  D'autres mathématiciens ont  proposés des modèles différents  à la
même  époque:  le  $\lambda$-calcul   d'Alonzo  \textsc{Church},  les  fonctions
récursives  de  Stephen  \textsc{Kleene},  la logique  combinatoire  de  Haskell
\textsc{Curry}.


Ces trois derniers  modèles n'utilisent pas le concept de  machine et de mémoire
de  \textsc{Turing} mais  uniquement de  valeur,  de calcul  d'autres valeurs  à
partir de fonctions qui sont elles-mêmes des valeurs.




Mmmmmm...Ça y est,  tout le monde est perdu. Il  va falloir changer de
stratégie.  Bon, revenons  un  peu  en arrière,  en  cette rentrée  en
Sixième où vous n'étiez pas  encore adolescent mais un(e) jeune enfant
spontané(e) et heureux(se)...


\section{Collège}


Pour votre goûter d'anniversaire vous confectionnez 3 sacs de 9 fraises Tagada
et de 5 nounours: combien y a-t-il de bonbons en tout?

Vous traduisez le problème en calcul:

\vspace{-1.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{kleene}
\caption{Stephen \textsc{Kleene}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}

$
3×(9 + 5)\\
⇒ 3×14\\
⇒ 42
$

mais vous  auriez pu  compter d'abord  le nombre  total de  fraises et
celui de nounours:

$ 
3×(9 + 5)\\
⇒ 3×9 + 3×5\\
⇒ 27 + 3×5\\
⇒ 27+15\\
⇒ 42
$

Ce qu'il  faut bien  remarquer, c'est qu'on  obtient le  même résultat
dans chaque cas.  Pour une même entrée $ 3×(9+5)$, on a la même résultat
42.  C'est ce  qu'on attend  d'une \textbf{fonction}  et c'est  un des
aspects de la \textit{pureté} de Haskell. 

Bon, et  maintenant, que se  passe-t-il si  vous avez deux  invités de
plus  à votre  anniversaire?  Ou si  vous avez  plus  de nounours  que
prévus?

Vous pouvez recommencer le calcul: $5× (9+5) $ ou bien vous pouvez
\textit{généraliser} le  problème. Vous pouvez créer  une fonction qui
calcul  le nombre  de bonbons  quelque  soit le  nombre d'invités,  de
fraises Tagada et de nounours.




\subsection*{Aparté technique}

En C vous feriez:

\ce

\begin{lstlisting}
#include <stdio.h>

int bonbons(int,int,int);

void main(void)
{ int x,y,z,b;

  printf("Entrez le nombre d'invités: ");
  scanf("%d" , &x);
  printf("Entrez le nombre de fraises Tagada par paquets: ");
  scanf("%d" , &y);
  printf("Entrez le nombre de nounours par paquets: ");
  scanf("%d" , &z);
  b = bonbons(x,y,z);
  printf("Le nombre total de bonbons est %d \n", b);
}

int bonbons(int x, int y, int z){ 
    return x*(y + z);}
\end{lstlisting}



Puis on compile et on exécute:

\shell

\begin{lstlisting}
$ gcc -o bonbons bonbons.c 
$ ./bonbons
Entrez le nombre d'invités: 3
Entrez le nombre de fraises Tagada par paquets: 9
Entrez le nombre de nounours par paquets: 5
Le nombre total de bonbons est 42 
\end{lstlisting}

\haskell

En Haskell, on va plutôt écrire dans GHCi:

\begin{lstlisting}
λ> let f x y z = x*(y + z)
λ> f 3 9 5
42
\end{lstlisting}

ou, pour être plus explicite:

\begin{lstlisting}
λ> let bonbons invites fraises nounours = invites*(fraises + nounours)
λ> bonbons 3 9 5
42
\end{lstlisting}

ou dans un fichier bonbons.hs

\begin{lstlisting}
{- fonction calculant le nombre de bonbons selon
   le nombre d'invités, de fraises Tagada et de nonours -}
bonbons invites fraises nounours =
    invites*(fraises + nounours)

main = print  (bonbons 3 9 5)
\end{lstlisting}

qu'on peut compiler:


\shell

\begin{lstlisting}
$ ghc bonbons.hs -o bonbons 
[1 of 1] Compiling Main             ( bonbons.hs, bonsons.o )
Linking bonbons ...
$ ./bonbonsHs 
42  
\end{lstlisting}

mais dans  un premier temps  nous nous contenterons de  travailler via
GHCi donc nous aurons une fenêtre avec  à gauche notre fichier hs et à
droite GHCi. Dans Emacs,  il suffit de taper C-c C-l  ou de charger le
fichier avec  la commande  \texttt{:l} (load) ou  \texttt{:r} (reload)
dans GHCi

\haskell

\begin{lstlisting}
λ> :l ./bonbons.hs
Ok, modules loaded: Main.
λ> bonbons 3 9 5
42
λ> bonbons 5 2 3
25
\end{lstlisting}

Bon, on s'éloigne du sujet. Ce ne sont là que des détails d'utilisation.

\begin{aparte}
  Avoir pour  seul but  l'apprentissage d'un langage  de programmation
  n'a  que  peu d'intérêt.  Apprendre  un  langage pour  résoudre  des
  problèmes va notablement accroître vos capacités intellectuelles.

  Programmer, ce  n'est pas  connaître la  syntaxe tout  comme peindre
  n'est pas savoir  bouger un pinceau, connaître  l'alphabet n'est pas
  être écrivain....et faire des mathématiques ne
  consiste pas seulement à calculer des dérivées...
\end{aparte}

\subsection*{Retour à l'essentiel}

Que se passe-t-il  (à peu près...) quand nous  tapons \texttt{bonbons 3
  9 5}?

D'abord  il  faut  comprendre  que  dans \texttt{bonbons  x  y  z}  et
\texttt{bonbons 3  9 5}, les  rôles joués  par \texttt{x, y,  z} d'une
part et \texttt{3, 9, 5} de  l'autre sont différents.

Il y  a d'abord une phase  d'\textit{expansion} (ou \textit{unfolding:
  dépliage}) de la définition de la fonction. 

On substitue  aux \textit{paramètres}  formels \texttt{x,  y, z}  les \textit{arguments}
(ou paramètres effectifs) \texttt{3, 9, 5}.

Ensuite \texttt{9+5} est \textit{réduit} en 14.

Plus     précisément     l'\textit{expression}    \texttt{9+5}     est
\textit{évaluée} en \texttt{14}.

\begin{NB}
  On  appelle en  Haskell les  \og  choses\fg{} que  l'on calcule  des
  \textit{expressions} et les \og  choses\fg{} qui résultent du calcul
  des \textit{valeurs}: on ne peut plus les réduire.

Par exemple, $ 9+5$ est une expression et $ 14$ une valeur. Mais $ 14$
est aussi une expression... Toute  valeur est une expression (car tout
est expression...) mais toute expression n'est pas une valeur.

En  fait,   une  expression,  c'est   ce  qu'on  rentre  devant  le
\textit{prompt} $  \mathtt{λ}>$ et  une valeur,  c'est ce  que renvoie
GHCi:

\begin{lstlisting}
λ> 9 + 5
14
λ> 14
14
λ> bonbons 3 9 5
42
\end{lstlisting}

Il y  a parfois des expressions  qui entraîne une infinité  de calculs
comme $ x=x+1$:

$ 
x\\
⇒ x+1\\
⇒ (x+1)+1\\
⇒ ((x+1)+1)+1\\
...
$

Cette  expression  \textit{diverge}.  Comme  toute  expression  a  une
valeur, on lui donne quand même un nom: $ \bot$ qui se lit \og antitruc\fg{}.
\end{NB}


\subsection*{Preuve des propriétés d'un programme}

La somme de deux entiers a une propriété bien connue: quelque soit les
nombres $ a$ et $b$, alors $ a+b=b+a$. On dit alors que l'addition des
entiers est \textit{commutative}.


Est-ce  que  par  hasard,  la  fonction  \texttt{bonbons}  aurait  une
propriété similaire?


Il  est  assez simple  de  démontrer  que  \texttt{bonbons  x y  z}  =
\texttt{bonbons x z y}.

\medskip
$ 
\mathtt{bonbons}\ x\ y\ z\\\
⇒ x*(y+z) \ \{\mathit{expansion}\}\\
⇒ x*(z+y)\ \{\text{\it commutativité}\}\\
⇒ \mathtt{bonbons}\ x\ z\ y\ \ \{\text{\itshape réduction}\}
$
\medskip
La dernière étape  est rarement accomplie par  un langage informatique
mais cela n'empêche pas un(e) informaticen(ne) de l'accomplir.

\section{Opérateurs}

On  reste au  collège. On  s'intéresse à  l'évaluation des  opérations
arithmétiques sur machine (voir \vref{exo::infixe}).



Le rôle des parenthèses est le plus souvent primordial  sur machine:



\begin{lstlisting}
λ> 5 + 4*3
17
\end{lstlisting}

et ce quelque soit le langage car des règles de priorité ont été établies.


Sinon, des parenthèses auraient dû être mises:

\begin{lstlisting}
λ> 9 / 2 + (-3)*4 - (-5)
-2.5
λ> 9 / ((2 + (-3)) * (4 - (-5)))
-1.0
\end{lstlisting}


Or dans  un calcul plus compliqué,  ne pas se soucier  des parenthèses
peut entraîner de mauvaises surprises.

Il est sûrement plus clair de visualiser le calcul à l'aide d'un arbre


\begin{center}
\begin{tikzpicture}
[edge from parent fork down,
every node/.style={fill=blue!30,rounded corners},
edge from parent/.style={blue,thick,draw},level 1/.style={sibling distance=4.5cm},
level 2/.style={sibling distance=2.5cm},
level 3/.style={sibling distance=1.4cm}]
\node{$/$}
    child{node[fill=white]{$9$}}
    child{node{$\times$}
       child{node{$+$}
       child{node[fill=white]{$2$}}
       child{node{$-$}
            child{node[fill=white]{$3$}}}
       }
       child{node{$-$}
       child{node[fill=white]{$4$}}
       child{node{$-$}
            child{node[fill=white]{$5$}}}
       }
};
\end{tikzpicture}
\end{center}



L'usage  du $-$  est  ici ambigu:  cet opérateur  est  parfois binaire,  parfois
unaire.  Pour éviter  ce problème,  on peut  par exemple  utiliser des  symboles
différents:




\begin{center}
\begin{tikzpicture}
[edge from parent fork down,
every node/.style={fill=blue!30,rounded corners},
edge from parent/.style={blue,thick,draw},level 1/.style={sibling distance=4.5cm},
level 2/.style={sibling distance=2.5cm},
level 3/.style={sibling distance=1.4cm}]
\node{$/$}
    child{node[fill=white]{$9$}}
    child{node{$\times$}
       child{node{$+$}
       child{node[fill=white]{$2$}}
       child{node{$\lnot$}
            child{node[fill=white]{$3$}}}
       }
       child{node{$-$}
       child{node[fill=white]{$4$}}
       child{node{$\lnot$}
            child{node[fill=white]{$5$}}}
       }
};
\end{tikzpicture}
\end{center}


On réduit alors l'arbre en remontant des feuilles vers la racine:






\begin{center}
\begin{tikzpicture}
[edge from parent fork down,
every node/.style={fill=blue!30,rounded corners},
edge from parent/.style={blue,thick,draw},level 1/.style={sibling distance=4.5cm},
level 2/.style={sibling distance=2.5cm},
level 3/.style={sibling distance=1.4cm}]
\node{$/$}
    child{node[fill=white]{$9$}}
    child{node{$\times$}
      child{node{$\lnot$}
        child{node[fill=white]{$1$}}
      }
      child{node[fill=white]{$9$}
      }
    };
\end{tikzpicture}
\end{center}


puis




\begin{center}
\begin{tikzpicture}
[edge from parent fork down,
every node/.style={fill=blue!30,rounded corners},
edge from parent/.style={blue,thick,draw},level 1/.style={sibling distance=4.5cm},
level 2/.style={sibling distance=2.5cm},
level 3/.style={sibling distance=1.4cm}]
\node{$/$}
    child{node[fill=white]{$9$}}
    child{node{$\lnot$}
      child{node[fill=white]{$9$}}
    };
\end{tikzpicture}
\end{center}

et finalement $\lnot 1$.


À  partir  de  l'arbre,  on   obtient  donc  une  \textit{séquence}  de  lecture
\textit{infixée} en \textit{profondeur}:

$$
9/((2+\lnot 3)\times (4- \lnot 5))
$$

L'emploi  des  parenthèses  agit  comme une  sorte  de  \textit{retardateur}  de
l'évaluation.


Comment une machine évalue une telle expression? 

Il s'agit d'abord d'étudier la \vref{exo::asso}.

\begin{definition}[Associativité]
  
  Soit $\star$ un opérateur quelconque défini sur un ensemble quelconque
  E. 
  
  On dit que l'opérateur $ \star$ est \textbf{associatif} sur E
  si, et seulement si, pour tout triplet $(x,y,z)$ d'élements de E on a:
  
  $$(x\star y)\star z = x \star (y \star z)$$
  
\end{definition}

Et voici  une définition  proche qui concerne  plutôt les  langages de
programmation:

\begin{definition}[Associativité à droite (à gauche)]
  
  Avec les  mêmes notations que  la définition précédente,  un opérateur
  est \textbf{associatif à droite} si, et seulement si:
  
  $$x\star y\star z=x\star (y\star z) $$
  
  et  \textbf{associatif à gauche} si, et seulement si:
  
  $$x\star y\star z = (x\star y) \star  z$$
  
\end{definition}

\section{Notation polonaise}

\vspace{-0.5cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{lukasiewicz}
\caption{ Jan   \textsc{\L  ukasiewicz}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}
En   1920,   le   mathématicien-logicien-philosophe  polonais   Jan   \textsc{\L
  ukasiewicz} (1878-1956) invente  la  notation  préfixée   alors  qu'il  est  ministre  de
l'éducation (on a le droit de rêver...).

35 ans  plus tard, le philosophe  et informaticien (!) australien  (!!!) Charles
\textsc{Hamblin} (1922 - 1985) s'en inspire.

Il a en effet en sa possession  l'un des deux ordinateurs présents à l'époque en
Australie. Il  se rend compte  que la saisie de  calculs avec les  opérateurs en
notation  infixée  induit   de  nombreuses  erreurs  de  saisie   par  oubli  de
parenthèses.  Il pense  aussi  à la  (très petite)  mémoire  des ordinateurs  de
l'époque.

% \end{minipage}
% \setindent{0cm}

%\piccaption{Charles \textsc{Hamblin} \\ (1922-1985)}
%\parpic[r]{ \includegraphics[width=2.5cm]{hamblin}}



Il trouve alors  son inspiration dans le travail de  \textsc{\L ukasiewicz} pour
éviter les parenthèses et il
 pense à mettre les opérateurs en position préfixée:
ainsi  il   introduit  la   notion  de   \textit{pile}  (ou   \textit{stack}  ou
\textsc{Lifo}) qui économise le nombre d'adresses mémoire nécessaires.


C'est  la  naissance de  la  Notation  Polonaise  Inversée  (NPI ou  RPN).  Elle
économise également la taille des composants électroniques des portes logiques.

Son seul inconvénient:  les mauvaises habitudes prises  d'utiliser des notations
infixées...




Un  autre  grand avantage:  il  faut  comprendre  le calcul  avant  de
l'exécuter :-)


\subsection*{Pile: découverte}


Une pile  (en anglais  \textit{stack}) est une  structure de  données permettant
l'insertion d'un élément et la suppression du dernier élément inséré.

L'acronyme anglais associé est LIFO (\textit{Last In First Out}).

Alan   \textsc{Turing}   proposa   dès   1945  les   termes   \textit{bury}   et
\textit{unbury} pour désigner les deux méthodes basiques de traitement des piles.

On utilise en français \textit{empiler} et \textit{dépiler} alors que les termes
anglais actuellement utilisés sont \textit{push} et \textit{pop}.

Imaginez une partie de cartes qui nécessite  une pioche. La seule carte qui nous
intéresse est celle du dessus. Piocher une  carte consiste à retirer la carte du
dessus  et  à la  lire  (dépiler)  ou rajouter  une  carte  \textit{sur} le  tas
(empiler).
 Toute information supplémentaire est superflue.

De nombreuses  situations sont similaires en  informatique et....\textit{dans la
  vraie vie}.

D.E. \textsc{Knuth} propose cette illustration (page 240 de \cite{knuth:vol1})





%\begin{figure}
\begin{center}
  \includegraphics[height=6cm]{trainKnuth}
\end{center}
%\end{figure}


qui  reprend l'article  fondateur de  E.W. \textit{Dijkstra}  (\cite{dij:shunt})
dont nous reparlerons bientôt:


%\begin{figure}
\begin{center}
  \includegraphics[width=\linewidth]{shuntingDijkstra}
\end{center}
%\end{figure}


Mais bon, on utilise le terme \textit{pile} en référence à un pile d'assiette: la
première que l'on saisira sera la dernière à avoir été empilée.


\subsection*{Pile et NPI}

Reprenons notre expression $9/((2+\lnot 3)\times (4- \lnot 5))$. 

La plupart des compilateurs vont plutôt la lire ainsi: \verb|9 2 3 NEG + 4 5 NEG - * /|
en utilisant une pile.

Il faut juste  connaître l'\textit{arité} de chaque opérateur,  i.e. leur nombre
d'opérandes, qui  doit être fixe  (c'est pourquoi on doit  absolument distinguer
\verb+-+ de \verb+NEG+ et  éviter l'habituelle \textit{surcharge} de l'opérateur
\verb+-+).

\begin{enumerate}
\item On lit l'expression de gauche à droite;
\item On empile les opérandes;
\item   Dès qu'on
lit un  opérateur, on l'applique  aux opérandes présents  sur la pile  selon son
arité;
\item On s'arrête quand on n'a plus rien à lire;
\item on renvoie le dernier élément présent dans la pile.
\end{enumerate}

Voici  par  exemple les  différentes  étapes  du  calcul  effectué à  l'aide  du
\textit{calculator} d'Emacs:


\emacs

\begin{multicols}{3}
\begin{enumerate}
\item On entre \verb+9+ , \verb+2+ puis \verb+3+:

\begin{lstlisting}
 Emacs Calculator Mode 
3:  9
2:  2
1:  3
.
\end{lstlisting}

\item \verb+NEG+
\begin{lstlisting}
 Emacs Calculator Mode 
3:  9
2:  2
1:  -3
.
\end{lstlisting}

\item \verb|+|

\begin{lstlisting}
 Emacs Calculator Mode 
2:  9
1:  -1
.
.
\end{lstlisting}


\item \verb|4| puis \Enter


\begin{lstlisting}
 Emacs Calculator Mode 
3:  9
2:  -1
1:  4
.
\end{lstlisting}

\item \verb|5| puis \Enter


\begin{lstlisting}
 Emacs Calculator Mode 
4:  9
3:  -1
2:  4
1:  5
\end{lstlisting}


\item \verb|NEG|


\begin{lstlisting}
 Emacs Calculator Mode 
4:  9
3:  -1
2:  4
1:  -5
\end{lstlisting}


\item \verb|-|


\begin{lstlisting}
 Emacs Calculator Mode 
3:  9
2:  -1
1:  9
.
\end{lstlisting}

\item \verb|*|


\begin{lstlisting}
 Emacs Calculator Mode 
2:  9
1:  -9
.
.
\end{lstlisting}

\item \verb|/|


\begin{lstlisting}
 Emacs Calculator Mode 
1: -1
.
.
.
\end{lstlisting}

\end{enumerate}

\end{multicols}



Plusieurs avantages:

\begin{itemize}
\item pas besoin de parenthèses, de règles d'associativité, de priorité;
\item on voit au sommet de la pile les résultats intermédiaires;
\item le calcul est directement implémentable sur machine.
\end{itemize}


Au collège, $9/((2+\lnot 3)\times (4- \lnot 5))$ serait lu: 

\begin{center}

\og le \textit{rapport} entre
9   et   le   \textit{produit}   de  la   \textit{somme}   de   2   et
l'\textit{opposé}  de  3   et  la  \textit{différence}  de   4  et  de
l'\textit{opposé} de 5\fg{} 

\end{center}

ce qui peut se coder en:

\begin{center}
  \verb| / 9 * + 2 NEG 3 - 4 NEG 5|
\end{center}

\haskell

C'est la méthode introduite en 1929 par Jan \textsc{\L ukasiewicz}. On a dénommé
\textit{notation polonaise}  cette méthode d'évaluation d'une  expression en son
honneur. On utilise également  la dénomination \textit{notation pré-fixée}. Cela
explique aussi l'appellation \textit{notation polonaise inversée} de la notation
post-fixée.


Ici aussi,  les opérateurs doivent être  d'arité fixe et l'évaluation  se fait à
l'aide d'une pile.


\vfill
\eject
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\modeexercice
\section{RECHERCHES}

\begin{exercice}[Encore des bonbons]

  \begin{enumerate}
  \item Détaillez toutes les étapes  de l'évaluation de l'expression $
    {\rm bonbons }\ ({\rm bonbons\ 2\ 3\ 4\ }) 5\ 6 $
  \item Démontrez comme fait dans le cours que $ {\rm bonbons}\ (a-b)\ a\
    b$ est évaluée par $ a^2-b^2$.
  \end{enumerate}
  
\end{exercice}


\begin{exercice}[Opérateur?]\label{exo::infixe}
  \illmpl{Derrière le symbole \texttt{+} se cache en fait une fonction. Elle a
  la caractéristique de se placer entre ses paramètres (on dit qu'elle
  est en position \textit{infixée}) et d'être
  symbolisée  par un  caractère  non alphanumérique.  On a  l'habitude
  d'appeler une telle fonction  un \textit{opérateur}. Par exemple, on
  aurait pu définir la fonction suivante: \lstinline{plus a b = a + b}.\\
En  fait,  ce n'est  pas  la  peine sur  Haskell  car  on peut  placer
l'opérateur en position \textit{préfixée}  en entourant l'opérateur de
parenthèses
}{operator}{0.7}{0.25}

\begin{lstlisting}
λ> (+) 3 4
7
λ> (+) ((-) 3 4) ((*) 2 7)
13
\end{lstlisting}

En fait, la position préfixée  correspond à la lecture de l'expression
arithmétique:

\og La somme de 3 et de 4\fg{}

\og La  somme de la  différence de 3  et de 4 et  du produit de  2 par
7\fg{}.

Écrivez l'expression suivante en notation infixe:

$$ (5+4+(2-(3-(6+4*5))))*(3*(6-2)*(2-7))\qquad(E)$$

Comment l'évalueriez-vous sous cette forme si vous étiez une machine?

En  fait, on  peut créer  ses propres  opérateurs du  moment que  l'on
n'utilise pas de symbole alphanumérique ni de caractères d'échappement
ni l'apostrophe qui est considérée comme alphanumérique.

\begin{lstlisting}
λ> let (<+>) x y = x + 2*y
λ> 3 <+> 5
13
\end{lstlisting}

Remplacez tous les + par des <+> dans l'expression (E) et évaluez-la.



\end{exercice}


\begin{exercice}[\textit{Benchmark} des évaluations]
Le chemin menant une expression à sa valeur n'est pas toujours le même
selon les langages.

Nous allons en distinguer trois: l'évaluation par valeur et l'évaluation par nom
et l'évaluation par besoin. 

Dans le  cas de l'évaluation  par valeur,  on évalue d'abord  les arguments
puis  on \og  déplie\fg{} la  fonction: \textit{on  va de  l'intérieur
  vers l'extérieur.}

Dans l'évaluation par nom, on déplie d'abord la fonction puis on évalue ses
arguments: \textit{on va de l'extérieur vers l'intérieur.}

Prenons un exemple. Soit les fonctions:
$ 
\mathtt{carre}\ x = x*x
$ 
et 
$
\mathtt{somC} (x,y) = \mathtt{carre}\ x + \mathtt{carre}\ y
$ 

Que se passe-t-il lors de l'appel de \texttt{somC (3,2+2)}?

\begin{description}
\item[évaluation par valeur] on réduit d'abord les arguments:

$ 
\mathtt{somC}\ (3,2+2)\\
\mathtt{somC}\ (3,4)\\
\mathtt{carre}\ 3 + \mathtt{carre}\ 4\\
3*3 + \mathtt{carre}\ 4\\
9 + \mathtt{carre}\ 4\\
9+4*4\\
9+16\\
25
$
\item[évaluation par nom] on déplie d'abord la fonction:

$
\mathtt{somC}\ (3,2+2)\\ 
\mathtt{carre}\ 3 + \mathtt{carre}\ (2+2)\\
3*3 + \mathtt{carre}\ (2+2)\\
9+\mathtt{carre}\ (2+2)\\
9+(2+2)*(2+2)\\
9+4*(2+2)\\
9+4*4\\
9+16\\
25
$

\item[évaluation par besoin] comme l'évaluation par nom ici.


\end{description}

Il est  temps de passer à  un petit test comparatif.  Mettez une croix
dans la colonne  qui correspond à l'évaluation la plus  rapide pour évaluer
les expressions proposées en considérant les fonctions:

$$\mathtt{schmox}\ (a,b) = a*a, \qquad \mathtt{bolos} = \mathtt{bolos}$$

\begin{center}
  \begin{tabular}[h]{|l|c|c|c|}
    \hline
    expression&APV&APN&idem\\
    \hline
    \texttt{schmox}\ (7, 8)&&&\\
    \hline
    \texttt{schmox}\ (3+4, 8)&&&\\
    \hline
    \texttt{schmox}\ (7, 2*4)&&&\\
    \hline
    \texttt{schmox}\ (3+4, 2*4)&&&\\
    \hline
    \texttt{schmox}\ (7, bolos)&&&\\
    \hline
    \texttt{schmox}\ (bolos, 8)&&&\\
    \hline
  \end{tabular}
\end{center}


Proposez  un  théorème  du  style: \og  si  l'évaluation...  termine  alors
l'évaluation.... aussi\fg{}. Que se passe-t-il pour la réciproque?



\begin{lstlisting}
λ> let bolos = bolos
λ> let schmox (a,b) = a*a
λ> schmox (3, bolos)
9
\end{lstlisting}


\end{exercice}






\begin{exercice}\label{exo::asso}
  
Bon,  d'abord une  question:  pourquoi  Haskell ne  se  trompe pas  en
calculant    \lstinline{5+4*3}?     Et    même     d'ailleurs    avec
\lstinline{5+4+3}, il manque des parenthèses...

Et que pensez-vous de ceci:

\begin{lstlisting}
λ> let double x = x + x 
λ> double 2 * double 5
40
λ> 2 + 2 * 5 + 5
17
\end{lstlisting}

et de ça:

\begin{lstlisting}
λ> (3 - 2) - 5
-4
λ> 3 - (2 - 5)
6
λ> (3 / 2) / 5
0.3
λ> 3 / (2 / 5)
7.5
\end{lstlisting}

et de cela:

\begin{lstlisting}
λ> 2 ** (3 ** 4)
2.4178516392292583e24
λ> (2 ** 3) ** 4
4096.0
\end{lstlisting}

sachant  que   \lstinline{**}  est   l'opérateur  des   puissances  de
flottants.


\end{exercice}



\begin{exercice}[récréation]

Proposez  des  expressions  infixes,  postfixes,  prefixes,  faites-les
traduire  par  votre voisin(e),  faites  des  remarques, proposez  des
méthodes de traduction et gardez vos notes: vous vous en servirez pour
programmer tout ça....
\end{exercice}

\begin{exercice}[]

Décomposez le calcul \verb| / 9 * + 2  NEG 3 - 4 NEG 5|. Comment l'organiser sur
machine?  Comparez avec  la  NPI.  Expliquez alors  le  choix  fait par  Charles
\textsc{Hamblin} d'utiliser plutôt la NPI sur machine.
\end{exercice}




\begin{exercice}[snake operator]

Python, langage très sexy et à la mode, dispose d'une bibliothèque \texttt{operator} comprenant
quelques fonctions usuelles.
  \pythonc

\begin{lstlisting}
In [1]: from operator import add,mul

In [2]: mul(add(2, mul(4, 6)), add(3, 5))
Out[2]: 208
\end{lstlisting}

C'est infixe? Postfixe ? Autre ?

Comment la machine peut évaluer cette expression?

Il faut savoir comment Python procède.

\begin{lstlisting}
In [9]: def fst(c):
   ...: return c[0]
   ...: 

In [10]: fst((1,2))
Out[10]: 1

In [11]: fst((1,1/0))
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-11-707229f26363> in <module>()
----> 1 fst((1,1/0))

ZeroDivisionError: division by zero
\end{lstlisting}


Tout le monde ne fait pas pareil, vous êtes déjà au courant:

\haskell

\begin{lstlisting}
λ> let fst (a,b) = a
λ> fst (1,2)
1
λ> fst (1,1/0)
1
\end{lstlisting}



Dresser   un  arbre   d'expression   qui   traduit  l'évalutation   de
\texttt{ mul(add(2, mul(4, 6)), add(3, 5))} en Python et en Haskell.


\end{exercice}






\modenormal
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "PolyMD1_14"
%%% End: 
