\documentclass[10pt]{tpcaml}

% TP caml à LLG, Début Février 2010
% par Gabriel Scherer
% Version modifiée des colles de Victor Nicollet

\tp{3}{Programmation impérative, bibliothèque, tris\\ }

\begin{document}

  \maketitle

\section{Programmation impérative}

Nous allons maintenant récapituler rapidement les aspects
``impératifs'' de \camli : boucles (\code{for}, \code{while}) et
champs modifiables (références, tableaux...). J'ai choisi de vous
présenter tout ça seulement après la programmation récursive parce que
c'est quelque chose que vous utilisez trop souvent\footnote{Malheureux
  héritage de la programmation Maple, peut-être ?}, alors que les
solutions sans boucles et sans références sont parfois plus simples et
plus lisibles.

Je vous en parle maintenant parce qu'il arrive que ce soit la bonne
solution, mais attention, ça ne veut pas dire qu'à partir de
maintenant, vous devez vous en servir tout le temps !

\subsection{Champs modifiables}

En \caml, les variables ne sont pas \emph{modifiables} : une fois
qu'une variable a été déclarée par un \code{let}, sa valeur ne change
pas (jusqu'à la déclaration suivante). Comme en mathématiques : vous
n'écrivez jamais dans une copie ``et maintenant n vaut n+1'' !

Les informaticiens, contrairement aux mathématiciens, ont parfois
besoin de \emph{modifier} des valeurs (mais on peut s'en
passer). Il existe donc plusieurs objets du langage \caml permettant
de faire cela.

Références : si \code{'a} est un type \caml, \code{'a ref}
désigne le type des \emph{références} contenant une valeur de type
\code{'a}. On peut voir une référence \code{x} comme un tiroir : on
peut l'ouvrir pour regarder à l'intérieur (c'est \code{!x}), on voit
un objet de type \code{'a}, ou bien changer son contenu pour y mettre
la valeur \code{v} (\code{x := v}).

\begin{codesection}
let test =\\
\ \ let a, b = ref 1, ref 2 in\\
\ \ let c, d = a, ref a in\\
\ \ a := !a + !b; d := c; !(!d) + !a;;
\end{codesection}

Pour créer une nouvelle référence, on utilise la fonction \code{ref}
en lui donnant une valeur de départ (la valeur que contiendra le
tiroir avant que son contenu ne soit modifié). Attention à la
subtilité : quand on utilise l'opérateur \code{:=}, on change le
\emph{contenu} de la référence, pas la référence elle-même (qui
désigne toujours le même tiroir) !

\begin{codesection}
  let a, b = ref 1, ref 1;; let c = a;;\\
  let test1 = (a = b, a == b);;\\
  b := 2;;\\
  let test2 = (a = b, a == c);;
\end{codesection}

\begin{question}
  Quelle est la valeur de la variable \code{test} ?
\end{question}

\vspace{12pt}

\begin{question}
  Que valent les variables \code{test1} et \code{test2} ? Que fait l'opérateur \code{==} ?
\end{question}

\vspace{12pt} 

Les cases des tableaux et des chaînes de caractères sont aussi des
champs modifiables : \code{tab.(i)} et \code{str.[i]} permettent
d'obtenir la valeur en i-ème position (en partant de 0) du tableau
\code{tab} et de la chaîne \code{str}. Pour les modifier on n'utilise
pas ``\code{:=}'' mais ``\code{<-}'' : \code{tab.(i) <- v}.

Les enregistrements (types produits utilisant la syntaxe
\code{\{ ... \}}) peuvent avoir certains champs modifiables, si c'est
précisé à la déclaration par le mot-clé \code{mutable} :\\
\code{type 'a reference = \{mutable contents : 'a\};;}

On peut alors modifier le champ avec la syntaxe \code{x.champ <- v}.

\vspace{12pt}

\begin{question}
  On peut redéfinir les références en partant des champs
  modifiables. Définir \code{get} (pour \code{!}), \code{set} (pour
  \code{:=}) et la fonction \code{new\_ref} (pour \code{ref}) en
  utilisant le type \code{reference} défini au dessus.
\end{question}

%références, tableaux, enregistrements
\subsection{Boucles}

Sans surprise :\\
\code{for <nom> = <expr1> to <expr2> do <expr3> done} : faire
  parcourir les entiers de \code{expr1} à \code{expr3} à la variable
  \code{nom} en évaluant \code{expr3} pour chaque valeur\\
\code{while <expr1> do <expr2> done} : évaluer \code{expr2} tant que le booléen \code{expr1} vaut \code{true}

\vspace{12pt}

\begin{question}
  Utiliser le crible d'eratosthène pour calculer la somme des nombres
  premiers entre $0$ et $10^6$.
\end{question}

\subsection{Exceptions}

Les exceptions sont une manière d'interrompre une partie d'un
programme en cas d'erreur. Par exemple, si vous avez une grosse
formule mathématique à calculer, et qu'en plein calcul vous vous
apercevez que vous devez diviser 0, vous allez vous arrêter et vous
plaindre que la formule n'est pas bien définie. \camli sait faire
pareil.

\begin{codesection}
  \#exception Erreur of string;;\\
  let boum () = raise (Erreur "boum");;\\
  try (boum (); "message") with\\
  | Exit -> "sortie"\\
  | Erreur message -> "erreur : " \^ message\\
  | \_ -> "exception inconnue"
\end{codesection}

Les expressions sont des objets de type \texttt{exn} qui ressemblent
beaucoup aux types sommes définis dans le précédent TP : ce sont des
constructeurs, qui peuvent comporter des arguments, et sont déclarés
par le mot-clé \texttt{exception}.

Quand on a trouvé une erreur, on peut \emph{lancer} une expression
avec la fonction \texttt{raise} : elle prend une expression en
paramètre, et interromp le calcul (en particulier, tout ce qui devait
se passer ensuite dans le programme n'est pas exécuté).

Cela permet de faire des erreurs qui stoppent complètement le
calcul. Parfois, on voudrait plutôt détecter l'erreur et utiliser une
solution adaptée pour continuer le programme (par exemple si l'erreur
est ``plus de papier dans l'imprimante'', il suffit de demander
à l'utilisateur de rajouter du papier avant de continuer, au lieu
d'annuler complètement l'impression en cours). On peut
\emph{rattrapper} une exception avec la construction \texttt{try
  <expr> with <filtrage>}. Cela se présente un peu comme un
\texttt{match .. with}, mais le comportement est différent :
\begin{itemize}
\item si l'évaluation de \texttt{<expr>} ne provoque aucune exception, on renvoie sa valeur
\item sinon, on effectue le filtrage sur la valeur de l'exception envoyée
\end{itemize}

\begin{codesection}
  let existe element tableau =\\
\ \    let i, trouve = ref 0, ref false in\\
\ \    while not !trouve \&\& !i < vect\_length tableau do\\
\ \ \ \      trouve := tableau.(!i) = element;\\
\ \ \ \      incr i\\
\ \    done;\\
\ \    !trouve\\
\end{codesection}

Plusieurs exceptions sont prédéfinies en \camli (vous les trouverez
dans le manuel, module \texttt{exc}). Vous rencontrerez (et/ou
utiliserez) sans doute entre autres \texttt{Exit}, qui permet
simplement de sortir d'un calcul, et \texttt{Failure of string} qui
permet d'indiquer la cause de l'erreur. On peut aussi utiliser la
fonction \texttt{failwith} qui lance \texttt{Failure}, et est définie
ainsi :
\code{let failwith str = raise (Failure str)}

\vspace{12pt}

\begin{question}
  Réécrire la fonction \texttt{existe} pour utiliser une boucle
  \texttt{for}, sans parcourir plus d'éléments du tableau.
\end{question}

\vspace{12pt}

\begin{question}
  Quel est le type de \texttt{raise} ? Pourquoi ?
\end{question}


\subsection{Dangers}
\begin{codesection}
let nouvelle\_matrice n p x =\\
\ \ make\_vect n (make\_vect p x);;\\
let mat = nouvelle\_matrice 3 3 0;;\\
 mat.(0).(1) <- 2; mat;;
\end{codesection}

On veut créer un tableau à deux dimensions, sans utiliser\footnote{ça forge le caractère} la fonction déjà toute faite \code{make\_matrix}.

\vspace{12pt} 

\begin{question}
  Quel est le problème avec \code{mat} ?\\
  Coder (correctement) \code{nouvelle\_matrice} avec une boucle.\\
  Coder \code{nouvelle\_matrice} avec \code{init\_vect}.\\
  Coder \code{nouveau\_pave} qui crée un tableau en trois dimensions.
\end{question}

\section{Boite à outils}

Vous avez globalement vu l'ensemble des concepts \camli dont vous
aurez besoin. Voici maintenant quelques \emph{bibliothèques}, des
ensembles de fonctions déjà existantes (vous en avez déjà rencontrées
plusieurs) qu'il est parfois utile de pouvoir utiliser sans les
recoder.

Pour s'informer, la meilleure solution est d'aller consulter la section du manuel :
http://caml.inria.fr/pub/docs/manual-caml-light/

Dans cette partie, vous aurez besoin de consulter la documentation. Si
vous n'avez pas d'accès internet, c'est le moment de se plaindre.

Les fonctions de ces bibliothèques sont organisés dans des
\emph{modules} thématiques. Par exemple le module \code{list} contient
toutes les fonctions pour manipuler des listes.

On distingue deux types de modules :
\begin{itemize}
\item les modules ``core'' : les fonctions des modules du core sont accessibles directement par leur nom, par exemple \code{map} dans le module \code{list}
\item les modules ``standard'' : les fonctions des modules standards
  doivent être préfixées par le nom du module : pour appeler la
  fonction \code{init} du module \code{random}, on utilise
  \code{random\_\_init}. Notez le \emph{double} underscore.
\end{itemize}

\begin{codesection}
  random\_\_init ();;\\
  \#open ``random'';;\\
  init ();;
\end{codesection}
Il est possible de se passer du nom du module en préfixe en utilisant
une directive \#open. Dans la suite du code il suffit alors de mettre
le nom des fonctions du module, comme pour les modules cores.


\subsection{stack, queue}

\texttt{stack} contient des fonctions pour manipuler des \emph{piles}
(premier entré dernier sorti), et \texttt{queue} des \emph{files}
(premier entré premier sorti). Ces structures de données se manipulent
de façon impérative.

\begin{question}
  Écrire des fonctions de conversion de pile en liste (et
  réciproquement) et de file en liste (idem).
\end{question}

\subsection{set, map}

\texttt{set} et \texttt{map} sont des structures de données plus
sophistiquées, qui permettent de stocker des éléments et d'y accéder
rapidement (en un temps logarithmique). \texttt{set} représente un
ensemble (on peut mettre des éléments et se demander des éléments sont
dedans) et \texttt{map} une table d'association : comme un tableau, mais
au lieu d'indexer par un entier on peut indexer par n'importe quel
type dont on sait comparer les éléments.

Pour faire des tables d'association, on peut aussi utiliser le module
de tables de hachage \texttt{hashtbl}. Il est plus adapté aux
contextes impératifs, et \texttt{map} aux contextes
fonctionnels/récursifs (sans modification de valeurs).

\vspace{12pt}

\begin{question}
  Écrire une fonction qui ajoute les entiers de 0 à 10000 dans une
  liste, puis teste pour chaque entier de 0 à 10000 s'il appartient
  à la liste.

  Faire de même avec un \texttt{set}, et comparer les temps
  d'exécution.
\end{question}


\vspace{12pt}
\begin{question}
  La complexité exponentielle de la version naïve de fibonnaci vient
  du fait que la fonction est rappellée un grand nombre de fois avec
  les mêmes arguments. On peut l'optimiser naïvement de la manière
  suivante : on crée une fonction fibonacci qui se ``souvient'' des
  réponses qu'elle a déjà donné : si on lui demande la valeur en un
  nombre pour la première fois, elle calcule le résultat et le stocke
  dans un ``cache'' (une \texttt{map}), et ensuite elle redonne
  directement le résultat calculé. Implémenter une telle fonction
  fibonnaci optimisée.
  
  Implementer une fonction \texttt{memoize : ('a -> 'b) -> ('a -> 'b)}
  qui est capable de ``mettre en cache'' n'importe quelle fonction (on
  utilisera pour créer la \texttt{map} la fonction de comparaison
  générique \texttt{compare}).
\end{question}

\subsection{random}


\begin{question}
  Écrire une fonction qui permute aléatoirement tous les éléments d'un
  tableau.
\end{question}

\subsection{printf}

\begin{codesection}
\#open "printf";;\\
printf "\%d$\backslash$n" 5;;\\
printf "J'ai \%d \%ss !$\backslash$n" 5 "pomme";;
\end{codesection}

Printf est un module d'affichage polyvalent. Il est aussi pratique que
sa documentation est indéchiffrable.

\vspace{12pt}

\begin{question}
  Aller lire, et essayer de comprendre une partie de, la documentation
  du module \texttt{printf}.  
  Que fait la fonction \texttt{sprintf} ?
\end{question}

\section{Questions difficiles}

\begin{question}
  Écrire une fonction \texttt{finie} qui renvoie vrai si et seulement
  si la liste passée en argument est de longueur finie (et qui termine
  dans tous les cas, bien sûr).
\end{question}

\vspace{20pt}

On essaiera dans cette partie de définir des fonctions récursives sans
utiliser le mot-clé \texttt{rec}. C'est inutile en \caml, mais cela
repose sur des idées intéressantes, et ce n'est pas facile.

\subsection{Dé-récursifier}

On travaillera sur l'emblématique fonction \texttt{fac} :
\code{let rec fac n = if n = 0 then 1 else n * fac (n - 1)}

On définit la fonction \texttt{fix} suivante :
\code{let rec fix f = fun x -> f (fix f) x}

\vspace{12pt}

\begin{question}
  Écrire une fonction non récursive \texttt{fac\_derec} telle qu'on puisse définir \texttt{fac} ainsi :
  \code{let fac = fix fac\_derec;;}
\end{question}

\vspace{12pt}

\texttt{fac\_derec} représente une version ``dérécursifiée'' (sans
appel récursif) de \texttt{fac}. On peut systématiquement
dérécursifier les fonctions récursive, et retrouver le comportement
initial en utilisant \texttt{fix}.

On a ici séparé deux choses : le corps de la fonction (qui effectue le
vrai calcul) et l'application de la récursivité (qui est reléguée
à \texttt{fix}, qui est elle-même définie en utilisant
\texttt{rec}). On cherche maintenant à écrire d'autres versions de
\texttt{fix}, qui font la même chose sans utiliser \texttt{rec}.

\subsection{Récursion par effet de bord}

\begin{question}
  Écrire une version de \texttt{fix} utilisant des références.

  Voici un squelette de code à compléter :\\
  \code{\ \ \ \ let fix f = let res = ref (fun \_ -> hd []) in ... ; !res}
\end{question}

\subsection{Récursion par type récursif}

\vspace{12pt}

\begin{question}
  On définit les fonctions suivantes :\\
  \code{\ \ \ \ let auto x = x x}\\
  \code{\ \ \ \ let fix f = auto (fun x -> f (auto x))}

  Montrer en utilisant un papier et un stylo, et en faisant les
  réductions à la main, que \code{fix f = f (fix f)}.

  Pourquoi ça ne marche pas en \camli ?
\end{question}

\vspace{12pt}

\begin{question}
  L'astuce est d'utiliser un \emph{type récursif}.
  
  Utiliser le type suivant pour définir une version ``qui marche'' de \texttt{auto} :\\
  \code{\ \ \ \ type 'b auto = Auto of ('b auto -> 'b)}

  Pourquoi a-t-on choisi cette définition du type \texttt{'b auto} ?
\end{question}

\vspace{12pt}

\begin{question}
  Définir correctement (en utilisant \texttt{auto}) le \texttt{fix} de la question 16. Tester avec \texttt{fac}.\\
  Utiliser plutôt \code{let fix f = auto (fun x -> f (fun y -> auto x y))}.
\end{question}

\end{document}
