I. Principes de base : référence vs valeur, mutable vs immuable

Ces principes sont valables autant en Python qu'en OCaml.

a) Valeurs

On va voir un ordinateur comme un processeur accompagné d'une mémoire.

La mémoire, c'est un peu comme une grande armoire, où sont rangées toutes les valeurs de vos variables. Quand le processeur a besoin de faire un calcul sur une valeur, il la sort de l'armoire, fait ce qu'il a à faire, et la remet.

a = 3 + 4
c = a

Mais le processeur, par défaut, n'est pas très organisé ! Il ne retient pas où sont rangés les objets. Donc si on change de "contexte", il oublie tout ! Par exemple, en entrant dans une fonction...

def plop(a):
    a = 9

a = 3
plop(a)
print(a)

Il se souvient qu'il a un 3 sur lui en entrant, mais il a complètement oublié où allait le 3 original ! Il est donc incapable de le modifier.

En OCaml, on interdit au processeur d'écrire dans les variables directement : comme ça, pas d'ambiguïté.

b) Références

Parfois, on aimerait bien modifier des variables, même dans des fonctions... Il y a donc des mécanismes pour ça : les références.

Le principe, c'est qu'au lieu de donner la valeur directement, on donne sa localisation dans la mémoire. Comme ça, même si le processeur la prend pour faire des calculs avec, il saura où la ranger ensuite !

Des objets fonctionnant sur ce principe, vous en connaissez : les listes et les dictionnaires en Python, les tableaux et les tables de hachage en OCaml. Comme ce sont des objets très gros, le processeur ne peut pas prendre toute la valeur de l'objet d'un coup : il retient juste où sont stockés les éléments !

En Python, les références sont implicites. C'est un peu confus, mais globalement, il n'y a que les listes et les dictionnaires qu'on peut modifier depuis une autre fonction. En particulier, les tuples ne sont pas modifiables : on ne peut donc pas les modifier depuis une autre fonction !

En OCaml, on peut faire des références explicites, c'est-à-dire qu'on dit à OCaml "ceci est une référence, laisse-moi la modifier s'il te plaît", et il est d'accord. On peut :

• créer une référence en ajoutant juste ref devant une valeur ;
• modifier la valeur dans une référence avec := (et non simplement = !) ;
• accéder à la valeur dans une référence avec !.

let a = ref 0;;
a := 3;;
a;;
!a;;

let rec compter n = match n with
    | 0 -> ()
    | n -> a := !a + 1; compter (n-1);;

compter 5;;
!a;;

Globalement, il suffit de retenir ces deux lignes :

let a = ref 0;;
a := !a + 1;;

Au passage, on a deux fonctions incr et decr qui permettent d'ajouter et d'enlever 1 à une référence d'entier. Ainsi, a := !a + 1 devient incr a.

On peut faire une référence de n'importe quoi ! Par exemple, une référence de liste, d'arbre, etc.

c) Instruction vs expression

En informatique, on distingue souvent les expressions des instructions. En Python, la distinction est assez claire : une instruction, c'est une ligne entière. Une expression, c'est quelque chose qui a une valeur.

a = 1 + max(2, 3)

Ici, on a une instruction, et 1 + max(2, 3) est une expression. Une instruction peut être simplement composée d'une expression : par exemple, un appel de fonction.

En OCaml, c'est un petit peu plus compliqué : en vérité, on a uniquement des expressions, mais on appelle instructions les expressions qui renvoient (), c'est-à-dire le type unit (en gros, rien). Par exemple :

• tableau.(i) <- 3, pour mettre une valeur dans un tableau ;
• print_string "bonjour", et les fonctions d'impression ;
• a := 8, les assignations de références ;
• et toutes les fonctions qui renvoient unit.

La particularité des instructions, c'est qu'on peut mettre un ; après, ce qui permet d'enchaîner sur d'autres instructions. Tout à la fin de la suite d'instructions, on peut mettre une expression, qui sera "renvoyée" en quelque sorte. Par exemple :

let b = (a := 3; 3);;

On a une instruction a := 3 à l'intérieur d'une expression, et la valeur de cette expression est 3. Cette expression a des effets sur la variable a : elle la modifie. On dira que c'est une expression avec des effets de bord.

II. Boucles en OCaml

Tout ça pour arriver au point intéressant : oui, on peut faire des boucles en OCaml. Sans récursion.

let a = ref 1;;

for i = 1 to 12 do
    incr a;
    a := !a * 2
done;;

!a;;

for i = 12 downto 1 do
    print_int i;
    print_string " "
done;;

let a = ref 42 in

while !a != 1 do
    if !a mod 2 = 0 then a := !a / 2
    else a := 3 * !a + 1;
    print_int !a;
    print_string " "
done;;

III. Fonctions anonymes et d'ordre supérieur

On peut faire ce qu'on appelle des fonctions anonymes en OCaml, c'est-à-dire des fonctions qui n'ont pas de nom. Par exemple :

fun x y -> x + y

L'avantage principal est lorsqu'on a besoin de fonctions très simples pour les placer dans des fonctions d'ordre supérieur, c'est-à-dire des fonctions qui prennent en argument des fonctions.

Celles que vous pouvez utiliser sont principalement les fonctions init, map et iter sur les listes et les tableaux (array). Par exemple :

(* List.init len f renvoie [f 0; f 1; f 2; ...; f (len - 1)] *)
let l = List.init 10 (fun i -> 2 * i);; (*renvoie [0; 2; 4; ...; 18]*)

List.iter (fun i -> print_int i) l;; (*affiche la liste l*)

List.map (fun i -> Array.make i 0) l;; (*renvoie une liste contenant des tableaux de taille 0, 2, 4, ..., 18, en suivant la liste l*)

Quasiment toutes les collections OCaml ont ces fonctions, quasiment à l'identique !

Exercices

let somme_tableau (t : int array) : int =
  let s = ref 0 in
  for i = 0 to Array.length t - 1 do
    s := !s + t.(i)
  done;
  !s;;

let renverse (t : 'a array) : unit =
  let n = Array.length t in
  for i = 0 to n / 2 - 1 do
    let x = t.(i) in
    t.(i) <- t.(n - 1 - i);
    t.(n - 1 - i) <- x
  done;;

let t = [|1; 2; 3; 4; 5|];;
renverse t;;
t;;

let premier_diviseur (n : int) : int =
  let d = ref 2 in
  while n mod !d <> 0 do
    incr d
  done;
  !d;;

premier_diviseur 91;;   (* 7 *)