Objective Caml/Structures

Dans presque tous les langages de programmation, l'une des phases les plus importantes lors de la conception d'un programme est de décider comment représenter les données du programme, qu'il s'agisse de ressources internes, telles que des valeurs numériques ou des fonctions ou des ressources extérieures au programme, telles que des imprimantes ou des fichiers. Dans tous les cas, le choix de bonnes représentations de données -- ou structures de données -- sera nécessaire pour écrire des programmes rapides, concis, corrects et dont le code source ressemblera aux spécifications.

Ainsi, considérons le cas des nombres complexes. Manipuler numériquement les nombres complexes nécessite de retenir la valeur de ces nombres, soit la partie réelle et la partie imaginaire, soit l'argument et le module, soit les deux à la fois. Dans un monde idéal, il n'y aurait aucune différence entre ces trois représentations. En pratique, sur un ordinateur, cependant, passer de la représentation polaire (argument et module) à la représentation cartésienne (partie réelle et partie imaginaire) ou réciproquement implique des calculs trigonométriques relativement lents et des erreurs d'arrondis. Une représentation mixte dans laquelle les coordonnées polaires et cartésiennes sont connues à tout instant, à son tour, gaspillerait beaucoup de temps et de précision à synchroniser systématiquement ces informations. Il convient donc de choisir une structure de données adaptée au problème et qui minimisera ces impondérables. Une autre contrainte importante sera d'adopter une représentation qui évitera le plus possibles d'erreurs de programmation, d'une part en évitant de confondre accidentellement les deux notations, d'autre part pour éviter de créer des valeurs sans aucun sens, telles que celles qu'on obtiendrait avec un argument strictement négatif.

Dans le cadre de logiciels non mathématiques, citons de même la représentation des fichiers. Dans certains langages ou certaines bibliothèques, dès qu'il s'agira de manipuler un fichier, par exemple pour consulter son contenu ou pour le modifier, il sera nécessaire de préciser le nom du fichier. Dans d'autres langages, toutes les opérations sur un fichier doivent être précédées d'une ouverture, qui associe au fichier un numéro unique et c'est ce numéro qui est manipulé par chacune des actions ultérieures de consultation ou de modification. Enfin, une troisième possibilité fait aussi appel à une phase d'ouverture et associe au fichier directement l'ensemble des actions qui pourront être entreprises sur ce fichier, sans passer par un entier ou une autre valeur concrète. De ces trois techniques, quelle est la meilleure ? La première est certainement la plus simple à comprendre mais c'est aussi la plus lente (à chaque opération, il est nécessaire de retrouver sur le disque ou en mémoire le fichier correspondant au nom qui vient d'être donné) et elle est aussi fort fragile, puisqu'aucun garde-fou ne permet de faire la différence entre un nom de fichier prévu pour être consulté, un nom de fichier prévu pour être modifié ou encore un nom qui n'a rien à voir avec un fichier. La deuxième technique est plus rapide et surtout plus simple à ajouter à un langage qui ne disposerait pas encore d'une bibliothèque de gestion de fichiers mais aussi plus complexe à manipuler (puisqu'il faut garder trace du numéro associé au fichier qui nous intéresse) et tout aussi fragile, puisqu'aucun garde-fou ne permet d'éviter de confondre le numéro d'un fichier ou le résultat d'une opération arithmétique. La troisième méthode est celle qui sera favorisée en OCaml. Si elle est plus complexe à ajouter à un langage (quelques langages ne seraient d'ailleurs pas assez puissant pour permettre cette méthode) et si elle est tout aussi abstraite que la méthode précédente, il s'agit de la plus robuste des trois, puisqu'il est impossible d'essayer de modifier un fichier qui a été ouvert pour être uniquement consulté et puisqu'il est impossible de confondre la représentation du fichier (ici, les opérations de manipulation) avec la représentation de quelque chose qui n'aurait rien à voir avec un fichier. Enfin, en théorie, cette dernière technique pourrait être la plus rapide, car cette robustesse permet d'éviter un certain nombre de tests qui sont fondamentaux dans des approches plus fragiles pour éviter les désastres.

En OCaml, une structure de données est composée d'un ou plusieurs types et les valeurs nécessaires pour manipuler les valeurs portant ces types. Ainsi, la structure des données des entiers peut être définie par le type int, les constantes 0, 1... et les quelques opérations de base. Au cours de ce chapitre, nous allons étudier les différentes techniques pour définir de nouvelles structures de données. À partir du chapitre suivant, nous commencerons à employer les structures de données déjà disponibles sous OCaml Batteries Included.

Objectifs du chapitre

Ce chapitre vous enseignera

• le rôle des types
• les types et structures de données les plus utilisées en OCaml
• comment définir de nouveaux types et de nouvelles structures de données.

Types de base

Jusqu'à présent, nous nous sommes intéressés essentiellement aux valeurs. Comme nous l'avons vu, en OCaml et comme dans la majorité des langages de programmation fortement typés, chaque valeur est associée à un type de donnée (ou juste "type").

Mathématiquement, les types peuvent être considérés comme une approximation de la notion d'ensembles. Ainsi, à partir de quelques ensembles simples et supposés connus, de nouveaux ensembles peuvent être construits par produit cartésien, par somme (union étiquetée), par génération de monoïdes libres, de fonctions, de quantificateurs existentiels ou universels, etc. Informatiquement, les types peuvent être considérés comme la définition de comment une information doit être représentée en mémoire. À partir de quelques types primitifs dont la spécification est supposée connue par OCaml, de nouvelles représentations peuvent être construites sous la forme de tuples de types, de types variants, de listes, de fonctions, de types paramétrés, etc.

Dans la quasi-totalité des langages de programmation, l'utilisation des types est contrainte par un système de types, dont le rôle est de garantir que les valeurs des différents types sont combinées correctement : un booléen ne peut pas être utilisé comme une fonction, une fonction n'est pas un texte, la fonction int_of_float s'applique à un nombre de type float et produit un nombre de type int... En OCaml, comme c'est presque systématiquement le cas en Java ou en C#, avant d'exécuter un programme, une phase d'analyse de types vérifie que l'utilisation des valeurs dans un programme est cohérente avec le système de types. Ce processus est dit statique car il a lieu avant l'exécution du programme, durant la compilation. D'autres langages fortement typés, comme Python, vérifient ces contraintes dynamiquement, c'est-à-dire durant l'exécution du programme. La vérification dynamique est plus souple mais plus lente et moins rigoureuse : là où l'analyse statique rejette un certain nombre de programmes corrects parce qu'ils risquent de produire des résultats incohérents -- c'est-à-dire parce que leur résultat ne peut être expliquée en termes d'ensembles -- l'analyse dynamique ne rejette a priori aucun programme, au risque de laisser passer quantité d'erreurs. Enfin, d'autres langages, comme C ou dans une moindre mesure C++, sont statiquement mais faiblement typés : des vérifications ont bien lieu durant la phase de compilation mais ces vérifications n'offrent aucune garantie sur la cohérence des ensembles.

Les types de donnés les plus simples offerts par OCaml sont :

• les entiers, int, approximation des entiers relatifs -- les éléments de int sont notés 1, 2, 3...
• les nombres flottants, float, approximation des réels -- les éléments de float sont notés 0.0, 0.1, -0.1, ...
• les booléens, bool, approximation de l'algèbre minimale de Boole -- les éléments de bool sont notés true et false
• les caractères, char, définis par le standard iso-8859-1 (alphabets européens) -- les éléments de char sont notés 'a', 'b' ...
• les chaînes de caractères, string, approximation de l'ensemble des suites finies de caractères européens -- les éléments de string sont notés "abc", "", "du texte"...
• les ficelles de caractères, Rope.t, approximation de l'ensemble des suites finies de caractères internationaux -- les éléments de Rope.t sont notés r"abc", r"", r"du texte"...
• l'unité, unit, ensemble à un seul élément qui sert généralement d'approximation à l'ensemble vide -- pour des raisons de cohérence de notations, on considère que cet ensemble contient exactement une valeur, notée ().

Voyons tout de suite comment construire et manipuler des types plus évolués.

Contraintes de types

Dans la suite de ce chapitre, nous serons quelquefois amenés à forcer OCaml à donner un type précis à une valeur, soit parce que c'est la seule manière de rendre un exemple convaincant, soit pour trouver la source d'un problème. Pour ce faire, OCaml permet de spécifier manuellement des contraintes de types.

Ainsi, les trois extraits suivants définissent chacun la fonction id_int, identique à la fonction id mais applicable uniquement à des entiers :

# let ( id_int : int -> int ) x = x ;;
val id_int : int -> int = <fun>

# let id_int ( x : int ) : int = x ;;
val id_int : int -> int = <fun>

# let id_int ( x : int ) = x ;;
val id_int : int -> int = <fun>

# let id_int = fun ( x : int ) -> x ;;
val id_int : int -> int = <fun>

De nouveau, les résultats de ces définitions sont rigoureusement équivalents. La première syntaxe insiste sur le fait que id_int est une fonction de type int -> int. La deuxième souligne sur le fait que x est lié à un entier (c'est le rôle de ( x : int )) et que le résultat de id_int est encore un entier (c'est le rôle de : int). La troisième souligne de même le fait que x est lié à un entier et laisse OCaml déterminer que le résultat de la fonction id_int est donc lui-même un entier. La quatrième est une variante sur la troisième.

Cette syntaxe est générale : dès qu'un nom (ici aussi bien id_int que x) est lié à une valeur, que ce soit à l'aide de let, let...in, de fun ou du filtrage par motifs (que nous rencontrerons dans ce chapitre), il est possible de forcer le type associé à ce nom, en ajoutant une annotation ( le_nom : le_type ). Comme d'habitude dans OCaml, les parenthèses ne sont pas systématiquement nécessaires.

Bien entendu, en introduisant des annotations de types, nous pouvons ajouter des erreurs de types dans une fonction qui, autrement, compilerait. Ainsi, si l'on demande à notre fonction de prendre un argument qui doit être simultanément flottant et entier, OCaml se plaindra d'une contradiction :

# let ( id_wrong : float -> float ) ( x : int ) = x ;;
                                      ^
This pattern matches values of type int
but is here used to match values of type float

Notez que le message d'erreur n'est pas exactement celui auquel OCaml nous a habitué en cas d'erreur de types. C'est que, ici, nous ne somme pas en train d'utiliser x mais de lier x. Du point de vue d'OCaml, il s'agit d'un motif ("pattern") et non pas d'une expression. À l'inverse, si l'erreur avait eu lieu dans le corps de la fonction, nous aurions retrouvé un message familier :

# let ( id_wrong_2 : int -> float ) ( x : int ) = x ;;
                                                  ^
This expression has type int but is here used with type float

Tout au long de ce chapitre, nous emploierons fréquemment les contraintes de types pour mettre en évidence des comportements du système de types d'OCaml. Au cours du développement de fonctions complexes, il arrive aussi régulièrement au programmeur d'insérer des contraintes de types le temps de comprendre pourquoi OCaml donne à une expression un type qui ne correspond pas à ce que le développeur avait prévu. Enfin, dans certains cas, heureusement rares, des annotations de types sont nécessaires pour demander à OCaml de prendre en compte le sous-typage. Nous y reviendrons en temps et en heure.

Liaison de types

De la même manière que nous avons utilisé let pour nommer globalement une valeur, nous pouvons employer type pour nommer globalement un type. Ainsi,

# type fonction_des_entiers_vers_les_entiers = int -> int ;;
type fonction_des_entiers_vers_les_entiers = int -> int

lie le nom de type fonction_des_entiers_vers_les_entiers à l'expression de type int -> int. Pour toute la suite du programme, nous pourrons employer fonction_des_entiers_vers_les_entiers comme synonyme exact de int -> int.

# let ( f : fonction_des_entiers_vers_les_entiers ) x = x ;;
val f : fonction_des_entiers_vers_les_entiers = <fun>

# f 5 ;;
- : int = 5

Avec quelques détours, nous pouvons vérifier que OCaml ne fait aucune distinction entre fonction_des_entiers_vers_les_entiers et int > int :

# let ( g : int -> int ) x = x ;;
val g : int -> int = <fun>

# let (teste_egalite_des_types : 'a -> 'a -> unit) x y = () ;;
val teste_egalite_des_types : 'a -> 'a -> unit = <fun>

# teste_egalite_des_types f g ;;
- : unit = ()

Dans ce qui précède, teste_egalite_des_types est une fonction dont les deux arguments doivent être de même type. Comme cette fonction accepte comme arguments f et g, nous pouvons en déduire que ces deux valeurs sont de même type int > int.

Note Un type n'est pas une valeur. Il n'est donc pas possible d'écrire des fonctions qui prennent en argument un type ou produisent comme résultat un type. Si vous avez réellement besoin de ce genre de fonctionnalités, vous aurez besoin d'employer des foncteurs, une notion plus puissante que les fonctions mais aussi quelque peu plus difficile à utiliser, et que nous aborderons dans un chapitre ultérieur.

Sommes/Variants

Les sommes comme énumérations

Les types sommes ou types variants d'OCaml représentent une approximation de l'union mathématique ou, plus précisément, de l'union disjointe. Sous leur forme la plus simple, les types sommes peuvent être utilisés de la même manière que les énumérations de C ou de Pascal. Ainsi, on écrira :

# type couleur_de_carte = 
   | Trefle
   | Pique
   | Coeur
   | Carreau ;;
type couleur_de_carte = Trefle | Pique | Coeur | Carreau

Cette définition déclare quatre constructeurs, Trefle, Pique, Coeur et Carreau, qui à eux quatre constituent l'ensemble des éléments de type couleur_de_carte:

# Trefle ;;
- : couleur_de_carte = Trefle

# Trefle = Pique  ;;
- : bool = false

# let ( x : couleur_de_carte ) = true ;;
                                 ^^^^
This expression has type bool but is here used with type couleur_de_carte

Pour manipuler une valeur de type couleur_de_carte, nous pourrons la comparer à l'aide d'une chaîne de if...then...else ou, de manière plus générale, employer le filtrage par motifs. Ce dernier permet de définir une fonction ou une expression dont le résultat sera déterminé par la structure d'une valeur.

Ainsi, pour calculer le nom d'une couleur, on écrira au choix :

# let string_of_couleur_de_carte c = 
    if c = Trefle       then "trefle"
    else if c = Pique   then "pique"
    else if c = Coeur   then "coeur"
    else                     "carreau" ;;
val string_of_couleur_de_carte : couleur_de_carte -> string = <fun>

# let string_of_couleur_de_carte c = match c with
    | Trefle -> "trefle"
    | Pique  -> "pique"
    | Coeur  -> "coeur"
    | Carreau-> "carreau" ;;
val string_of_couleur_de_carte : couleur_de_carte -> string = <fun>

# let string_of_couleur_de_carte = function
    | Trefle -> "trefle"
    | Pique  -> "pique"
    | Coeur  -> "coeur"
    | Carreau-> "carreau" ;;
val string_of_couleur_de_carte : couleur_de_carte -> string = <fun>

La première version de la fonction string_of_couleur_de_carte emploie le mécanisme de contrôle if...then...else que nous avons déjà vu et ne devrait surprendre personne. La deuxième version met l'accent sur un contrôle de flux, de la même manière que le switch de C ou Java, et s'énonce "la valeur de string_of_couleur_de_carte c dépend de la structure de c: si c est le constructeur Trefle, cette valeur est "trefle", si c est le constructeur Pique, cette valeur est "pique", si c est le constructeur Coeur, cette valeur est "coeur", si c est le constructeur Carreau, cette valeur est "carreau"." La troisième syntaxe, plus mathématique, est une définition de fonction par cas, qui pourrait s'énoncer "string_of_couleur est la fonction qui à Trefle associe "trefle", à Pique associe "pique", à Coeur associe "coeur" et à Carreau associe "carreau"."

Les trois versions de cette fonction produiront exactement les mêmes résultats. La deuxième et la troisième sont strictement équivalentes et seront probablement plus rapides que la premières. De plus, le mécanisme de filtrage par motifs employé dans ces deux dernières variantes est plus lisible, plus sûr et, comme nous le verrons bientôt, bien plus puissant qu'une simple chaîne de if...then...else.

Pourquoi plus sûr ? Parce que, comme nous pouvons le constater, OCaml est capable de vérifier que nous n'avons oublié aucun cas :

# val string_of_couleur_de_carte_oubli = function
                                         ^^^^^^^^
    | Trefle -> "trefle"
    ^^^^^^^^^^^^^^^^^^^^
    | Pique  -> "pique"
    ^^^^^^^^^^^^^^^^^^^^
    | Coeur  -> "coeur" ;;
    ^^^^^^^^^^^^^^^^^^^^^
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Carreau
val string_of_couleur_de_carte_oubli : couleur_de_carte -> string = <fun>

OCaml nous répond ici que nous avons oublié dans notre filtrage par motifs (en anglais, "pattern-matching"), de gérer une valeur telle que Carreau. Ceci est considéré comme un avertissement ("warning") et non pas une erreur, car nous pourrions l'avoir fait exprès en sachant pertinemment que la fonction ne sera jamais appliquée à une couleur_de_carte Carreau. (La lettre "P" désigne le nom de l'avertissement, de manière à pouvoir activer ou désactiver les avertissements lors de la compilation.)

Après une telle définition, nous pouvons manipuler string_of_couleur_de_carte_oubli, à nos risques et périls :

# string_of_couleur_de_carte_oubli Trefle ;;
- : string = "trefle"

# string_of_couleur_de_carte_oubli Carreau ;; 
Exception: Match_failure ("", 30, -72).

Appliquer string_of_couleur_de_carte_oubli au constructeur Trefle a produit le résultat escompté alors que l'appliquer à Carreau a provoqué une erreur Match_failure (erreur au cours du filtrage). Cette erreur est peu lisible lorsque nous utilisons OCaml en mode ligne de commande mais pourra s'avérer bien plus utile pour déboguer du code lorsque nous manipulerons OCaml en tant que langage compilé.

Note L'exception Match_failure est le plus proche équivalent OCaml au NullPointerException de Java. On la rencontre bien moins souvent car le compilateur OCaml vous avertira toujours lorsque vous définissez une fonction qui peut déclencher cette exception.

Du point de vue d'OCaml, les nombres 1, 2, 3 ... sont eux aussi autant de constructeurs du type int, qui aurait pu être défini sous la forme

# type int = 0 | 1 | 2 | (* .... *) | -1 | -2 | (* ... *) ;;

Une conséquence de cette conception des nombres est que nous pouvons procéder à des filtrages par motifs sur les entiers :

# let string_of_nombre_francais = function
   | 1 -> "Un"
   | 2 -> "Deux"
   | 3 -> "Trois"
   | 4 -> "Quatre"
   | 5 -> "Cinq"
   | 6 -> "Six"
   | 7 -> "Sept"
   | 8 -> "Huit"
   | 9 -> "Neuf"
   | 0 -> "Zero" 
   | n -> string_of_int n ;;
val string_of_nombre_francais : int -> string = <fun>

Les dix premiers cas sont comparables à ce que nous avons déjà rencontré. Le dernier est plus surprenant, car il introduit une variable n, qui est liée à la valeur que nous sommes en train de filtrer. En d'autres termes, cette fonction peut s'énoncer "la fonction qui à 1 associe "Un", à 2 associe "Deux"..., à 0 associe "Zero" et à toute autre valeur n associe le résultat de string_of_int n." Cette dernière fonction convertit un nombre entier en une représentation sous la forme d'une chaîne de caractères.

Note Tout comme une succession de "if...then...else", le filtrage par motifs essaye tous les cas dans l'ordre dans lequel ils sont écrits. En d'autres termes, le motif n, qui peut accepter n'importe quelle valeur, n'est essayé que si aucun des motifs 1, 2, ..., 9, 0, n'accepte l'argument de la fonction.

Ainsi, on aura

# string_of_nombre_francais 5 ;;
- : string = "Cinq"

# string_of_nombre_francais 11 ;;
- : string = "11"

De la même manière que les entiers sont des constructeurs prédéfinis, les booléens sont les éléments d'un type bool qui aurait pu être défini sous la forme

# type bool = false | true ;;

Note Les noms de constructeurs commencent par une majuscule. Les seules exceptions sont quelques types prédéfinis par OCaml, notamment les booléens (dont les constructeurs sont true et false), les entiers, les flottants...

Ainsi, si nous tentons de définir un type à l'aide de constructeurs qui commencent par une minuscule, nous obtiendrons

# type somme_erreur = a | b ;;
                        ^
Error: Parse error: [str_item] or ";;" expected (in [top_phrase])

C'est-à-dire "Je ne comprends pas ce que vous avez écrit. À cet endroit-là d'une [top_phrase] (une phrase de plus haut niveau, c'est-à-dire une déclaration), j'attends soit une autre [str_item] (c'est-à-dire une déclaration ou un calcul), soit un ';;'."

Nous reviendrons fréquemment sur le filtrage par motifs -- pour le moment sans le définir précisément -- car il s'agit d'un des mécanismes les plus intéressants de la programmation fonctionnelle.

Les sommes comme conteneurs

Comme mentionné plus haut, les types somme approximent la notion mathématique d'union. Jusqu'à présent, nous avons n'avons guère vu l'union se manifester. Ceci est du au fait que nos constructeurs Trefle, Pique, Coeur et Carreau ne prennent aucun argument -- et ne désignent donc chacun, en pratique, qu'un ensemble réduit à un singleton. Voyons tout de suite un type un peu plus complexe, qui tirera parti d'ensembles plus vastes :

# type carte_de_tarot = 
  | Atout    of int
  | Roi      of couleur_de_carte
  | Dame     of couleur_de_carte
  | Cavalier of couleur_de_carte
  | Valet    of couleur_de_carte
  | As       of couleur_de_carte
  | Nombre   of int * couleur_de_carte ;;
type carte_de_tarot =
  | Atout of int
  | Roi of couleur_de_carte
  | Dame of couleur_de_carte
  | Cavalier of couleur_de_carte
  | Valet of couleur_de_carte
  | As of couleur_de_carte
  | Nombre of int * couleur_de_carte

La déclaration (et la réponse) s'énoncent "le type carte_de_tarot est constitué de l'ensemble des valeurs Atout i où i est un entier, de l'ensemble des valeurs Roi c où c est une couleur_de_carte, de l'ensemble des valeurs Dame c où c est une couleur_de_carte, de l'ensemble des valeurs Cavalier c où c est une couleur_de_carte, de l'ensemble Valet c où c est une couleur_de_carte, de l'ensemble As c où c est une couleur_de_carte et enfin de l'ensemble Nombre i c où i est un entier et c est une couleur_de_carte."

Après cette définition, nous pouvons employer des valeurs de type carte_de_tarot:

# Atout 5 ;;
- : carte_de_tarot = Atout 5

# Cavalier Trefle ;;
- : carte_de_tarot = Cavalier Trefle

# Nombre (5, Trefle) ;;
- : carte_de_tarot = Nombre 5 Trefle

Vocabulaire Les constructeurs de carte_de_tarot sont Atout _, Roi _, Dame _, Cavalier _, Valet _, As _ et Nombre(_, _).

Notons que cette représentation laisse un élément de fragilité, puisque nous pouvons très bien écrire :

# Atout 23;;
- : carte_de_tarot = Atout 23

# Nombre (-1, Trefle);;
- : carte_de_tarot =  Nombre (-1, Trefle)

En d'autres termes, nous ne pouvons pas encore manipuler les cartes en toute sécurité. Avant cela, nous devrons nous assurer que Nombre ne peut être associés qu'à des entiers compris entre 1 et 9 et Atout à des entiers entre 0 et 21. Nous verrons comment garantir ce genre de propriétés lorsque nous parlerons de modules.

Nous pouvons maintenant manipuler les carte_de_tarots à l'aide du filtrage par motifs. Ainsi, pour afficher le nom complet d'une carte, nous pourrons définir la fonction

# let string_of_carte_de_tarot carte = match carte with
  | Atout    i    -> string_of_int i ^ " d'atout"
  | Roi      c    -> "Roi de "       ^ ( string_of_couleur_de_carte c )
  | Dame     c    -> "Dame de "      ^ ( string_of_couleur_de_carte c )
  | Cavalier c    -> "Cavalier de "  ^ ( string_of_couleur_de_carte c )
  | Valet    c    -> "Valet de "     ^ ( string_of_couleur_de_carte c )
  | As       c    -> "As de "        ^ ( string_of_couleur_de_carte c )
  | Nombre (i, c) -> string_of_chiffre_francais i ^ " de " ^ ( string_of_couleur_de_carte c ) ;;
val string_of_carte_de_tarot : carte_de_tarot -> string = <fun>

# let string_of_carte_de_tarot = function
  | Atout    i    -> string_of_int i ^ " d'atout"
  | Roi      c    -> "Roi de "       ^ ( string_of_couleur_de_carte c )
  | Dame     c    -> "Dame de "      ^ ( string_of_couleur_de_carte c )
  | Cavalier c    -> "Cavalier de "  ^ ( string_of_couleur_de_carte c )
  | Valet    c    -> "Valet de "     ^ ( string_of_couleur_de_carte c )
  | As       c    -> "As de "        ^ ( string_of_couleur_de_carte c )
  | Nombre (i, c) -> string_of_chiffre_francais i ^ " de " ^ ( string_of_couleur_de_carte c ) ;;
val string_of_carte_de_tarot : carte_de_tarot -> string = <fun>

Les deux écritures de string_of_carte_de_tarot sont strictement équivalentes. Dans ce qui précède, nous avons utilisé la fonction string_of_chiffre_francais définie plus haut, la fonction string_of_int vue plus haut et l'opérateur ^ de concaténation de chaînes de caractères. La première syntaxe, de nouveau, insiste sur le fait que le comportement de la fonction est différent selon la structure de carte : si carte s'écrit Atout i, la fonction se comporte comme string_of_int i ^ " d'atout" sinon, si carte> s'écrit Roi c, la fonction se comporte comme "Roi de " ^ ( string_of_couleur_de_carte c ) ... La deuxième syntaxe, plus mathématique, se prononcerait "s'il existe un entier i tel que l'argument s'écrive Atout i, le résultat est donné par ..." ou encore, avec un point de vue ensembliste, "string_of_carte_de_tarot est la fonction qui à tout élément i de l'ensemble Atout associe string_of_int i ^ " d'atout", à tout élément c de l'ensemble Roi associe..." ou encore, cette fois avec un point de vue plus informatique, "string_of_carte_de_tarot est la fonction qui à tout entier i étiqueté Roi associe ..."

De nouveau, lors du filtrage par motifs, nous avons lié des variables (ici i ou/et c selon les cas) à des valeurs contenues dans carte.

Une fois cette fonction définie, nous pouvons écrire

# string_of_carte_de_tarot ( Atout 5 ) ;;
- : string = "5 d'atout"

# string_of_carte_de_tarot ( Valet Pique ) ;;
- : string = "Valet de pique"

# string_of_carte_de_tarot ( Nombre (5, Trefle ));;
- : string = "Cinq de trefle"

Notons que nous n'avons pas à nous arrêter en si bon chemin : nous pouvons très bien utiliser le filtrage par motifs pour chercher des motifs de complexité arbitraire. Ainsi, considérons l'extrait suivant :

# let est_pique = function
   | As         Pique  -> true
   | Roi        Pique  -> true
   | Dame       Pique  -> true
   | Cavalier   Pique  -> true
   | Nombre (_, Pique) -> true
   | _                 -> false ;;
val est_pique : carte_de_tarot -> bool = <fun>

Tout comme As c était un motif, qui acceptait n'importe quel As et liait c à sa couleur, As Pique est un motif plus précis, qui accepte uniquement la valeur As Pique. Le motif Nombre _ Pique, quant à lui, est équivalent au motif Nombre c Pique -- le symbole _, qui se prononce "don't care", est un motif qui accepte n'importe quelle valeur mais ne procède à aucune liaison. En d'autres termes, on emploiera _ pour signifier que nous ne somme pas intéressés par un valeur correspondante. C'est ainsi, le dernier motif _ accepte toutes les valeurs. Comme dans l'exemple string_of_nombre_francais, nous tirons parti du fait que les motifs sont essayés dans l'ordre dans lequel ils sont écrits, si bien que _ tient ici un rôle similaire à else (dans le cadre d'un if...then...else) ou default: (dans le cadre d'un switch(...) case: ... default: ....

Nous verrons plus loin comment fusionner plusieurs motifs et réduire la taille de la fonction est_pique

Exercices

1. Définissez un type de données couleur_ou_erreur qui pourra contenir soit une couleur_de_carte (constructeur Couleur), soit un message d'erreur (une chaîne de caractères quelconque, avec le constructeur Erreur).
2. Définissez une fonction get_couleur : carte_de_tarot -> couleur_ou_erreur, qui renverra la couleur de la carte qu'on lui passe en argument. Comme les Atouts n'ont pas de couleur, on utilisera Erreur pour répondre dans le cas où la carte serait un Atout.
3. La fonction suivante ne produit pas le résultat escompté. Pourquoi ? Le type de cette fonction pourra vous aider à trouver l'erreur.

# let est_couleur couleur = function
  | As       couleur    -> true
  | Roi      couleur    -> true
  | Dame     couleur    -> true
  | Cavalier couleur    -> true
  | Nombre (_, couleur) -> true
  | _                   -> false ;;
val est_couleur : 'a -> carte_de_tarot -> bool = <fun>

1. Définissez une fonction est_couleur : couleur_de_carte -> carte_de_tarot -> bool, qui détermine si une carte porte bien une couleur donnée. Vous pourrez utiliser = pour comparer les couleurs. Renvoyez false si la carte est un Atout.

Filtrage par motifs

Match

En OCaml, le filtrage par motifs est une manière de définir une expression en fonction de la structure d'une valeur, c'est-à-dire de la manière dont la valeur est construite -- et ce terme cache les constructeurs que nous avons rencontrés tout au long de cette section.

Sous sa forme la plus générale, le filtrage par motifs selon la structure de la valeur v s'écrit

match v with
| p1 -> e1
| p2 -> e2
(* ... *)
| pn -> en

Cette construction se lit "si v a la structure p1, évaluer l'expression e1, dans le cas contraire, si v a la structure p2, évaluer l'expression e2 ... dans le cas contraire, si v a la structure pn, évaluer l'expression en." Si v n'a aucune de ces structures, il s'agit d'une erreur fatale d'exécution.

Notons que la valeur v utilisée ici peut être remplacée par n'importe quelle expression expr, auquel cas c'est le résultat de l'évaluation de expr qui sera utilisé à la place de v.

Vocabulaire p1, p2 ... pn sont des motifs.

Nous avons déjà vu de nombreux exemples de motifs. Ainsi, dans

# let string_of_couleur_de_carte c = match c with
    | Trefle -> "trefle"
    | Pique  -> "pique"
    | Coeur  -> "coeur"
    | Carreau-> "carreau" ;;

les constructeurs Trefle, Pique, Coeur, Carreau sont employés en tant que motifs. De même, dans

# let string_of_nombre_francais x = match x with
   | 1 -> "Un"
   | 2 -> "Deux"
   | 3 -> "Trois"
   | 4 -> "Quatre"
   | 5 -> "Cinq"
   | 6 -> "Six"
   | 7 -> "Sept"
   | 8 -> "Huit"
   | 9 -> "Neuf"
   | 0 -> "Zero" 
   | n -> string_of_int n ;;

les constructeurs sans arguments 1, 2, 3, 4, 5, 6, 7, 8, 9 et 0 et le nom de variable n sont utilisés en tant que motifs. De manière plus compliquée, dans

# let string_of_carte_de_tarot carte = match carte with
  | Atout    i    -> string_of_int i ^ " d'atout"
  | Roi      c    -> "Roi de "       ^ ( string_of_couleur_de_carte c )
  | Dame     c    -> "Dame de "      ^ ( string_of_couleur_de_carte c )
  | Cavalier c    -> "Cavalier de "  ^ ( string_of_couleur_de_carte c )
  | Valet    c    -> "Valet de "     ^ ( string_of_couleur_de_carte c )
  | As       c    -> "As de "        ^ ( string_of_couleur_de_carte c )
  | Nombre (i, c) -> string_of_chiffre_francais i ^ " de " ^ ( string_of_couleur_de_carte c ) ;;

le motif Atout i est composé de la variable i placée dans le constructeur à un argument Atout, le motif Roi c est composé de la variable c placée dans le constructeur à un argument Roi... et le motif Nombre(i, c) est composé de la variable c et de la variable i placés dans le constructeur à deux arguments Nombre.

Voyons tout de suite la définition exacte d'un motif :

• une variable v est un motif, qui accepte n'importe quelle valeur -- lorsque la valeur est acceptée, v est liée à cette valeur
• si A est un constructeur qui n'accepte aucun argument, alors A est un motif, qui accepte exactement la valeur A
• si A est un constructeur qui accepte n arguments, si p1, p2 .. pn sont n motifs, alors A(p1, p2, ..., pn) est un motif, qui accepte tous les A(e1, e2, ..., en) tels que p1 accepte e1, p2 accepte e2 ... pn accepte en
• si p1 et p2 sont des motifs, p1 | p2 est un motif, prononcé "p1 ou p2" et qui accepte toutes les expressions acceptées soit par p1, soit par p2.

Ainsi, dans la définition de string_of_carte_de_tarot :

• OCaml commence par vérifier si carte est défini à l'aide du constructeur Atout
  • Le cas échéant, OCaml vérifie si carte s'écrit bien Atout i pour une certaine valeur de i -- de fait, comme x est défini à l'aide du constructeur Atout, c'est effectivement toujours le cas
  • Le cas échéant, OCaml lie i à la valeur nécessaire pour que carte s'écrive Atout i et donc l'expression string_of_int i ^ " d'atout"
• si x ne s'écrivait pas à l'aide du constructeur Atout, OCaml vérifie si x peut s'écrire à l'aide du constructeur Roi
  • Le cas échéant, OCaml vérifie si carte s'écrit bien Roi c pour une certaine valeur de c - de fait, comme x est défini à l'aide du constructeur Roi, c'est effectivement toujours le cas
  • Le cas échéant, OCaml lie c à la valeur nécessaire pour que carte s'écrive Roi c et évalue l'expression

"Roi de " ^ ( string_of_couleur_de_carte c )

• ...
• Si x ne s'écrit d'aucune des manières précédentes, OCaml vérifie si carte peut s'écrire à l'aide du constructeur Nombre
  • Le cas échéant, OCaml vérifie si carte s'écrit bien Nombre(i, c) pour une certaine valeur de i et c - de fait, comme carte est défini à l'aide du constructeur Nombre, c'est effectivement toujours le cas
  • Le cas échéant, OCaml lie c et i aux valeurs nécessaires pour que x s'écrive Nombre i c et évalue l'expression string_of_chiffre_francais i ^ " de " ^ ( string_of_couleur_de_carte c ).

Insistons sur le fait qu'un motif peut contenir un motif. Ainsi, on aurait pu ajouter un premier cas plus spécifique

# let string_of_carte_de_tarot carte = match carte with
  | Atout    0 -> "Excuse"
  | Atout    i -> string_of_int i ^ " d'atout"
 ...

auquel cas, en plus de vérifier si carte peut s'écrire Atout x pour un certain x, OCaml aurait vérifié si la valeur de x était de plus acceptée par 0.

Function

Dans certains des exemples que nous avons rencontrés, nous avons employé function au lieu de match. Ceci est permis par quelques raccourcis syntaxiques d'OCaml. Ainsi, considérons l'expression suivante :

fun x -> match x with
   | p1 -> e1
   | p2 -> e2
   ...
   | pn -> en

Pour peu que ce nom x ne soit pas utilisé dans e1...en, cette expression peut s'abréger de la manière suivante :

function p1 -> e1
       | p2 -> e2
       | ...
       | pn -> en

Précautions et limitations

Variables dans les motifs

Lorsqu'un motif accepte une valeur, toutes les variables qui apparaissent dans ce motif sont liées par le filtrage. En particulier, nous aurons

# let x = 1 in match 5 with x -> x ;;
      ^
Warning Y: unused variable x.
- : int = 5

Comme le signale l'avertissement, la première définition de x est totalement ignorée. L'utilisation de x en tant que motif accepte n'importe quelle valeur -- ici 5 -- et lie cette valeur à x.

C'est pour cette raison qu'une même variable ne peut pas apparaître deux fois dans un motif sans | :

# match (1,2) with (x,x) -> print_int x ;;
                        ^
Variable x is bound several times in this matching

En effet, pour que cette expression ait un sens, x devrait valoir à la fois la valeur 1 et la valeur 2.

À l'inverse, dans un motif de la forme p1 | p2, les variables qui apparaissent dans p1 doivent être exactement les mêmes que celles qui apparaissent dans p2.

# function
    Atout i | Roi j  -> i  ;;
            ^^^^^^^^^^^
Variable i must occur on both sides of this | pattern

À titre de comparaison

Dans Java ou tout autre langage par objets statiquement typé, l'équivalent du type somme carte_de_tarot serait une hiérarchie de classes doté d'un visiteur (le visiteur est l'un des patrons de conception les plus importants pour la programmation orientée objets) :

public interface CarteDeTarotVisitor<T>
{
  public T visitAtout   (Atout c);
  public T visitRoi     (Roi   c);
  public T visitDame    (Dame   c);
  public T visitCavalier(Cavalier  c);
  public T visitValet   (Valet   c);
  public T visitAs      (As   c);
  public T visitNombre  (Nombre c);
}

public abstract class CarteDeTarot
{
  protected CarteDeTarot()
  {
  }

  public<T> T accept(CarteDeTarotVisitor<T> v);
}


public class Atout extends CarteDeTarot
{
  public final int valeur;
  public Atout(int valeur)
  {
    assert(0 <= valeur && valeur <= 21 );
    this.valeur = valeur;
  }

  public<T> T accept(CarteDeTarotVisitor<T> v);
  {
     return v.visitAtout(this);
  }
}

public class Roi extends CarteDeTarot
{
  public final CouleurDeCarte couleur;
  public Roi(CouleurDeCarte couleur)
  {
    assert(couleur != null );
    this.couleur = couleur;
  }

  public<T> T accept(CarteDeTarotVisitor<T> v);
  {
     return v.visitRoi(this);
  }
}

public class Dame extends CarteDeTarot
{
  public final CouleurDeCarte couleur;
  public Dame(CouleurDeCarte couleur)
  {
    assert(couleur != null );
    this.couleur = couleur;
  }

  public<T> T accept(CarteDeTarotVisitor<T> v);
  {
     return v.visitDame(this);
  }
}

public class Cavalier extends CarteDeTarot
{
  public final CouleurDeCarte couleur;
  public Cavalier(CouleurDeCarte couleur)
  {
    assert(couleur != null );
    this.couleur = couleur;
  }

  public<T> T accept(CarteDeTarotVisitor<T> v);
  {
     return v.visitCavalier(this);
  }
}

public class Valet extends CarteDeTarot
{
  public final CouleurDeCarte couleur;
  public Valet(CouleurDeCarte couleur)
  {
    assert(couleur != null );
    this.couleur = couleur;
  }

  public<T> T accept(CarteDeTarotVisitor<T> v);
  {
     return v.visitValet(this);
  }
}

public class As extends CarteDeTarot
{
  public final CouleurDeCarte couleur;
  public As(CouleurDeCarte couleur)
  {
    assert(couleur != null );
    this.couleur = couleur;
  }

  public<T> T accept(CarteDeTarotVisitor<T> v);
  {
     return v.visitAs(this);
  }
}

public class Nombre extends CarteDeTarot
{
  public final CouleurDeCarte couleur;
  public final int            valeur;
  public Nombre(CouleurDeCarte couleur, int valeur)
  {
    assert(couleur != null );
    assert(2 <= valeur && valeur <= 10 );
    this.couleur = couleur;
    this.valeur  = valeur;
  }

  public<T> T accept(CarteDeTarotVisitor<T> v);
  {
     return v.visitNombre(this);
  }
}

À ce stade, le seul avantage de la version Java sur notre version OCaml est que cette première vérifie la valeur de la carte, pour garantir qu'un Atout sera toujours entre 0 et 21 et une carte numérotée entre 2 et 10. Nous verrons bientôt qu'il est aussi simple de faire de même en OCaml, en introduisant l'équivalent des constructeurs Java -- en OCaml, ce sont des fonctions ordinaires. Dans les langages orientés objet, l'utilisation du patron de conception Visiteur est importante pour pouvoir implanter par la suite des fonctions telles que string_of_carte_de_tarot sans modifier la hiérarchie originelle. Notons que, sur ce dernier point, il ne s'agit pas d'un avantage décisif d'OCaml mais d'une manière différente de concevoir la programmation : dans les langages par objets, le comportement d'un programme se décrit essentiellement sous la forme d'un ensemble de classes, où chaque classe est caractérisée par des propriétés (les champs) et des instructions auxquelles elle sait répondre (les méthodes). À l'inverse, dans les langages fonctionnels, les comportement d'un programme se décrit essentiellement sous la forme d'un ensemble de conteneurs de données (les structures), sur lesquelles agissent des transformations (les fonctions). Un problème dans lequel une fonction devra agir sur plusieurs structures se traduira donc plus naturellement en programmation fonctionnelle, tandis qu'un problème mieux caractérisé par des interactions entre objets se traduira plus naturellement en programmation orientée objets. Nous verrons plus loin comment rassembler des propriétés et instructions en modules sous OCaml et ainsi retrouver une bonne partie des bénéfices de la programmation par objets.

Une fois cette hiérarchie implantée et en supposant que l'on s'interdit de modifier la susdite hiérarchie, par exemple parce qu'elle est fournie sous la forme d'une bibliothèque de programmation, l'équivalent de la fonction string_of_carte_de_tarot, en supposant que nous savons déjà transformer une couleur de carte en une chaîne de caractères, serait :

public class StringOfCarteDeTarot implements CarteDeTarotVisitor<String>
{
  public String visitAtout   (Atout c)
  {
     return c.valeur + " d'atout ";
  }
  public String visitRoi     (Roi   c)
  {
     return "Roi de "+c.couleur;
  }
  public String visitDame    (Dame   c)
  {
     return "Dame de "+c.couleur;
  }
  public String visitCavalier(Cavalier  c)
  {
     return "Cavalier de "+c.couleur;
  }
  public String visitValet   (Valet   c)
  {
     return "Valet de "+c.couleur;
  }
  public String visitAs      (As   c)
  {
     return "As de "+c.couleur;
  }
  public String visitNombre  (Nombre c)
  {
     return Utilitaires.getChiffreFrancais ( c.valeur ) + " de " + c.couleur ;
  }
}

Paramètres de types

Tout comme nous avons employé des types de fonctions contenant des paramètres de types 'a, 'b..., nous pouvons définir de nouveaux types paramétriques avec ces mêmes variables. Ainsi, une variante sur le type couleur_ou_erreur est le type option, défini dans la bibliothèque standard de OCaml comme

# type 'a option =
    | Some of 'a
    | None ;;
type 'a option = Some of 'a | None

Nous pouvons donc utiliser :

# None ;;
- : option 'a = None

# Some 5 ;;
- : option int = Some 5

# Some "blue ";;
- : option string = Some "blue"

Nous pouvons de même réécrire get_couleur

# let get_couleur = function
    | As       c    -> Some c
    | Roi      c    -> Some c
    | Valet    c    -> Some c
    | Dame     c    -> Some c
    | Cavalier c    -> Some c
    | Nombre (_, c) -> Some c
    | _             -> None ;;
val get_couleur : carte_de_tarot -> couleur_de_carte option = <fun>

Comme d'habitude, c'est OCaml qui détermine quel type doit remplacer 'a.

La fonction est_couleur se réécrit alors par exemple :

# let est_couleur couleur carte = match get_couleur carte with
      None   -> false
    | Some c -> c = couleur ;;
val est_couleur : couleur_de_carte -> carte_de_tarot -> bool = <fun>

De même, il est fréquent d'utiliser des types ressemblant à

# type ('a, 'b) succes_ou_erreur =
    | Succes  of 'a
    | Erreur  of 'b ;;
type ('a, 'b) succes_ou_erreur =  Succes  of 'a | Erreur  of 'b

Un tel type permet d'écrire des fonctions qui produiront comme résultat Succes x, où x est une valeur renvoyée lorsque la fonction s'exécute correctement ou Erreur y, où code y est une valeur renvoyée lorsque la fonction rencontre un problème :

# let division x y =
    if y = 0 then  Erreur "Division par zero"
    else           Succes ( x / y );;
val division : int -> int -> succes_ou_erreur int string = <fun>

On pourrait, de même, définir le type d'un singleton, d'un couple, d'un triplet... par

# type empty_set           = EmptySet ;;
# type 'a singleton        = Singleton of 'a ;;
# type ('a, 'b) pair       = Pair of 'a * 'b ;;
# type ('a, 'b, 'c) triple = Triple of 'a * 'b * 'c;;

En fait, nous verrons bientôt qu'OCaml propose une autre syntaxe, plus concise, pour les n-uplets.

À titre de comparaison

En Java et dans l'essentiel des langages de programmation, le type 'a option est inutile car (presque) tous les types peuvent prendre la valeur spéciale null. Cette possibilité est un héritage de l'ère C, dans laquelle les références en mémoire ne sont que des entiers comme les autres et la valeur 0 est utilisée par convention pour représenter un pointeur qui ne pointe sur rien d'intéressant. L'inconvénient de cette approche est double :

• quelques types précis, fixés lors de la conception du langage, ne peuvent, pour des raisons de performances, pas prendre la valeur null
• comme toute valeur à l'exception de ces quelques types peut valoir null, le compilateur ne peut pas vérifier si l'on passe null à une fonction qui ne peut pas accepter ce genre de valeur. C'est au programmeur d'ajouter manuellement à chaque fonction qui ne peut pas accepter une valeur null une vérification sur la null-ité des arguments, sous peine de devoir plus tard déboguer des NullPointerExceptions (en Java), voire des SEGFAULT (dans beaucoup d'autres langages).

Par comparaison, l'approche OCaml :

• garantit l'impossibilité d'erreurs comparables au NullPointerException
• permet de documenter clairement quelles valeurs peuvent prendre la valeur None et quelles valeurs sont toujours définies
• peut s'étendre, comme le montre l'exemple succes_ou_erreur pour renvoyer des détails sur une éventuelle erreur
• pourrait encore s'étendre pour gérer un nombre arbitraire de possibilités, contrairement à l'alternative null / pas null.

Sommes récursives

En OCaml, les types peuvent être définis récursivement -- et c'est fréquemment le cas des types sommes. Pour ce faire, il n'est pas nécessaire d'utiliser un mot-clé particulier. Ainsi, une liste de cartes pourra être définie comme :

• soit la liste vide
• soit une liste non-vide, c'est-à-dire une carte suivie d'une liste de cartes (que nous appellerons la queue).

En OCaml, nous traduirons ceci par

# type liste_de_cartes =
     | ListeVide
     | ListeNonVide of (carte_de_tarot * liste_de_cartes ) ;;
type liste_de_cartes =
     | ListeVide
     | ListeNonVide of (carte_de_tarot * liste_de_cartes )

De fait, à l'aide des paramètres de types, on pourrait même écrire

# type 'a liste =
     | ListeVide
     | ListeNonVide of ( 'a * 'a liste ) ;;
type 'a liste =
     | ListeVide
     | ListeNonVide of ( 'a * 'a liste )

Note Il existe une syntaxe plus agréable et plus lisible pour les listes, ainsi que toute une bibliothèque de fonctions sur ces listes, que nous détaillerons plus tard. Pour le moment, contentons-nous d'oublier que tout ceci est déjà défini dans OCaml.

Nous venons de définir les constructeurs ListeVide et ListeNonVide(_, _). Pour ajouter un élément en tête d'une liste, nous pourrons écrire par exemple :

# let cons tete queue = ListeNonVide tete queue ;;
val cons : 'a -> 'a liste -> 'a liste = <fun>

Note Le nom "cons" (le "s" se prononce) est couramment utilisé en programmation fonctionnelle. Il désigne l'ajout d'un élément en tête de liste.

En appliquant plusieurs fois les constructeurs ou cons, nous pouvons écrire de la manière suivante la liste qui contient 1, 2, 3, 4 et 5 :

# let une_liste = ListeNonVide (1, ListeNonVide (2, ListeNonVide (3, ListeNonVide (4, ListeNonVide (5, ListeVide ) ) ) ) ;;
val une_liste : int liste =
  ListeNonVide ( 1,
   ListeNonVide ( 2,
     ListeNonVide ( 3,  (ListeNonVide (4,  ListeNonVide (5, ListeVide))))

# let une_liste = cons 1 (cons 2 (cons 3 (cons 4 (cons 5 ListeVide)))) ;;
val une_liste : int liste =
  ListeNonVide ( 1,
   ListeNonVide ( 2,
     ListeNonVide ( 3,  (ListeNonVide (4,  ListeNonVide (5, ListeVide))))

Note Ceci est une liste (chaînée) au sens de la programmation fonctionnelle. Contrairement aux listes impératives, on s'interdit de modifier la liste en supprimant ou en insérant de nouveaux éléments. Au lieu de cela, insérer ou supprimer un élément d'une liste seront des opérations de transformation, qui construiront de nouvelles listes en lieu et place des anciennes. Bien entendu, en OCaml, il est aussi possible de définir des listes impératives. D'expérience, ces dernières sont utilisées bien moins fréquemment.

Nous pouvons aisément déterminer si une liste est vide :

# let est_vide = function
   | ListeVide -> true
   | _         -> false ;;
val est_vide : 'a liste -> bool = <fun>

# let est_vide l = l = ListeVide ;;
val est_vide : 'a liste -> bool = <fun>

# let est_vide = ( = ) ListeVide ;;
val est_vide : '_a liste -> bool = <fun>

La première formulation utilise le filtrage par motifs. La deuxième compare l avec ListeVide pour produire le même résultat. Pour le moment, laissons de côté la troisième formulation et son surprenant '_a -- sachez juste que si vous rencontrez un tel type, vous êtes tombés sur une limitation du système de types actuel d'OCaml et que pour vous en tirer, la bonne méthode est d'ajouter l'argument l à votre fonction et de revenir à la deuxième formulation.

Dans tous les cas, nous aurons

# est_vide une_liste ;;
- : bool = false

Nous pouvons de même aisément compter le nombre de cartes dans une liste de cartes. Pour ce faire, nous pourrons appliquer la définition par récurrence suivante :

• la liste vide contient 0 cartes
• dans une liste non vide, nous pouvons commencer par calculer le nombre de cartes de la queue et lui ajouter 1.

Soit, en OCaml, récursivement et à l'aide du filtrage par motifs

# let rec longueur l = match l with
    | ListeVide               -> 0
    | ListeNonVide (_, queue) -> longueur queue + 1 ;;
val longueur : 'a liste -> int = <fun>

# let rec longueur = function
    | ListeVide               -> 0
    | ListeNonVide (_, queue) -> longueur queue + 1 ] ;
val longueur : 'a liste -> int = <fun>

De nouveau, les deux formulations sont équivalentes. Notons que l'argument est de type 'a liste : comme nous n'avons jamais utilisé le contenu de la liste, leur type n'est pas contraint -- et cette fonction peut traiter des listes de n'importe quel type.

Bien entendu, de la même manière que nous avons défini des fonctions abstraites sur les entiers, il est naturel de définir des fonctions abstraites sur les listes. Ainsi, en généralisant la valeur 0 (sous la forme d'un argument init) et l'opération + (sous la forme d'un argument f), nous obtenons, selon l'ordre des opérations :

# let operation_sur_liste_droite f init = 
   let rec aux = function
     | ListeVide               -> init
     | ListeNonVide (c, queue) -> ( f c ( aux queue ) ) 
   in aux;;
val operation_sur_liste_droite : ('a -> 'b -> 'b) -> 'b -> 'a liste -> 'b =
  <fun>

ou

# let operation_sur_liste_gauche f init = 
   let rec aux acc = function
     | ListeVide               -> acc
     | ListeNonVide (c, queue) -> aux ( f c acc ) queue
   in aux init;;
val operation_sur_liste_gauche : ('a -> 'b -> 'b) -> 'b -> 'a liste -> 'b =
  <fun>

Une fois ceci fait, nous pouvons demander à OCaml d'appliquer une transformation à la liste une_liste, en passant chaque élément par cons et en initialisant le résultat à ListeVide :

# operation_sur_liste_droite cons ListeVide une_liste ;
- : int liste =
  ListeNonVide ( 1,
   ListeNonVide ( 2,
     ListeNonVide ( 3,  (ListeNonVide (4,  ListeNonVide (5, ListeVide))))

# operation_sur_liste_gauche cons ListeVide une_liste ;
- : liste int =
  ListeNonVide ( 5,
   ListeNonVide ( 4,
     ListeNonVide ( 3,  (ListeNonVide (2,  ListeNonVide (1, ListeVide))))

On pourrait définir de même des fonctions de filtre, de transformations de listes...

... et listes

Comme mentionné plus haut, il n'est en fait pas nécessaire de définir nous-même une notion de liste, puisque OCaml dispose de cette notion et d'une syntaxe simplifiée pour les manipuler.

Conceptuellement, l'ensemble des listes d'éléments de type 'a, noté 'a list est un type somme doté des constructeurs

• [], la liste vide
• _ :: _ , la liste non vide -- on notera h :: t la liste dont le premier élément est h et le reste des éléments est une liste t.

Vocabulaire Le constructeur [] est appelé "nil". Le constructeur _ :: _ est appelé "cons".

Ainsi, nous aurons

# [] ;;
- : 'a list = []

# 1 :: 2 :: 3 :: 4 :: 5 :: [] ;;
- : int list = [1; 2; 3; 4; 5]

Comme le montre la réponse d'OCaml, il existe en fait une notation plus simple :

# [1; 2; 3; 4; 5];;
- : int list = [1; 2; 3; 4; 5]

Ces notations peuvent être utilisées aussi bien pour créer de nouvelles listes que pour le filtrage par motifs. Ainsi, nous pouvons définir les fonctions est_vide, tete, queue comme

# let est_vide = function
   |  []  -> true
   |  _   -> false ;;
val est_vide : 'a list -> bool = <fun>


# let tete = function  h :: _  -> h ;;
             ^^^^^^^^^^^^^^^^^^^^^^
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
val tete : 'a list -> 'a = <fun>

# let queue = function _ :: t -> t ;;
              ^^^^^^^^^^^^^^^^^^^^
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
val queue : 'a list -> 'a = <fun>

Ces deux dernières définitions sont accompagnées d'un avertissement -- effectivement, elle n'ont aucun sens lorsque la liste est vide.

Note La fonction tete est déjà définie dans la bibliothèque standard sous le nom List.hd et la fonction queue sous le nom List.tl. De nombreuses autres fonctions sur les listes sont définies dans la bibliothèque standard. Systématiquement,

pour définir une fonction qui compte le nombre d'éléments dans une liste, nous pourrons écrire

# let rec longueur = function
   |  [] -> 0
   |  _ :: t -> longueur t + 1 ;;

Dans l'extrait qui précède, le motif [] désigne la liste vide. De même, le motif _ :: t consiste en le constructeur cons appliqué aux deux motifs _ (en position de la tête de liste) et t (en position de la queue de liste). En d'autres termes, ce motif désigne une liste contenant au moins un élément (qui ne nous intéresse pas) et dont la queue de liste est liée au nom t.

De même, pour écrire une fonction qui filtrera une liste et ne gardera qu'un élément sur deux, nous pourrons écrire

# let rec un_sur_deux = function
   | []           -> []
   | _ :: []      -> []
   | h :: _ :: t  -> h :: (un_sur_deux t) ;;
val un_sur_deux : 'a list -> 'a list = <fun>

Cette définition s'énonce "la fonction un_sur_deux se définit récursivement par

• un_sur_deux appliqué à la liste vide produit la liste vide
• un_sur_deux appliqué à une liste à un seul élément produit encore la liste vide
• un_sur_deux appliqué à une liste contenant au moins deux éléments se calcule de la manière suivante
  • appelons h le premier élément
  • appelons t la suite de la liste
  • calculons un_sur_deux t
  • utilisons ce dernier résultat pour donner la suite de notre nouvelle liste et h comme premier élément
  • ceci est notre résultat."

Formulé différemment, nous avons parcouru la liste en éliminant un élément sur deux.

De fait, avec la notation raccourcie, nous pourrions réécrire la fonction sous la forme suivante

# let rec un_sur_deux = function
   | []                -> []
   | [ _ ]             -> [] (* une liste composée d'un seul élément *)
   | h :: _ :: t       -> h :: (un_sur_deux t) ;;
val un_sur_deux : 'a list -> 'a list = <fun>

Exercices

1. Écrivez une fonction qui détermine le dernier élément d'une liste.
2. Écrivez une fonction qui détermine l'avant-dernier élément d'une liste.
3. Écrivez une fonction qui inverse une liste.

Arbres

De la même manière que nous avons défini des listes à l'aide d'un type somme récursif, ces mêmes types peuvent servir à définir des arbres. Ainsi, on peut représenter les formules de logique booléenne sous la forme suivante :

# type formule =
    | Booleen  of bool
    | Variable of string
    | Et       of formule * formule
    | Ou       of formule * formule
    | Non      of formule
    | Implique of formule * formule ;;
type formule =
  | Booleen of bool
  | Variable of string
  | Et of formule * formule
  | Ou of formule * formule
  | Non of formule
  | Implique of formule * formule 

# Booleen true ;
- : formule = Booleen true

Partant de là, nous pouvons définir des transformations sur les arbres :

# let formule_ou_exclusif a b = Et ( Ou ( a, b ), Ou ( Non a, (Non b ) ) );;
val formule_ou_exclusif : formule -> formule -> formule = <fun>

# formule_ou_exclusif ( Booleen true ) ( Booleen false ) ;;
- : formule =
Et (Ou (Booleen true, Booleen false),
 Ou (Non (Booleen true), Non (Booleen false)))

De même, nous pouvons programmer l'évaluation d'une expression booléenne, en supposant qu'aucune variable n'apparaît dans l'expression :

# let rec evalue arbre = match arbre with
  | Booleen _ -> arbre
  | Et (f, g) -> (match (evalue f, evalue g) with
     | (Booleen true, Booleen true)   -> Booleen true
     | _                              -> Booleen false )
  | Ou (f, g) -> (match (evalue f, evalue g) with
     | (Booleen false, Booleen false) -> Booleen false
     | _                              -> Booleen true )
  | Non f     -> (match (evalue f) with
     | Booleen true  -> Booleen false
     | Booleen false -> Booleen true
     |  _            -> failwith "Erreur dans l'évaluation d'une négation" )
  | Implique (f, g) -> (match (evalue f, evalue g) with
     | (_, Booleen true  )   -> Booleen true
     | (Booleen false, _ )   -> Booleen true
     | _                     -> Booleen false )
  | _ -> failwith "Erreur dans l'évaluation d'une formule" ;;

val evalue : formule -> formule = <fun>

Dans ce qui précède, nous avons procédé à du filtrage par motifs sur le couple de valeurs (simplifie f, simplifie g). Le résultat est un couple, sur lequel nous pouvons de nouveau procéder à du filtrage par motifs. Nous avons aussi utilisé la fonction failwith, qui provoque une erreur et interrompt immédiatement le calcul. Nous reparlerons de cette fonction lorsque nous nous intéresserons à la gestion des erreurs.

Notez aussi que nous avons été obligés de mettre entre parenthèses les match... intérieurs, pour éviter toute ambigüité.

Nous pourrions étendre la fonction précédente de manière à simplifier autant que possible les expressions contenant des variables :

# let rec simplifie arbre = match arbre with
   | Booleen _  -> arbre    (*Impossible de simplifier un booléen  *)
   | Variable _ -> arbre    (*Impossible de simplifier une variable*)
   | Et (f, g)  -> (match (simplifie f, simplifie g) with
       ( ( Booleen false, _ ) -> Booleen false   (*Faux et x => Faux *)
       | ( _, Booleen false ) -> Booleen false   (*x et Faux => Faux *)
       | ( Booleen true,  x ) -> x               (*Vrai et x => x    *)
       | ( x,  Booleen true ) -> x               (*x et Vrai => x    *)
       | (f', g')             -> Et (f', g'))    (*Sinon, on ne peut pas simplifier plus  *)
   | Ou (f, g)   -> match (simplifie f, simplifie g) with
       | ( Booleen true, _  ) -> Booleen true    (* ... *)
       | ( _, Booleen frue  ) -> Booleen true
       | ( Booleen false,  x) -> x
       | ( x,  Booleen false) -> x
       | (f', g')             -> Ou (f', g') )
   | Non f       -> ( match simplifie f with
       | Booleen true         -> Booleen false
       | Booleen false        -> Booleen true
       | x                    -> Non x )
   | Implique (f, g) -> (match (simplifie f, simplifie g) with
     | ( _, Booleen true  )   -> Booleen true
     | ( Booleen false, _ )   -> Booleen true
     | ( Booleen true, Booleen false ) -> Booleen false 
     | ( f', g')              -> Implique (f', g') );;
val simplifie : formule -> formule = <fun>

Exercices

1. À ce qui précède, nous pourrions ajouter des simplifications supplémentaires, telles que
   • tirer parti du fait que, pour tout x, non non x a la même valeur que x
   • tirer parti du fait que, pour tout x, x et non x a la même valeur que faux
   • tirer parti du fait que, pour tout x, x ou non x a la même valeur que vrai

complétez la fonction simplifie pour procéder à toutes ces simplifications.

1. Modifiez la fonction evalue pour supprimer l'utilisation de assert False -- au lieu de cela, pour gérer

les erreurs, vous utiliserez le type option formule.

1. Écrivez une fonction substitue : string -> bool -> formule -> formule, qui prend en argument un nom de variable, une valeur v à donner à cette variable et une formule et renvoie une formule dans laquelle toutes les occurrences de la variable ont été remplacées par Booleen v.
2. Modifiez la fonction substitue pour que, au lieu d'un booléen, elle accepte n'importe quelle formule.

Produit cartésien

Jusqu'à présent, nous avons manipulé les types somme. Ceux-ci permettent de représenter aisément l'union de plusieurs ensembles. Comme nous l'avons vu dans le cadre de ces types somme, un constructeur peut servir à accéder à plusieurs informations. La possibilité de combiner plusieurs informations en une seule valeur est fondamentale pour la programmation. Ainsi, l'emplacement d'un point à l'écran est en fait composé de deux entiers, l'un représentant son abscisse, l'autre son ordonnée. Une couleur pourra de même être représentée par trois entiers qui détermineront les proportions de rouge, de vert et de bleu, un nombre rationnel pourra être identifié à un entier relatif (son numérateur) et un entier strictement positif (son dénominateur)...

Mathématiquement, dans chacun de ces cas, la représentation peut être modélisée sous la forme d'un produit cartésien. En OCaml, plusieurs techniques sont disponibles pour implanter ces structures de données. Avec les types pair, triple,... nous avons déjà vu comment utiliser les types sommes pour arriver à ces fins. Dans cette section, nous verrons deux alternatives souvent plus confortables : les n-uplets et les enregistrements.

Couples et n-uplets

Au cours du chapitre sur les fonctions, nous avons déjà rencontré les n-uplets, sans les nommer. En OCaml, ceux-ci servent à rassembler plusieurs valeurs en une seule, sans plus de précisions. Ainsi, considérons l'extrait suivant :

# ( 1, 2 ) ;;
- : (int * int) = (1, 2)

La réponse d'OCaml s'énonce "le résultat de la dernière évaluation est de type int * int, c'est-à-dire un couple d'entiers, et vaut (1, 2)".

Cette syntaxe se généralise aux triplets et autres n-uplets, qui peuvent eux-mêmes contenir des éléments de n'importe quel type :

# ( true, 2, "autre chose" ) ;;
- : (bool * int * string) = (true, 2, "autre chose")

# ( 1, 'a', ( 1, 2, 3 ), "encore des éléments", false ) ;;
- : (int * char * (int * int * int) * string * bool) = (1, 'a', (1, 2, 3), "encore des éléments", false)

Sans surprise, nous pouvons aussi produire un n-uplet comme résultat d'une fonction :

# let creer_couple a b = ( a, b ) ;;
val creer_couple : 'a -> 'b -> ('a * 'b) = <fun>

# creer_couple 1 2 ;;
- : (int * int) = (1, 2)

Vocabulaire On dit que ( _, _ ) est le constructeur du type 'a * 'b. De même, ( _, _, _ ) est le constructeur du type 'a * 'b * 'c, ( _, _, _, _ ) celui de 'a * 'b * 'c * 'd... Une fois de plus, cette notion de constructeur n'a rien à voir avec les constructeurs de la programmation orientée objets.

Profitons de ce dernier exemple pour remarquer que les couples forment un type polymorphe à deux paramètres, ici 'a et 'b.

Les deux fonctions duales de creer_couple, prédéfinies dans OCaml (ou triviales à redéfinir, comme nous le verrons plus loin), sont fst et snd, les projections :

# fst ;;
- : ('a * 'b) -> 'a = <fun>
# snd ;;
- : ('a * 'b) -> 'b = <fun>

Comme leur type l'indique, fst et snd prennent chacune en argument un couple et renvoient respectivement son premier élément ou son second élément :

# fst ( 1, 2 );;
- : int = 1
# snd ( 1, 2 );;
- : int = 2

Insistons sur le fait que fst et snd ne fonctionnent que sur des couples -- comme en mathématiques, un triplet n'est pas un couple, si bien que :

# fst ( 1, 2, 3 );;
       ^^^^^^^^^^^
This expression has type (int * int * int) but is here used with type
  ('a * 'b)

# snd ( 1, 2, 3 );;
       ^^^^^^^^^^^
This expression has type (int * int * int) but is here used with type
  ('a * 'b)

Comment faire, alors, pour consulter le premier, le deuxième ou le troisième élément d'un n-uplet ? En fait, le mécanisme le plus simple pour déconstruire un n-uplet est de nouveau le filtrage par motifs. Ici, partant du fait que ( _, _, _) est un constructeur, nous pourrons écrire, comme pour les types somme :

# let fst_of_3 triplet = match triplet with
   ( a, b, c ) -> a ;;
val fst_of_3 : ('a * 'b * 'c) -> 'a = <fun>

ou, de manière plus concise,

# let fst_of_3 = function ( a, b, c ) -> a ;;
val fst_of_3 : ('a * 'b * 'c) -> 'a = <fun>

ou encore, en combinant le filtrage par motifs avec la définition de fonction,

# let fst_of_3 triplet = let ( a, b, c ) = triplet in a ;;
val fst_of_3 : ('a * 'b * 'c) -> 'a = <fun>

# let fst_of_3 ( a, b, c ) = a ;;
val fst_of_3 : ('a * 'b * 'c) -> 'a = <fun>

# let fst_of_3 ( a, _, _ ) = a ;;
val fst_of_3 : ('a * 'b * 'c) -> 'a = <fun>

Profitons-en pour rappeler l'une des utilisations des n-uplets, pour définir plusieurs valeurs en une seule fois :

# let (a, b, c) = ( 1, 2, 3 );;
val a : int = 1
val b : int = 2
val c : int = 3

Note En OCaml, puisque les couples, triplets et autres n-uplets n'ont pas le même type, il n'est pas possible d'écrire une fonction fst qui fonctionnera à la fois sur les couples, triplets et autres n-uplets. Il serait cependant possible de définir par méta-programmation une famille de fonctions fst_of_N pour tout N telle que, pour chaque N, fst_of_N puisse agir sur les N-uplets. Nous reviendrons dans un chapitre ultérieur sur les techniques de méta-programmation.

Enregistrements

Si les paires et autres tuples offrent une manière simple de manipuler deux, trois ou plus d'informations, les utiliser en permanence pose un risque d'ambigüité. En effet, un couple de nombres flottants peut servir à représenter aussi bien des coordonnées sur une carte, un nombres complexe sous forme cartésienne, un nombre complexe sous forme polaire, la probabilité d'un évènement, etc. Si chacun de ces usages est tout à fait acceptable, utiliser le même type de données pour représenter des informations sans rapport est une pratique découragée car elle interdit à OCaml de vérifier le bon usage de ces informations.

Pour plus de sûreté, nous pourrions donc employer des types sommes dotés d'un seul constructeur. Malheureusement, pour ce genre d'usage, leur lisibilité peut laisser à désirer. Ainsi, considérons un moment le type suivant :

# type polaire = Polaire of float * float ;;

Si nous souhaitons employer ce type pour représenter les nombres complexes sous forme polaire, c'est-à-dire sous la forme d'un argument et d'un module, nous devrons nous munir d'une convention. Par exemple, convenir que, dans Polaire (x, y), x est toujours l'argument et y toujours le module. Si ceci est toujours acceptable, de nouveau, nous avons introduit une fragilité, puisque c'est à nous de vérifier à chaque utilisation que nous ne confondons pas argument et module. L'idéal serait de permettre à OCaml de vérifier ceci systématiquement.

C'est pour cette raison qu'OCaml propose un autre style de produit cartésien : les enregistrements. Ainsi, la déclaration suivante définit un nouveau type, nommé cartesien, et qui va contenir deux nombres flottants, que nous choisissons de nommer re et im :

# type cartesien = { re : float; im : float };;
type cartesien = { re : float; im : float }

Vocabulaire Dans ce qui précède, re et im sont les champs de l'enregistrement cartesien.

Note Le terme "enregistrement" n'a rien à voir avec le fait d'enregistrer un fichier sur le disque dur. Il s'agit uniquement d'une manière de représenter des informations durant l'exécution d'un programme. Nous verrons dans un chapitre ultérieur comment enregistrer et récupérer des informations dans un fichier.

À partir du moment où cartesien est défini, nous pouvons créer de nouvelles valeurs de ce type :

# { re = 5.0; im = 10.0 } ;;
- : cartesien = {re=5; im=10}

# let i = { im = 1.; re = 0.} ;;
val i : cartesien = {re=0; im=1}

Ce dernier extrait s'énonce "Appelons i la valeur dont im vaut 1.0 et re vaut 0.0." Notons que l'ordre dans lequel sont donnés im et re est sans importance.

Toute tentative de créer une valeur de type cartesien contenant trop ou trop peu de définitions de champs provoquera une erreur lors de l'analyse de types :

# let x = { im = 5. } ;;
          ^^^^^^^^^^^
Some record field labels are undefined: re

# let y = { im = 5.; re = 3.; stuff = 8. } ;;
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Unbound record field label stuff

# let z = { im = 5.; re = 3.; re = 8. } ;;
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The record field label re is defined several times

Vocabulaire { im = _; re = _} est le constructeur de type cartesien. Comme l'ordre des champs est sans importance, on pourra considérer, au choix, que le constructeur de ce type est { re = _; im = _}.

Pour consulter la valeur d'un champ, on pourra employer la notation . (le point), similaire à celle des langages orientés-objets :

# let partie_reelle c = c.re ;;
val partie_reelle : cartesien -> float = <fun>

# partie_reelle i ;;
- : float = 0

Une autre possibilité consiste à utiliser le filtrage par motifs :

# let partie_relle c = match c with
   { re = x; im = _ } -> x  ;;
val partie_reelle : cartesien -> float = <fun>

# let partie_relle = function
   { re = x; im = _ } -> x ;;
val partie_reelle : cartesien -> float = <fun>

# let partie_relle { re = x; im = _ } = x ;;
val partie_reelle : cartesien -> float = <fun>

Qui plus est, OCaml propose un raccourci supplémentaire : il n'est pas nécessaire de faire figurer dans le motif les champs qui ne nous intéressent pas. Ainsi, nous pourrons écrire encore plus simplement

# let partie_relle c = match c with  { re = x } -> x ;;
val partie_reelle : cartesien -> float = <fun>

# let partie_relle = function { re = x } -> x;;
val partie_reelle : cartesien -> float = <fun>

# let partie_relle { re = x } = x ;;
val partie_reelle : cartesien -> float = <fun>

Et, pour achever la simplification de la syntaxe, comme avec les n-uplets, nous pouvons affecter directement une valeur, par exemple

# let { re = y } = i;;
val y : float = 0;;

Muni de ces outils, nous pouvons définir les opérations habituelles sur les nombres complexes :

# let add_cartesiens {re = x; im = y} {re = x'; im = y'} = {re = x +. x'; im = y +. y'} ;;
val add_cartesiens : cartesien -> cartesien -> cartesien = <fun>

# let mult_cartesiens {re = x; im = y} {re = x'; im = y'} = {re = x *. x' -. y *. y'; im = x *. y' +. x' *. y } ;;
val mult_cartesiens : cartesien -> cartesien -> cartesien = <fun>

etc.

On définirait de même une représentation polaire des nombres sous la forme :

# type polaire   = { arg : float ; mo : float };;
type polaire   = { arg : float ; mo : float }

Note Nous n'avons utilisé ni le nom module ni le terme mod pour désigner le module d'un nombre sous forme polaire car ces deux mots sont réservés par le langage.

Pour le moment, nous n'avons pas vu de méthode pour interdire de construire un polaire avec un module négatif, ce qui constituerait une erreur grossière mais potentiellement difficile à retrouver dans le code. Nous verrons plus tard comment gérer ce cas, avec les mêmes méthodes que nous emploierons aussi pour interdire de construire des cartes de tarot dont le numéro d'Atout n'est pas compris entre 0 et 21.

Sans surprise, OCaml interdit d'appliquer à la représentation polaire une fonction prévue pour la représentation cartésienne :

# add_cartesiens { arg = 0.; mo = 0. } ;;
                 ^^^^^^^^^^^^^^^^^^^^^
This expression has type polaire but is here used with type cartesien

Pour faire interagir complexes cartésiens et complexes polaires, il sera nécessaire de définir des fonctions de conversion. Par convention, nous les appellerons cartesien_of_polaire et polaire_of_cartesien :

# let cartesien_of_polaire { arg = a; mo = m } = { re = m *. cos a ; im = m *. sin a } ;;
val cartesien_of_polaire : polaire -> cartesien = <fun>

# let polaire_of_cartesien { re = r; im = i } = 
   { 
      mo  = sqrt ( r *. r +. i *. i ) ;
      arg = atan ( i /. r )
   } ;;
val polaire_of_cartesien : cartesien -> polaire = <fun>

Notons que cette fonction est correcte même si re vaut 0., en raison de la manière dont atan gère les valeurs infinies.

Nous pourrons alors manipuler cartésiens et polaires de la même manière que nous avons manipulé entiers et nombres flottants : en introduisant des conversions manuelles dès que nécessaire. Nous pourrons aussi définir de nouveaux opérateurs sur les nombres complexes de manière à simplifier légèrement les notations :

# let ( +++. ) = add_cartesiens ;;
val ( +++. ) : cartesien -> cartesien -> cartesien = <fun>

# let ( ***. ) = mult_cartesiens ;;
val ( ***. ) : cartesien -> cartesien -> cartesien = <fun>

#  { mo = sqrt 2. /. 2. ; arg = 3.1415926 }  +++. { re = 1.; im = 2. } ;;
   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This expression has type polaire but is here used with type cartesien

# polaire_of_cartesien ( cartesien_of_polaire { mo = sqrt 2. /. 2. ; arg = 3.1415926 }  +++. { re = 1.; im = 2. } ) ;;
- : polaire = {arg=1.42538337901; mo=2.02133287442}

Cette obligation de convertir explicitement est parfois lourde mais nécessaire pour garantir la bonne manipulation des nombres cartésiens et polaires sans sacrifier la vitesse ni introduire d'ambigüités.

Enregistrements vs. N-uplets vs. Sommes

La construction de nouveaux types sous la forme d'enregistrements ou de n-uplets ou de types sommes avec un seul constructeur servira les mêmes objectifs. Pour cette raison, de nombreux langages ne proposent comme structure de donnée que des enregistrements (ou des classes) ou que des n-uplets (ou des listes non typées). Par opposition, OCaml offre la possibilité de choisir une syntaxe différente et adaptée au problème. S'il n'y a pas un critère universel pour décider entre ces possibilités, on peut tout de même citer quelques conseils de bon sens.

Cas traités avec des types sommes

On emploiera des types sommes dès que les données peuvent prendre plusieurs formes, comme c'est le cas pour la liste (qui peut être vide ou non-vide, seul cas où on aura besoin de connaître une valeur et une suite de liste). Dans les autres cas, on préférera se passer des types sommes.

Cas traités avec des N-uplets

Comme nous l'avons déjà vu, il est possible d'utiliser des N-uplets pour lier en une seule évaluation plusieurs valeurs, que ce soit localement ou globalement. S'il serait possible de faire la même chose avec des enregistrements, on préférera souvent les N-uplets, plus confortables à manipuler.

# let (x,y) = (10, 15) ;;
val x : int = 10
val y : int = 15

# let (valeur_de_pi, incertitude_entre_valeurs) = 
    let ( pi_1, pi_2 ) = 
      ( 2. *. acos ( 0. ), 2. *. asin ( 1. ) )
    in
      ( pi_1, abs_float ( pi_1 -. pi_2 ) );;
val valeur_de_pi : float = 3.14159265359
val incertitude_entre_valeurs : float = 0

Le mécanisme est aussi utilisé fréquemment dès qu'il s'agit de produire plusieurs résultats à l'intérieur d'une sous-fonction.

Cas traités avec des enregistrements

Comme nous l'avons vu, utiliser des enregistrements permet à OCaml de détecter plus d'erreurs lors de l'analyse de types que les N-uplets. On aura donc tendance à utiliser des enregistrements dès que les informations qui constituent la valeur vont devoir être utilisées ensemble fréquemment et seront généralement conservées ensemble.

Note Nous verrons aussi dans le chapitre consacré à la programmation impérative comment définir et utiliser des enregistrements mutables.

À titre de comparaison

N-uplets en Java

En Java, on pourrait définir de même les n-uplets sous la forme d'une série de classes

public class Pair<A,B>
{
  public final A fst;
  public final B snd;
  public Pair(A fst, B snd)
  {
    this.fst = fst;
    this.snd = snd;
  }
}

public class Triple<A,B,C>
{
  public final A fst;
  public final B snd;
  public final C thrd;
  public Pair(A fst, B snd, C thrd)
  {
    this.fst = fst;
    this.snd = snd;
    this.thrd= thrd;
  }
}

//...autant de classes que nécessaire

Pour construire et manipuler un n-uplet, on emploierait

Triple <Integer, String, Float> myTriple = new Triple<Integer, String, Float>(100, "blue", 10.1);
System.out.println (myTriple.fst);
//...

En général, la version OCaml sera plus concise, plus rapide et prendra moins de mémoire vive -- mais les idées sont les mêmes.

Enregistrements en Java

Les enregistrements se traduisent naturellement en classes Java : la notion d'enregistrement OCaml est très proche de la notion de classe en Java, sans constructeur, sans modificateurs d'accès, sans héritage et sans accès à this. Nous verrons dans un chapitre ultérieur comment retrouver avec (ou sans) les enregistrements des fonctionnalités comparables en OCaml.

Types de fonctions

Nous avons déjà rencontré et manipulé les types de fonctions en OCaml.

Les types de fonctions se manipulent exactement de la même manière que tous les autres types en OCaml:

# type int_to_int = int -> int ;;
type int_to_int = int -> int

# (fun x -> x, fun x -> x + 1) ;;
- : ('a -> 'a * int -> int) = (<fun>, <fun>)

Précautions et limitations

Masquage de types

De la même manière qu'un nom de valeur peut être masqué si l'on donne le même nom à une autre valeur, le nom d'un type, d'un champ ou d'un constructeur peut être masqué si l'on donne le même nom à un autre type/champ/constructeur.

Cela peut donner lieu à des messages d'erreur surprenants :

# type t = { champ : int };;
type t = { champ : int }

# let unmake_t { champ = x } = x;;
value unmake_t : t -> int = <fun>
# unmake_t { champ = 5 };
- : int = 5

# type t = { champ : int };;
type t = { champ : int }

# unmake_t { champ = 5 };;
           ^^^^^^^^^^^^^^
This expression has type t but is here used with type t

Ici, le problème est que l'ancien type t a été remplacé par un nouveau type t. Même si ce nouveau type est identique au précédent, OCaml fait la différence. Si ce genre de choses ne devrait pas vous poser de problèmes lorsque vous compilez un programme, faites attention à ces redéfinitions de types lorsque vous utilisez la ligne de commande OCaml.

De même, on rencontrera le problème suivant si un constructeur de type somme est redéfini :

# type a = A | B ;;
type a = A | B
# type b = B | C ;;
type b = B | C
# B ;;
- : b = B
# A ;;
- : a = A
# fun A -> 1 | B -> 2 ;;
               ^
This pattern matches values of type b
but is here used to match values of type a

Exemple en taille réelle : vers un langage de programmation

Jusqu'à présent, nous avons travaillé sur des exemples de quelques lignes. Cela dit, rien ne nous oblige à nous cantonner à de petits extraits. De fait, maintenant, que nous avons fait un premier tour des structures de données en OCaml, nous disposons de toutes les connaissances nécessaires pour définir le noyau d'un langage de programmation, sous la forme d'un interpréteur à grands pas. C'est ce que nous allons faire tout de suite. Dans la suite de l'ouvrage, nous allons progressivement compléter cet interpréteur pour en faire une implantation complète d'un langage de programmation minimal.

Avant toute autre chose, commençons par décider à quoi ressemblera notre langage. Ce langage sera un petit sous-ensemble de JavaScript, doté de

• variables dynamiquement typées
• une boucle for et une boucle while
• fonctions d'ordre supérieur (donc avec la possibilité de renvoyer une fonction depuis une fonction ou de prendre une fonction comme argument d'une fonction).

Un code source pourra ressembler à :

print ("Bonjour, le monde !");
var x = 0;
var add = function(x, y)
{
  return x + y
};
x = 7;
print(add(x, 5));

Syntaxe abstraite

Une fois que nous avons à peu près décidé des fonctionnalités du langage, il convient de choisir sa syntaxe abstraite, c'est-à-dire de décider à quoi ressemble un programme, une fois qu'on a supprimé tous les aspects purement lexicaux tels que les commentaires, les espaces, le choix du caractère de séparation, etc., pour se plonger dans le monde des mathématiques ou des structures de données. Ici,

• un programme est une suite d'instructions
• une instruction est
  • soit un bloc d'instructions, qui est à son tour une suite d'instructions
  • soit une définition de variable
  • soit une expression
  • soit une affectation
  • soit return
  • soit un test avec une condition (qui est une expression), une instruction à exécuter si la condition est vraie et une instruction à exécuter si la condition est fausse
• une définition de variable est la donnée de
  • un nom de variable
  • et en option une valeur donnée à la variable, c'est-à-dire une expression
• une expression est
  • soit une constante
  • soit une variable, caractérisée uniquement par son nom
  • soit un appel de fonction (nous considérerons que les opérations arithmétiques sont des fonctions comme les autres)
• une constante est
  • soit un nombre entier
  • soit un texte
  • soit une fonction
  • soit la valeur spéciale "pas de valeur"
• la valeur d'une fonction est la donnée de
  • une liste d'arguments, c'est-à-dire une liste de noms
  • et le corps de la fonction, c'est-à-dire une liste d'instructions
  • et la valeur des variables locales utilisées par la fonction (la clôture proprement dite), c'est-à-dire une liste de noms de variables et de constantes
• un appel de fonction est la donnée de
  • une fonction appelée, c'est-à-dire une expression
  • et des arguments, c'est-à-dire une liste d'expressions
• une affectation est la donnée de
  • un nom de variable
  • et une valeur donnée à la variable, c'est-à-dire ici aussi une expression
• un return est la donnée d'une expression
• un nombre est un entier OCaml (pour le moment -- nous déciderons peut-être plus tard de remplacer les entiers par des nombres dont la taille est limitée uniquement par la quantité de mémoire de l'ordinateur)
• un texte est une chaîne de caractères OCaml (pour le moment -- ici aussi, nous déciderons peut-être plus tard de remplacer ceci par une autre manière de représenter le texte)
• un nom est une chaîne de caractères OCaml (de nouveau, ceci pourra changer)

Reprenons tout ceci point par point et construisons les types dont nous aurons besoin :

• un programme est une suite d'instructions

Ceci se traduit immédiatement par

type programme = instruction list

à charge pour nous de définir le type instruction

• une instruction est
  • soit un bloc d'instructions, qui est à son tour une suite d'instructions
  • soit une définition de variable
  • soit une expression
  • soit une affectation
  • soit return

Cette succession de "soit" se traduit immédiatement en un type somme tel que

and instruction =
| Bloc        of instruction list
| Definition  of definition
| Expression  of expression
| Affectation of affectation
| Return      of return 
| Si          of expression * instruction * instruction

Pour que ce type ait un sens, il nous reste à définir instruction, definition, expression, affectation et return.

• une définition de variable est la donnée de
  • un nom de variable
  • et en option une valeur donnée à la variable, c'est-à-dire une expression

Ici, il s'agit d'un "et", donc un type produit. Pour plus de clarté, nous allons employer un enregistrement.

and definition =
{
  definition_nom : nom;
  definition_val : expression option
}

Nous avons ici opté pour un type nom plutôt que d'employer directement string, de manière à pouvoir remettre à plus tard la décision sur la manière dont est représenté un nom. Ainsi, si nous souhaitons uniquement manipuler des langages européens, string est parfaitement approprié mais si nous souhaitons pouvoir programmer dans n'importe quelle langue, nous utiliserons plutôt un type de ficelles de caractères Unicode plutôt que le type par défaut des chaînes européennes.

Nous avons aussi opté pour une option, introduit précédemment, pour les informations optionnelles.

Enfin, nous avons choisi des noms relativement complexes pour les champs pour éviter toute collision entre les divers enregistrements que nous allons manipuler.

• une expression est
  • soit une constante
  • soit une variable, caractérisée uniquement par son nom
  • soit la valeur d'une fonction
  • soit un appel de fonction (nous considérerons que les opérations arithmétiques sont des fonctions comme les autres)
  • soit un test avec une condition (qui est une expression), une instruction à exécuter si la condition est vraie et une instruction à exécuter si la condition est fausse

De nouveau, cette succession de "soit" se traduit naturellement en un type somme :

and expression =
| Constante of constante
| Variable  of nom
| Appel     of appel

• une constante est
  • soit un nombre entier
  • soit un texte
  • soit une fonction
  • soit la valeur spéciale "pas de valeur"

type constante =
| Nombre    of nombre
| Texte     of texte 
| Fonction  of fonction
| Pas_de_valeur

• la valeur d'une fonction est la donnée de
  • une liste d'arguments, c'est-à-dire une liste de noms
  • et le corps de la fonction, c'est-à-dire une liste d'instructions
  • et la valeur des variables locales utilisées par la fonction (la clôture proprement dite), c'est-à-dire une liste de noms de variables et de constantes

type fonction =
{
 fonction_arguments : nom list;
 fonction_corps     : instruction list;
 fonction_cloture   : ( nom * constante ) list;
};;

• un appel de fonction est la donnée de
  • une fonction appelée, c'est-à-dire une expression
  • et des arguments, c'est-à-dire une liste d'expressions

type appel =
{
 appel_fonction  : expression;
 appel_arguments : expression list
};;

• une affectation est la donnée de
  • un nom de variable
  • et une valeur donnée à la variable, c'est-à-dire ici aussi une expression

type affectation =
{
 affectation_nom : nom;
 affectation_val : expression
};;

• un return est la donnée d'une expression

type return = expression;;

• un nombre est un entier OCaml (pour le moment -- nous déciderons peut-être plus tard de remplacer les entiers par des nombres dont la taille est limitée uniquement par la quantité de mémoire de l'ordinateur)

type nombre = int;;

• un texte est une chaîne de caractères OCaml (pour le moment -- ici aussi, nous déciderons peut-être plus tard de remplacer ceci par une autre manière de représenter le texte)

type texte = string;;

• un nom est une chaîne de caractères OCaml (de nouveau, ceci pourra changer)

type nom = string;;

En fait, ceci est un peu trop permissif : en général, on considère que seules certaines chaînes de caractères peuvent être des noms de variables. Par exemple, "0", " ", "(" ou "f x" ne sont généralement pas admis comme noms de variables. Pour le moment, nous allons nous contenter de supposer que le type nom ne contient que des noms corrects. Au prochain chapitre, nous allons introduire le mécanisme nécessaire pour empêcher les chaînes mal formées d'être employées comme noms.

Une fois tout ceci rassemblé et mis dans un ordre compréhensible par OCaml, nous obtenons :

type programme = instruction list

and instruction =
| Bloc        of instruction list
| Definition  of definition
| Expression  of expression
| Affectation of affectation
| Return      of return 
| Si          of expression * instruction * instruction

and definition =
{
  definition_nom : nom;
  definition_val : expression option
}

and expression =
| Constante of constante
| Variable  of nom
| Appel     of appel 

and constante =
| Nombre    of nombre
| Texte     of texte 
| Fonction  of fonction
| Pas_de_valeur

and fonction =
{
 fonction_arguments : nom list;
 fonction_corps     : instruction list;
 fonction_cloture   : ( nom * constante ) list;
}

and appel =
{
 appel_fonction  : expression;
 appel_arguments : expression list
}

and affectation =
{
 affectation_nom  : nom;
 affectation_val  : expression
}

and return = expression
and nombre = int
and texte = string
and nom = string;;

Comment créer et afficher un arbre de syntaxe abstraite ?

Nous disposons maintenant de la possibilité de manipuler un programme pour notre mini-JavaScript. Ainsi, l'extrait plus haut se notera

let programme_de_test =
[
 Expression (Appel {appel_fonction  = Variable "print"; appel_arguments = [
    Constante (Texte "Bonjour, le monde !")
 ]});
 Definition {definition_nom = "x";   definition_val = Some (Constante (Nombre 0))};
 Definition {definition_nom = "add"; definition_val =
   Some (Constante (Fonction {fonction_arguments = ["x"; "y"];
    fonction_corps     = [Return (Appel {
      appel_fonction = Variable "+";
      appel_arguments= [
        Variable "x";
        Variable "y"
      ]})];
    fonction_cloture   = []
   }))
 };
 Affectation {affectation_nom = "x"; affectation_val = Constante (Nombre 7)};
 Expression (Appel {appel_fonction  = Variable "print"; appel_arguments = [
    Appel {appel_fonction = Variable "add"; appel_arguments = [
      Variable "x";
      Constante (Nombre 0)
    ]}
 ]})
];;

Ceci est assez peu agréable aussi bien à écrire qu'à relire. Pour le moment, nous n'avons pas vu les concepts nécessaires pour permettre à l'utilisateur de notre langage d'écrire un programme directement en mini-JavaScript. Par contre, nous pouvons définir une fonction qui affichera un programme plus esthétique.

Pour ce faire, nous allons définir autant de fonctions qu'il y a de types dans notre arbre de syntaxe abstraite, fonctions qui renverront une chaîne de caractères en mini-JavaScript.

Note En OCaml, la concaténation de chaînes de caractères est une opération lente. En temps normal, nous utiliserions une implantation différente qui éviterait toute concaténation. Nous verrons cette implantation dans le chapitre consacré aux entrées/sorties. Cette implantation nous permettra aussi d'automatiser une partie des traitements que nous sommes sur le point de programmer manuellement. Pour le moment, nous allons donc nous contenter de la version relativement verbeuse et peu efficace, qui nous suffira largement pour des programmes courts.

Pour ce faire, commençons par définir une fonction qui convertit une liste d'instructions en une chaîne de caractères. Cette fonction nous servira plusieurs fois :

let rec string_of_instruction_list l = match l with
 | []   -> ""
 | h::t -> (string_of_instruction h)^";\n"^(string_of_instruction_list t)

Rappelons que le symbole ^ sert à concaténer deux chaînes de caractères. La chaîne de caractères ";\n" est un peu inhabituelle, puisqu'elle fait intervenir le symbole spécial \n, qui représente le retour à la ligne. À partir d'une liste d'instructions, cette cette fonction produit donc une chaîne de caractères, dans laquelle chaque instruction s'achève par un point-virgule et un retour à la ligne.

Bien entendu, cette fonction n'a aucun sens sans la fonction string_of_instruction_list, définie comme suit :

and string_of_instruction = function
 | Bloc b        -> "{\n" ^ string_of_instruction_list b ^ "}\n"
 | Definition d  -> string_of_definition d
 | Expression e  -> string_of_expression e
 | Affectation a -> string_of_affectation a
 | Return r      -> string_of_return r
 | Si (x, y, z)-> "if("^(string_of_expression x)^")\n"^(string_of_instruction y)^"\n else\n"^(string_of_instruction z)

cette fonction appelle la fonction string_of_instruction_list pour traiter les blocs et appelle string_of_definition, string_of_expression, string_of_affectation ou string_of_return pour traiter les autres cas -- à charge pour nous d'écrire toutes ces fonctions.

Intéressons-nous aux définitions de variables dans notre mini-JS :

and string_of_definition d = match d.definition_val with
 | None   -> "var "^d.nom
 | Some v -> "var "^d.nom^" = "^(string_of_expression v)

cette fonction se construit par cas. Si la définition ne contient pas de valeur, nous allons juste renvoyer var toto, où toto est le nom de la variable que nous venons de créer. Si une valeur est présente, nous devons renvoyer var toto = blop où blop est l'expression correspondante. Pour déterminer dans quel cas nous sommes, il nous suffit de vérifier si d.definition_val est de la forme None ou de la forme Some v, où v est une expression -- rappelons qu'il s'agit des deux seules formes possibles pour d.definition_val car ce champ est de type expression option.

La prochaine étape est donc de définir string_of_expression, à peu près de la même manière que string_of_instruction:

and string_of_expression = function
| Constante c -> string_of_constante c
| Variable  v -> string_of_nom       v
| Appel     a -> string_of_appel     a

Enchaînons sur string_of_constante, string_of_nombre et string_of_texte qui sont aussi simples:

and string_of_constante = function
| Nombre n      -> string_of_nombre n
| Texte  t      -> string_of_texte t
| Fonction  f   -> string_of_fonction  f
| Pas_de_valeur -> ""
and string_of_nombre n = string_of_int n
and string_of_texte  t = t
and string_of_nom    n = n

Il nous reste encore à gérer la définition de fonctions. Pour ce faire, commençons par spécifier la conversion d'une liste de noms d'arguments en une chaine de caractères. Toute la difficulté est dans la gestion de la virgule, qui doit apparaître entre deux éléments consécutifs :

• pour une liste, vide, le résultat est vide
• pour une liste composée d'exactement un élément, le résultat est cet élément
• pour une liste composée d'au moins deux éléments, le résultat est le premier élément, suivi d'une virgule, suivi du résultat appliqué à la liste privée de son premier élément.

En d'autres termes,

and string_of_nom_list = function
| []      -> ""
| [x]     -> string_of_nom x
| x::y::t -> string_of_nom x ^ ", "^ string_of_nom_list (y::t)

À partir de cette définition, nous pouvons construire string_of_fonction.

and string_of_fonction f =
 "function ("^string_of_nom_list f.fonction_arguments^") {\n"^string_of_instruction_list f.fonction_corps^"}"

Cette version de string_of_function ne prend pas en compte la clôture elle-même. Si nécessaire, nous réécrirons string_of_function plus tard de manière à afficher plus de détails.

De la même manière que nous avons implanté l'affichage d'une liste de noms, nous pouvons construire l'affichage d'une liste d'expressions, dont nous déduisons l'appel de fonction :

and string_of_expression_list = function
| []      -> ""
| [x]     -> string_of_expression x
| x::y::t -> string_of_expression x ^ ", "^ string_of_expression_list (y::t)
and string_of_appel a =
(string_of_expression a.appel_fonction) ^ "(" ^(string_of_expression_list a.appel_arguments)^")"

Il nous reste enfin à construire l'affectation et le renvoi de valeur :

and string_of_affectation a = 
 a.affectation_nom ^ " = " ^ string_of_expression a.affectation_val
and string_of_return r =
 "return "^string_of_expression r

Enfin, comme un programme est une suite d'instructions, nous pouvons construire :

and string_of_programme = string_of_instruction_list;;

Nous pouvons maintenant tester le programme :

# let _ = print_endline (string_of_instruction_list programme_de_test);;
print(Bonjour, le monde !);
var x = 0;
var add = function (x, y) {
return +(x, y);
};
x = 7;
print(add(x, 0));

- : unit = ()

À la lecture de ceci, quelques remarques s'imposent :

1. la première ligne du résultat est incorrecte, puisque "Bonjour, le monde !" devrait être entre guillemets
2. l'affichage de la ligne return est elle aussi incorrecte, puisque le + devrait être entre x et y
3. le résultat pourrait être plus esthétique si return était écarté de quelques caractères de la marge de gauche.

Laissons ces trois problèmes en exercice au lecteur.

Exercices

1. Résolvez le premier problème, de manière à ce que "Bonjour, le monde !" s'affiche correctement. Pour ce faire, vous aurez besoin de retrouver dans le code source quelle fonction est responsable de renvoyer cette chaîne de caractères et d'utiliser la fonction String.quote : string -> string. Cette fonction sert à ajouter des guillemets autour d'une chaîne de caractères, tout en protégeant les guillemets qui peuvent apparaître à l'intérieur de la chaîne, de manière à ce qu'elle s'affiche avec les guillemets par exemple lors d'un appel à print_endline :

# print_endline "Bonjour, le monde !";;
Bonjour, le monde !
- : unit = ()

# String.quote "Bonjour, le monde !";;
- : string = "\"Bonjour, le monde !\""

# print_endline (String.quote "Bonjour, le monde !");;
"Bonjour, le monde !"
- : unit = ()

1. Résolvez le deuxième problème, c'est-à-dire débrouillez-vous pour que les appels à la fonction + s'affichent sous la forme x+y et non pas +(x,y). Vous en profiterez pour faire de même avec les fonctions -, *, /, <, >, <=, >=, =.
2. Écrivez une fonction espaces : int -> string qui, à partir d'un nombre entier [n] positif ou nul, construit une chaîne de [n] caractères espaces. Ainsi, espaces 5 produira " ".
3. À l'aide de la fonction espaces, modifiez les fonctions string_of_... de manière à ajouter des tabulations. Chacune de vos fonctions prendra un argument supplémentaire n, qui représentera le nombre d'espaces à afficher au début de chaque ligne. À chaque fois que vous entrerez dans un bloc ou dans une fonction, vous augmenterez n de 4.

Exécuter un programme

La prochaine étape de notre développement consistera à implanter la sémantique de notre langage de programmation, c'est-à-dire de définir exactement comment s'exécute un programme. S'il existe de nombreuses manières de spécifier cette sémantique, nous allons employer un raccourci, sous la forme d'une compilation vers OCaml. En d'autres termes, à partir d'un programme défini dans notre arbre de syntaxe abstraite, nous allons générer un fichier de texte contenant un code source OCaml, que nous pourrons ensuite demander à OCaml de compiler et d'exécuter.

Tout ceci attendra que nous ayons vu comment lire et écrire des fichiers.

... et plus si affinités

Le système de types de OCaml dispose d'autres fonctionnalités, considérées comme plus avancées. Ces fonctionnalités sont liées à la notion de sous-typage : il s'agit d'une part des classes et des objets, à un sens proche de Java ou plutôt de Python, et d'autre part des variants polymorphes, qui généralisent les types sommes. Nous ne détaillerons ces concepts que dans un chapitre ultérieur.

Un autre aspect des structures de données que nous n'avons pas encore abordé est l'architecture de ces structures : comment concevoir les types et les fonctions de manière à permettre aux structures de données de tirer parti des structures existantes de OCaml, et réciproquement. Nous détaillerons ces pratiques un peu plus tard, lorsque toutes les techniques sous-jacentes auront été introduites.