\documentclass{tpcaml}
% \includeversion{prof}
% \excludeversion{eleve}
\includeversion{eleve}
\excludeversion{prof}

\Newassociation{corrige}{Sol}{soltp1sup}
\renewcommand{\Sollabel}[1]{\textbf{\large Question #1}}

\title{TP 1 : présentation du langage \textsc{Caml}}
\begin{document}

\maketitle Vous allez, dans ce TP, découvrir le langage \textsc{Caml}. Vous
pourrez constater à cette occasion combien la manière d'écrire les
programmes est proche du langage naturel.

Exécutez les instructions en observant attentivement la syntaxe, en
essayant de prévoir ce qui va se passer. Réfléchissez sur les réponses
transmises par l'interpréteur. Retrouvez dans le mémento les
définitions données.

\begin{prof}
  Vous entrerez les commandes à exécuter après le \emph{prompt}
  \texttt{\#}. Les résultats donnés par \textsc{Caml} seront précédés du
  symbole \texttt{- :}. Ne tapez pas le dièse précédant chaque
  commande. Par contre, n'oubliez pas de terminer toutes vos commandes
  par un double point-virgule et par un appui sur \textsc{Entrée}. Si
  une commande ne tient pas sur une ligne, vous pouvez (et vous
  \textsc{devez}, par souci de lisibilité) passer à la ligne en
  appuyant sur \textsc{Entrée} et continuer à taper. \textsc{Caml} attendra le
  signal \texttt{;;} pour interpréter votre prose..
\end{prof}

\section{Calculs numériques}
Nous allons pour le moment utiliser \textsc{Caml} comme une
calculatrice. D'abord un peu de calcul sur les entiers.
\bigskip
\begin{Programme}
  \caption{opérations usuelles avec les entiers}
  \medskip  
\begin{verbatim}
  # 1 + 1;;
  # 34 * 78;;
  # 2301 / 123;;
  # 2301 mod 123;;
  # 8976 - 2345;;
\end{verbatim}
\end{Programme}

Vous remarquerez qu'après chaque commande, \textsc{Caml} renvoie non seulement
la réponse, mais reconnaît aussi son type%
\begin{prof}
  (ici le type \texttt{int}, les entiers (signés) de la machine). \textsc{Caml}
  sait effectuer les opérations usuelles sur ces entiers.  Remarquez
  que le résultat de la division est le quotient entier, pas un nombre
  réel ou fractionnaire. D'ailleurs, si \textsc{Caml} connaît un type de réels,
  il ne connaît en revanche pas les fractions. Nous essayerons de lui
  apprendre à les manipuler dans un prochain TD
\end{prof}%
.

Les réels sont représentés avec un point décimal anglo-saxon, et
utilisent éventuellement la notation scientifique. Les opérations sur
les réels sont notées \texttt{+.}, \texttt{*.}, \texttt{-.},
\texttt{/.}. :
\bigskip
\begin{Programme}
  \caption{calculs avec des réels}
  \medskip  
\begin{verbatim}
  # 10.13e-4;;
  # 1.2e3 + 3.65e-1;;
  # 1.2345 *. 6.35678 -. 2.7658;;
  # 5.45674 /. 8.6354;;
  # (2.34598 -. 5.6475) *. (4.87654 +. 6.3265) -. 1.368;;
  # exp(1) *. cos(4.56);;
\end{verbatim}
\end{Programme}

L'avant-dernière ligne vous montre un exemple de parenthèsage
d'expression. \textsc{Caml} respecte les règles classiques de priorité des
opérateurs mathématiques.
\begin{eleve}
  Corrigez les deux commandes provoquant des messages d'erreurs après
  avoir bien lu ces messages.
\end{eleve}
\begin{prof}
  Lisez bien les messages d'erreurs lorsque vous n'obtenez pas la
  réponse attendue. Ainsi, le premier message donne une indication :
  \texttt{1.2} est de type \texttt{float}, (en français \emph{nombre
    en virgule flottante} ; nous verrons ce que cela signifie dans
  l'étude des types de données), alors qu'on voudrait qu'il soit de
  type \texttt{int}. Qui le voudrait ? Le symbole \texttt{+}, bien
  sûr.  Celui-ci sait additionner des entiers, pas des réels. Quand au
  deuxième message d'erreur, il indique que \texttt{1} est de type
  \texttt{int} alors qu'on essaie de l'utiliser comme
  \texttt{float}. C'est bien sûr la fonction \texttt{exp} qui
  n'accepte que des arguments de type flottant. Pour faire comprendre
  à \textsc{Caml} que c'est un nombre réel que nous voulons passer à cette
  fonction, il suffit d'écrire \texttt{exp(1.)}.
  
  Ces contraintes au niveau du typage des données peuvent vous
  paraître plutôt gênantes pour l'instant. Il est vrai qu'on
  préférerait taper \texttt{1+exp(2)} à la place de
  \texttt{1.+.exp(2.)}. C'est à ce prix (bien léger) que la syntaxe de
  \textsc{Caml} est si proche du langage mathématique, et c'est aussi un
  excellent moyen d'éviter les confusions lorsqu'on écrit des
  programmes un tant soit peu conséquents. Vous vous y habituerez très
  vite.
\end{prof}

\section{Variables globales, locales, affectation}

Essayez le code suivant. Qu'avez-vous obtenu ? Quel est l'intérêt de
ce symbole \texttt{pi} ?
\bigskip
\begin{Programme}
  \caption{Stockage d'une constante}
  \medskip  
\begin{verbatim}
  # let pi = 3.14159265389;;
  # sin(pi);;
  # cos(pi);;
  # tan(pi /. 4.);;
  # let pi = 8;;
  # pi * 375;;
\end{verbatim}
\end{Programme}
On traduira par la suite \texttt{let a = expression} en ``soit $a$ la
variable de valeur \emph{expression}''.

\begin{prof}
  Ce symbole \texttt{pi} contient, après la première ligne, une valeur
  approchée de $\pi$, et est de type \texttt{float}. On pourra
  l'utiliser partout où on aurait pu écrire un nombre de type
  \texttt{float}. Cet état dure jusqu'à ce qu'une nouvelle définition
  (\texttt{let pi = 8}) modifie sa valeur \textsc{et} son type. De ce
  point de vue (le changement de type), \textsc{Caml} est beaucoup moins strict
  que d'autres langages.
  
  Remarquez aussi au passage le comportement de la ``calculette'' \textsc{Caml}
  face aux flottants.
\end{prof}
Une variable peut aussi être locale à un calcul. Quel peut-en être
l'utilité ?
\bigskip
\begin{Programme}
  \caption{Variables globales, variables locales}
  \medskip  
\begin{verbatim}
  # let a = 3 and b = 5;;
  # a * 3;;
  # let a = log(sin(1.2)) in
    (cos(2. *. a) -. 1.) /. (exp(3. *. a) +. 1.);;
  # let a = sin(1.35) and b = cos(2.65) in
    (a +. b) /. (a -. b);;
  # a * a + 2 * a * b + b * b
    where a = 2 and b = -1;;
  # a * a + 2 * a * b + b * b;;
\end{verbatim}
\end{Programme}

\begin{prof}
  Remarquez la construction alternative \texttt{where}. Ici, le calcul
  de $\frac{\cos(2\ln(\sin(1.2)))-1}{e^3\ln(\sin(1.2))+1}$ est
  légèrement raccourci. Mais utiliser des variables \emph{locales}
  permet surtout d'éviter de toucher à des définitions qu'on souhaite
  conserver.
\end{prof}

\texttt{let a = log(sin(1.2)) in ...} se lit ``posons $a =
log(sin(1.2))$ dans ...'', et \texttt{where} se lit ``lorsque''.
Remarquez qu'on peut enchaîner les définitions avec le mot-clé
\texttt{and}, qui se lit simplement ``et''. Facile, non ?

\section{Fonctions d'une variable}

Les fonctions jouent un rôle très important en programmation, et tout
particulièrement en \textsc{Caml}. Définissons la fonction $f:x\mapsto \ln(\cos
x)\sin x$, et testons la :
\bigskip
\begin{Programme}
  \caption{Définition et utilisation d'une fonction d'une variable}
  \medskip    
\begin{verbatim}
  # let f = function x -> log(cos(x)) *. sin(x);;
  # f(1.);;
  # f(1);;
  # f(1.5);;
  # f(3.);;
  # f(-0.5);;
\end{verbatim}
\end{Programme}

Remarquez la réponse de \textsc{Caml} à la définition de $f$, ainsi que les
messages d'erreurs. Retenez qu'une fonction associe toujours un type
de donnée à un autre type. Ceci permet au compilateur de contrôler la
validité du code.

On peut bien entendu définir une fonction localement :
\bigskip
\begin{Programme}
  \caption{Définition locale de fonctions}
  \medskip    
\begin{verbatim}
  # let h = function x -> log(sin(x)) in
    (cos(2. *. h(1.2)) -. 1.) /. (exp(3. *. h(1.2)) +. 1.);;
  # let g =
    (let f = function y -> y *. y +. 1. in
    function x -> sin(2. *. f(x)) +. cos(f(x)));;
  # g(1.);;
  # f(-0.5);;
\end{verbatim}
\end{Programme}

\begin{prof}
  Réessayez la définition de $g$ sans les parenthèses extérieures. Se
  débarrasser des parenthèses est une des préoccupations des
  concepteurs de \textsc{Caml}, pour éviter de lui donner la même réputation de
  ``brouteur de parenthèses'' de son grand frère Lisp.
  
  Essayez aussi de taper \texttt{x} à la place de \texttt{y}. Ceci
  vient de l'\emph{anonymat} de la variable utilisée pour définir une
  fonction.
\end{prof}

On peut nettement raccourcir la définition des fonctions : on dit
souvent (et abusivement), en mathématiques, \emph{posons $f(x)=x^2+1$}
plutôt que \emph{soit $f$ la fonction $x\mapsto x^2+1$}. On peut faire
de même avec \textsc{Caml} :
\bigskip
\begin{Programme}
  \caption{Définition étendue et variables muettes}
  \medskip    
\begin{verbatim}
  # let g(x) = sin(2. *. f(x)) +. cos(f(x))
    where f(y) = y *. y +. 1.;;
  # g(1.4);;
\end{verbatim}
\end{Programme}

\begin{prof}
  Nous éliminerons encore quelques parenthèses inutiles pour arriver à
  une forme très simplifiée, mais toujours lisible, ce qui est très
  important dés qu'on écrit plus de deux lignes de code.
\end{prof}
\newpage
\section{Fonctions de plusieurs variables, curryfication,
  décurryfication}

\begin{prof}
  Nous introduisons ici une méthode pour construire de nouveaux types.
  si $E$ et $F$ sont deux ensembles, on peut définir un ensemble
  noté $E\times F$ formé des couples $(x,y)$, où $x\in E$ et $y\in
  F$. Plus généralement, si $E_1,\dots,E_n$ sont des ensembles, alors
  $E_1\times\dots E_n$ est l'ensemble des $n$-uplets $(x_1,\dots,x_n)$
  où $x_1\in E_1,\dots,x_n\in E_n$.
\end{prof}

Étant donnés deux objets de \textsc{Caml} $x$ et $y$, on peut construire le
couple $(x,y)$. Plus généralement, on peut définir des
$n$-uplets. Observez les types reconnus par \textsc{Caml} 
\begin{prof}
  (toujours cette préoccupation d'éviter les parenthèses)
\end{prof}
:
\bigskip
\begin{Programme}
  \caption{Couples et $n$-uplets}
  \medskip    
\begin{verbatim}
  # let a = (2 , 5);;
  # let b = (2.567 , 5.352);;
  # let c = (2 , 5.733);;
  # let triplet = (2 , exp(1.) , 63);;
\end{verbatim}
\end{Programme}

Ceci nous permet de définir des fonctions de plusieurs variables :
\bigskip
\begin{Programme}
  \caption{Fonctions de plusieurs variables}
  \medskip    
\begin{verbatim}
  # let f = function (x,y) -> sin(x *. x +. y *. y);;
  # f(2.567 , 5.352);;
  # let g(x,y,z) = exp(x *. y *. z);;
  # g(1.2, -0.6, -1.5);;
  # let trapeze (f,a,b) = (b -. a) *. (f(a) +. f(b)) /. 2.;;
  # let f(x) = x *. x in trapeze(f,0.,2.2);;
\end{verbatim}
\end{Programme}
Les fonctions d'une ou de plusieurs variables sont des objets comme
les autres. Elles ont donc un type, par exemple \texttt{float ->
  float}. Observez celui des fonctions que nous venons de définir, en
particulier celui de la fonction trapèze.

\begin{prof}
  Cette fonction \texttt{trapeze} associe à un triplet composé d'une
  fonction de $\R$ dans $\R$ (de type \texttt{float -> float}) et de
  deux réels (de type \texttt{float}), à un triplet type
  \texttt{(float -> float) * float * float} donc, associe un réel.
  Donc elle a bien pour type \texttt{(float -> float) * float * float
    -> float}.
\end{prof}

Observez ce nouvel exemple. Le type de la fonction \texttt{add} semble
particulièrement difficile à décoder. Qu'auriez-vous plutôt écrit
comme définition ? Quant à la définition de la fonction \texttt{add3},
peut-on rêver plus simple ?
\bigskip
\begin{Programme}
  \caption{Curryfication des fonctions de plusieurs variables}
  \medskip    
\begin{verbatim}
  # let add x y = x + y;;
  # add 2 8;;
  # let add3 = add 3;;
  # add3 5;;
\end{verbatim}
\end{Programme}%
\begin{prof}
  La notation \texttt{add 2 8} doit être lue \texttt{((add 2)
  8)}. \texttt{add 2} est une fonction qui à un entier associe sa
somme avec $2$. D'où le type \texttt{int -> int -> int} de la fonction
\texttt{add}. Cette fonction est, mathématiquement parlant,
strictement équivalente à cette autre définition :
\bigskip
\begin{Programme}
  \caption{Problèmes posés par la forme non curryfiée}
  \medskip    
\begin{verbatim}
  # let add_nc(x,y) = x + y;;
  # add_nc(2,8);;
  # let add3 = add_nc 3;;
\end{verbatim}
\end{Programme}
On voit bien sur la dernière ligne les avantages de cette manière de
définir les fonctions. La fonction \texttt{add} est appelée la forme
\emph{curryfiée\footnote{du nom du logicien Haskell Curry}} de la
fonction \texttt{add_nc}, cette dernière portant le nom de \emph{forme
  non curryfiée}.
\end{prof}%
Vous vous habituerez très vite à ces simplifications. Prenez quand
même l'habitude de donner des noms de fonctions à vos fonctions, et
des noms de variables à vos variables. Il est plus agréable de lire
\texttt{trapeze racine\_carree x y} que \texttt{a b c d}. La longueur
des noms des variables n'a aucune influence sur la rapidité
d'exécution des commandes.

\section{Calculs sur les booléens}

Lorsqu'on veut juste indiquer si quelque chose est vrai ou faux, on n'a
besoin que de deux valeurs. L'ensemble des \emph{booléens} est là pour
ça :
\bigskip
\begin{Programme}
  \caption{Travail avec les booléens et les opérateurs de comparaison,
    fonctions booléennes}
  \medskip    
\begin{verbatim}
  # 0 = 0;;
  # 0 > 1;;
  # 1.56 >=. 1.27;;
  # 0 <> 1;;
  # 0.1 <> 1.53;;
  # (1 < 5) && (not(1.56 >=. 1.27) || not(0 = 1));;
  # let somme_nulle x y = (x + y = 0);;
  # somme_nulle 2 3;;
  # somme_nulle 2 (-2);;
\end{verbatim}
\end{Programme}

Les notation \texttt{\&\&}, \texttt{||} et \texttt{not} symbolisent
respectivement le \emph{et}, le \emph{ou} et le \emph{non} logique.
Nous étudierons ultérieurement ces fameux booléens.

\begin{prof}
  Remarquez les parenthèses autour de \texttt{-2} dans la dernière
  ligne. Il est conseillé de toujours bien parenthéser ces expressions
  booléennes, car les opérateurs booléens ont une faible priorité.
\end{prof}

\section{Les effets de bord}

Si vous avez jusque là pu lire les résultats du code que vous avez
tapé, c'est parce que l'interpréteur \textsc{Caml} renvoie ces résultats. Mais
dans le cas d'un programme compilé, il n'en sera rien. Nous allons
donc rencontrer ici des objets qui font \emph{réellement}
quelque chose à l'environnement.

\subsection{Les procédures}
Les procédures sont des fonctions qui ne renvoient rien. Pour cette
raison, un type spécial, nommé \texttt{unit}, est fourni par
\textsc{Caml}. Voici quelques procédures utiles :
\bigskip
\begin{Programme}
  \caption{Fonctions d'écriture à l'écran}
  \medskip    
\begin{verbatim}
  # print_int(264 + 389);;
  # print_float(power 2. 128.);;
\end{verbatim}
\end{Programme}

Notez la forme différente de la réponse de \textsc{Caml}.

\subsection{Les séquences}

On peut enchaîner les expressions, en les séparant par des
point-virgule.
\bigskip
\begin{Programme}
  \caption{Séquences d'expressions}
  \medskip    
\begin{verbatim}
  # exp(0.1); exp(2.5);;
  # print_float(exp(0.1); print_newline();
    print_float(exp(2.5); print_newline();;
\end{verbatim}
\end{Programme}

Remarquez que seule la dernière expression provoque un affichage :
\texttt{exp(2.5)} dans la première ligne, \texttt{print\_newline()}
dans la deuxième.
\begin{prof}
  Cette fonction \texttt{print\_newline} est de type \texttt{unit ->
  unit}, c'est à dire qu'elle ne renvoie rien lorsqu'on ne lui donne
  rien, tout en provoquant un changement de ligne à l'écran.
\end{prof}
Si une séquence doit être délimitée, on peut l'encadrer par les
mots-clés \texttt{begin} et \texttt{end}.

\subsection{Les références}

Il est interdit d'effectuer une définition dans une séquence
d'expression. \textsc{Caml} introduit la notion de \emph{référence}, qui est
identique à celle de pointeur en C ou en Pascal. Nous allons juste
esquisser le mécanisme, que vous découvrirez en détail par vous-même
dans le mémento et nos prochains TP.
\bigskip
\begin{Programme}
  \caption{Utilisation de références}
  \medskip    
\begin{verbatim}
  # (let x=2); exp(1.0);;
  # let n = ref 1;;
  # n;;
  # !n;;
  # n := !n +15;;
  # let x = ref 1.56743;;
  # let y = x;;
  # y := 1.27;;
  # !x;;
  # let x = ref 3.14 in
    x := !x +. 12.; x := sin(!x *. !x); x := !x /. (!x +. 1.);
    print_float(!x); print_newline();;
\end{verbatim}
\end{Programme}

La première ligne permet de constater qu'une définition ne peut avoir
lieu dans une séquence. Il faut voir la définition \texttt{let n = ref
  1} comme la définition d'une case mémoire ; \texttt{n} est l'adresse
où l'on peut trouver cette mémoire. On accède à la valeur stockée par
\texttt{!n}, et on peut modifier cette valeur avec
l'\emph{affectation} \texttt{:=}.

\begin{prof}
  Remarquons que \texttt{:=} est considéré par \textsc{Caml} comme une
  application qui à une référence vers un type donné et à un objet de
  ce type associe rien (c'est-à-dire \texttt{()}). Seul l'effet de
  bord de cette procédure est important : il consiste à modifier la
  valeur se trouvant dans la référence désignée.

  Quant à \texttt{!b}, il réalise un appel de fonction (la fonction
  \texttt{prefix !}) avec le paramètre \texttt{b}.
\end{prof}
L'exemple suivant vous montrera une différence fondamentale entre les
variables et des références :
\bigskip
\begin{Programme}
  \caption{Utilisation de références}
  \medskip    
\begin{verbatim}
  # let b = 2;;
  # let double x = b * x;;
  # let b = 145;;
  # double 3;;
  # let b = ref 2;;
  # let double_pas_correct x = !b * x;;
  # b := 145;;
  # double_pas_correct 3;;
\end{verbatim}
\end{Programme}


\section{Les structures de contrôle}
Nous allons apprendre dans cette partie à exécuter nos instructions
seulement dans certains cas.

\subsection{Les conditionnelles}

La fonction valeur absolue est définie par : $\abs{x} = 
\begin{cases}
  x & \text{si }x\ge0 \\
  -x & \text{si }x<0
\end{cases}$.

Pour simuler ce comportement, \textsc{Caml} fournit une construction ``si
... alors ... sinon ...'' :
\bigskip
\begin{Programme}
  \caption{Structure conditionnelle}
  \medskip    
\begin{verbatim}
  # let abs x =
    (if x >= 0 then x else -x);;
  # abs(-1200);;
  # abs(346);;
  # let f x =
    if x < 0 then 0
    else if x <= 5 then 2 * x
    else x * x;;
  # f(-8);;
  # f(3);;
  # f(10);;
\end{verbatim}
\end{Programme}

\subsection{Les motifs}

Les motifs généralise les expressions, et réalise en même temps la
reconnaissance de la \emph{forme} d'une expression et l'attribution
d'un nom à chacune des parties de cette expression.
\bigskip
\begin{Programme}
  \caption{Présentation d'une expression conditionnelle par cas}
  \medskip    
\begin{verbatim}
  # match expr with
        motif1 -> expr1
      | motif2 -> expr2
      | ...............
      | motifn -> exprn
\end{verbatim}
\end{Programme}

Cette expression réalisera \emph{expr1} si \emph{expr} peut être
identifiée à \emph{motif1}, ..., \emph{exprn} si \emph{expr} peut être
identifiée à \emph{motifn}.
\newpage
Construisons une fonction sous cette forme :
\bigskip
\begin{Programme}
  \caption{Utilisation des motifs}
  \medskip    
\begin{verbatim}
  # let f x =
      match x with
        0 -> 18
      | 1 -> 24
      | y -> y*y;;
  # f 0;;
  # f 1;;
  # f 2;;
  # let g x =
      match x with
        0 -> 18
      | y -> y*y;;
      | 1 -> 24
  # g 0;;
  # g 1;;
  # g 2;;
  # let h z =
      match z with
        (m,0) -> m
      | (0,n) -> -n
      | (m,n) -> m + n;;
  # h(3,0);;
  # h(0,6);;
  # h(1,7);;
\end{verbatim}
\end{Programme}

Remarquez dans le cas de la fonction $g$ que \textsc{Caml} reconnaît un motif
inutile (sans provoquer de message d'erreur). 
\begin{prof}
  Nous verrons bien d'autres exemple d'utilisation des motifs. C'est
  une des caractéristique les plus intéressantes de \textsc{Caml}.
\end{prof}

\subsection{Les boucles indexées (``pour'')}

Pour terminer cette initiation, nous allons voir deux constructions de
\emph{boucles}. On utilise ces constructions chaque fois qu'on veut
répéter une séquence d'expressions un certain nombre de fois.

Dans ce premier cas, on connaît le nombre de boucles à réaliser :
\bigskip
\begin{Programme}
  \caption{Boucles indexées}
  \medskip    
\begin{verbatim}
  # let ecris_cube m n =
      for i = m to n do
        print_int(i * i * i);
        print_newline()
      done;;
  # ecris_cube 4 8;;
  # ecris_cube 8 6;;
  # let ecris_cube_dec m n =
      for i = m downto n do
        print_int(i * i * i);
        print_newline()
      done;;
  # ecris_cube_dec 8 6;;
  # ecris_cube 4 8;;
\end{verbatim}
\end{Programme}
\newpage
\subsection{Les boucles conditionnelles (``tant que'')}

Dans ce cas, on ne connaît pas le nombre de boucles, mais on veut
réaliser une action \emph{tant que} une certaine condition est
réalisée. Voyons un exemple :
\bigskip
\begin{Programme}
  \caption{Boucles conditionnelles}
  \medskip    
\begin{verbatim}
  # let pg_puissance x y =
      let p = ref 1 in
      while !p <= y do p := !p * x done;
      !p / x;;
  # pg_puissance 2 63;;
  # pg_puissance 2 64;;
  # pg_puissance 6 5;;
  # pg_puissance 5 12345678;;
\end{verbatim}
\end{Programme}

Que fait ce programme ?
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: