Découvrir OCaml : expressions, valeurs et types

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

Le tronc commun vous a appris à programmer en Python, un langage impératif : on y donne des ordres (« affecte ceci », « répète cela »), et l'on modifie pas à pas l'état de la machine. L'option informatique vous fait découvrir un second langage, OCaml, qui repose sur une idée différente et complémentaire : programmer, c'est avant tout décrire des valeurs par des expressions, et laisser la machine les évaluer. On ne dit plus tant comment faire que ce que l'on veut calculer.

Deux traits d'OCaml structureront tout ce cours. D'abord, OCaml est fortement et statiquement typé : chaque expression possède un type, vérifié par le compilateur avant toute exécution. Une bonne part des erreurs qui, en Python, ne se révèlent qu'au pire moment (sur le troisième jeu de données, le jour du concours) sont ici interceptées dès la compilation. Ensuite, ce typage est inféré : vous écrivez rarement les types vous-même, c'est le compilateur qui les reconstitue. Le compilateur cesse d'être un simple exécuteur pour devenir un relecteur exigeant et bienveillant.

Ce premier chapitre installe le socle : la boucle d'interaction et la notion d'expression, les types de base et leurs opérateurs, la liaison de noms par let et la portée lexicale, la conditionnelle vue comme une expression, les fonctions (curryfication, ordre supérieur), l'inférence de types et l'idée naïve du polymorphisme, les n-uplets, et enfin les définitions récursives. Tout ce qui suit sera supposé acquis dans les chapitres ultérieurs.

1.2 Le toplevel : tout est expression

OCaml s'utilise de deux façons complémentaires, comme Python : en mode interactif dans une boucle d'interaction (le toplevel), et en mode compilé sur un fichier .ml. Le toplevel est l'outil d'exploration idéal : on y saisit une phrase terminée par un double point-virgule ;;, et il répond en affichant le type et la valeur du résultat.

# 2 + 3;;
- : int = 5
# 7 / 2;;
- : int = 3

La réponse du toplevel se lit toujours sur le même patron : - : <type> = <valeur> pour une expression anonyme, et val <nom> : <type> = <valeur> lorsqu'on nomme le résultat (voir la section suivante).

1.3 Les types de base et leurs opérateurs

1.3.1 Entiers et flottants : deux mondes séparés

OCaml distingue strictement les entiers (int) des nombres à virgule flottante (float), et — c'est sa grande surprise pour qui vient de Python — leurs opérateurs sont distincts. Sur les entiers : +, -, , / (division entière) et mod (reste, à n'employer pour l'instant que sur des grandeurs positives). Sur les flottants, les mêmes opérateurs suivis d'un point : +., -., ., /..

# 17 mod 5;;
- : int = 2
# 3.0 *. 2.5;;
- : float = 7.5

# 1 + 2.0;;
Error: This expression has type float but an expression
       was expected of type int

1.3.2 Booléens et évaluation paresseuse

Le type bool a pour seules valeurs true et false. On dispose de la négation not, de la conjonction && et de la disjonction ||. Ces deux derniers opérateurs sont paresseux : ils n'évaluent leur second argument que si c'est nécessaire.

# let n = 0;;
val n : int = 0
# n <> 0 && 10 / n > 2;;
- : bool = false

1.3.3 Les comparaisons

Les opérateurs = (égalité), <> (différence), <, >, <=, >= renvoient un bool. Ils s'appliquent à beaucoup de types — entiers, flottants, booléens, et d'autres rencontrés plus tard — ce qui est notre premier indice de polymorphisme (voir § sec:inference).

1.4 Lier des noms : let et la portée lexicale

1.4.1 Définitions globales et locales

On donne un nom à une valeur avec let. Au toplevel, le compilateur confirme la liaison sous la forme val nom : type = valeur.

# let pi = 3.14159;;
val pi : float = 3.14159
# let aire_disque = pi *. 2.0 *. 2.0;;
val aire_disque : float = 12.56636

Pour une liaison locale, valable seulement le temps d'une expression, on emploie let nom = e in e' : le nom est défini dans e' et nulle part ailleurs.

let discriminant a b c =
  let delta = b *. b -. 4.0 *. a *. c in
  delta

1.4.2 Portée lexicale

OCaml suit la portée lexicale : quand une définition utilise une variable globale, c'est la valeur de cette variable au moment de la définition qui est figée — pas celle qu'elle aurait plus tard. Redéfinir un nom (masquage) crée une nouvelle liaison sans modifier les définitions déjà construites.

# let x = 10;;
val x : int = 10
# let lire_x () = x;;
val lire_x : unit -> int = <fun>
# let x = 20;;
val x : int = 20
# lire_x ();;
- : int = 10

1.5 La conditionnelle est une expression

L'expression if c then eV else eF évalue d'abord la condition c (de type bool), puis l'une des deux branches selon le résultat. Comme c'est une expression, elle possède une valeur — et les deux branches doivent donc avoir le même type.

let valeur_absolue x =
  if x >= 0 then x else -x

1.6 Les fonctions : curryfication et ordre supérieur

1.6.1 Définir et appliquer

On définit une fonction par let f x = ..., et on l'applique en juxtaposant la fonction et son argument, sans parenthèses obligatoires : f 3. Les arguments sont passés par valeur : ils sont évalués avant l'appel.

# let successeur x = x + 1;;
val successeur : int -> int = <fun>
# successeur 41;;
- : int = 42

Le type int -> int se lit « fonction qui, à un int, associe un int ». On peut aussi écrire une fonction anonyme avec fun : fun x -> x + 1 dénote la même fonction que successeur ci-dessus, mais sans lui donner de nom.

1.6.2 Curryfication

En OCaml, une fonction à plusieurs arguments est en réalité une cascade de fonctions à un argument : c'est la curryfication. La définition let ajoute x y = x + y a pour type int -> int -> int, à lire de droite à gauche : « fonction qui à un int associe une fonction int -> int ».

# let ajoute x y = x + y;;
val ajoute : int -> int -> int = <fun>
# ajoute 3 4;;
- : int = 7
# let ajoute10 = ajoute 10;;
val ajoute10 : int -> int = <fun>
# ajoute10 5;;
- : int = 15

1.6.3 Fonctions d'ordre supérieur

Une fonction peut prendre une autre fonction en argument, ou en renvoyer une : on parle de fonction d'ordre supérieur. C'est un trait central du style fonctionnel.

# let applique_deux_fois f x = f (f x);;
val applique_deux_fois : ('a -> 'a) -> 'a -> 'a = <fun>
# applique_deux_fois successeur 5;;
- : int = 7

1.7 Typage statique et inférence ; polymorphisme

Vous n'avez écrit aucun type dans les exemples précédents, et pourtant le toplevel en affiche partout : c'est l'inférence. À partir des opérations employées, le compilateur reconstitue le type le plus général compatible. Dans let successeur x = x + 1, l'usage de + force x : int, d'où successeur : int -> int.

Lorsqu'une fonction n'impose aucune contrainte sur le type de son argument, l'inférence produit un type polymorphe, noté avec une variable de type 'a (« alpha »).

# let identite x = x;;
val identite : 'a -> 'a = <fun>

1.8 Composer des valeurs : les n-uplets

Pour grouper plusieurs valeurs en une seule, on forme un n-uplet en les séparant par des virgules. Le type d'un couple (3, 4) est int int ; celui de (3, "trois", true) est int string * bool. Les composantes peuvent être de types différents.

# let point = (3, 4);;
val point : int * int = (3, 4)

Pour récupérer les composantes, nul besoin d'un filtrage élaboré : un let déstructurant suffit.

let (a, b) = point         (* a vaut 3, b vaut 4 *)

let norme_carree (x, y) =  (* argument : un couple *)
  x * x + y * y

# let division a b = (a / b, a mod b);;
val division : int -> int -> int * int = <fun>
# division 17 5;;
- : int * int = (3, 2)

1.9 Définitions récursives : let rec

Une fonction qui s'appelle elle-même doit être introduite par let rec (et non simplement let), afin que son propre nom soit visible dans son corps.

let rec factorielle n =
  if n <= 1 then 1
  else n * factorielle (n - 1)

Deux fonctions peuvent s'appeler mutuellement : on les lie ensemble avec let rec ... and ....

let rec est_pair n =
  if n = 0 then true else est_impair (n - 1)
and est_impair n =
  if n = 0 then false else est_pair (n - 1)

Ici est_pair appelle est_impair et réciproquement ; le and permet à chacune de « voir » l'autre.

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

Niveau $\star$ (application directe du cours)

17 / 5 ;;     17 mod 5 ;;     2.0 *. 3.0 ;;     3 <= 3 ;;     not (1 = 2) ;;

- : int = 3        (* division entière : la partie entière de 17/5 *)
- : int = 2        (* reste de la division *)
- : float = 6.     (* opérateurs flottants : type float *)
- : bool = true    (* comparaison : 3 <= 3 *)
- : bool = true    (* 1 = 2 vaut false, sa négation true *)

(* a *) 3 + 4.0
(* b *) if 1 < 2 then 0 else "zéro"
(* c *) 5.0 /. 2

let est_positif n = n > 0          (* val est_positif : int -> bool *)
let milieu x y = (x +. y) /. 2.0   (* val milieu : float -> float -> float *)

Niveau $\star \star$ (raisonnement intermédiaire)

let a = 5
let f y = a + y
let a = 100
let resultat = f 1

# let compose f g x = f (g x);;
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
# let ajoute1_puis_double = compose (fun n -> 2 * n) (fun n -> n + 1);;
val ajoute1_puis_double : int -> int = <fun>
# ajoute1_puis_double 5;;
- : int = 12

let echange (x, y) = (y, x)              (* 'a * 'b -> 'b * 'a *)
let normalise (a, b) = (a / b, a mod b)  (* int * int -> int * int *)

Niveau $\star \star \star$ (approfondissement)

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

let rec u n =
  if n = 0 then 1 else u (n - 1) + v (n - 1)
and v n =
  if n = 0 then 1 else u (n - 1)

let rec puissance x n =
  if n = 0 then 1
  else x * puissance x (n - 1)

1.11 Exercices d'entraînement

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

Thème A — Types, valeurs, opérateurs.

• [11.] $\star$ Donner le type et la valeur de 10 - 3 2, (10 - 3) 2, 10.0 /. 4.0, 15 mod 4.
• [12.] $\star$ Pour chacune, dire si elle est bien typée : 2 *. 3, 2.0 = 2.0, true && 1, not false.
• [13.] $\star \star$ $⧫$ Écrire xor a b (ou exclusif de deux booléens) sans utiliser d'opérateur autre que &&, ||, not, puis avec <>.

Thème B — Liaisons et portée.

• [14.] $\star$ À l'aide d'un let ... in, écrire aire_triangle base hauteur en nommant le produit intermédiaire.
• [15.] $\star \star$ $⧫$ Prédire la valeur de resultat : ```ocaml

let c = 2 let g x = c * x let c = 7 let resultat = g 5 + c ```

• [16.] $\star \star$ Expliquer la différence entre let x = 1 in let y = x + 1 in x + y et un programme qui définirait x puis y au niveau global.

Thème C — Fonctions, curryfication, ordre supérieur.

• [17.] $\star$ Définir double, triple et carre sur les entiers ; donner leurs types.
• [18.] $\star \star$ On donne let applique f x = f x. Quel est le type de applique ? Que vaut applique successeur 9 ?
• [19.] $\star \star \star$ $⧫$ Écrire applique_n f n x qui applique $n$ fois la fonction f à x (pour $n\ge 0$), par récursion. En déduire une autre écriture de la fonction « ajouter $n$ » à partir de successeur.

Thème D — n-uplets et récursivité.

• [20.] $\star \star$ Écrire minmax a b qui renvoie le couple (plus petit, plus grand) de deux entiers.
• [21.] $\star \star$ $⧫$ Écrire somme_chiffres n qui calcule la somme des chiffres d'un entier $n\ge 0$ (par récursion, à l'aide de mod 10 et / 10).
• [22.] $\star \star \star$ Écrire syracuse n qui renvoie le nombre d'étapes pour atteindre $1$ à partir de $n\ge 1$ (étape : $n\mapsto n/2$ si pair, $n\mapsto 3n+1$ sinon). Pourquoi ne sait-on pas prouver que cette fonction s'arrête toujours ?