\documentclass{tpcaml}
\tp{1}{Premiers pas}

% TP caml à LLG, Janvier 2012
% par Gabriel Scherer
% Utilise les classes LaTeX de Victor Nicollet

\begin{document}
  \maketitle

Le but de ces TPs est de vous donner, en complément du cours de votre
professeur d'informatique, un peu de pratique de la programmation
(plus particulièrement du langage \camli). Les premières séances
seront consacrées à la découverte du langage.

\section{Introduction}

Le langage \camli{} est ce qu'on appelle un \emph{langage
  fonctionnel}. Il est assez proche, dans sa conception, des
mathématiques : assez formel, il repose sur la manipulation de
fonctions. Il est cependant très polyvalent et intègre des concepts de
nombreux langages de programmation. C'est un bon langage pour débuter.

\subsection{Utilisation du terminal}

L'interaction avec le terminal \camli\ se déroule sous la forme d'un
dialogue : l'utilisateur (ou utilisatrice) envoie une \emph{phrase}
caml, et le terminal répond. Quand le terminal attend une phrase, il
le signale en affichant un symbole \#. Pour signaler que vous avez
terminé votre phrase, vous devez la conclure par un double point
virgule.

\begin{codesection}
  \#2 + 2;;\\
  - : int = 4\\
  \#cos 0.;;\\
  - : float = 1.0 \\
  \#2 = 3;;\\
  - : bool = false\\
  \#vzjg3w;u21]3wqf<aepiju3[t;;\\
  Erreur de syntaxe.
\end{codesection}

Voyez l'exemple ci-contre : le terminal affiche le code qui lui a été
envoyé (les lignes commençant par le symbole dièse), suivi par sa
réponse (les lignes commençant par un tiret).

Les phrases envoyées ici sont toutes des \emph{expressions} (on peut
envoyer d'autres sortes de phrases, comme les déclarations que vous
verrez ensuite). Quand on lui envoie une expression, le terminal
répond en donnant son type et sa valeur, sous la forme suivante :

\code{- : \textit{<type>} = \textit{<valeur>}}

\subsection{Types des expressions}

On ne peut effectuer une opération que sur des valeurs du bon type. Quelques exemples :
\begin{itemize}
  \setlength{\itemsep}{0cm}\setlength{\parskip}{0cm}
  \item opérations qui renvoient un \code{int} (nombre entier) :
    \code{ + }\code{ - }\code{ * }\code{ / }\code{ mod} (modulo)
    \code{ int\_of\_float }
  \item opérations qui renvoient un \code{float} ($\simeq$ réels) :
    \code{ +. }\code{ -. }\code{ *. }\code{ /. }\code{ **} (puissance)
    \code{ float\_of\_int }
  \item opérations qui renvoient un \code{bool} (booléen) :
    \code{ < }\code{ <= }\code{ > }\code{ >= }\code{ = }\code{ <> }
  \item opération qui renvoie un \code{string} (texte) : \code{ $\hat{}$ }
\end{itemize}

\begin{codesection}
  (1 +  2) = 3;;\\
   1 + (2  = 3);;\\
  "Texte" + "autre texte";;\\
  exp(1.234) < 1.5;;\\
  2 * 3.141592;;
\end{codesection}
%
\begin{question}
  Examinez la liste de programmes donnée ci-contre: à votre avis, quel 
  sera le type du résultat de chacun? Lesquels comportent une erreur? 
  Pourquoi cette erreur a-t-elle lieu? Comment la corriger?
\end{question}

\paragraph{Remarque :} Vous ferez très souvent l'erreur d'utiliser une opération
ou une valeur du mauvais type. Surtout pour les flottants.

\subsection{Nommer des variables}

\begin{codesection}
  \#let pi = 3.141592;;\\
  pi :\ float = 3.141592
\end{codesection}

Voici une autre sorte de phrases : les \emph{déclarations} de
valeurs. Elles sont de la forme suivante (où \textit{<expr>} désigne
une expression quelconque) : \code{let \textit{<nom>} = \textit{<expr>}}
  
Un nom continue à désigner la valeur à laquelle il est attaché jusqu'à
ce qu'une nouvelle définition le lie à une autre valeur. Cette
modification n'a aucun effet sur les utilisations précédentes du nom,
qui conservent leur ancienne valeur.

\begin{codesection}
  let x = 1;;\\
  let y = x + x;;\\
  let x = 2;;\\
  x + y;;
\end{codesection}
%
\begin{question}
  Essayer de prévoir le résultat de la suite d'instructions ci-dessous
  sans l'exécuter, puis vérifier les prédictions à l'aide du terminal.
\end{question}

\vspace{12pt} Il est important de bien choisir les noms donnés aux
variables: \code{a}, \code{x} ou \code{bool} sont des noms qui
n'apportent pas en général d'information pertinente à un lecteur
humain. Au contraire, des noms comme \code{compteur},
\code{discriminant} ou \code{fini} donnent des informations sur
l'algorithme utilisé. Il est en général préférable d'écrire plus pour
avoir un programme plus lisible.

\section{Expressions}

Les expressions que l'on a vues jusqu'à présent étaient simples : des
constantes (\code{1}, \code{5.7}, \code{"blabla"}), des noms de
variables, et des opérations (addition, test d'égalité, etc.). On
verra ici trois sortes d'expressions plus évoluées : les fonctions,
les expressions conditionnelles et les déclarations locales.

\subsection{Fonctions}

Une fonction est une expression de la forme suivante : \hspace{12pt} \code{fun \textit{<nom>} -> \textit{<expr>}}

\begin{codesection}
  \#fun x -> x + x;;\\
  - : int -> int = <fun>\\
  \#(fun x -> x * x) 4;;\\
  - : int = 16\\
  \#let carre = fun x -> x * x;;\\
  carre : int -> int = <fun>\\
  \#carre 5;;\\
  - : int = 25
\end{codesection}
\caml\ ne connait pas de représentation textuelle pour les fonctions :
à la place de leur valeur il affiche \code{<fun>}. Le type, par
contre, est bien donné : la fonction ci-contre prend un paramètre de
type \code{int} et renvoie une valeur de type \code{int}.

Pour appliquer un argument à une fonction, il suffit de l'écrire à la
suite. Les fonctions étant des valeurs comme les autres, on peut
aussi les nommer.

\vspace{12pt}
\begin{question}
  Reprendre la fonction \code{carre} ci-dessus, et l'utiliser pour 
  écrire la fonction polynômiale $p(x) = x^2 + 2x +1$. Calculer $p(1)$ et $p(2)$.
\end{question}
\vspace{12pt}

Comme les déclarations de fonctions sont très courantes dans un
programme \caml, il existe une syntaxe spéciale qui évite de devoir
écrire \code{let f = fun x -> ...} à chaque fois; on peut écrire à la place :
\code{let f x = ...}\\
Les deux phrases suivantes sont strictement équivalentes :\\
\code{let carre = fun x -> x * x ;;}\\ \hspace{12pt} \code{let carre x = x * x ;;}

\subsection{Conditions}

Les conditions sont des expressions de la forme :
\code{if \textit{<expr>} then \textit{<expr>} else \textit{<expr>}}

\begin{codesection}
  let abs x = if x >= 0 then x else -x ;;
\end{codesection}
L'exemple ci-contre définit la fonction valeur absolue en utilisant la
position de $x$ par rapport à zéro.

\vspace{12pt}
\begin{question}
  \'Ecrire la fonction définie par:
  \[f(x) = \left\{\begin{array}{rl}
      x/2 & \mathrm{si\ }x\mathrm{\ est\ pair}\\
      3x + 1 & \mathrm{si\ }x\mathrm{\ est\
        impair}\end{array}\right.\]\end{question} 
\vspace{12pt}

\paragraph{Remarque :} L'expression conditionnelle dans son ensemble
possède, comme toutes les expressions \caml, un type. C'est aussi le
type des expressions dans les deux branches (``then'' et ``else'') de
la condition. En particulier, ces dernières doivent avoir le même type
et la phrase suivante est incorrecte :

\hspace{12pt} \code{if 2 = 3 then 2 else "toto"}


\subsection{Définitions locales}

\begin{codesection}
  \#let truc = 3+6 * 6+3 in truc / 3+1 + truc;;\\
  - : int = 57\\
  \#truc;;\\
  L'identificateur truc n'est pas défini.
\end{codesection}

Parfois, on veut nommer une valeur pour alléger les notations, mais on
n'a pas besoin de conserver la valeur pour tout le reste du
programme. On utilise alors une \emph{déclaration locale}, qui porte
seulement sur l'expression suivante, et pas tout le reste du
programme :\\
\hspace{12pt} \code{let \textit{<nom>} = \textit{<expr>} in \textit{<expr>}}

\begin{codesection}
  let double x = x + x in\\
\ \ 1 + (let a = 1 in (let b = double a in 1 + b));;
\end{codesection}

Une déclaration locale est, prise dans son ensemble, une expression
\caml\ comme les autres. En particulier, elle peut se trouver
à l'intérieur d'une fonction, et on peut mettre une déclaration locale
dans une déclaration locale.

C'est très utile, mais il faut prendre garde de ne pas écrire des
choses complètement illisibles.

\vspace{12pt}
\begin{question}
  Écrire une fonction qui donne le $n$-ième terme de la suite de
  fibonnaci en utilisant la formule suivante :
  \[ \phi = \frac{1 + \sqrt{5}}{2} \qquad u_n = \frac{\phi^n - (1 - \phi)^n}{\sqrt{5}} \]
\end{question}

\begin{codesection}
  let double x = x + x in\\
\ \  let deux\_pi = double pi;;
\end{codesection}

Attention : une déclaration locale doit être suivie par une
\emph{expression}, et non par une phrase OCaml quelconque (déclaration
de valeur, de type...). Ainsi, le code ci-contre, qui définit
\code{deux\_pi}, est incorrect.
\begin{question}
  Comment le corriger ?
\end{question}

\section{Traitement des fonctions à plusieurs paramètres}

\begin{codesection}
  \# let deux\_fois f = (fun x -> f x + f x);;\\
  \# let augmenter\_deux\_fois =\\
\ \ \ \ let augmenter n = n + 1 in\\
\ \ \ \ \ \ deux\_fois augmenter in\\
\ \ augmenter\_deux\_fois 3 ;;\\
  - : int = 8\\
  \# deux\_fois (fun n -> n + 1) 3 ;;\\
  - : int = 8
\end{codesection}

Une fonction est une valeur comme les autres. Elle peut par exemple
être passée en argument d'une autre fonction, ou renvoyée comme valeur
de retour. Ici, \code{deux\_fois} prend une fonction \code{f} en
paramètre et renvoie une autre fonction (\code{fun x -> ..}).

Si l'on fait un peu attention, on peut aussi voir \code{deux\_fois}
comme une fonction prend deux arguments, $f$ et $x$, et renvoie
$f(x) + f(x)$. On peut d'ailleurs écrire (et c'est strictement
équivalent) : \hspace{12pt} \code{let deux\_fois f x = f x + f x}.

Cette méthode permet d'exprimer des fonctions à plusieurs
arguments. On peut la généraliser à un nombre quelconque (mais fixé
à l'avance) d'arguments. Elle s'appelle la \emph{curryfication}, et
correspond à l'isomorphisme, en mathématiques, entre $(A \times B) \to
C$ et $A \to (B \to C)$.

\paragraph{Remarque :} Avec les fonctions à plusieurs arguments, on
voit apparaître des types de la forme\\ \code{int -> int -> int}. Dans
ces cas là il faut lire (la flèche est associative à droite)
\code{int -> (int -> int)}.

\begin{question}
  Écrire une fonction qui renvoie la somme de trois paramètres.
\end{question}

\paragraph{Notations}

On a déjà vu que l'on peut écrire \code{let f x = a} à la place de
\code{let f = fun x -> a}. Selon le même principe, on peut simplifier
l'écriture de fonctions à plusieurs paramètres :
\begin{itemize}
\item on peut compresser une suite de \code{fun}, par exemple
  \code{fun x -> fun y -> z} s'écrit aussi \code{fun x y -> z}.
\item on peut faire rentrer plusieurs \code{fun} dans un \code{let} :
  \code{let f = fun x y -> z} s'écrit aussi \code{let f x y = z}.
\end{itemize}

Il faut bien comprendre que ces notations représentent exactement le
même code, et savoir faire ces transformations dans les deux sens pour
raisonner sur les programmes.

\subsection{Application partielle}

\begin{codesection}
\# let somme x y = x + y;;\\
\# let somme' x = fun y -> x + y;;\\
\# let somme\_3 = somme' 3;;\\
\# somme\_3 2;;\\
- int : 5
\end{codesection}

Au risque de me répéter : il n'y a pas à proprement parler de
``fonction à deux arguments'' en Caml. Il y a par contre des fonctions
qui prennent un argument, puis renvoient une fonction qui prend un
deuxième argument et renvoie un résultat. En particulier, fournir un
seul argument à une fonction Caml est toujours défini, vous n'aurez
jamais d'erreur du style ``Vous n'avez pas fourni assez d'arguments''.

Par exemple, dans le code ci-contre, les fonctions \code{somme} et
\code{somme'} sont exactement identiques, mais la deuxième permet
mieux de comprendre ce que signifie \code{somme 3} : c'est la fonction
qui, quand on lui donne un paramètre, lui ajoute 3. On parle dans ce
cadre d'\emph{application partielle} : on a donné seulement une partie
des arguments à la fonction.


\subsection{Placement des parenthèses}

J'ai été assez surpris de constater en donnant des colles qu'une des
principales sources d'erreurs chez les élèves est le \emph{placement
  des parenthèses} en Caml. C'est regrettable, parce que ce placement
obéit à des règles très simples et logiques, qu'il suffit de
comprendre une fois pour savoir toujours où placer des parenthèses. La
source d'erreur est le fait que le placement des parenthèses en Caml
est \emph{différent} de la notation mathématique habituelle.

Les parenthèses utilisées autour des expressions n'ont \emph{pas de
  signification}. Elles servent uniquement à éliminer les ambiguités,
comme en mathématiques (différence entre $1 + 2 * 3$ et $(1 + 2) *
3$).

Pour appeler une fonction \code{f} avec un argument \code{x}, on écrit
simplement \code{f x}. Vous pouvez aussi écrire \code{(f x)},
\code{(f)x}, \code{f(x)} ou \code{(f)((x))} si cela vous fait plaisir,
mais contrairement à la notation mathématique, les parenthèses autour
du \code{x} ne sont \emph{pas} nécessaires, et je vous déconseille de
les mettre.

Le problème de la notation mathématique est son extension aux appels
de fonction à plusieurs arguments, comme par exemple \code{g x y} : on
donne à la fonction \code{g} l'argument \code{g}, puis \code{y}. Si
l'on veut être précis, on dit que l'application de \code{x} à \code{g}
renvoie une fonction (\code{g} est de la forme \code{fun a -> fun b ->
  c}), et que c'est à cette fonction qu'on applique y. On pourrait
donc aussi écrire \code{let h = g x in h y} ou \code{(g x) y}.

\begin{codesection}
  let somme x y = x + y;;\\
  somme\\
  \ \    somme somme 2 3 4\\
  \ \ somme 2 somme 3 4;;
\end{codesection}

C'est ici que la notation mathématique à laquelle vous êtes habitués
risque de vous faire faire des erreurs. \code{g x y} est équivalent
à \code{(g x) y}, mais \textbf{pas} à \code{g(x y)} ! Cette deuxième
écriture signifie qu'on applique \code{y} à \code{x}, et qu'on donne
le résultat à \code{g}. Par contre, si vous voulez écrire $f(g(x))$,
c'est bien \code{f (g x)} et pas \code{f g x} !

\begin{question}
  Rajoutez les parenthès nécessaires pour que le code ci-dessus soit
  correct.
\end{question}

\section{Quelques adresses}
  Il est possible de télécharger \camli\ à l'adresse suivante:
  \begin{center}
    \texttt{\hbox{http://caml.inria.fr/download.fr.html}}
  \end{center}
  
  Le manuel de référence en anglais, qui n'est pas vraiment adressé aux 
  débu\-tants en informatique, se trouve quant à lui sur:
  \begin{center}
    \texttt{\hbox{http://caml.inria.fr/pub/docs/manual-caml-light/}}
  \end{center}

  Ce manuel contient cependant des pages qui vous seront très utiles
  quand vous maîtriserez un peu mieux le langage, à savoir les
  descriptions des bibliothèques (l'ensemble des fonctions
  préprogrammées dans \camli). Les principales sont :
  \begin{center}
    The core library :
    \texttt{\hbox{http://caml.inria.fr/pub/docs/manual-caml-light/node14.html}}\\
    The standard library :
    \texttt{\hbox{http://caml.inria.fr/pub/docs/manual-caml-light/node15.html}}\\
  \end{center}

  Le livre ``Le langage Caml'', qui a été récemment mis en ligne en
  libre accès. Écrit par deux des concepteurs du langage, c'est un
  excellent outil d'apprentissage, qui va au delà du niveau attendu en
  classes préparatoires. N'hésitez pas à y jeter un oeil si vous
  chercher une explication alternative à un concept que vous avez du
  mal à comprendre, ou des exercices d'entraînement supplémentaires :
  \begin{center}
    \texttt{\hbox{http://caml.inria.fr/pub/distrib/books/llc.pdf}}
  \end{center}
\end{document}
