Programmation fonctionnelle
Table des matières

La syntaxe d'OCaml et le paradigme de programmation fonctionnelle permettent de mieux voir un programme comme une fonction retournant une valeur calculée à partir de paramètres. Cela se rapproche des définitions mathématiques des fonctions, par opposition aux descriptions opérationnelles que l'on trouve dans les langages impératifs.

Illustrons cela avec l'exemple de la fonction factorielle. Une définition mathématique possible est la suivante:


\[fact: \mathbb{N}\rightarrow\mathbb{N}; \quad fact(0) = 1 ;\quad fact(n) = n * fact(n-1)\]

En OCaml, cette fonction sera définie comme ci-dessous; on notera la ressemblance de syntaxe entre les deux définitions.

let rec fact = function
  0 -> 1
| n -> n * fact (n-1);;

En C, cette fonction pourrait s'écrire:

unsigned int fact (unsigned int n) {
  unsigned int i = 1, res = 1;

  while (i <= n) res = res * i++;
  return res;
}
1. Noyau fonctionnel

Le noyau fonctionnel du langage permet d'appliquer des fonctions à des valeurs. Les valeurs sont typées et peuvent être de types de base (entier, flottant, ..., cf. 1.1.1), de types plus élaborés construits à partir d'autres types, ou bien de type fonction. En effet, en OCaml, les fonctions sont des valeurs de premier ordre, c'est-à-dire que le langage permet de les manipuler comme d'autres valeurs "simples" comme les entiers. En particulier, on peut définir des fonctions et les passer en paramètres d'autres fonctions.

1.1. Valeurs, fonctions et types de base
1.1.1. Types de base

Les types ci-dessous sont prédéfinis en OCaml. On donne pour chacun la syntaxe et des exemples de manipulation.

1.1.1.1. Les entiers (type int)
# 1 (* l'entier 1 *);;
- : int = 1
# 1 + 0xde (* l'addition avec l'opérateur '+', 0xde est la notation hexadécimale*) ;;
- : int = 223
# 3 - 0o11 (* la soustraction, 0o11 est la notation octale *) ;;
- : int = -6
# 4 * 0b10101 (* la multiplication, 0b10101 est la notation binaire *) ;;
- : int = 84
# 10 / 3 (* la division entière *) ;;
- : int = 3
# (/) 10 3 (* idem, en utilisant l'opérateur en position préfixe *) ;;
- : int = 3
# ( * ) 10 3 (* multiplication; espaces nécessaires pour distinguer des commentaires *);;
- : int = 30
# 15000003 mod 4 (* le modulo, reste de la division entière *) ;;
- : int = 3
# 15_000_003 mod 4 (* même opération, avec un entier plus lisible *) ;;
- : int = 3
# max_int (* le plus grand entier disponible *) ;;
- : int = 4611686018427387903
# min_int - 1 (* attention, pas de contrôle sur le dépassement des limites *) ;;
- : int = 4611686018427387903

max_int et min_int dépendent de l'architecture de la machine. Sur une machine 32 bits, les entiers natifs sont codés sur 31 bits, sur 63 bits sur une machine 64 bits. Cela est dû à la façon dont sont encodées les valeurs.

Il existe beaucoup d'autres opérations sur les entiers, incluant également les manipulations au niveau bits.

On remarquera que l'interprète a automatiquement déterminé le type des expressions saisies (ici, int). C'est ce que l'on appelle l'inférence de type: le typeur a déduit d'après le code les types des expressions évaluées. Nous verrons d'autres exemples d'inférence de type au fur et à mesure de la formation.

1.1.1.2. Les flottants (type float)
# 1.0 (* le réel 1.0 *);;
- : float = 1.
# 1.0e+5 (* notation avec exposant *) ;;
- : float = 100000.
# 1.2 +. 1. (* l'addition avec l'opérateur '+.' *) ;;
- : float = 2.2
# 3.3 -. 2.15 (* la soustraction *) ;;
- : float = 1.15
# 4. *. 3. (* la multiplication *) ;;
- : float = 12.
# 10. /. 3. (* la division *) ;;
- : float = 3.33333333333333348
# (/.) 10. 3. (* idem, en utilisant l'opérateur en position préfixe *) ;;
- : float = 3.33333333333333348
# mod_float 15000003. 4.5 (* le modulo *) ;;
- : float = 0.
# mod_float 15_000_003. 4.5 (* même opération, avec un flottant plus lisible *) ;;
- : float = 0.
# 1.999999999 +. 100000000. (* la précision est celle de la norme IEEE 754 *);;
- : float = 100000002.
# ceil 3.5 (* arrondi à l'entier supérieur *) ;;
- : float = 4.
# floor 3.5 (* arrondi à l'entier inférieur *) ;;
- : float = 3.
# truncate 3.5 (* ne conserve que la partie entière *) ;;
- : int = 3
# 1. /. 0. (* la division par zéro donne l'infini *);;
- : float = infinity
# 0. /. 0. (* diviser 0 par 0 ne donne pas un nombre, 'not a number' ou 'NaN' *);;
- : float = nan

D'autres opérations sont disponibles sur les flottants; on consultera le manuel pour les découvrir.

Les opérateurs + et +. ne sont pas génériques et s'appliquent respectivement sur des entiers et des flottants (idem pour les autres opérateurs exposés plus haut):

# 1 + 2.0 ;;
Error: This expression has type float but an expression was expected of type
         int
# 1 +. 2.0 ;;
Error: This expression has type int but an expression was expected of type
         float
1.1.1.3. Les booléens (type bool)
# true (* la valeur 'vrai' *) ;;
- : bool = true
# false (* la valeur 'faux' *) ;;
- : bool = false
# true && false (* ET paresseux séquentiel, évalué de gauche à droite *) ;;
- : bool = false
# true || false (* OU paresseux séquentiel, évalué de gauche à droite *) ;;
- : bool = true
# not true (* NON logique *) ;;
- : bool = false
1.1.1.4. Les caractères (type char)
# 'a' (* le caractère 'a' *) ;;
- : char = 'a'
# int_of_char 'a' (* son code ASCII *) ;;
- : int = 97
# char_of_int 123 (* le caractère de code ASCII 123 *) ;;
- : char = '{'

D'autres fonctions sont disponibles dans le module Char.

1.1.1.5. Les chaînes de caractères (type string)

On crée une chaîne de caractères en la mettant entre guillemets ":

# "hello world !";;
- : string = "hello world !"

Le caractère \ est utilisé pour indiquer des caractères spéciaux:

  • \" permet d'insérer le caractère " au lieu de signaler la fin de la chaîne,
  • \n indique une fin de ligne,
  • \r indique un retour chariot,
  • \t indique une tabulation.
OCaml ≥ 4.02.0

Une syntaxe alternative peut être utilisée pour éviter de devoir «échapper» les caractères spéciaux, en utilisant {|...|} ou {id|...|id}, id pouvant être _ ou n'importe quelle suite de lettres en minuscules:

# String.length {|\"|} (* pas d'échappement *);;
- : int = 2
# {foo||}|foo} (* utilisation d'un délimiteur *);;
- : string = "|}"
# {xml|<a href="http://....">bla bla bla</a>|xml};;
- : string = "<a href=\"http://....\">bla bla bla</a>"
OCaml ≥ 4.02.0

Il est également possible d'utiliser des fonctions créant des chaînes:

# let chaine = String.make 10 'a';;
val chaine : string = "aaaaaaaaaa"
# string_of_int 42;;
- : string = "42"
# string_of_float 84.;;
- : string = "84."
# Printexc.to_string Not_found (* une chaîne à partir d'une exception *);;
- : string = "Not_found"
# "hello " ^ "world!" (* concaténation *);;
- : string = "hello world!"

Beaucoup d'autres fonctions sont disponibles dans le module String:

# String.length "hello world!" (* longueur de chaîne *);;
- : int = 12
# String.sub "hello world!" 0 5 ;;
- : string = "hello"

L'accès à un caractère d'une chaîne est possible de deux façons, soit en utilisant la fonction String.get, soit en utilisant une syntaxe spéciale, chaine.[indice]. Les indices de caractères commencent à zéro.

# String.get "hello world!" 4 (* accès au 5ème caractère *);;
- : char = 'o'
# "hello world!".[4];;
- : char = 'o'
Avertissement 1: Pas de conversion automatique

Il n'existe pas de conversion automatique d'un type vers un autre comme dans beaucoup d'autres langages interprétés. Ainsi:

# string_of_int 25 (* construction d'une chaîne représentant l'entier 25 *) ;;
- : string = "25"
# 3 + "25";;
Error: This expression has type string but an expression was expected of type
         int
Avertissement 2: Transition vers des chaînes de caractères non mutables
OCaml < 4.02.0

Une transition, engagée depuis la version 4.02.0 d'OCaml, aboutira à des chaînes de caractères non mutables. Dans la version 4.02.0, un nouveau module Bytes et un type bytes apparaissent. Ce type permet de représenter des tableaux d'octets, mutables. Le module fournit des fonctions similaires aux fonctions du module String et des fonctions de conversion depuis et vers le type string.

En OCaml 4.02.0, les chaînes sont encore mutables, mais une option -safe-string permet de rendre le type string non mutable et les types bytes et string incompatibles (non unifiables). Les utilisateurs sont fortement incités à utiliser cette option pour commencer cette transition. A terme, ce comportement sera celui par défaut.

Dans cette formation, nous utilisons déjà ce mode, avec des chaînes non modifiables. Le module Bytes, qui concerne une structure de donnée mutable, est abordé dans la partie relative à la programmation impérative.

1.1.1.6. Le type unit

Le type unit décrit un ensemble ne possédant qu'une seule valeur, notée ().

# ();;
- : unit = ()

Cette valeur sera plus particulièrement utilisée dans les programmes impératifs (cf. Programmation impérative) pour les fonctions qui effectuent des effets de bord. Les fonctions dont le résultat est la valeur () simulent la notion de procédure qui n'existe pas en OCaml comme le fait le type void dans le langage C.

1.1.1.7. Les n-uplets

Les n-uplets permettent de grouper plusieurs valeurs, potentiellement de types différents. Un n-uplet à 2 éléments est aussi appelé paire. Voici quelques exemples de constructions de n-uplets:

# (1, 2) (* paire d'entiers *) ;;
- : int * int = (1, 2)
# (1, "2") (* paire composée d'un entier et d'une chaîne *) ;;
- : int * string = (1, "2")
# fst (1, 2) (* accès à la première composante de la paire *) ;;
- : int = 1
# snd (1, 2) (* accès à la seconde composante *);;
- : int = 2
# (1, 2, 3) (* n-uplet de 3 éléments *) ;;
- : int * int * int = (1, 2, 3)
# (1.0, "hello", "world", '!') (* n-uplet de 4 éléments de 3 types différents *) ;;
- : float * string * string * char = (1., "hello", "world", '!')

On notera que les types des n-uplets inférés sont notés par une '*', comme dans int * string * string * char.

Avertissement 3: fst et snd

Les fonctions fst et snd ne s'appliquent qu'à des paires et non à des n-uplets de taille supérieure, comme l'indique le type de ces fonctions:

# snd;;
- : 'a * 'b -> 'b = <fun>
# fst (1, 2, 3);;
Error: This expression has type 'a * 'b * 'c
       but an expression was expected of type 'd * 'e

La notation 'a * 'b -> 'a indique qu'il s'agit d'un type fonctionnel (aussi appelé type "flèche"), décrivant une fonction prenant en argument une paire d'éléments de types quelconques ('a * 'b) et renvoyant une valeur de même type que le premier élément de la paire ('a).

1.1.1.8. Les listes (type 'a list)

Le type list est prédéfini et permet de construire des listes d'éléments de même type. C'est un type paramétré, 'a indique le paramètre de type, qui peut être instancié selon le type des éléments de la liste:

# [] (* une liste vide, donc sans contrainte sur le type des éléments *) ;;
- : 'a list = []
# [ 1 ] (* une liste d'entiers à un élément *) ;;
- : int list = [1]
# [ 1 ; 2 ; 3 ] (* une liste de 3 entiers *) ;;
- : int list = [1; 2; 3]
# [ "hello" ; "world" ; "!" ] (* une liste de chaînes *) ;;
- : string list = ["hello"; "world"; "!"]
# [ 1 ; "2" ; 3 ] (* liste invalide car les éléments n'ont pas le même type *) ;;
Error: This expression has type string but an expression was expected of type
         int

Voyons quelques exemples de manipulation de listes:

# 1 :: 2 :: 3 :: [] (* ajout d'élément en tête de liste par l'opérateur 'cons' :: *) ;;
- : int list = [1; 2; 3]
# [ 1 ; 2 ] @ [ 3 ; 4 ; 5] (* concaténation de deux listes (de même type) *) ;;
- : int list = [1; 2; 3; 4; 5]
# List.length [ "hello" ; "world" ; "!" ] (* accès à la longueur *) ;;
- : int = 3
# List.hd [ 1 ; 2 ; 3 ] (* récupération de l'élément de tête de liste *) ;;
- : int = 1
# List.tl [ 1 ; 2 ; 3 ] (* récupération de la queue de liste (i.e. sans la tête) *) ;;
- : int list = [2; 3]
# String.concat "-" [ "bonjour" ; "le" ; "monde" ] (* concaténation d'une liste de chaînes *) ;;
- : string = "bonjour-le-monde"

Beaucoup d'autres fonctions sont disponibles dans le module List.

1.2. Comparaisons

OCaml offre des fonctions de comparaisons polymorphes, c'est-à-dire opérant sur n'importe quels types de données, à la seule condition que les valeurs comparées soient du même type. Elles sont donc de type 'a -> 'a -> bool, indiquant clairement que le type des deux arguments doit être le même.

Voyons ces fonctions:

# 1 = 2 (* égalité structurelle sur des entiers *) ;;
- : bool = false
# "bonjour" = "monde" (* ... ou sur des chaînes *) ;;
- : bool = false
# (1, 2, 3) = (1, 2, 4) (* ... ou des n-uplets *) ;;
- : bool = false
# [ 1 ; 2 ; 3 ] <> [ 1 ; 2 ; 4 ] (* différence structurelle, ici sur des listes *) ;;
- : bool = true
# not ([ 1 ; 2 ; 3 ] = [ 1 ; 2 ; 4 ])
  (* idem que ci-dessus, en utilisant la négation de l'égalité *) ;;
- : bool = true
# 1 < 2 (* infériorité (structurelle) stricte *) ;;
- : bool = true
# 1 <= 2 (* inférieur ou égal *) ;;
- : bool = true
# "bonjour" > "monde" (* supérieur *) ;;
- : bool = false
# [ 1 ; 2 ; 3 ] >= [ 1 ; 2 ] (* supérieur ou egal *) ;;
- : bool = true
# 1 == 2 (* égalité physique *) ;;
- : bool = false
# 1 != 2 (* différence physique *) ;;
- : bool = true

L'égalité structurelle teste l'égalité de deux valeurs en explorant leur structure, alors que l'égalité physique teste si les deux valeurs occupent la même zone mémoire. Ces deux égalités retournent le même résultat pour les valeurs simples : booléens, caractères, entiers et constructeurs constants.

La comparaison structurelle repose sur l'ordre des entiers pour les entiers, les chaînes et les caractères (en utilisant les codes ascii), l'ordre naturel sur les flottants.

1.3. Structure de contrôle conditionnelle

La syntaxe de la conditionnelle peut prendre deux formes:

if expression de type bool then expression
if expression de type bool then expression1 else expression2

La première forme, sans écriture de la branche else, est en fait évaluée comme

if expression de type bool then expression else ()

Le typage correct de l'expression toute entière impose que les expressions des branches then et else soient du même type. En effet, si ce n'était pas le cas, l'expression entière aurait un type différent selon que l'expression de condition est vraie ou fausse. L'expression toute entière est donc du même type que celui des branches.

Pour cette raison, l'expression du then de la première forme doit être de type unit, car l'expression de la branche else implicite est (), qui est de type unit.

Voyons quelques exemples:

# if true then 1 lsl 5 + 10 else 1
  (* lsl est le décalage logique de bits vers la gauche *) ;;
- : int = 42
# (if 12 * 4 < 40 then 15 else 2) + (if 3 > 4 then 10 else 4 * 10)
  (* une expression conditionnelle est aussi une expression dont le calcul
     retourne une valeur. *);;
- : int = 42
# if true then 1;;
Error: This expression has type int but an expression was expected of type
         unit

La dernière expression est un exemple d'expression mal typée, car les types des branches then et else diffèrent, ce que signale l'interprète: l'expression 1 est de type entier alors qu'on attend ici une expression de type unit (comme la branche else).

1.4. Déclarations de valeurs

Les déclarations de valeurs sont des associations entre un nom (un identifiant) et une valeur. L'obtention de la valeur nécessite le calcul de l'expression de la définition de l'identifiant. On dit que la valeur est liée (en anglais bound) au nom dans l'environnement. Les identifiants sont de la forme suivante: [a-z_][0-9A-Za-z_']*, c'est-à-dire qu'ils peuvent contenir les caractères 'a' à 'z', 'A' à 'Z', '0' à '9', _ et ' mais doivent commencer par une lettre minuscule ou le caractère _.

Il existe deux types de déclarations: globales et locales.

1.4.1. Déclarations globales

La syntaxe est la suivante:

let identifiant = expression;;

La valeur résultant du calcul de l'expression est ensuite associée à l'identifiant. Cet identifiant est alors connu et peut être utilisé dans toutes les expressions qui suivent dans le programme. Il est alors remplacé dans ces expressions par sa valeur associée:

# let x = 1 ;;
val x : int = 1
# let y = 41 ;;
val y : int = 41
# let z = x + y ;;
val z : int = 42

Il est impossible d'utiliser un identifiant inconnu:

# foo + 1;;
Error: Unbound value foo

Le message indique que la valeur foo n'est pas liée dans l'environnement.

On remarquera qu'il est syntaxiquement impossible de déclarer un nom sans valeur. Cela est fait exprès pour éviter des problèmes de variables non initialisées comme en C:

void foo () { int toto ; ... }

Dans la fonction C ci-dessus, on peut déjà utiliser la variable toto sans savoir à quoi elle fait référence, ce qui peut provoquer des erreurs d'exécution aléatoires.

1.4.2. Déclarations locales

Il est possible de déclarer localement des valeurs. Le nom de la valeur n'est alors visible que dans une seule expression. La syntaxe est la suivante:

let identifiant = expression_1 in expression_2

La valeur de l'expression_1 est calculée et liée à l'identifiant. Ce dernier n'est visible que dans l'expression_2. Exemple:

# let foo = (* déclaration globale foo *)
    let bar =
      let glop = 1 in (* déclaration locale de glop *)
        glop + 2
    in (* déclaration locale de bar, glop n'est plus visible *)
      let gee = bar + 1 in (* déclaration locale de gee, utilisant bar *)
        gee + bar + 2 (* utilisation de gee et bar locales *);;
val foo : int = 9
# let buz = bar + foo (* bar n'est plus visible ici *) ;;
Error: Unbound value bar

L'indentation ci-dessus permet de bien voir l'imbrication des expressions. Cependant, elle prend davantage de place en largeur. On trouvera souvent cette seconde indentation, n'ajoutant pas de décalage supplémentaire après un in:

# let foo =
    let bar =
      let glop = 1 in
      glop + 2
    in
    let gee = bar + 1 in
    gee + bar + 2;;
val foo : int = 9

Des conseils sur l'indentation sont disponibles ici.

Avertissement 4: Déclarations locales et globales

Une déclaration locale (let ... = ... in ...) ne peut englober une déclaration globale (let ... = ... ;;):

# let x = 1 in let y = 2;;
Error: Syntax error
1.4.3. Déclarations simultanées

Il est possible de déclarer simultanément plusieurs valeurs globales:

let ident_1 = expression_1
and ident_2 = expression_2
...
and ident_N = expression_N;;

ou locales:

let ident_1 = expression_1
and ident_2 = expression_2
..
and ident_N = expression_N in
expression

Les valeurs ne deviennent cependant visibles qu'après toutes les déclarations simultanées:

# let x_int = 1
and x_float = 1.0;;
val x_int : int = 1
val x_float : float = 1.
# let y_int = 2
and y_float = float_of_int y_int;;
Error: Unbound value y_int
Hint: Did you mean x_int?

Une autre façon de définir plusieurs valeurs en même temps est d'utiliser la notation des n-uplets:

# let (a, b, c) = (1, 2, 3);;
val a : int = 1
val b : int = 2
val c : int = 3
# let (a, b) = (1, 2, 3);;
Error: This expression has type 'a * 'b * 'c
       but an expression was expected of type 'd * 'e
# let (a, b, c) = (1, 2);;
Error: This expression has type 'a * 'b
       but an expression was expected of type 'c * 'd * 'e

Contrairement à d'autres langages, le compilateur veille à ne pas avoir de variable non initialisée comme cela serait le cas pour c dans let (a, b, c) = (1, 2). Les valeurs de l'expression de définition ne sont pas non plus "recyclées" comme dans le langage R (ce qui aurait donné la valeur 1 à c dans notre exemple).

Enfin, dans let (a, b) = (1, 2, 3), le compilateur nous indique clairement que la construction n'est pas correcte puisque nous avons un n-uplet de taille 3 à droite alors que nous le filtrons par un n-uplet de taille 2. Nous verrons le filtrage en détail dans la section 2.1.

1.5. Expressions fonctionnelles, fonctions

Une expression fonctionnelle est constituée d'un paramètre et d'un corps. Le paramètre formel est un nom de variable et le corps une expression. On dit que le paramètre est abstrait. C'est pour cela qu'une expression fonctionnelle est aussi appelée abstraction.

1.5.1. Définition de fonctions

On définit une fonction par la syntaxe suivante:

function identifiant -> expression

Une fonction ne prend qu'un seul paramètre. Cependant, elle peut renvoyer à son tour une valeur fonctionnelle, ce qui permet de simuler des fonctions à plusieurs paramètres:

function identifiant_1 -> function identifiant_2 -> expression

Voyons quelques exemples de définition de fonctions:

# function x -> x * x (* la fonction carré sur les entiers *) ;;
- : int -> int = <fun>
# function x -> function y -> x +. y (* l'addition sur les flottants *) ;;
- : float -> float -> float = <fun>
# fun x y -> x +. y (* raccourci syntaxique pour l'expression ci-dessus *);;
- : float -> float -> float = <fun>

On remarquera le type de ces expressions, inféré automatiquement par l'interprète. Les types des valeurs fonctionnelles sont notés avec ->. Ainsi, int -> int indique une valeur fonctionnelle prenant en paramètre une valeur de type int et retournant une valeur de type int.

Le type float -> float -> float est équivalent à float -> (float -> float) (associativité à droite de ->), ce qui signifie que la valeur prend en paramètre un float et retourne une valeur fonctionnelle de type float -> float qui elle aussi prend un float mais retourne une valeur de type float.

1.5.2. Application de fonctions

L'application d'une fonction à une valeur s'écrit en juxtaposant une valeur fonctionnelle et un paramètre:

# (function x -> x + 1) 41 ;;
- : int = 42
# ((function x -> function y -> x +. y) 1.0) 41.0 ;;
- : float = 42.
# (function x -> function y -> x +. y) 1.0 41.0 (* suppression des parenthèses inutiles *) ;;
- : float = 42.

Dans la dernière expression ci-dessus, nous supprimons les parenthèses inutiles car l'application est associative à gauche, c'est-à-dire que le premier paramètre 1.0 est appliqué à function x -> ..., ce qui revient donc à calculer l'expression (function y -> 1.0 +. y) (le paramètre x est remplacé par la valeur 1.0 à laquelle est appliquée la fonction); la valeur obtenue est encore une fonction qui est alors appliquée à 41.0 pour finalement calculer 1.0 +. 41.0.

Il est donc possible d'appliquer un seul paramètre à la même valeur fonctionnelle:

# (function x -> function y -> x +. y) 1.0;;
- : float -> float = <fun>

Le résultat est une expression fonctionnelle. Cet aspect est parfois appelé application partielle quand on considère la fonction comme ayant deux paramètres x et y.

L'expression function (x, y) -> ... n'est pas équivalente à function x -> function y -> .... En effet, dans la première on définit une fonction prenant en paramètre un couple, tandis que la seconde définit une fonction retournant une fonction, ce qui revient à une fonction à deux paramètres.

Le mode d'évaluation de l'application en OCaml est le passage par valeur, c'est-à-dire que l'expression en paramètre d'une fonction est d'abord évaluée et ensuite cette valeur est passée à la fonction pour évaluer cette dernière. Cela est différent du passage par nom. Ainsi, dans l'expression

# (function x -> x+1) (24 + 17);;
- : int = 42

l'expression 24 + 17 est d'abord évaluée et la valeur 41 est passée à la fonction pour en évaluer le corps.

La valeur de retour d'une fonction est la valeur de l'expression du corps de la fonction.

Les fonctions définies et appliquées "au vol" sont appelées fonctions anonymes, car elles ne sont pas liées à un identifiant. Bien souvent, on nommera les fonctions pour les appliquer plus tard, en effectuant des déclarations globales ou locales:

# let square = function x -> x * x (* fonction carré sur les entiers *) ;;
val square : int -> int = <fun>
# let add = fun x y -> x + y (* en utilisant le raccourci de syntaxe *) ;;
val add : int -> int -> int = <fun>
# let sub = function x -> function y -> x - y ;;
val sub : int -> int -> int = <fun>
# let sub x y = x - y (* idem en utilisant un autre raccourci de syntaxe *) ;;
val sub : int -> int -> int = <fun>

Enfin, le compilateur effectue des vérifications de type lors de l'application de fonction, comme nous l'avons vu précédemment sur les opérateurs arithmétiques. Voyons quelques exemples corrects et incorrects:

# square 24 ;;
- : int = 576
# square 24.0 (* erreur: le paramètre doit être un entier *) ;;
Error: This expression has type float but an expression was expected of type
         int
# (square 1) 2 (* erreur (square 1) n'est pas une fonction et ne peut être appliquée *) ;;
Error: This expression has type int
       This is not a function; it cannot be applied.
# let add1 = add 1 (* application "partielle" de add pour obtenir une fonction d'incrément *) ;;
val add1 : int -> int = <fun>
# add1 41 ;;
- : int = 42
Avertissement 5: Place des parenthèses

Les parenthèses ne peuvent être mises n'importe où:

# let f x y = x + y ;;
val f : int -> int -> int = <fun>
# f 1 2 ;;
- : int = 3
# (f 1) 2 ;;
- : int = 3
# (f 1 2) ;;
- : int = 3
# ((f 1) 2) ;;
- : int = 3
# f ( 1 ) 2 ;;
- : int = 3
# f 1 ( 1 + 1);;
- : int = 3
# f ( 0 + 1 ) ( 2 + 0 );;
- : int = 3
# f (1 2);;
Error: This expression has type int
       This is not a function; it cannot be applied.
1.5.3. Fermetures

Considérons l'exemple suivant:

# let increment = 2;;
val increment : int = 2
# let add_increment x = x + increment ;;
val add_increment : int -> int = <fun>
# add_increment 1 ;;
- : int = 3
# let increment = 20 ;;
val increment : int = 20
# add_increment 1 ;;
- : int = 3

Nous constatons que la valeur retournée par add_increment 1 ne varie pas, même après avoir redéfini la variable increment.

Ce comportement, qui est celui souhaité, est obtenu grâce aux fermetures. Une fermeture (en anglais closure) est composée d'une fonction et de son environnement, c'est-à-dire les valeurs liées à des identifiants au moment de la définition de fonction.

En OCaml, la définition d'une expression fonctionnelle entraîne la création d'une fermeture pour garantir ce comportement, et c'est cette fermeture qui est retournée. Lors de l'application d'une fonction, la valeur du paramètre est associée au paramètre et le corps de la fonction est évalué dans l'environnement conservé dans la fermeture enrichi par la valeur liée au paramètre.

1.5.4. Opérateurs infixes

Nous avons vu comment définir des fonctions préfixes, c'est-à-dire qu'elles sont positionnées avant les expressions sur lesquelles elles sont appliquées, comme dans add 30 12.

Il est parfois plus lisible d'avoir des fonctions s'appliquant à deux paramètres et dont l'application s'écrira plus naturellement avec le nom de la fonction entre ses paramètres. C'est le cas des opérateurs arithmétiques vus précédemment: il est plus habituel d'écrire 1 + 2 que + 1 2.

Il est possible en OCaml de définir de tels opérateurs, en utilisant les parenthèses autour de l'identifiant et en utilisant pour ce dernier certains caractères réservés:

# let (++) (x, y) n = (x + n, y + n);;
val ( ++ ) : int * int -> int -> int * int = <fun>
# (2, 0) ++ 2 (* utilisation en position infixe *) ;;
- : int * int = (4, 2)
# (++) (2, 0) 2 (* utilisation en position préfixe *) ;;
- : int * int = (4, 2)

Les caractères réservés à ce genre de définition sont indiqués ici.

1.5.5. Ordre supérieur

Une valeur fonctionnelle (une fermeture) peut être retournée comme résultat. Elle peut également être prise comme argument d'une fonction. Les fonctions prenant en argument ou retournant des valeurs fonctionnelles sont dites d'ordre supérieur. Par exemple:

# let h = function f -> function y -> (f y) + y ;;
val h : (int -> int) -> int -> int = <fun>

La bibliothèque standard est pleine de fonctions d'ordre supérieur, souvent polymorphes. Ainsi, la fonction List.map prend en paramètres une fonction et une liste et applique la fonction à chaque élément de la liste pour construire une nouvelle liste:

# List.map ;;
- : ('a -> 'b) -> 'a list -> 'b list = <fun>
# List.map square [ 1 ; 2 ; 3 ; 4 ; 5 ; 6 ];;
- : int list = [1; 4; 9; 16; 25; 36]
1.6. Récursion

L'ajout à l'environnement d'une variable globale ou locale est fait à la fin de la déclaration. Il est donc impossible d'utiliser la variable dans sa définition, puisqu'elle n'est pas encore dans l'environnement:

# let compte x = if x <= 0 then x else compte (x-1) + 1;;
Error: Unbound value compte
Hint: Did you mean compare?

Pour pouvoir déclarer des valeurs récursives (qui font appel à elles-mêmes), il faut explicitement les indiquer comme telles, en utilisant le mot-clé rec:

# let rec compte x = if x <= 0 then x else compte (x-1) + 1;;
val compte : int -> int = <fun>
# compte 10;;
- : int = 10

Il est également possible de définir des valeurs mutuellement récursives globales:

# let rec triple x = if x <= 0 then 0 else triple_aux (x - 2) + 1
and triple_aux x = triple (x+1) + 2;;
val triple : int -> int = <fun>
val triple_aux : int -> int = <fun>
# triple 20;;
- : int = 60

ou locales:

# let rec triple2 x = if x <= 0 then 0 else triple2_aux (x - 2) + 1
and triple2_aux x = triple2 (x+1) + 2 in
triple2 20;;
- : int = 60
# triple2 30;;
Error: Unbound value triple2
Hint: Did you mean triple?
1.7. Polymorphisme et contrainte de type
1.7.1. Polymorphisme

Les fonctions dont l'un des paramètres ou la valeur de retour est d'un type qu'il n'est pas nécessaire de préciser sont dites polymorphes. Le synthétiseur de types contenu dans le compilateur d'OCaml trouve le type le plus général pour chaque expression. Dans ce cas, OCaml utilise des variables, ici 'a et 'b, pour désigner ces types généraux. Ces variables sont instanciées par le type de l'argument lors de l'application de la fonction.

Avec les fonctions polymorphes d'OCaml nous cumulons les avantages de pouvoir écrire un code générique utilisable pour des valeurs de tout type, tout en conservant la sûreté d'exécution du typage statique. En outre, la vérification des types est effectuée à la compilation, donc la généricité du code ne nuit pas à l'efficacité du programme.

Quelques exemples:

# fst ;;
- : 'a * 'b -> 'a = <fun>
# fst (1, 'a');;
- : int = 1
# fst ("hello", 1.2);;
- : string = "hello"
# List.map ;;
- : ('a -> 'b) -> 'a list -> 'b list = <fun>
# square ;;
- : int -> int = <fun>
# List.map square [ 1 ; 2 ; 3 ; 4 ; 5 ; 6 ];;
- : int list = [1; 4; 9; 16; 25; 36]
# string_of_int ;;
- : int -> string = <fun>
# List.map string_of_int [ 1 ; 2 ; 3 ; 4 ; 5 ; 6 ];;
- : string list = ["1"; "2"; "3"; "4"; "5"; "6"]
1.7.2. Contrainte de type

Il est possible de forcer le type des valeurs, ce qui est utile dans plusieurs cas:

  • pour améliorer la lisibilité du programme, en indiquant explicitement les types des paramètres d'une fonction par exemple,
  • pour n'autoriser l'utilisation d'une valeur que dans un certain contexte,
  • pour indiquer quel type devra prendre une valeur modifiable (cf. chapitre Programmation impérative); en effet, lors de leur création certaines valeurs ne permettent pas de déterminer leur type (par exemple la liste vide []), ce qui pose problème lorsqu'il s'agit de données modifiables: le compilateur doit pouvoir vérifier qu'on n'affecte pas une valeur du mauvais type à une donnée modifiable,
  • pour comprendre un problème de type signalé par le compilateur: en indiquant explicitement les types attendus, le typeur peut signaler au plus tôt les conflits de type.

Les contraintes de types d'une variable sont notées ainsi:

( identifiant : type )

Exemple:

# let (mon_map : ('a -> int) -> 'a list -> int list) = List.map;;
val mon_map : ('a -> int) -> 'a list -> int list = <fun>
# mon_map square [ 1 ; 2 ; 3 ; 4 ; 5 ; 6 ];;
- : int list = [1; 4; 9; 16; 25; 36]
# mon_map string_of_int [ 1 ; 2 ; 3 ; 4 ; 5 ; 6 ];;
Error: This expression has type int -> string
       but an expression was expected of type int -> int
       Type string is not compatible with type int
# mon_map int_of_string [ "1" ; "2" ; "3" ; "4" ; "5" ; "6" ];;
- : int list = [1; 2; 3; 4; 5; 6]
Avertissement 6: Contrainte et polymorphisme

Il n'est pas possible de forcer le type d'un identifiant à être polymorphe là où il ne l'est pas:

# let (f : 'a -> 'a -> int) = fun x y -> x + 1;;
val f : int -> int -> int = <fun>
1.8. Exercices

On pourra s'aider de la documentation du module List.

Exercice 1: Redéfinition de List.map

Réécrire la fonction List.map, prenant en paramètres une fonction f et une liste d'éléments et retournant une nouvelle liste, résultat de l'application de f à chaque élément. La fonction conserve l'ordre des éléments. On utilisera la récursion et les fonctions List.length, List.tl, List.hd et le constructeur ::.

Exercice 2: Le plus petit entier

Ecrire une fonction prenant une liste d'entiers et retournant le plus petit ou max_int si la liste est vide.

Exercice 3: Moyenne d'une liste

Ecrire une fonction prenant une liste d'entiers et retournant la moyenne sous forme d'un flottant, ou 0. si la liste est vide.

2. Déclaration de types et filtrage de motifs
2.1. Filtrage de motif (pattern matching)

Le filtrage permet:

  • d'effectuer des traitements adaptés selon la structure et le contenu d'une valeur,
  • d'accéder à une partie d'une valeur en la déconstruisant.

Les motifs s'expriment dans une syntaxe presque identique à celle des expressions, bien qu'il ne soit pas question d'évaluation mais de test sur la structure et le contenu des valeurs filtrées. Le terme anglais pour le filtrage est pattern matching.

La syntaxe est la suivante:

match expression_0 with
 | pattern_1 -> expression_1
 | pattern_2 -> expression_2
 | ...

L'évaluation de cette expression se déroule ainsi: L'expression_0 est évaluée. Sa valeur est ensuite comparée au premier motif pattern_1. Si la valeur est filtrée (elle correspond aux contraintes de ce motif), alors l'expression_1 est évaluée en une valeur qui est la valeur de toute la construction match ... with. Si ce n'est pas le cas, la valeur de expression_0 est comparée au motif pattern_2, et ainsi de suite jusqu'à ce qu'un motif corresponde à la valeur.

Si aucun motif ne correspond à la valeur à filtrer, une exception (cf. 3.1) Match_failure est levée. Pour se prémunir contre cette erreur de programmation qui correspond à un cas non prévu par le programmeur, deux solutions:

  • utiliser un motif "attrape-tout" exprimé par _,
  • s'assurer que les motifs permettent d'attraper tous les cas; ce travail est facilité par le compilateur OCaml qui signale les constructions match ... with non-exhaustives et donne un exemple de valeur non filtrée.

Les motifs permettent à la fois

  • d'exprimer des contraintes sur la valeur filtrée,
  • de lier de nouveaux identifiants à des parties de la valeur filtrée.

Voyons maintenant quelques exemples:

# match 1 + 1 with
  0 -> print_endline "bizarre"
| 1 -> print_endline "étrange"
| 2 -> print_endline "ouf!"
;;
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
3
ouf!
- : unit = ()

Dans l'exemple ci-dessus, l'expression 1 + 1 est évaluée et ensuite comparée jusqu'à trouver un motif lui correspondant, ici 2, ce qui provoque l'évaluation de l'expression print_endline "ouf!". Le compilateur émet un avertissement indiquant que la construction de filtrage n'est pas exhaustive, en exhibant un cas non filtré, la valeur 3.

# match List.map string_of_int [ 1 ; 2 ; 3 ] with
  []
| _ :: [] -> assert false
| [s1 ; s2] -> assert false
| s1 :: s2 :: s3 :: _ ->
    List.iter print_endline [ s1 ; s2 ; s3 ]
| l ->
    List.iter print_endline l
;;
Warning 11: this match case is unused.
1
2
3
- : unit = ()

Dans cet exemple, nous filtrons une valeur de type string list. Les premier ([]) et deuxième (_::[]) motifs filtrent respectivement la liste vide et n'importe quelle liste à un élément, et partagent le même traitement associé (assert false1). Le troisième motif [s1 ; s2] filtre les listes à deux éléments, en liant le premier élément à l'identifiant s1 et le second à l'élément s2. Dans notre exemple, la liste filtrée aura toujours trois éléments donc nous ne passerons jamais dans cette branche.

Le motif s1 :: s2 :: s3 :: _ filtre toutes les listes d'au moins trois éléments. Il utilise l'opérateur de construction de liste :: (appelé cons), avec à gauche un élément et à droite une liste. Dans ce motif, les trois premiers éléments de la liste sont associés aux identifiants s1, s2 et s3. Les identifiants créés dans un motif ne sont visibles que dans l'expression associée à ce motif.

Enfin, OCaml nous indique que le dernier motif l, qui permet de filtrer n'importe quelle liste en l'associant à l'identifiant l, est inutile car les motifs précédents permettent de filtrer tous les cas possibles.

Une erreur fréquente lorsqu'on commence à utiliser la structure de filtrage est d'utiliser un identifiant pour imposer une contrainte d'égalité avec un identifiant prédéfini:

# let x = 3;;
val x : int = 3
# match [ 0 ] with
  [x] -> true
| _ -> false;;
- : bool = true

Ce n'est pas l'effet attendu. Le x du motif [x] crée une nouvelle liaison dans l'environnement entre un nouvel identifiant x et la valeur 0. Il n'est fait aucune comparaison avec l'identifiant x précédemment défini. La bonne façon de faire sera d'utiliser une clause when permettant d'ajouter une expression de type bool à un motif. Dans ce cas, l'expression associée au motif (à droite de ->) ne sera exécutée que si l'expression est évaluée à vraie. Si ce n'est pas le cas, l'effet sera le même que si le motif ne correspondait pas à la valeur filtrée, et l'évaluation de la structure de filtrage passera au motif suivant:

# match [ 0 ] with
| [y] when y = x -> true
| _ -> false
;;
- : bool = false

A noter que l'on n'écrira pas:

# match [ 0 ] with
| [x] when x = x -> true
| _ -> false
;;
- : bool = true

car les deux x de x = x font référence tous deux à l'identifiant créé dans le motif [x]. Les clauses when sont également appelées gardes.

Avertissement 7: Pas de liaisons multiples

Il n'est pas possible de lier plusieurs fois la même variable dans un motif, y compris pour exprimer une contrainte d'égalité entre deux parties de l'expression filtrée:

# match (1,2) with
  (x,x) -> true
| _ -> false
;;
Error: Variable x is bound several times in this matching

Le mot clé as permet de créer un nouvel identifiant pour tout ou partie d'un motif:

# match [ [ 1 ; 2 ] ; [ 3 ; 4 ] ] with
  [ [ 1 ; 2 ] as liste1 ; liste2 ] as tout ->
   List.iter print_int liste1;
   print_newline();
   List.iter (fun l -> List.iter print_int l) tout;
   print_newline();
| _ -> assert false
;;
12
1234
- : unit = ()

Nous verrons d'autres exemples de filtrage dans la suite du document, car cette construction est très utilisée.

2.2. Exercice
Exercice 4: Liste palindrome

Définir une fonction prenant en paramètre une liste d'éléments quelconques et retournant vrai si la liste est un palindrome, faux sinon.

Quelques tests:

# palindrome_list [1 ; 2 ; 3 ; 2 ; 1 ];;
- : bool = true
# palindrome_list ['1' ; '2' ; '3' ; '3' ; '2' ; '1' ];;
- : bool = true
# palindrome_list ['r' ; 'a' ; 'd' ; 'a'; 'r'];;
- : bool = true
# palindrome_list ['r' ; 'a' ; 'v' ; 'e'; 'r'];;
- : bool = false
# palindrome_list [1.0 ; 2.0 ; 3.0 ; 4.0 ; 2.0 ; 1.0];;
- : bool = false
# palindrome_list [];;
- : bool = true
2.3. Déclaration de valeurs par filtrage d'un motif

Il est possible d'utiliser le pattern-matching pour déclarer plusieurs variables en même temps, en filtrant le résultat d'une expression:

# let (x, y, z) = (1, "2", 3.0);;
val x : int = 1
val y : string = "2"
val z : float = 3.
# let [s1 ; s2 ; s3] = [ "un" ; "deux" ; "trois"];;
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
(_::_::_::_::_|_::_::[]|_::[]|[])
val s1 : string = "un"
val s2 : string = "deux"
val s3 : string = "trois"
# let [x1 ; x2] = [ 1 ; 2 ; 3 ] ;;
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
(_::_::_::_|_::[]|[])
Exception: Match_failure ("", 1, 4).
2.4. Déclaration de types

OCaml permet de définir ses propres types de données, en plus de ceux de base. La syntaxe est la suivante:

type identifiant = définition

Les types mutuellement récursifs seront définis de la façon suivante:

type identifiant_1 = définition_1
and identifiant_2 = définition_2
...
and identifiant_N = définition_N

On remarquera qu'il n'y a pas de mot-clé rec pour les définitions de type, chaque type pouvant être récursif sans syntaxe particulière.

OCaml ≥ 4.02.2

Cependant, le mot-clé nonrec permet d'avoir une définition explicitement non récursive, c'est-à-dire que le type introduit n'est pas connu dans sa définition:

# type nonrec my_tree = Node of my_tree list | Value of int;;
Error: Unbound type constructor my_tree
OCaml ≥ 4.02.2

Les identifiants de types ont la même syntaxe que les identifiants de valeurs, mais sont dans un espace de noms différent, ce qui signifie que l'on peut définir une valeur foo et un type foo sans problème.

Les paramètres des types paramétrés doivent être indiqués avant l'identifiant:

type 'a identifiant = définition utilisant le paramètre de type 'a
type ('a, 'b) identifiant = définition utilisant 'a et 'b

Ainsi, on peut définir le type des listes de paires d'éléments d'un type en paramètre:

# type 'a pairs = ('a * 'a) list;;
type 'a pairs = ('a * 'a) list
# let int_pair_list = [ (1, 2) ; (5, 4) ] ;;
val int_pair_list : (int * int) list = [(1, 2); (5, 4)]
# let (int_pairs : int pairs) = [ (1, 2) ; (3, -3) ; (6, 8)];;
val int_pairs : int pairs = [(1, 2); (3, -3); (6, 8)]
# let (bool_pairs : bool pairs) = [ (true, true) ; (false, false) ; (true, false)];;
val bool_pairs : bool pairs = [(true, true); (false, false); (true, false)]

Ce type étant défini uniquement à partir de types existants, nous devons indiquer explicitement le type que nous voulons voir apparaître, sinon le compilateur infère le type à partir des types de base, comme pour int_pair_list ci-dessus. Cependant, nous pouvons utiliser indifféremment des valeurs de type 'a pairs ou du type ('a * 'a) list, le compilateur réalisant l'unification de ces types pour vérifier qu'ils sont bien compatibles:

# (=);;
- : 'a -> 'a -> bool = <fun>
# int_pair_list;;
- : (int * int) list = [(1, 2); (5, 4)]
# int_pairs;;
- : int pairs = [(1, 2); (3, -3); (6, 8)]
# int_pair_list = int_pairs;;
- : bool = false

Si les types ne sont pas compatibles, le compilateur signale une erreur:

# let (float_pairs : float pairs) = [ (1., 2.) ; (3., 4.)];;
val float_pairs : float pairs = [(1., 2.); (3., 4.)]
# int_pairs = float_pairs;;
Error: This expression has type float pairs = (float * float) list
       but an expression was expected of type int pairs = (int * int) list
       Type float is not compatible with type int
2.5. Enregistrements
2.5.1. Définition d'un type

Les enregistrements sont des n-uplets dont chaque champ est nommé à la manière des record de Pascal ou des struct de C. Un enregistrement correspond toujours à la déclaration d'un nouveau type. Un type enregistrement est défini par la déclaration de son nom, du nom de chacun de ses champs et de leur type.

La syntaxe est la suivante:

type [variables de type] identifiant = {
  nom_de_champ_1 : type_1 ;
  ...
  nom_de_champ_n : type_n ;
}

Un type enregistrement ne peut avoir deux noms de champs identiques.

2.5.2. Création de valeurs

Par mesure de sûreté, le compilateur impose que chaque champ soit initialisé, lors de la création d'une valeur de type enregistrement. Cela évite des problèmes de champs non initialisés comme on peut en rencontrer en langage C.

On peut créer une valeur d'un type enregistrement de deux façons:

  • soit à partir de rien, avec la syntaxe suivante:
    { champ_1 = expression_1 ; ... ; champ_n = expression_n }
  • soit à partir d'une autre valeur du même type, en modifiant certains champs:
    { identifiant with champ_i = expression_i ; ... ; champ_j = expression_j } 

L'ordre dans lequel le contenu des champs est défini est sans importance. Cependant, on aura à cœur de définir les champs toujours dans le même ordre afin de faciliter la lecture et la maintenance du programme. Par ailleurs, l'ordre d'affectation des champs n'est pas spécifié, ni l'ordre dans lequel les expressions correspondantes sont évaluées. On ne se reposera donc pas sur cet ordre si ces expressions ont des effets de bord (lors de l'utilisation de traits impératifs du langage).

2.5.3. Accès aux champs

L'accès à un champ d'une valeur de type enregistrement se fait en utilisant le point '.' entre l'identifiant de la valeur et le nom du champ. Ainsi, foo.bar.gee représente l'accès à la valeur du champ gee de la valeur du champ bar de la valeur foo.

2.5.4. Filtrage

Il est bien sûr possible d'utiliser le filtrage sur des valeurs de type enregistrement, en mettant des contraintes sur tout ou partie des champs du type:

match expression with
{ champ_i = motif_i ; ... ; champ_y = motif_y } -> ...
2.5.5. Exemple

Voici un exemple de définition et d'utilisation d'un type enregistrement coord avec deux champs x et y, tous deux de type float:

# type coord = { x : float ; y : float};;
type coord = { x : float; y : float; }
# let origin = { x = 0. ; y = 0. };;
val origin : coord = {x = 0.; y = 0.}
# let add p1 p2 = { x = p1.x +. p2.x ; y = p1.y +. p2.y };;
val add : coord -> coord -> coord = <fun>
# let unite = { x = 1. ; y = 1. };;
val unite : coord = {x = 1.; y = 1.}
# let unite_x = { unite with y = 0. };;
val unite_x : coord = {x = 1.; y = 0.}
# let p1 = add (add origin unite) unite;;
val p1 : coord = {x = 2.; y = 2.}
# p1 = unite;;
- : bool = false
# match add p1 unite with
  { x = mon_x } as foo when foo.y > 1. -> string_of_float mon_x
| { x = x ; y = y } -> string_of_float (x +. y);;
- : string = "3."
2.6. Types somme
2.6.1. Définition d'un type

À la différence des n-uplets ou des enregistrements, qui correspondent à un produit cartésien, la déclaration d'un type somme correspond à une union d'ensembles. On regroupe dans un même type des types différents (par exemple des entiers et des chaînes de caractères). Les différents membres de la somme sont discriminés par des constructeurs qui permettent d'une part, comme leur nom l'indique, de construire les valeurs de ce type et d'autre part d'accéder aux composantes de ces valeurs grâce au filtrage de motif. Appliquer un constructeur à un argument, c'est indiquer que la valeur retournée appartient à ce nouveau type.

On déclare un type somme en donnant le nom de ses constructeurs et le type de leur éventuel argument.

La syntaxe est la suivante:

type [variables de type] identifiant =
  Constructeur_1
  ...
| Constructeur_i of type_i
  ...
| Constructeur_n of type_n1 * ... * type_nm

Les noms des constructeurs doivent commencer par une majuscule.

Chaque constructeur d'un type somme peut avoir 0, 1 ou plusieurs paramètres, dont le type est indiqué dans la définition du type somme.

Un type somme ne peut avoir deux constructeurs de même nom.

Voici un exemple de définition d'un type somme:

# type direction =
  Nord
| Sud
| Est
| Ouest
| Compose of direction * direction;;
type direction = Nord | Sud | Est | Ouest | Compose of direction * direction
2.6.2. Création de valeurs

Une valeur d'un type somme est créée à l'aide d'un constructeur de ce type et des paramètres adaptés selon le constructeur, par la syntaxe suivante:

  • pour un constructeur sans paramètre: Constructeur,
  • pour un constructeur avec un paramètre: Constructeur expression,
  • pour un constructeur avec n paramètres:
    Constructeur (expression_1,...,expression_n)

Avec notre exemple de type direction, cela donne par exemple:

# let nne = Compose (Nord, Compose (Nord, Est));;
val nne : direction = Compose (Nord, Compose (Nord, Est))
2.6.3. Filtrage

Il est bien sûr possible d'utiliser le filtrage sur des valeurs de type somme, en procédant par cas sur les constructeurs du type:

match expression de type somme with
| Constructeur_1 -> expression_1
| Constructeur_i motif_i -> expression_i
| Constructeur_j (motif_j1, ..., motif_jn) -> expression_j
...

Par exemple:

# let rec string_of_direction = function
  Nord -> "nord"
| Sud -> "sud"
| Est -> "est"
| Ouest -> "ouest"
| Compose (d1, d2) -> (string_of_direction d1)^"-"^(string_of_direction d2);;
val string_of_direction : direction -> string = <fun>
# string_of_direction nne;;
- : string = "nord-nord-est"
2.6.4. Exercice
Exercice 5: Représentation d'expressions arithmétiques

Définir un type somme expr pour représenter les expressions contenant les 4 opérations habituelles sur les entiers ainsi que les valeurs entières. On aura donc 5 constructeurs.

Ensuite, définir une fonction prenant une valeur de ce type et calculant la valeur entière en réalisant l'opération décrite.

2.7. Portée des déclarations

Les déclarations de type ont la même portée que les déclarations globales de variables et peuvent comme elles être masquées par de nouvelles déclarations avec des noms similaires. Cependant, les valeurs définies avec un type t ne changent pas de type en cas de définition d'un nouveau type t (et heureusement!). Par contre, ces homonymies peuvent rendre les messages d'erreur du compilateur un peu déroutants:

# type t = Foo | Bar;;
type t = Foo | Bar
# let x = Foo;;
val x : t = Foo
# type t = Gee | Buz;;
type t = Gee | Buz
# let y = Gee;;
val y : t = Gee
# x = y;;
Error: This expression has type t/1585 but an expression was expected of type
         t/1581

Le même phénomène de masquage est possible sur les noms des champs des types enregistrements. Cependant, depuis la version 4.01.0 d'OCaml, les informations de typage sont utilisées pour lever les possibles ambiguïtés. Ainsi, dans l'exemple ci-dessous, lors de la définition de y, le type de x est déjà connu comme étant rec1, ce qui permet au système de type de comprendre champ = 3 comme le champ champ du type rec1 et non du type rec2:

# type rec1 = { champ : int; champ2: int };;
type rec1 = { champ : int; champ2 : int; }
# let x = { champ = 0 ; champ2 = 1;};;
val x : rec1 = {champ = 0; champ2 = 1}
# type rec2 = { champ : int ; champ3 : int};;
type rec2 = { champ : int; champ3 : int; }
# let y = { x with champ = 3 };;
val y : rec1 = {champ = 3; champ2 = 1}

De même sur les noms des constructeurs de types sommes dans l'exemple ci-dessous. Le type de x étant t, le constructeur Foo dans le filtre est compris comme le constructeur Foo du type t et non de t2. Le compilateur indique donc que le cas où la valeur est construite avec Bar n'est pas traité.

# type t = Foo | Bar;;
type t = Foo | Bar
# let x = Foo;;
val x : t = Foo
# type t2 = Foo;;
type t2 = Foo
# match x with
| Foo -> 0;;
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Bar
- : int = 0

Même avec ce système de désambiguation, il est souvent utile de choisir des noms "à préfixe" pour les champs et les constructeurs, par exemple:

# type user = { user_name : string; user_login: string};;
type user = { user_name : string; user_login : string; }
# type host = { host_name : string; host_ipv4: int * int * int * int};;
type host = { host_name : string; host_ipv4 : int * int * int * int; }

Même si cela est plus verbeux, cela facilite la lecture et la maintenance des programmes.

2.8. Types fonctionnels

Les types fonctionnels sont les types représentant des fonctions, comme nous en avons déjà vu précédemment. Il est possible de créer ses propres types fonctionnels ou encore d'utiliser des types fonctionnels pour les champs d'enregistrements ou les paramètres de constructeurs.

Ainsi, on peut définir le type d'un afficheur de messages:

# type printer = string -> unit;;
type printer = string -> unit

Tout comme il est possible d'avoir des champs fonctionnels dans un type enregistrement:

# type output_context = {
  output_error : string -> unit ;
  output_message : string -> unit ;
};;
type output_context = {
  output_error : string -> unit;
  output_message : string -> unit;
}

ou bien, en utilisant notre type printer:

# type output_context = {
  output_error : printer ;
  output_message : printer ;
};;
type output_context = { output_error : printer; output_message : printer; }

On peut également avoir des paramètres fonctionnels pour des constructeurs:

# type action =
  Init of (unit -> output_context)
| Compute of (unit -> unit)
| Terminate of (unit -> unit);;
type action =
    Init of (unit -> output_context)
  | Compute of (unit -> unit)
  | Terminate of (unit -> unit)

Ces valeurs fonctionnelles peuvent être nommées dans des motifs de filtrage pour être appliquées:

# let action = Compute (fun () -> print_endline "coucou");;
val action : action = Compute <fun>
# match action with
  Compute f -> f () (* application de la fonction f à () *)
| Init f -> ignore(f())
| Terminate f -> f();;
coucou
- : unit = ()
2.9. Exercice
Exercice 6: Expressions génériques

On souhaite rendre les expressions de l' Exercice 5 génériques. Pour cela, ajouter un paramètre de type au type expr pour ne plus limiter les valeurs des expressions à des entiers.

Ensuite, on veut pouvoir paramétrer la fonction eval pour spécifier le traitement à effectuer pour chaque opérateur de notre type expression. Définir un type enregistrement operators permettant de donner la fonction associée à chaque opérateur d'expression. Ce type est paramétré par le type des valeurs calculées.

Enfin, définir une nouvelle fonction eval prenant en paramètre supplémentaire les fonctions à utiliser pour effectuer les calculs lors de l'évaluation (une valeur de type operators).

Définir une valeur du type operators et s'en servir pour évaluer une expression contenant des flottants.

3. Typage, domaine de définition et exceptions

Le type inféré d'une fonction correspond à un sur-ensemble de son domaine de définition. Ce n'est pas parce qu'une fonction prend un paramètre de type int qu'elle saura calculer une valeur pour tous les entiers passés en argument. On traite en général ce problème en utilisant le mécanisme d'exceptions d'OCaml. Le déclenchement d'une exception provoque une rupture du calcul qui peut être interceptée et traitée par le programme. Pour cela l'exécution du programme doit avoir posé un récupérateur d'exception avant le calcul de l'expression qui provoque le déclenchement de cette exception.

3.1. Fonctions partielles et exceptions

Le domaine de définition d'une fonction correspond à l'ensemble des valeurs sur lesquelles la fonction effectue son calcul.

Que faire quand est passée à une fonction une valeur qu'elle ne sait pas traiter ? Retourner une valeur arbitraire n'est pas la bonne solution. Les exceptions sont faites pour gérer ces situations. Par exemple, la fonction List.hd récupérant le premier élément d'une liste lèvera une exception Failure "hd" si une liste vide lui est passée.

Une fonction peut être partielle parce qu'elle ne traite pas toutes les formes possibles d'un paramètre:

# type dummy = One | Two | Three;;
type dummy = One | Two | Three
# let succ = function
  One -> Two
| Two -> Three
;;
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Three
val succ : dummy -> dummy = <fun>

Le compilateur signale que la fonction est partielle, en indiquant que la structure de filtrage ne traite pas le cas Three. En effet, l'application de cette fonction à la valeur Three déclenchera une exception prédéfinie pour ce genre de cas:

# succ Three;;
Exception: Match_failure ("", 1, 11).

Ce genre d'exception n'est pas très facile à traiter car il est utilisé pour n'importe quel pattern-matching non exhaustif. On préférera donc définir et utiliser ses propres exceptions afin d'être en mesure de traiter efficacement et précisément chaque erreur.

Les exceptions prédéfinies et utilisées par les modules de la bibliothèque standard d'OCaml sont indiquées ici.

3.2. Définition d'une exception

Une nouvelle exception est définie avec la syntaxe

exception Identifiant

L'identifiant doit commencer par une majuscule, comme pour les constructeurs de type somme. On peut également définir une exception portant une valeur d'un type indiqué à la définition:

exception Identifiant of type

ce qui permet de passer de l'information sur les causes, l'endroit et les conditions menant à ce comportement exceptionnel.

# exception Mon_erreur of string;;
exception Mon_erreur of string

Les exceptions peuvent être vues comme des valeurs d'un type somme exn qui serait enrichi à chaque création d'exception:

# Mon_erreur "message";;
- : exn = Mon_erreur "message"

Remarque: le type d'une exception ne peut être polymorphe.

3.3. Déclenchement d'une exception

Une exception est déclenchée (ou levée) grâce à la fonction raise prédéfinie:

# raise (Mon_erreur "Ceci n'est pas un message d'erreur");;
Exception: Mon_erreur "Ceci n'est pas un message d'erreur".

Nous pouvons redéfinir notre fonction succ pour lever une exception appropriée:

# let succ = function
  One -> Two
| Two -> Three
| Three -> raise (Mon_erreur "Je ne sais pas compter plus loin")
;;
val succ : dummy -> dummy = <fun>

La levée d'une exception interrompt l'évaluation normale de l'expression qui la contient. Cela peut avoir de l'importance lorsque l'ordre d'évaluation n'est pas spécifié, comme dans l'exemple suivant:

# let f x =
  (* l'affichage, trait impératif par excellence,
     n'est là que pour montrer l'ordre d'exécution *)
  print_endline (Printf.sprintf "Appel de f avec x = %d" x);
  if x < 0 then
    raise (Mon_erreur "c'est negatif!")
  else
    x + 1;;
val f : int -> int = <fun>
# (f (-1)) + (f 1);;
Appel de f avec x = 1
Appel de f avec x = -1
Exception: Mon_erreur "c'est negatif!".

On constate ici que l'ordre d'évaluation des arguments passés à une fonction (ici l'opérateur infixe (+)) est de droite à gauche. Cela signifie que nous avons tout de même effectué une partie du calcul avant de lever l'exception. De telles situations peuvent rendre plus difficile la correction d'un programme. On s'appliquera parfois, pour se prémunir contre de telles situations, à forcer l'ordre d'évaluation des paramètres avant de les passer à la fonction:

# let p1 = f (-1) in
let p2 = f 1 in
p1 + p2;;
Appel de f avec x = -1
Exception: Mon_erreur "c'est negatif!".

On se trouve ici au bord de la programmation impérative.

3.4. Récupération d'une exception

La construction suivante permet de récupérer (on dit aussi "attraper") une exception levée dans l'expression:

try expression
with
  motif_1 -> expression_1
| ...
| motif_n -> expression_n

Dans la partie with, on donne des motifs de filtrage d'exception, qui fonctionnent de la même façon que les motifs de filtrage de valeurs. Concrètement, on pourra écrire comme suite de notre exemple:

# try ignore(succ Three)
  with
    Mon_erreur s -> print_endline ("Erreur: "^s)
  | Failure s ->  print_endline ("Failure: "^s);;
Erreur: Je ne sais pas compter plus loin
- : unit = ()

Contrairement au filtrage sur des valeurs, le compilateur ne peut ici indiquer si les motifs du bloc with sont exhaustifs. Cela nécessiterait de connaître toutes les exceptions potentiellement levées à chaque point du code, ce qui demanderait une analyse de flots de données, notamment à cause des possibilités de passage de fonction en paramètre. En effet, une telle fonction pourrait lever une exception, mais, dans bien des situations, le paramètre effectif ne sera connu qu'à l'exécution.

Par ailleurs, on ne souhaite pas forcément rattraper toutes les exceptions possibles à chaque point d'un programme, mais plutôt rattraper seulement certaines, que l'on peut traiter, en laissant volontairement remonter celles correspondant à des cas plus inattendus dans lesquels on ne peut rien faire d'autre qu'interrompre le traitement en cours.

Il est possible de rattraper toutes les exceptions avec le motif universel '_', ou bien en liant l'exception rattrapée à un identifiant, comme ci-dessous:

# try List.hd []
with
  e ->
    (* traitement effectué pour n'importe quelle exception *)
    print_endline "An exception was caught!";
    let msg =
      match e with
        Failure s | Sys_error s -> s
      | _ -> Printexc.to_string e
    in
    print_endline ("Some info about the exception: "^msg);
    (* relançons l'exception *)
    raise e;;
An exception was caught!
Some info about the exception: hd
Exception: Failure "hd".
OCaml ≥ 4.02.0

La construction match ... with permet également de rattraper des exceptions en utilisant le mot-clé exception dans les motifs. Si une exception est levée lors de l'évaluation de l'expression entre le match et le with, alors elle pourra être rattrapée par un motif d'exception. L'expression associée à un tel motif doit bien sûr être du même type que les autres branches pour que l'expression match ... with soit correctement typée. Voyons un exemple:

# match List.assoc "z" [ "x", 1 ; "y", 2 ] with
| exception Failure msg ->
    assert false (* cette exception n'est pas censée être levée par List.assoc *)
| exception Not_found ->
    None (* aucune valeur n'est associée à "z" *)
| n -> Some n;;
- : int option = None

On peut ajouter plusieurs motifs pour rattraper des exceptions, et on peut les mettre à n'importe quelle position dans la liste des motifs. Si une exception est levée, alors le premier motif exception dans la liste et qui correspond à l'exception levée attrape l'exception et l'expression associée est évaluée. Si aucun motif exception n'attrape l'exception, alors cette dernière est propagée dans l'expression englobante.

Avertissement 8: Branches normales et branches exception

On ne peut pas "mettre en commun" une expression sous un motif exception et un autre motif, que cela soit un autre motif exception ou un motif filtrant la valeur retournée par l'expression entre le match et le with:

# match String.sub "hello" 0 12 with
  | exception Invalid_argument str
  | exception Failure str -> str
  | str -> str;;
Error: Exception patterns must be at the top level of a match case.
# match String.sub "hello" 0 12 with
  | exception Invalid_argument str
  | str -> str;;
Error: Exception patterns must be at the top level of a match case.
# match String.sub "hello" 0 12 with
  | exception Invalid_argument str -> str
  | exception Failure str -> str
  | str -> str;;
- : string = "String.sub / Bytes.sub"
OCaml ≥ 4.02.0
3.5. Exercice
Exercice 7: try_finalize

Ecrire une fonction try_finalize spécifiée de la façon suivante: try_finalize f x g y applique la fonction f à la valeur x.

  • si une exception est levée, alors on évalue g y et on relève ensuite l'exception,
  • si aucune exception n'est levée, on évalue aussi g y et on retourne la valeur retournée par f x.
  • si une exception est levée par g y, cette exception est levée par la fonction try_finalize.

Nous pouvons tester notre fonction de la façon suivante:

# try_finalize (fun x -> x * 2) 21 print_endline "application de g a y";;
application de g a y
- : int = 42
# try_finalize (fun x -> 1 / x) 0 print_endline "application de g a y";;
application de g a y
Exception: Division_by_zero.
4. Récursivité terminale

La programmation fonctionnelle conduit souvent à écrire des fonctions récursives. Il existe deux types de récursivités: terminale et non-terminale. Illustrons cette différence sur un exemple, la fonction de map sur les listes.

Voici une première version, récursive non-terminale:

# let rec map_nt f = function
  [] -> []
| h::q -> (f h) :: (map_nt f q);;
val map_nt : ('a -> 'b) -> 'a list -> 'b list = <fun>
# map_nt ((+) 1) [ 1 ; 2 ; 3 ; 4 ];;
- : int list = [2; 3; 4; 5]

La fonction map_nt effectue bien le calcul demandé, mais présente un risque de débordement de pile dans le cas de grandes listes:

# let big_list =
  let rec build n acc =
    if n < 1_000_000 then build (n+1) (n::acc) else acc
  in
  build 0 [];;
val big_list : int list =
  [999999; 999998; 999997; 999996; 999995; 999994; 999993; 999992; 999991;
   999990; 999989; 999988; 999987; 999986; 999985; 999984; 999983; 999982;
   999981; ...]
# try map_nt ((+) 1) big_list
with Stack_overflow -> failwith "La pile d'appel est pleine!";;
Exception: Failure "La pile d'appel est pleine!".

Que se passe-t-il ? Notre fonction map_nt fonctionne par cas sur la structure de la liste en paramètre:

  • soit la liste est vide, la fonction retourne donc la liste vide,
  • soit la liste n'est pas vide, dans ce cas la fonction crée une nouvelle liste composée de l'application de f à la tête de la liste, et de l'application récursive de map_nt à la queue de la liste. Cette opération de création de la nouvelle liste nécessite le calcul de la nouvelle tête de liste et de la nouvelle queue de liste. Ensuite seulement la nouvelle liste est créée et retournée. De ce fait, les appels récursifs s'empilent jusqu'au débordement de la pile d'appel. Cette fonction est dire récursive non-terminale car il reste du calcul à effectuer avec la valeur retournée par l'appel récursif.

Voyons maintenant une autre définition, cette fois récursive terminale:

# let map f l =
  let rec iter acc = function
    [] -> List.rev acc
  | h::q -> iter ((f h) :: acc) q
  in
  iter [] l;;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>
# map string_of_int big_list;;
- : string list =
["999999"; "999998"; "999997"; "999996"; "999995"; "999994"; "999993";
 "999992"; "999991"; "999990"; "999989"; "999988"; "999987"; "999986";
 "999985"; "999984"; "999983"; "999982"; "999981"; ...]

Notre fonction map n'est plus récursive mais se contente de définir et d'appeler une autre fonction iter qui, elle, est récursive terminale. Cette fonction iter prend en paramètre un accumulateur, ce qui permet, lors de l'appel récursif, d'avoir déjà effectué la création de la nouvelle liste composée de la nouvelle tête (f h) et du reste de la nouvelle liste déjà calculé (acc).

Cette façon de procéder donne une liste en ordre inverse, d'où l'appel à List.rev pour retourner l'accumulateur (la nouvelle liste) lorsqu'on tombe sur le cas de la liste vide (fin de la liste à traiter).

La fonction iter est récursive terminale car l'appel récursif à elle-même est bien le dernier calcul effectué dans le cas où la liste n'est pas vide.

Cependant, c'est l'appel récursif et non la fonction qui est ou non terminal. Dans l'exemple suivant:

# let rec f x =
  if x < 1 then f (x + 1) else 1 + f (x - 1);;
val f : int -> int = <fun>

la fonction f est récursive et s'appelle à deux endroits. Le premier appel récursif (f (x + 1)) est bien terminal. Par contre, le second (f (x - 1)) ne l'est pas, car la valeur de retour de cet appel sera additionnée à 1. On ne peut donc pas parler de fonction récursive terminale mais d'un appel terminal et d'un appel non terminal.

Les appels récursifs terminaux sont compilés de façon efficace (avec des sauts plutôt qu'en utilisant la pile) par le compilateur: au lieu de faire augmenter la taille de la pile, l'appel récursif est placé au même endroit que l'appel original, ce qui donne un gain de temps pour retourner la valeur finale (pas besoin de dépiler des milliers d'appels récursifs) et un gain de place (la pile n'augmente pas de taille). Nous avons donc pu appliquer notre fonction sur big_list.

Avertissement 9: Exceptions et récursivité terminale

L'utilisation de constructions try ... with pour la gestion des exceptions peut faire d'une fonction récursive terminale une fonction récursive non-terminale. Supposons que nous voulions modifier notre fonction map pour, en cas d'exception Failure lors de l'application de f à un élement de la liste, conserver la valeur initiale de l'élément. Nous pouvons tenter la définition suivante:

# let safe_map f l =
  let rec iter acc = function
    [] -> List.rev acc
  | h::q ->
    try iter ((f h) :: acc) q
    with Failure _ -> iter (h :: acc) q
  in
  iter [] l
;;
val safe_map : ('a -> 'a) -> 'a list -> 'a list = <fun>
# safe_map ((+) 1) big_list;;
Stack overflow during evaluation (looping recursion?).

La présence du bloc try ... with en vue de rattraper l'exception Failure ne permet plus au compilateur d'optimiser les appels récursifs sur la pile. En effet, l'appel récursif n'est plus forcément le dernier calcul effectué, car s'il lève une exception, il faudra la filtrer dans ce contexte et non dans celui de l'appel récursif. On écrira donc plutôt:

# let safe_map f l =
  let rec iter acc = function
    [] -> List.rev acc
  | h::q ->
    let v = try f h with Failure _ -> h in
    iter (v :: acc) q
  in
  iter [] l
;;
val safe_map : ('a -> 'a) -> 'a list -> 'a list = <fun>
# safe_map ((+) 1) big_list;;
- : int list =
[1000000; 999999; 999998; 999997; 999996; 999995; 999994; 999993; 999992;
 999991; 999990; 999989; 999988; 999987; 999986; 999985; 999984; 999983;
 999982; ...]

Dans ce cas, l'appel récursif redevient le dernier calcul, le rattrapage d'exception étant limité au calcul de f h.

Un appel peut être terminal même s'il ne s'agit pas d'un appel récursif. Le compilateur pourra faire des optimisations dans ce cas aussi.

L'option -annot des compilateurs OCaml génère, à la compilation d'un fichier d'implémentation foo.ml, un fichier foo.annot contenant diverses informations, notamment les types inférés pour chaque expression et, depuis la version 3.11.0, une indication de terminalité pour chaque appel de fonction: tail indiquera que l'appel est terminal, tandis que stack indiquera que l'appel se fera sur la pile.


1 La fonction assert prend en paramètre une expression de type bool et lève une exception Assertion_failed si l'expression est évaluée à false.