Programmation impérative : références et boucles

Cours complet · OCaml (option informatique), chapitre 4 · prépas MPSI et MP, option informatique

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>4.1 Introduction et motivation

OCaml n'est pas un langage purement fonctionnel : il offre aussi un style impératif, où l'on modifie l'état de la machine au fil du temps. Pourquoi s'en servir alors que la récursion suffit ? Parce que certains calculs s'expriment plus naturellement par une boucle et une variable qui évolue : compter, accumuler, itérer un nombre connu de fois. Le programme officiel le souligne toutefois : les références doivent être utilisées à bon escient. On ne renonce pas au style fonctionnel ; on ajoute un outil, qu'on emploie là où il clarifie.

Ce chapitre présente les briques de l'impératif en OCaml : la notion d'effet et le type unit, la séquence, les références (la seule forme de variable modifiable vue ici), et les deux boucles while et for. On retrouvera, transposé aux boucles while, l'outil de validation déjà central en Python : le variant, qui prouve qu'une boucle se termine.

4.2 Effets, `unit` et séquence

En OCaml, il n'y a pas d'instruction au sens de Python : tout est expression. Une expression évaluée pour son effet (afficher, modifier une case mémoire) et non pour sa valeur a le type unit, dont l'unique valeur est notée ().


# print_string "Bonjour";;
Bonjour- : unit = ()

iRemarqueAffichage : rappel

Les fonctions d'affichage print_int : int -> unit, print_string : string -> unit et print_float : float -> unit produisent un effet (l'écriture à l'écran) et renvoient (). Ce sont des fonctions « à effet », typiques de l'impératif.

4.2.1 La séquence

Pour enchaîner deux expressions, on les sépare par un point-virgule ; : l'expression e1 ; e2 évalue e1 (pour son effet — e1 doit être de type unit), puis e2, et sa valeur est celle de e2.


let saluer () =
  print_string "Bonjour, ";
  print_string "le monde";
  print_newline ()

Attention

Ne pas confondre les trois points-virgules d'OCaml : ; (séquence entre expressions), ; séparateur d'éléments de liste ([1; 2; 3]), et ;; (fin de phrase au toplevel). Le contexte les distingue, mais c'est une source d'erreurs au début. Si e1 dans e1 ; e2 n'est pas de type unit, le compilateur émet un avertissement : sa valeur serait jetée.

4.2.2 `begin … end` et le `if` sans `else`

Pour grouper une séquence en une expression — par exemple dans une branche de if ou un corps de boucle — on l'entoure de begin … end (synonyme de parenthèses).


if x < 0 then begin
  print_string "négatif";
  print_newline ()
end

iRemarque

Un if c then e sans else équivaut à if c then e else () : la branche e doit donc être de type unit. C'est cohérent — sans else, que vaudrait l'expression quand la condition est fausse, sinon () ? On réserve donc le if sans else aux effets.

4.3 Les références

Une référence est une « case mémoire » modifiable contenant une valeur. C'est la seule variable mutable de ce cours (les liaisons let, elles, sont définitives).

Définition 4.1Références

Pour une valeur de type 'a :

ref v crée une nouvelle référence initialisée à v ; son type est 'a ref ;
!r lit (déréférence) le contenu actuel de r ;
r := v remplace le contenu de r par v ; cette affectation a pour valeur ().


# let compteur = ref 0;;
val compteur : int ref = {contents = 0}
# compteur := !compteur + 1;;
- : unit = ()
# !compteur;;
- : int = 1

Attention

Distinguer la liaison et la référence. let r = ref 0 lie définitivement le nom r à une référence ; on ne peut pas relier r, mais on peut modifier son contenu par :=. Et l'on n'écrit jamais r := !r + 1 sans le ! : r + 1 n'a pas de sens (on n'additionne pas une référence et un entier).

4.4 Les boucles

4.4.1 La boucle `while`

while c do b done évalue le corps b (de type unit) tant que la condition c est vraie ; l'ensemble a le type unit.

Exemple 4.2Compter à rebours


let rebours n =
  let i = ref n in
  while !i > 0 do
    print_int !i;
    print_string " ";
    i := !i - 1
  done;
  print_newline ()

La référence i porte l'état qui évolue ; chaque tour l'affiche puis la décrémente. La séquence finale (done; print_newline ()) saute une ligne après la boucle.

Méthode : Prouver qu'une boucle `while` se termine : le variant

Une boucle for sur un intervalle fini se termine d'elle-même. Pour une boucle while, on exhibe un variant : une quantité entière qui reste $\geq 0$ tant que la boucle tourne et qui décroît strictement à chaque tour. Une suite d'entiers naturels strictement décroissante étant finie, la boucle s'arrête. Dans rebours, le variant est !i : positif tant que !i > 0, décroissant de $1$ par tour.

4.4.2 La boucle `for`

for v = d to f do b done exécute le corps b pour v prenant successivement les valeurs entières de d à f.

ImportantLes deux bornes sont atteintes

Contrairement au range(a, b) de Python (où b est exclue), la boucle for v = d to f parcourt d, d+1, …, f : les deux bornes sont incluses. Si d > f, le corps n'est pas exécuté. La variable v est locale à la boucle et ne peut pas être modifiée dans le corps.

Exemple 4.3Factorielle, version impérative


let factorielle n =
  let r = ref 1 in
  for i = 2 to n do
    r := !r * i
  done;
  !r

On accumule le produit dans r, de 2 à n inclus. Le corps de la fonction est une séquence : la boucle (de type unit), puis !r, qui fournit le résultat. À comparer à la version récursive du chapitre 1 : même résultat, deux styles.

4.5 Itératif ou récursif ?

Un même calcul s'écrit souvent des deux façons. Le choix relève du style et de la lisibilité — et parfois de l'efficacité.

Exemple 4.4PGCD : récursif contre itératif

Version récursive (chapitre 1) :


let rec pgcd a b =
  if b = 0 then a else pgcd b (a mod b)

Version impérative, avec deux références et une boucle while :


let pgcd a b =
  let x = ref a and y = ref b in
  while !y <> 0 do
    let r = !x mod !y in
    x := !y;
    y := r
  done;
  !x

Les deux calculent la même chose. La récursive est plus concise et se lit comme la définition mathématique ; l'impérative explicite l'état qui évolue. Variant de la boucle while : !y, positif et strictement décroissant (le reste !x mod !y est $<! y$ ).

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>4.6 Exercices résolus

Niveau $⋆$ (application directe du cours)

Exercice 1 : Lire une session de références

Donner la valeur finale affichée.


let r = ref 3 in
r := !r + 1;
r := !r * 2;
!r

Démonstration

r part à 3 ; après r := !r + 1, contenu 4 ; après r := !r * 2, contenu 8. L'expression finale !r vaut donc 8. Chaque := renvoie () ; seul le !r final produit une valeur entière.

Exercice 2 : Somme des premiers entiers

Écrire somme n qui calcule $1 + 2 + \dots + n$ avec une boucle for et une référence.

Démonstration


let somme n =
  let s = ref 0 in
  for i = 1 to n do
    s := !s + i
  done;
  !s

On accumule dans s, de 1 à n inclus. Pour n = 0, la boucle ne s'exécute pas et somme 0 vaut 0, comme attendu.

Exercice 3 : Puissance entière, version `for`

Écrire puissance x n calculant $x^{n}$ ( $n \geq 0$ ) avec une boucle.

Démonstration


let puissance x n =
  let r = ref 1 in
  for _i = 1 to n do
    r := !r * x
  done;
  !r

On multiplie n fois par x, en partant de 1. L'indice _i ne sert pas dans le corps (on l'écrit avec un _ initial pour le signaler) : seule compte la répétition. Cas n = 0 : 1.

Niveau $⋆ ⋆$ (raisonnement intermédiaire)

Exercice 4 : PGCD impératif

Écrire pgcd avec une boucle while, et donner son variant.

Démonstration


let pgcd a b =
  let x = ref a and y = ref b in
  while !y <> 0 do
    let r = !x mod !y in
    x := !y;
    y := r
  done;
  !x

Variant : !y. Il reste positif tant que la condition !y <> 0 (avec !y initialement $\geq 0$ ) tient, et il décroît strictement car le nouveau !y vaut !x mod !y $<! y$ . La boucle se termine donc.

Exercice 5 : Fibonacci itératif

Écrire fibo n ( $n \geq 0$ ) en $Θ (n)$ avec deux références, et expliquer l'avantage sur la version doublement récursive du chapitre 3.

Démonstration


let fibo n =
  let a = ref 0 and b = ref 1 in
  for _i = 1 to n do
    let s = !a + !b in
    a := !b;
    b := s
  done;
  !a

On fait avancer une « fenêtre » de deux termes consécutifs. fibo 0 $= 0$ , fibo 1 $= 1$ , fibo 6 $= 8$ . Coût $Θ (n)$ : chaque terme est calculé une fois, là où la définition récursive naïve $u_{n} = u_{n - 1} + u_{n - 2}$ recalcule exponentiellement les mêmes valeurs.

Exercice 6 : Compter les diviseurs

Écrire nb_diviseurs n ( $n \geq 1$ ), le nombre de diviseurs de n, avec une boucle.

Démonstration


let nb_diviseurs n =
  let c = ref 0 in
  for d = 1 to n do
    if n mod d = 0 then c := !c + 1
  done;
  !c

On essaie chaque d de 1 à n et l'on incrémente c quand d divise n. Le if sans else est légitime : sa branche est de type unit. (On pourrait s'arrêter à $n$ pour un gain de coût.)

Exercice 7 : Suite de Syracuse

Écrire syracuse n ( $n \geq 1$ ), le nombre d'étapes pour atteindre $1$ (étape : $n \mapsto n /2$ si pair, $n \mapsto 3 n + 1$ sinon), avec une boucle while.

Démonstration


let syracuse n =
  let m = ref n and etapes = ref 0 in
  while !m <> 1 do
    if !m mod 2 = 0 then m := !m / 2
    else m := 3 * !m + 1;
    etapes := !etapes + 1
  done;
  !etapes

On itère la transformation jusqu'à atteindre 1, en comptant les étapes. Contrairement aux exemples précédents, on ne connaît aucun variant prouvant la terminaison pour tout n : c'est la conjecture de Syracuse, ouverte à ce jour. La boucle s'arrête en pratique, mais nul ne sait le démontrer en général.

Niveau $⋆ ⋆ ⋆$ (approfondissement)

Exercice 8 : Racine carrée entière

Écrire racine n ( $n \geq 0$ ) renvoyant le plus grand entier $r$ tel que $r^{2} \leq n$ , avec une boucle while, et prouver sa terminaison par un variant.

Démonstration


let racine n =
  let r = ref 0 in
  while (!r + 1) * (!r + 1) <= n do
    r := !r + 1
  done;
  !r

On incrémente r tant que (r+1)^2 ne dépasse pas n. À la sortie, r^2 <= n < (r+1)^2 : c'est bien la partie entière de $n$ . Variant : n - !r !r, entier positif tant que la boucle tourne, qui décroît strictement (!r croît de $1$ ). (racine 10 $= 3$ , car $3^{2} = 9 \leq 10 < 16 = 4^{2}$ .)*

Exercice 9 : Test de primalité

Écrire est_premier n avec une boucle while qui s'arrête dès qu'un diviseur est trouvé.

Démonstration


let est_premier n =
  if n < 2 then false
  else begin
    let d = ref 2 and premier = ref true in
    while !d * !d <= n && !premier do
      if n mod !d = 0 then premier := false;
      d := !d + 1
    done;
    !premier
  end

On cherche un diviseur d de 2 à $n$ . La référence booléenne premier sert de drapeau : la condition ... && !premier (évaluation paresseuse) arrête la boucle dès qu'un diviseur est trouvé. Le begin … end groupe la séquence de la branche else en une seule expression.

Exercice 10 : Partage d'une référence (aliasing)

Donner la valeur finale de chacun des deux fragments, et expliquer la différence.


(* A *)                      (* B *)
let a = ref 0 in             let a = ref 0 in
let b = a in                 let b = ref !a in
a := 5;                      a := 5;
!b                           !b

Démonstration

(A) renvoie 5 ; (B) renvoie 0.

En (A), let b = a lie b à la même référence que a (les deux noms désignent l'unique case mémoire) : modifier via a se voit à travers b. C'est l'aliasing.

En (B), ref !a crée une nouvelle référence initialisée avec la valeur actuelle de a (soit 0) ; a et b sont alors indépendantes, et l'affectation ultérieure sur a ne touche pas b.

(C'est tout l'enjeu du « à bon escient » : une référence partagée par mégarde est une source classique de bogues. On retiendra : let b = a partage, let b = ref !a copie.)

Synthèse du chapitre (à retenir)

Pas d'instruction : une expression à effet a le type unit, de valeur unique ().
Séquence e1 ; e2 : e1 (de type unit) pour l'effet, puis e2 ; begin … end groupe. if c then e sans else exige e : unit.
Références : ref v crée ('a ref), !r lit, r := v écrit (renvoie ()). La liaison let r est définitive ; seul le contenu change.
Boucles : while c do b done (corps unit) ; for v = d to f do b done — les deux bornes incluses, v locale et non modifiable.
Variant : pour prouver qu'un while se termine, exhiber une quantité entière $\geq 0$ qui décroît strictement à chaque tour (!y pour le PGCD, n - r*r pour la racine).
Aliasing : let b = a partage la référence ; let b = ref !a en copie la valeur. Références à bon escient.

4.7 Exercices d'entraînement

Légende : $⋆$ application directe, $⋆ ⋆$ raisonnement intermédiaire, $⋆ ⋆ ⋆$ approfondissement ; $⧫$ signale un classique incontournable. La numérotation prolonge celle des dix exercices résolus.

Thème A — Références et séquences.

[11.] $⋆$ Donner la valeur de let r = ref 10 in r := !r - 3; r := !r - 3; !r.
[12.] $⋆$ Écrire echange a b qui échange les contenus de deux références a et b (de type int ref). Quel est son type de retour ?
[13.] $⋆ ⋆$ $⧫$ Expliquer pourquoi let c = ref 0 in for _i = 1 to 5 do c := !c + 1 done; !c vaut 5.

Thème B — Boucles `for`.

[14.] $⋆$ Écrire somme_carres n ( $1^{2} + \dots + n^{2}$ ) avec une boucle.
[15.] $⋆ ⋆$ Écrire compte_chiffres n ( $n \geq 0$ ), le nombre de chiffres de n en base $10$ , avec une boucle while (diviser par $10$ ).
[16.] $⋆ ⋆ ⋆$ Afficher la table de multiplication de $1$ à $9$ avec deux boucles for imbriquées et print_int.

Thème C — Boucles `while` et variants.

[17.] $⋆ ⋆$ Écrire log2 n ( $n \geq 1$ ), le nombre de fois qu'on peut diviser n par $2$ avant d'atteindre $1$ ; donner le variant.
[18.] $⋆ ⋆$ $⧫$ Écrire somme_chiffres n ( $n \geq 0$ ) avec une boucle while (somme des chiffres en base $10$ ).
[19.] $⋆ ⋆ ⋆$ Écrire premier_diviseur n ( $n \geq 2$ ) : le plus petit diviseur $\geq 2$ de n, par une boucle qui s'arrête dès qu'il est trouvé ; prouver la terminaison.

Thème D — Itératif contre récursif.

[20.] $⋆ ⋆$ Réécrire factorielle de façon récursive (chapitre 1) puis itérative, et comparer.
[21.] $⋆ ⋆ ⋆$ Écrire pgcd_rec et pgcd_iter et vérifier sur quelques cas qu'elles coïncident.
[22.] $⋆ ⋆ ⋆$ $⧫$ Discuter : pour parcourir une liste, pourquoi la récursion est-elle plus naturelle que les références et les boucles vues ici ?

Continuer sur Adloun : animation, QCM, fiches, exercices

Programmation impérative : références et boucles

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>4.1 Introduction et motivation

4.2 Effets, unit et séquence

4.2.1 La séquence

4.2.2 begin … end et le if sans else

4.3 Les références

4.4 Les boucles

4.4.1 La boucle while

Méthode : Prouver qu'une boucle `while` se termine : le variant

4.4.2 La boucle for

4.5 Itératif ou récursif ?

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>4.6 Exercices résolus

Niveau ⋆ (application directe du cours)

Niveau ⋆⋆ (raisonnement intermédiaire)

Niveau ⋆⋆⋆ (approfondissement)

4.7 Exercices d'entraînement

Thème A — Références et séquences.

Thème B — Boucles for.

Thème C — Boucles while et variants.

Thème D — Itératif contre récursif.

4.2 Effets, `unit` et séquence

4.2.2 `begin … end` et le `if` sans `else`

4.4.1 La boucle `while`

4.4.2 La boucle `for`

Niveau $⋆$ (application directe du cours)

Niveau $⋆ ⋆$ (raisonnement intermédiaire)

Niveau $⋆ ⋆ ⋆$ (approfondissement)

Thème B — Boucles `for`.

Thème C — Boucles `while` et variants.