3

Introduction à OCaml

I À propos d’OCaml
Caml est un langage de programmation développé depuis 1985 par l’INRIA 1 . La variante ac-
tuellement active de ce langage est OCaml, qui est le langage que nous utiliserons.
OCaml est un langage « presque confidentiel mais pas tout-à-fait » : il est principalement utilisé
dans l’univers de la recherche et pour créer des outils manipulant des programmes éventuellement
écrits dans un autre langage (compilateurs, analyse statique, génération automatique de code…).
On peut citer deux variantes assez populaires de OCaml :
• F#, qui a été créé par Microsoft et fait partie de l’environnement .Net : il y a quelques diffé-
rences par rapport à OCaml mais il est immédiat d’apprendre l’un si l’on connaît l’autre ;
• Reason, créé assez récemment par Facebook. Ici, on ne peut même pas vraiment parler de
variante : le langage est exactement le même (et utilise le même compilateur), seule la syn-
taxe a été modifiée de manière à être moins déroutante pour des développeurs habitués à
JavaScript ou PHP (qui sont les langages les plus utilisés chez Facebook).
Plusieurs langages et frameworks populaires ont été assez nettement influencés par OCaml (et
par les idées de la programmation fonctionnelle plus généralement). On peut citer Rust (qui vise
à fournir une alternative plus sûre à C/C++) et React (le framework JavaScript le plus populaire
aujourd’hui, créé par l’auteur de ReasonML).

Un langage compilé
Les fichiers source doivent d’abord être traduits en langage machine avant d’être exécutés, comme
en C, C++, Java et au contraire de Python.
OCaml est cependant doté d’une REPL (Read Eval Print Loop) qui permet de travailler comme
vous en avez sans doute eu l’habitude en Python.

Un langage fonctionnel
OCaml se range principalement dans la catégorie des langages fonctionnels, même s’il permet
aussi une programmation impérative, et même orientée objet dans le cas d’OCaml.
Dans un langage impératif, on utilise des suites d’instructions pour modifier l’état de la mémoire.
On distingue alors les instructions des expressions. Par exemple, en Python, 3 * x + 1 est une
expression, alors que y = 3 * x + 1 est une instruction.
1. Institut National de Recherche en Informatique et Automatique, un établissement public de recherche français
comme le CNRS, l’INSERM…

1
 Dans un langage fonctionnel tel qu’OCaml, on met en avant la notion d’expression et l’applica-
tion de fonctions. En OCaml, la notion d’instruction n’existe pas vraiment : on ne travaille qu’avec
des expressions.
Par ailleurs, les fonctions sont des valeurs comme les autres, qui peuvent être renvoyées comme
résultat d’un calcul, prises en argument… Un langage fonctionnel met également l’accent sur la
récursion plus que sur l’itération et privilégie les valeurs non mutables (essentiellement, fonctions et
variables sont utilisées d’une manière proche de ce que l’on fait en mathématiques et pas comme des
cases mémoire dans lesquelles on écrit à notre gré). La mutation (modification de la valeur d’une
variable) est néanmoins possible dans certains cas pour avoir une approche impérative.

Un langage statiquement et fortement typé

Tout objet défini par un langage de programmation possède un type (int, float, etc).
Le langage est dit statiquement et fortement typé car :
• le typage d’une expression est réalisé au moment de la compilation ;
• le typage d’une expression ne peut donc pas changer au cours de l’execution ;
• les conversions implicites de type sont formellement interdites.
Par exemple, en Python, il est possible d’additionner directement un flottant et un entier :
l’entier sera dynamiquement converti en flottant au moment de l’exécution.
En OCaml, cette conversion ne peut pas être implicite, il faut réaliser explicitement la conver-
sion, et utiliser l’opérateur adapté :
# 2 + 2.3;;
Error: This expression has type float but an expression was expected of
type
int
# float_of_int 2 +. 2.3;;
- : float = 4.3

En effet, OCaml n’autorise pas la surcharge d’opérateur : le symbole + désigne uniquement

l’addition des entiers, l’addition des flottants est notée +.

II Types de bases
A. Les entiers
On retrouve les opérateurs usuels sur les entiers. En l’absence de parenthèses, les règles usuelles
de priorité s’appliquent.

Opérateur Signification
+ Addition d’entiers
* Multiplication d’entiers
- Soustraction / opposé
/ « Quotient » de la division euclidienne
mod « Reste » de la division euclidienne
abs Valeur absolue

Table 3.1 – Opérations sur les entiers

2
 # 5 + 7 mod 2;;
- : int = 6

# 3 + 2 * 4;;
- : int = 11

# (-5) mod 2;;

- : int = -1

Remarque. Pour la division, a / b fait un arrondi vers 0, et ne correspond donc à la division

euclidienne mathématique que si 𝑎 et 𝑏 sont de même signe. a mod b est défini de telle manière
que l’identité a = (a / b) * b + (a mod b) soit systématiquement vérifiée, ce qui signifie que
a mod b est négatif si a est négatif.

• Sur une architechure 32 bits, les entiers OCaml sont codés sur 31 bits et sont signés. On peut
donc représenter tout l’intervalle J−230 , 230 − 1K ;
• Sur une architechure 64 bits, les entiers OCaml sont codés sur 63 bits et sont signés. On peut
donc représenter tout l’intervalle J−262 , 262 − 1K ;
• Dans l’interface en ligne qu’on utilisera en TP, il y a une traduction directe vers des entiers
javascript, on travaille avec l’intervalle J−231 , 231 − 1K.
Il faut donc prendre soin à ne pas dépasser ces limites, sous peine d’obtenir des résultats différents
de ceux attendus.
# -4611686018427387904 - 1;;
- : int = 4611686018427387903

Les valeurs maximales et minimales de type int sont accessibles par max_int et min_int.
min_int, max_int;;
- : int * int = (-4611686018427387904, 4611686018427387903)

B. Les flottants
Les calculs effectués sur les flottants sont bien souvent approchés. La représentation interne
d’un flottant et toutes les questions liées à la précision des calculs seront traitées ultérieurement.
# 0.1 *. 3.;;
- : float = 0.300000000000000044

Opérateur Signification
+. Addition de flottants
*. Multiplication de flottants
-. Soustraction / opposé
/. Division de flottants
** Puissance
floor « Partie entière » 2
ceil Arrondi par excès
abs_float Valeur absolue

Table 3.2 – Opérations sur les flottants

3
 On dispose de plus d’un certain nombre de fonctions mathématiques : sqrt, exp, log (qui dé-
signe le logarithme népérien), sin, cos, tan, asin, acos, atan…
# 3. ** 2. +. sqrt 4.;;
- : float = 11.

# sin (asin 0.3);;

- : float = 0.3

Coercitions Contrairement à la plupart des langages, OCaml ne fait jamais de conversion auto-
matique des entiers vers les flottants (ni évidemment des flottants vers les entiers). Les fonctions de
conversion de type, aussi appelées coercitions, sont :

Fonction Type Comportement

float_of_int int -> float Injection canonique
int_of_float float -> int Arrondi vers zéro

Table 3.3 – Conversion entiers ↔ flottants

C. Les booléens
Le type bool comporte deux constantes : true et false et dispose des opérateurs logiques non
(not), et (&&), ou (||).
Les opérateurs && et || fonctionnent suivants le principe de l’évaluation paresseuse : p && q ne
va évaluer q que si p est vraie, et p || q ne va évaluer q que si p est fausse.
# (2. < 3.) || (1/0 = 1);;
- : bool = true

# not (2. < 3.) || (1/0 = 1);;

Exception: Division_by_zero.

# (3 < 0) && (5/0 = 1);;

- : bool = false

# (3 > 0) && (5/0 = 1);;

Exception: Division_by_zero.

Opérateurs de comparaison Les opérateurs de comparaison sont *polymorphes*, cela signifie

qu’ils vont pouvoir comparer deux éléments de n’importe quel type (les deux éléments doivent
néanmoins être de même type).
# 3 < 5;;
- : bool = true

# 5.4 >= 8.9;;

- : bool = false

# 3 < 3.14;;
Error: This expression has type float but an expression was expected of type
int

4
 Opérateur Signification
= Égalité structurelle
<> Différence structurelle
< Inférieur strict
<= Inférieur ou égal
> Supérieur strict
>= Supérieur ou égal

Table 3.4 – Opérateurs de comparaisons

Remarque. Il existe aussi les opérateurs == et != qui teste l’égalité et la différence physique, c’est-à-
dire l’égalité (ou la différence) des pointeurs sous-jacents. Nous ne les utiliserons pas.

D. Les caractères et chaînes de caractères

OCaml distingue les caractères, de type char, et les chaînes de caractères, de type string. Les
caractères sont entourés de guillemets simples, les chaînes de caractères de guillemets doubles. Les
chaînes de caractères disposent d’un opérateur de concaténation, noté ^.
# 'a';;
- : char = 'a'

# ”a”;;
- : string = ”a”

# ”mp2i”;;
- : string = ”mp2i”

# ”do” ^ ”du”;;
- : string = ”dodu”

La fonction length du module String permet d’obtenir la longueur d’une chaîne de caractères
et il est possible d’obtenir un caractère d’indice donné (en commençant la numérotation à zéro) :
# String.length ”dodu aime OCaml”;;
- : int = 15

# ”dodu”.[2];;
- : char = 'd'

# ”dodu”.[4];;
Exception: Invalid_argument ”index out of bounds”.

III Définitions globales et locales

En OCaml, le mot-clé let permet d’attribuer un nom à une valeur.
# let u = 2 + 5 * 8;;
val u : int = 42

Lorsqu’il lit une phrase let x = e;; où l est un nom et e une expression, OCaml évalue l’ex-
pression e et ajoute dans l’environnement l’association entre x et la valeur de e.

5
 La syntaxe let x = e in permet de définir temporairement un nom uniquement pour le cal-
cul courant (cela sera principalement utile à l’intérieur de la définition d’une fonction).
# let a = 4 in a * a + 1;;
- : int = 17

# a;;
Error: Unbound value a

Une définition locale peut masquer une définition globale.

# let b = 12;;
val b : int = 12

# let b = 5 in b * b - 3;;
- : int = 22

# b;;
- : int = 12

IV Expressions conditionnelles
Une expression conditionnelle est une expression de la forme if e1 then e2 else e3, où e1
est une expression booléenne. Si la valeur de e1 est true, l’expression e2 est évaluée et sa valeur est
renvoyée ; sinon, ce sera la valeur de e3 qui sera renvoyée.
# if 3. ** 7. < 2. ** 11. then 2 + 2 + 2 else 3 + 3 + 3;;
- : int = 9

# let x = 3;;
val x : int = 3

# let y = 5;;
val y : int = 5

# let z = 8 + (if x < y then 2 * 7 else 0);;

val z : int = 22

Attention. Pour que l’expression conditionnelle soit bien typée, il est indispensable que les ex-
pressions e2 et e3 soient de même type.
utop # if 3 < 5 then 0 else 2.5;;
Error: This expression has type float but an expression was expected of type
int

En particulier, il n’est pas possible d’écrire un if ... then ... sans else ....

utop # if 3 < 5 then 0;;

Error: This expression has type int but an expression was expected of type
unit because it is in the result of a conditional with no else branch

6
V Fonctions
A. Expressions fonctionnelles
En OCaml, les fonctions ont un statut de première classe, c’est-à-dire qu’elles ont le même statut
que les autres objets.
Les valeurs fonctionnelles à une variable sont de la forme fun v -> e, où v est un nom de va-
riable et e une expression. Pour construire une fonction nommée, on procède comme avec n’importe
quelle autre objet, en utilisant let.
# fun x -> x * x;;
- : int -> int = <fun>

# let carre = fun x -> x * x;;

val carre : int -> int = <fun>

# let repetition x = x ^ x;;

val repetition : string -> string = <fun>

Remarque. Le langage devine tout seul le type de la fonction (sans l’exécuter et sans qu’on lui
indique le type de son argument). Comme l’opérateur * ne fonctionne que sur les entiers, OCaml
sait que x doit être un entier, et comme le résultat de la multiplication de deux entiers est un entier,
OCaml sait que le résultat sera un entier. Il en déduit le type de la fonction : int -> int. On dit
que OCaml a inféré le type de la fonction carre.
On notera immédiatement une différence importante avec C et Python : il n’y a pas de return.
En OCaml, tout est une expression, et en particulier la valeur de retour d’une fonction est sim-
plement la valeur de l’expression définissant la fonction une fois que l’on a substitué les valeurs
concrètes des arguments formels.
Pour appliquer une expression fonctionnelle f à un argument e, on écrit tout simplement f e.
# carre 7;;
- : int = 49

# carre 5 + 2;;
- : int = 27

Remarque. L’application d’une fonction est prioritaire.

Syntaxe alternative. Pour les fonctions nommées, on dispose d’une syntaxe alternative 3
# let valeur_absolue x =
if x > 0 then x else -x;;
val valeur_absolue : int -> int = <fun>

B. Fonctions à plusieurs variables

La manière naturelle de construire une fonction à plusieurs variables en OCaml est d’utiliser
l’expression fun v1 v2 ... vn -> e, où v1,…,vn sont des noms de variables et 𝑒 une expression.

3. syntaxe que j’utiliserai sans doute plus que l’autre…

7
 # fun x y -> x * (x + y);;
- : int -> int -> int = <fun>

On dispose d’une autre syntaxe possible dans le cas d’une fonction nommée.
# let ajoute x y = x + y;;
val ajoute : int -> int -> int = <fun>

Remarque. Une telle fonction à plusieurs variables, où le type fait apparaître plusieurs flèches et
aucun produit cartésien, est dite curryfiée.
Si l’on veut ajouter le carré de 4 et celui de 2 + 3 (en utilisant les fonctions que nous venons de
définir), il faut alors écrire :
# ajoute (carre 4) (carre (2 + 3));;
- : int = 41

C. Fonctions récursives
Contrairement au langage C, un identifiant n’est utilisable en OCaml qu’après la fin de sa défini-
tion. Si on veut 4 écrire une fonction récursive, il faut lui indiquer explicitement pour être autorisé à
appeler la fonction à l’intérieur de sa propre définition. Cela se fait en utilisant les mots-clés let rec
au lieu de rec.
# let rec fact n =
if n = 0 then 1
else n * fact (n-1);;
val fact : int -> int = <fun>

# fact 5;;
- : int = 120

D. Filtrage
Il est alors possible d’utiliser une construction très puissante nommée filtrage (ou pattern-matching),
pour écrire des disjonctions de cas.
Exemple. Pour tester la parité d’un entier naturel, on pourrait par exemple écrire la fonction
est_pair suivante (très inefficace…)

let rec est_pair n = match n with

| 0 -> true
| 1 -> false
| _ -> est_pair (n - 2);;
val est_pair : int -> bool = <fun>

Chaque cas de filtrage est formé d’un motif, suivi d’une flèche, suivi d’une expression. On a ici
trois cas de filtrage. On considère leurs motifs un par un, jusqu’à en trouver un qui filtre la valeur 𝑛.
On exécute alors l’expression à droite de la flèche correspondante et on renvoie sa valeur.
• Le premier cas de filtrage a pour motif 0. Si n vaut 0, on dit que ce motif filtre n, auquel cas
on renvoie true.
4. et on le voudra souvent !

8
 • Le second cas a pour motif 1. Si n vaut 1, on dit que ce motif filtre n, auquel cas on renvoie
false.
• Le troisième cas a pour motif _. Ce motif filtre toute valeur. Si n n’a été pas été filtré par un
des deux motifs précédents, il est filtré par celui-ci. On exécute alors l’expression à droite de
la flèche, et on renvoie la valeur ainsi calculée.

VI Listes
Le type list est un type prédéfini en OCaml. Il permet de représenter des listes de valeurs de
type arbitraire mais homogène. Cela signifie que l’on peut définir une liste d’entiers ou une liste de
booléens, mais pas une liste contenant à la fois des entiers et des booléens.
On peut définir une liste en mettant les éléments entre crochets et en les séparant par des
points-virgules :
# let l = [];;
val l : 'a list = []

# let m = [1];;
val m : int list = [1]

# let s = [3; 5; 0];;

val s : int list = [3; 5; 0]

Étant donnée une liste, on peut en construire une nouvelle en ajoutant un élément en tête :
# let k = 3 :: l ;;
val k : int list = [3]

# let j = 7 :: k ;;
val j : int list = [7; 3]

Tous les éléments d’une liste doivent avoir le même type (uniquement des entiers, ou alors uni-
quement des flottants, ou alors…) :
# let w = [3.2; 5.1];;
val w : float list = [3.2; 5.1]

# let t = [3.2 ; 5];;

Error: This expression has type int but an expression was expected of type
float
Hint: Did you mean `5.'?

Essentiellement, il y a deux types de listes : la liste vide, et les autres. Une liste non vide est
constituée d’un premier élément, appelé tête ou head et de la liste (éventuellement vide) de ses autres
éléments, appelée queue ou tail. Le pattern matching suivant est la manière standard d’opérer sur des
listes :
# let rec somme l = match l with
| [] -> 0
| x :: xs -> x + somme xs;;
val somme : int list -> int = <fun>

On voit ici le schéma fondamental de filtrage sur les listes : soit la liste est vide (c’est ici, comme
souvent, le cas de base de la récursion), soit elle s’écrit head :: tail, avec head un élément de type
'a et tail une liste de type 'a list.