Diaporama n°13¶

Le langage OCaml - Aspects impératifs¶

I. Les fonctions "impures" ou à "effet de bord"¶

Ce sont les fonctions ou opérations, qui, en plus de renvoyer une valeur, réalisent une action (affectation, affichage, ...)

En OCaml, il n'y a que des expressions : toute opération renvoie / calcule toujours quelque chose, à minima ()

  • fonction pure (sans effet de bord) :
    • ne modifie pas l'état de la mémoire (ni ses paramètres)
    • n'interagit pas avec l'extérieur (n'affiche rien, pas d'entrée utilisateur)
    • à paramètres égaux, renvoie le même résultat
  • fonction impure (avec effet de bord) :
    • change un état mémoire
    • entrée / sortie
    • résultat aléatoire

NB : les fonctions impures ont souvent le type unit dans leur signature

Quelques fonctions à effet de bord¶

  • les fonctions d'entrée / sortie
    • affichage sur stdout
      • print_int : int -> unit, print_float : float -> unit, print_string : string -> unit
      • print_newline : unit -> unit : fin de ligne \n puis 'flush' (force l'écriture à l'écran)
      • print_endline : string -> unit : print_string puis print_newline
  • lecture sur stdin
    • read_int : unit -> int, read_float : unit -> float,
    • read_line : unit -> string : lit une ligne (caractère \n exclu du résultat).
  • (à suivre) : opérations d'affectation (référence et tableau)
In [9]:
let x = Random.float 1.0 in
let y = Random.float 1.0 in 
print_string "Un point aléatoire (";   (* ; séquence *)
print_float x;
print_string ",";
print_float y;
print_string ")";
print_newline();;

Un point aléatoire (0.987177314953,0.167445477467)
Out[9]:
- : unit = ()

NB : module Printf

  • Printf.printf format arg1 arg2 ... (cf printf en C)
  • %d %f %c %s pour afficher int float char string (comme en C)
  • %b pour afficher bool (non disponible en C)
In [10]:
let x = Random.float 1.0 in
let y = Random.float 1.0 in 
Printf.printf "Un point aléatoire (%f,%f)" x y;
print_newline();;

Un point aléatoire (0.557458,0.758517)
Out[10]:
- : unit = ()

II. Les références¶

Structure de donnée mutable

Des variables qui peuvent changer de valeur .. introduit par le mot-clé : ref

  • définition : let x = ref expr
  • type : x : T ref (avec T le type de expr)
  • affectation x := expr2 de type unit (effet de bord)
  • valeur contenue : !x de type T
In [12]:
let x = ref 3;; (* définition *)

x := !x + 1;; (* affectation *)

!x;; (* valeur contenue*)
Out[12]:
val x : int ref = {contents = 3}
Out[12]:
- : unit = ()
Out[12]:
- : int = 4

NB val x : int ref = {contents = 3}

  • on a défini une variable x de type int ref
  • sa valeur est {contents = 3} ??? cf plus tard (enregistrement à champ mutable)
In [14]:
let message = ref "un message";;

message := "un autre message";;

!message;;
Out[14]:
val message : string ref = {contents = "un message"}
Out[14]:
- : unit = ()
Out[14]:
- : string = "un autre message"

La référence est typée

In [15]:
let x = ref 0;;

x := "hello";; (* erreur *)
Out[15]:
val x : int ref = {contents = 0}

File "[15]", line 3, characters 5-12:
3 | x := "hello";;
         ^^^^^^^
Error: This expression has type string but an expression was expected of type
         int

NB : Les structures de données mutables posent le problème de l'"aliasing"

In [38]:
let x = ref 0;;

let y = x;;

y := 3;;

!x;;
Out[38]:
val x : int ref = {contents = 0}
Out[38]:
val y : int ref = {contents = 0}
Out[38]:
- : unit = ()
Out[38]:
- : int = 3

Du point de vue de la mémoire, x et y pointent vers le même emplacement, modifiable.

La modification du contenu de x modifie donc le contenu de y

III. Les structures de contrôle¶

III.1 la séquence ;¶

Pour enchaîner des "instructions" : expr1 ; expr2

Subtilités :

  • quelle est la valeur de cette expression ?

c'est la valeur de expr2

expr1 ; expr2

  • et donc, quel est son type ?

c'est le type de expr2

NB : à l'évaluation de expr1 ; expr2, la valeur de expr1 est jetée / oubliée

Le plus souvent, expr1 est de type unit

Si ce n'est pas le cas, on obtient un avertissement du compilateur

In [22]:
(* Exemple Séquence OK *)
let experience () =
    let x = Random.float 1.0 in
    let y = Random.float 1.0 in 
    Printf.printf "Un point aléatoire (%f,%f)\n" x y; (* unit *)
    x ** 2. +. y ** 2. < 1.;; (* bool *)

experience ();;
experience ();;
Out[22]:
val experience : unit -> bool = <fun>

Un point aléatoire (0.868197,0.544966)
Out[22]:
- : bool = false

Un point aléatoire (0.630258,0.078126)
Out[22]:
- : bool = true

NB : la première expression de la séquence est de type unit est inutilisée : OK

In [24]:
(* Exemple Séquence WARNING *)

let c = (4 ; 5);;

File "[24]", line 3, characters 9-10:
3 | let c = (4 ; 5);;
             ^
Warning 10: this expression should have type unit.
Out[24]:
val c : int = 5

NB : la première expression de la séquence 4 est de type int ($\neq$ unit) est inutilisée : WARNING

Ici, peut-être est-ce une erreur de frappe ?

In [1]:
let c = (4 , 5);;
Out[1]:
val c : int * int = (4, 5)

Généralisation :¶

  • expr1 ; expr2 ; expr3 ... ; exprn a pour type le type de exprn

  • si l'une des expressions expr1 ... expr(n-1) n'a pas le type unit, on obtient un avertissement

NB : cas d'usage les expressions dont le résultat est inutilisé sont en général des "effets de bord" (affichage, affectation)

In [ ]:
(* Exemple séquence multiple *)
let x = Random.float 1.0 in
let y = Random.float 1.0 in 
print_string "Un point aléatoire (";
print_float x;
print_string ",";
print_float y;
print_string ")";
print_newline();
(x, y);;
In [2]:
let x = Random.float 1.0 in
let y = Random.float 1.0 in 
print_string "Un point aléatoire (";   (* unit *)
print_float x;     (* unit *)
print_string ",";   (* unit *)
print_float y;       (* unit *)
print_string ")";     (* unit *)
print_newline();     (* unit *)
(x, y);;  (*  float * float  *)

Un point aléatoire (0.597822945853,0.866881591015)
Out[2]:
- : float * float = (0.597822945853105914, 0.866881591014789565)

III.2 Bloc begin ... end¶

Les séquences d'instructions ne sont pas toujours très visibles ...

On peut les regrouper avec des parenthèses ( expr1 ; expr2 ) (pas très visible ...)

On peut les regrouper entre begin et end (début et fin de bloc).

convention : on indente à l'intérieur du bloc¶

In [5]:
(* Exemple : begin ... ends *)
let x = Random.float 1.0 in
let y = Random.float 1.0 in 
begin
  print_string "Un point aléatoire (";
  print_float x;
  print_string ",";
  print_float y;
  print_string ")";
  print_newline();
  (x, y)
end;;

Un point aléatoire (0.559742196387,0.153847848803)
Out[5]:
- : float * float = (0.559742196386998736, 0.153847848802657422)

A RETENIR : begin ... end est indispensable lorsque les branches d'un if sont des séquences

Pourquoi ??

Complément : expression conditionnelle avec une seule branche¶

  • if cond then expr
  • contrainte de type : expr doit être de type unit
  • cette expression a donc le type unit
In [16]:
if 2 = 1 + 1 then print_endline "hello";;

hello
Out[16]:
- : unit = ()

Exemple de code ambigu

In [ ]:
if cond then
   expr1 ;
   expr2

est lu par OCaml :

In [ ]:
(if cond then expr1) ; expr2

si expr1 et expr2 sont concernés par cond, on écrira donc

In [ ]:
if cond then begin
   expr1 ;
   expr2
end
In [2]:
(* Erreur fréquente : oubli begin end *)
let compare x y = 
    if x = y then
        print_endline "Egaux";
        0
    else
        print_endline "Differents";
        1
    ;;
    
compare 2 3;;

File "[2]", line 5, characters 4-8:
5 |     else
        ^^^^
Error: Syntax error
In [5]:
(* Code correct : avec begin end *)
let compare x y = 
    if x = y then begin
        print_endline "Egaux";
        0
    end else begin
        print_endline "Differents";
        1
    end;;
    
compare 2 3;;
Out[5]:
val compare : 'a -> 'a -> int = <fun>

Differents
Out[5]:
- : int = 1
In [6]:
(* Code correct : avec begin end *)
let compare x y = 
    if x = y then begin
        print_endline "Egaux";
        0
    end else if x > y then begin
        print_endline "Supérieur";
        1
    end else begin
        print_endline "Inférieur";
        -1
    end;;
    
compare 2 3;;
Out[6]:
val compare : 'a -> 'a -> int = <fun>

Inférieur
Out[6]:
- : int = -1

A RETENIR :¶

Utiliser begin end si une branche de if contient une séquence ;¶

III.3 les boucles for¶

for ident = deb to fin do

$\quad$ expr

done

  • deb et fin de type int
  • ident : variable de boucle de type int
  • créée à deb et incrémentée automatiquement jusqu'à fin INCLUS

for ident = deb to fin do

$\quad$ expr

done

Quel typage ??

Même principe que pour la séquence, mais c'est la même "instruction" qui est répétée

  • expr de type unit (sinon avertissement)

  • et donc le type de la boucle for est unit

In [3]:
for i = 0 to 10 do
   print_int i
done;;
print_newline ();;
Out[3]:
- : unit = ()

012345678910
Out[3]:
- : unit = ()

NB : do ... done dispensent d'utiliser begin ... end

ATTENTION : pas de continue, pas de break : on utilise plutôt des exceptions (cf MPI)

Variante : boucle for "décrémentale"¶

for ident = fin downto deb do

$\quad$ expr

done

  • fin et deb inclus
In [7]:
for i = 10 downto 0 do
   print_int i;
   print_string " "
done;;
print_newline ();;
Out[7]:
- : unit = ()

10 9 8 7 6 5 4 3 2 1 0
Out[7]:
- : unit = ()

Exercice 1 (c'est pas trop tôt ...)¶

Ecrire (dans le style impératif) une fonction qui calcule $\displaystyle \sum_{k=1}^n \dfrac{1}{k}$

In [21]:
let f n =
    let c = ref 0. in
    for i = 1 to n do
        c := !c +. 1. /. float_of_int i
    done;
    !c;;
    
f 10000;;
Out[21]:
val f : int -> float = <fun>
Out[21]:
- : float = 9.7876060360443482

NB : il y a une séquence expr1 ; expr2 dans le code

NB : en style fonctionnel, on tournerait le problème de façon récursive (cf TP)

III.3 boucle while¶

while cond do

$\quad$ expr

done

Typage ?

  • cond de type bool
  • expr de type unit sinon avertissement
  • la boucle while est de type unit

Exercice 2¶

Ecrire (dans le style impératif) une fonction puiss_2_sup:int->int telle que puiss_2_sup x calcule la plus petite puissance de 2 supérieure ou égale à x

In [23]:
let puiss_2_sup x =
    let n = ref 1 in
    while !n < x do
        n := 2 * !n
    done;
    !n;;
    
puiss_2_sup 55;;
Out[23]:
val puiss_2_sup : int -> int = <fun>
Out[23]:
- : int = 64

NB : mêmes remarques que pour l'exercice 1

IV. Les tableaux 'a array¶

Les tableaux en OCaml sont homogènes, de taille fixe, mutables, polymorphes

  • homogène : tous les éléments du tableau sont de même type
  • taille fixe : une fois défini, le tableau n'est pas "extensible" (on peut créer un tableau plus grand par recopie)
  • mutable : les élements du tableaux sont modifiables
  • polymorphe : 'a array : qui signifie tableau d'éléments de type 'a

Rapplel : 'a est une variable de type, représentant un type quelconque

NB : le module Array contient beaucoup de fonctions prédéfinies.

Structure de donnée polymorphe¶

On peut définir des tableaux d'entiers, de floattants, de chaines de caractères, de tableaux, de fonctions ...

  • [| expr1; expr2 ...; exprn |] où toutes les expressions sont de type t est un t array de longueur $n$
In [7]:
let tab1 = [|2; 4; 5|];;
let tab2 = [|"hello"; "bonjour"|];;
let tab3 = [| [|1;2;1|]; [|0;4;1|] |];;
let tab4 = [|(+); (-); (/)|];;
let tabvide = [||];;
Out[7]:
val tab1 : int array = [|2; 4; 5|]
Out[7]:
val tab2 : string array = [|"hello"; "bonjour"|]
Out[7]:
val tab3 : int array array = [|[|1; 2; 1|]; [|0; 4; 1|]|]
Out[7]:
val tab4 : (int -> int -> int) array = [|<fun>; <fun>; <fun>|]
Out[7]:
val tabvide : 'a array = [||]

Opérations sur les tableaux :¶

  • creation : Array.make : int -> 'a -> 'a array (en $\mathcal{O}(n)$)
    • Array.make n v crée un tableau de taille n dont tous les éléments sont initialisés à v
  • longueur : Array.length : 'a array -> int (en $\mathcal{O}(1)$)
  • accès au i-ème élément du tableau tab : tab.(i) de type 'a (en $\mathcal{O}(1)$)
  • modification du i-ème élément du tableau tab : tab.(i) <- v de type unit (en $\mathcal{O}(1)$)

NB : les indices valides vont de 0 à n-1

NB : l'accès à un indice invalide déclenche une exception

NB En mémoire : la longueur + des éléments contigus

In [47]:
let tab1 = Array.make 10 4.;;

let tab2 = Array.make 3 "hello";;

Array.length tab1;;

Array.length tab2;;
Out[47]:
val tab1 : float array = [|4.; 4.; 4.; 4.; 4.; 4.; 4.; 4.; 4.; 4.|]
Out[47]:
val tab2 : string array = [|"hello"; "hello"; "hello"|]
Out[47]:
- : int = 10
Out[47]:
- : int = 3

NB : c'est le type du deuxième paramètre qui détermine le type du tableau

NB : la fonction length s'applique à n'importe quel type de tableau

In [9]:
(* Exemple : accès *)
let tab = [|17; 20; -5; 40|];;

tab.(0);;
Out[9]:
val tab : int array = [|17; 20; -5; 40|]
Out[9]:
- : int = 17
In [10]:
(* Exemple : accès invalide *)

tab.(4);;

Exception: Invalid_argument "index out of bounds".
Raised by primitive operation at unknown location
Called from file "toplevel/toploop.ml", line 208, characters 17-27
In [11]:
(* Exemple : modifications *)
let tab = [|17; 20; -5; 40|];;

tab.(0) <- 9;;
tab.(1) <- tab.(1) - 10;;

tab;;
Out[11]:
val tab : int array = [|17; 20; -5; 40|]
Out[11]:
- : unit = ()
Out[11]:
- : unit = ()
Out[11]:
- : int array = [|9; 10; -5; 40|]

NB : bien que polymorphe, un tableau est typé:

les éléments d'un tableau ne peuvent pas changer de type¶

In [15]:
let tab = [|33|];;
tab.(0) <- "hello";;
Out[15]:
val tab : int array = [|33|]

File "[15]", line 2, characters 11-18:
2 | tab.(0) <- "hello";;
               ^^^^^^^
Error: This expression has type string but an expression was expected of type
         int

Attention à l'"aliasing"¶

La valeur v passée à Array.make n v est "partagée" (elle n'est pas dupliquée n fois)

In [9]:
(* Code incorrect *)
let tab2D_bug = Array.make 3 [|0 ; 0|];;
Out[9]:
val tab2D_bug : int array array = [|[|0; 0|]; [|0; 0|]; [|0; 0|]|]
In [11]:
tab2D_bug.(0).(0) <- 7;;
tab2D_bug;;
Out[11]:
- : unit = ()
Out[11]:
- : int array array = [|[|7; 0|]; [|7; 0|]; [|7; 0|]|]

Attention à l'aliasing - suite¶

Pour créer un tableau à 2 dimensions :

On utilise la fonction Array.make_matrix : int -> int -> 'a -> 'a array array telle que Array.make_matrix n p v crée un tableau n lignes, p colonnes dont chaque élément est initialisé à v

In [14]:
(* Code correct *)
let tab2D = Array.make_matrix 3 2 0;;
tab2D.(0).(0) <- 7;;
tab2D;;
Out[14]:
val tab2D : int array array = [|[|0; 0|]; [|0; 0|]; [|0; 0|]|]
Out[14]:
- : unit = ()
Out[14]:
- : int array array = [|[|7; 0|]; [|0; 0|]; [|0; 0|]|]

Manipulation des tableaux¶

On a facilement accès à la longueur d'un tableau, ainsi qu'à chaque élément.

On manipule donc souvent les tableaux avec des boucles for

In [ ]:
let n = Array.length tab in 
for i = 0 to n-1 do
    ... tab.(i) ...
done

NB ou boucles while ou approche récursive

A suivre ...¶