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 codice_1, les constantes codice_2, codice_3... 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
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 codice_4 s'applique à un nombre de type codice_5 et produit un nombre de type codice_1... 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 :
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 codice_31, identique à la fonction codice_32 mais applicable uniquement à des entiers :
val id_int : int -> int = <fun>
val id_int : int -> int = <fun>
val id_int : int -> int = <fun>
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 codice_31 est une fonction de type codice_34. La deuxième souligne sur le fait que codice_35 est lié à un entier (c'est le rôle de codice_36) et que le résultat de codice_31 est encore un entier (c'est le rôle de codice_38). La troisième souligne de même le fait que codice_35 est lié à un entier et laisse OCaml déterminer que le résultat de la fonction codice_31 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 codice_31 que codice_35) est lié à une valeur, que ce soit à l'aide de codice_43, codice_44, de codice_45 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 codice_46. 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 :
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 codice_35 mais de lier codice_35. 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 :
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é codice_43 pour nommer globalement une valeur, nous pouvons employer codice_50 pour nommer globalement un type. Ainsi,
type fonction_des_entiers_vers_les_entiers = int -> int
lie le nom de type codice_51 à l'expression de type codice_34. Pour toute la suite du programme, nous pourrons employer codice_51 comme synonyme exact de codice_34.
val f : fonction_des_entiers_vers_les_entiers = <fun>
- : int = 5
Avec quelques détours, nous pouvons vérifier que OCaml ne fait aucune distinction entre codice_51 et codice_56 :
val g : int -> int = <fun>
val teste_egalite_des_types : 'a -> 'a -> unit = <fun>
- : unit = ()
Dans ce qui précède, codice_57 est une fonction dont les deux arguments doivent être de même type. Comme cette fonction accepte comme arguments codice_58 et codice_59, nous pouvons en déduire que ces deux valeurs sont de même type codice_56.
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 :
 | Trefle
 | Pique
 | Coeur
 | Carreau ;;
type couleur_de_carte = Trefle | Pique | Coeur | Carreau
Cette définition déclare quatre "constructeurs", codice_61, codice_62, codice_63 et codice_64, qui à eux quatre constituent l'ensemble des éléments de type codice_65:
- : couleur_de_carte = Trefle
- : bool = false
This expression has type bool but is here used with type couleur_de_carte
Pour manipuler une valeur de type codice_65, nous pourrons la comparer à l'aide d'une chaîne de codice_67 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 :
 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>
 | Trefle -> "trefle"
 | Pique -> "pique"
 | Coeur -> "coeur"
 | Carreau-> "carreau" ;;
val string_of_couleur_de_carte : couleur_de_carte -> string = <fun>
 | 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 codice_68 emploie le mécanisme de contrôle codice_67 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 codice_70 de C ou Java, et s'énonce "la valeur de codice_71 dépend de la structure de codice_72: si codice_72 est le constructeur codice_61, cette valeur est codice_75, si codice_72 est le constructeur codice_62, cette valeur est codice_78, si codice_72 est le constructeur codice_63, cette valeur est codice_81, si codice_72 est le constructeur codice_64, cette valeur est codice_84." La troisième syntaxe, plus mathématique, est une définition de fonction par cas, qui pourrait s'énoncer "codice_85 est la fonction qui à codice_61 associe codice_75, à codice_62 associe codice_78, à codice_63 associe codice_81 et à codice_64 associe codice_84."
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 codice_67. 
Pourquoi plus sûr ? Parce que, comme nous pouvons le constater, OCaml est capable de vérifier que nous n'avons oublié aucun cas :
 | 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 codice_64. 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 codice_65 codice_64. 
Après une telle définition, nous pouvons manipuler codice_98, à nos risques et périls :
- : string = "trefle"
Exception: Match_failure ("", 30, -72).
Appliquer codice_98 au constructeur codice_61 a produit le résultat escompté alors que l'appliquer à codice_64 a provoqué une erreur codice_102 (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 codice_102 est le plus proche équivalent OCaml au codice_104 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 codice_3, codice_106, codice_107 ... sont eux aussi autant de constructeurs du type codice_1, qui aurait pu être défini sous la forme
Une conséquence de cette conception des nombres est que nous pouvons procéder à des filtrages par motifs sur les entiers :
 | 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 codice_109, 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 codice_110, à 2 associe codice_111..., à 0 associe codice_112 et "à toute autre valeur n" associe le résultat de codice_113." 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 codice_109, 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 = "Cinq"
- : 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 codice_11 qui aurait pu être défini sous la forme
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 codice_13 et codice_14), les entiers, les flottants...
Ainsi, si nous tentons de définir un type à l'aide de constructeurs qui commencent par une minuscule, nous obtiendrons
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 codice_61, codice_62, codice_63 et codice_64 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 :
 | 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 codice_122 est constitué de l'ensemble des valeurs codice_123 où codice_124 est un entier, de l'ensemble des valeurs codice_125 où codice_72 est une codice_65, de l'ensemble des valeurs codice_128 où codice_72 est une codice_65, de l'ensemble des valeurs codice_131 où codice_72 est une codice_65, de l'ensemble codice_134 où codice_72 est une codice_65, de l'ensemble codice_137 où codice_72 est une codice_65 et enfin de l'ensemble codice_140 où codice_124 est un entier et codice_72 est une codice_65." 
Après cette définition, nous pouvons employer des valeurs de type codice_122:
- : carte_de_tarot = Atout 5
- : carte_de_tarot = Cavalier Trefle
- : carte_de_tarot = Nombre 5 Trefle
Vocabulaire Les "constructeurs" de codice_122 sont codice_146, codice_147, codice_148, codice_149, codice_150, codice_151 et codice_152.
Notons que cette représentation laisse un élément de fragilité, puisque nous pouvons très bien écrire :
- : carte_de_tarot = Atout 23
- : 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 codice_153 ne peut être associés qu'à des entiers compris entre 1 et 9 et codice_154 à 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 codice_122s à l'aide du filtrage par motifs. Ainsi, pour afficher le nom complet d'une carte, nous pourrons définir la fonction 
 | 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>
 | 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 codice_156 sont strictement équivalentes. Dans ce qui précède, nous avons utilisé la fonction codice_157 définie plus haut, la fonction codice_158 vue plus haut et l'opérateur codice_159 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 codice_160 : si codice_160 s'écrit codice_123, la fonction se comporte comme codice_163 sinon, si codice_164 s'écrit codice_125, la fonction se comporte comme codice_166 ... La deuxième syntaxe, plus mathématique, se prononcerait "s'il existe un entier codice_124 tel que l'argument s'écrive codice_123, le résultat est donné par ..." ou encore, avec un point de vue ensembliste, "codice_156 est la fonction qui à tout élément codice_124 de l'ensemble codice_154 associe codice_163, à tout élément codice_72 de l'ensemble codice_174 associe..." ou encore, cette fois avec un point de vue plus informatique, "codice_156 est la fonction qui à tout entier codice_124 étiqueté codice_174 associe ..."
De nouveau, lors du filtrage par motifs, nous avons "lié" des variables (ici codice_124 ou/et codice_72 selon les cas) à des valeurs contenues dans codice_160. 
Une fois cette fonction définie, nous pouvons écrire
- : string = "5 d'atout"
- : string = "Valet de pique"
- : 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 :
 | 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 codice_137 était un motif, qui acceptait n'importe quel codice_182 et liait codice_72 à sa couleur, codice_184 est un motif plus précis, qui accepte uniquement la valeur codice_184. Le motif codice_186, quant à lui, est équivalent au motif codice_187 -- le symbole codice_188, 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 codice_188 pour signifier que nous ne somme pas intéressés par un valeur correspondante. C'est ainsi, le dernier motif codice_188 accepte toutes les valeurs. Comme dans l'exemple codice_191, nous tirons parti du fait que les motifs sont essayés dans l'ordre dans lequel ils sont écrits, si bien que codice_188 tient ici un rôle similaire à codice_193 (dans le cadre d'un codice_67) ou codice_195 (dans le cadre d'un codice_196.
Nous verrons plus loin comment fusionner plusieurs motifs et réduire la taille de la fonction codice_197
Exercices.
 | 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>
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 codice_207 s'écrit
match v with
Cette construction se lit "si codice_207 a la structure codice_209, évaluer l'expression codice_210, dans le cas contraire, si codice_207 a la structure codice_212, évaluer l'expression codice_213 ... dans le cas contraire, si codice_207 a la structure codice_215, évaluer l'expression codice_216." Si codice_207 n'a aucune de ces structures, il s'agit d'une erreur fatale d'exécution.
Notons que la valeur codice_207 utilisée ici peut être remplacée par n'importe quelle expression codice_219, auquel cas c'est le résultat de l'évaluation de codice_219 qui sera utilisé à la place de codice_207.
Vocabulaire codice_209, codice_212 ... codice_215 sont des "motifs".
Nous avons déjà vu de nombreux exemples de motifs. Ainsi, dans
 | Trefle -> "trefle"
 | Pique -> "pique"
 | Coeur -> "coeur"
 | Carreau-> "carreau" ;;
les constructeurs codice_61, codice_62, codice_63, codice_64 sont employés en tant que motifs. De même, dans 
 | 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 codice_3, codice_106, codice_107, codice_232, codice_233, codice_234, codice_235, codice_236, codice_237 et codice_2 et le nom de variable codice_109 sont utilisés en tant que motifs. De manière plus compliquée, dans
 | 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 codice_123 est composé de la variable codice_124 placée dans le constructeur à un argument codice_154, le motif codice_125 est composé de la variable codice_72 placée dans le constructeur à un argument codice_174... et le motif codice_246 est composé de la variable codice_72 et de la variable codice_124 placés dans le constructeur à deux arguments codice_153.
Voyons tout de suite la définition exacte d'un motif :
Ainsi, dans la définition de codice_156 :
codice_166
Insistons sur le fait qu'un motif peut contenir un motif. Ainsi, on aurait pu ajouter un premier cas plus spécifique
 | Atout 0 -> "Excuse"
 | Atout i -> string_of_int i ^ " d'atout"
auquel cas, en plus de vérifier si codice_160 peut s'écrire codice_314 pour un certain codice_35, OCaml aurait vérifié si la valeur de codice_35 était de plus acceptée par codice_2.
Function.
Dans certains des exemples que nous avons rencontrés, nous avons employé codice_318 au lieu de codice_319. 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 codice_35 ne soit pas utilisé dans codice_210...codice_216, 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
Warning Y: unused variable x.
- : int = 5
Comme le signale l'avertissement, la première définition de codice_35 est totalement ignorée. L'utilisation de codice_35 en tant que motif accepte n'importe quelle valeur -- ici codice_233 -- et lie cette valeur à codice_35.
C'est pour cette raison qu'une même variable ne peut pas apparaître deux fois dans un motif sans codice_327 :
Variable x is bound several times in this matching
En effet, pour que cette expression ait un sens, codice_35 devrait valoir à la fois la valeur codice_3 et la valeur codice_106.
À l'inverse, dans un motif de la forme codice_269, les variables qui apparaissent dans codice_209 doivent être exactement les mêmes que celles qui apparaissent dans codice_212.
 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 codice_122 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 codice_156 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 codice_156, 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 codice_337, codice_338..., nous pouvons définir de nouveaux types "paramétriques" avec ces mêmes variables. Ainsi, une variante sur le type codice_198 est le type codice_340, défini dans la bibliothèque standard de OCaml comme
 | Some of 'a
 | None ;;
type 'a option = Some of 'a | None
Nous pouvons donc utiliser :
- : option 'a = None
- : option int = Some 5
- : option string = Some "blue"
Nous pouvons de même réécrire codice_341 
 | 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 codice_337.
La fonction codice_343 se réécrit alors par exemple :
 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 à 
 | 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 codice_344, où codice_35 est une valeur renvoyée lorsque la fonction s'exécute correctement ou codice_346, où code codice_347 est une valeur renvoyée lorsque la fonction rencontre un problème :
 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
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 codice_348 est inutile car (presque) tous les types peuvent prendre la valeur spéciale codice_349. 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 codice_2 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 :
Par comparaison, l'approche OCaml :
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 :
En OCaml, nous traduirons ceci par
 | 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
 | 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 codice_363 et codice_364. Pour ajouter un élément en tête d'une liste, nous pourrons écrire par exemple :
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 codice_365, nous pouvons écrire de la manière suivante la liste qui contient 1, 2, 3, 4 et 5 :
val une_liste : int 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))))
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 :
 | ListeVide -> true
 | _ -> false ;;
val est_vide : 'a liste -> bool = <fun>
val est_vide : 'a liste -> bool = <fun>
val est_vide : '_a liste -> bool = <fun>
La première formulation utilise le filtrage par motifs. La deuxième compare codice_366 avec codice_363 pour produire le même résultat. Pour le moment, laissons de côté la troisième formulation et son surprenant codice_368 -- 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 codice_366 à votre fonction et de revenir à la deuxième formulation.
Dans tous les cas, nous aurons
- : 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 :
Soit, en OCaml, récursivement et à l'aide du filtrage par motifs
 | ListeVide -> 0
 | ListeNonVide (_, queue) -> longueur queue + 1 ;;
val longueur : 'a liste -> int = <fun>
 | 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 codice_370 : 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 codice_2 (sous la forme d'un argument codice_372) et l'opération codice_373 (sous la forme d'un argument codice_58), nous obtenons, selon l'ordre des opérations :
 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 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 codice_375,
en passant chaque élément par codice_365 et en initialisant le résultat à codice_363 :
- : int liste =
 ListeNonVide ( 1,
 ListeNonVide ( 2,
 ListeNonVide ( 3, (ListeNonVide (4, ListeNonVide (5, ListeVide))))
- : 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 codice_337, noté codice_379 est un type somme doté des constructeurs
Vocabulaire Le constructeur codice_380 est appelé "nil". Le constructeur codice_381 est appelé "cons".
Ainsi, nous aurons
- : 'a list = []
- : int list = [1; 2; 3; 4; 5]
Comme le montre la réponse d'OCaml, il existe en fait une notation plus simple :
- : 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 codice_387, codice_388, codice_389 comme
 | [] -> true
 | _ -> false ;;
val est_vide : 'a list -> bool = <fun>
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>
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 codice_388 est déjà définie dans la bibliothèque standard sous le nom codice_391 et la fonction queue sous le nom codice_392. 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
 | [] -> 0
 | _ :: t -> longueur t + 1 ;;
Dans l'extrait qui précède, le motif codice_380 désigne la liste vide. De même, le motif codice_394 consiste en le constructeur cons appliqué aux deux motifs codice_188 (en position de la tête de liste) et codice_384 (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 codice_384.
De même, pour écrire une fonction qui filtrera une liste et ne gardera qu'un élément sur deux, nous pourrons écrire
 | _ :: [] -> []
 | h :: _ :: t -> h :: (un_sur_deux t) ;;
val un_sur_deux : 'a list -> 'a list = <fun>
Cette définition s'énonce "la fonction codice_398 se définit récursivement par
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
 | [ _ ] -> [] (* 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>
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 :
 | 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 
- : formule = Booleen true
Partant de là, nous pouvons définir des transformations sur les arbres :
val formule_ou_exclusif : formule -> formule -> formule = <fun>
- : 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 :
 | 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 codice_406. Le résultat est un couple, sur lequel nous pouvons de nouveau procéder à du filtrage par motifs. Nous avons aussi utilisé la fonction codice_407, 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 codice_408 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 :
 | 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.
complétez la fonction codice_409 pour procéder à toutes ces simplifications.
les erreurs, vous utiliserez le type codice_412.
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 codice_418, codice_419... 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 :
- : (int * int) = (1, 2)
La réponse d'OCaml s'énonce "le résultat de la dernière évaluation est de type codice_420, c'est-à-dire un couple d'entiers, et vaut codice_421". 
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 :
- : (bool * int * string) = (true, 2, "autre chose")
- : (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 :
val creer_couple : 'a -> 'b -> ('a * 'b) = <fun>
- : (int * int) = (1, 2)
Vocabulaire On dit que codice_422 est le "constructeur" du type codice_423. De même, 
codice_424 est le constructeur du type codice_425, codice_426 celui
de codice_427... 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 codice_337 et codice_338.
Les deux fonctions duales de codice_430, prédéfinies dans OCaml (ou triviales à redéfinir, comme nous le verrons plus loin), sont codice_431 et codice_432, les "projections" :
- : ('a * 'b) -> 'a = <fun>
- : ('a * 'b) -> 'b = <fun>
Comme leur type l'indique, codice_431 et codice_432 prennent chacune en argument un couple et renvoient respectivement son premier élément ou son second élément :
- : int = 1
- : int = 2
Insistons sur le fait que codice_431 et codice_432 ne fonctionnent que sur des couples -- comme en mathématiques, un triplet n'est pas un couple, si bien que :
This expression has type (int * int * int) but is here used with type
 ('a * 'b)
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 codice_437 est un constructeur, nous pourrons écrire, comme pour les types somme :
 ( a, b, c ) -> a ;;
val fst_of_3 : ('a * 'b * 'c) -> 'a = <fun>
ou, de manière plus concise,
val fst_of_3 : ('a * 'b * 'c) -> 'a = <fun>
ou encore, en combinant le filtrage par motifs avec la définition de fonction,
val fst_of_3 : ('a * 'b * 'c) -> 'a = <fun>
val fst_of_3 : ('a * 'b * 'c) -> 'a = <fun>
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 :
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 codice_431 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 codice_439 pour tout codice_440 telle que, pour chaque codice_440, codice_439 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 :
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 codice_443, codice_35 est toujours l'argument et codice_347 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é codice_446, et qui va contenir deux nombres flottants, que nous choisissons de nommer codice_447 et codice_448 :
Vocabulaire Dans ce qui précède, codice_447 et codice_448 sont les "champs" de l'enregistrement codice_446.
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ù codice_446 est défini, nous pouvons créer de nouvelles valeurs de ce type :
Ce dernier extrait s'énonce "Appelons codice_124 la valeur dont codice_448 vaut 1.0 et codice_447 vaut 0.0." Notons que l'ordre dans lequel sont donnés codice_448 et codice_447 est sans importance.
Toute tentative de créer une valeur de type codice_446 contenant trop ou trop peu de définitions de champs provoquera une erreur lors de l'analyse de types :
Some record field labels are undefined: re
Unbound record field label stuff
The record field label re is defined several times
Vocabulaire codice_459 est le "constructeur" de type codice_446. Comme l'ordre des champs est sans importance, on pourra considérer, au choix, que le constructeur de ce type est codice_461.
Pour consulter la valeur d'un champ, on pourra employer la notation codice_462 (le point), similaire à celle des langages orientés-objets :
val partie_reelle : cartesien -> float = <fun>
- : float = 0
Une autre possibilité consiste à utiliser le filtrage par motifs :
 { re = x; im = _ } -> x ;;
val partie_reelle : cartesien -> float = <fun>
 { re = x; im = _ } -> x ;;
val partie_reelle : cartesien -> float = <fun>
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
val partie_reelle : cartesien -> float = <fun>
val partie_reelle : cartesien -> float = <fun>
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
val y : float = 0;;
Muni de ces outils, nous pouvons définir les opérations habituelles sur les nombres complexes :
val add_cartesiens : cartesien -> cartesien -> cartesien = <fun>
val mult_cartesiens : cartesien -> cartesien -> cartesien = <fun>
etc.
On définirait de même une représentation polaire des nombres sous la forme :
Note Nous n'avons utilisé ni le nom codice_463 ni le terme codice_464 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 codice_465 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 :
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 codice_466 et codice_467 :
val cartesien_of_polaire : polaire -> cartesien = <fun>
 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 codice_447 vaut codice_469, en raison de la manière dont codice_470 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 :
val ( +++. ) : cartesien -> cartesien -> cartesien = <fun>
val ( ***. ) : cartesien -> cartesien -> cartesien = <fun>
This expression has type polaire but is here used with type cartesien
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. 
val x : int = 10
val y : int = 15
 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 à codice_471. 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
- : ('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 :
value unmake_t : t -> int = <fun>
- : int = 5
This expression has type t but is here used with type t
Ici, le problème est que l'ancien type codice_384 a été remplacé par un nouveau type codice_384. 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 b = B | C
- : b = B
- : a = A
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
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,
Reprenons tout ceci point par point et construisons les types dont nous aurons besoin :
Ceci se traduit immédiatement par
type programme = instruction list
à charge pour nous de définir le type codice_478
Cette succession de "soit" se traduit immédiatement en un type somme tel que
and instruction =
Pour que ce type ait un sens, il nous reste à définir codice_478, codice_481, codice_482, codice_483 et codice_476.
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 codice_485 plutôt que d'employer directement codice_19, 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, codice_19 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 codice_340, 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.
De nouveau, cette succession de "soit" se traduit naturellement en un type somme :
and expression =
type constante =
type fonction =
 fonction_arguments : nom list;
 fonction_corps : instruction list;
 fonction_cloture : ( nom * constante ) list;
type appel =
 appel_fonction : expression;
 appel_arguments : expression list
type affectation =
 affectation_nom : nom;
 affectation_val : expression
type return = expression;;
type nombre = int;;
type texte = string;;
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, codice_490, codice_491, codice_492 ou codice_493 ne sont généralement pas admis comme noms de variables. Pour le moment, nous allons nous contenter de supposer que le type codice_485 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 =
and definition =
 definition_nom : nom;
 definition_val : expression option
and expression =
and constante =
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 codice_159 sert à concaténer deux chaînes de caractères. La chaîne de caractères codice_496 est un peu inhabituelle, puisqu'elle fait intervenir le symbole spécial codice_497, 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 codice_498, 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 codice_498 pour traiter les blocs et appelle codice_500,
codice_501, codice_502 ou codice_503 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 codice_504, où codice_505 est le nom de la variable que nous venons de créer. Si une valeur est présente, nous devons renvoyer codice_506 où codice_507 est l'expression correspondante. Pour déterminer dans quel cas nous sommes, il nous suffit de vérifier si codice_508 est de la forme codice_359 ou de la forme codice_510, où codice_207 est une expression -- rappelons qu'il s'agit des deux seules formes possibles pour codice_508 car ce champ est de type codice_513.
La prochaine étape est donc de définir codice_501, à peu près de la même manière que codice_515:
and string_of_expression = function
Enchaînons sur codice_516, codice_517 et codice_518 qui sont aussi simples:
and string_of_constante = function
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 :
En d'autres termes,
and string_of_nom_list = function
À partir de cette définition, nous pouvons construire codice_519. 
and string_of_fonction f =
 "function ("^string_of_nom_list f.fonction_arguments^") {\n"^string_of_instruction_list f.fonction_corps^"}"
Cette version de codice_520 ne prend pas en compte la clôture elle-même. Si nécessaire,
nous réécrirons codice_520 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
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 :
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 :
Laissons ces trois problèmes en exercice au lecteur.
Exercices.
Bonjour, le monde !
- : unit = ()
- : string = "\"Bonjour, le monde !\""
"Bonjour, le monde !"
- : unit = ()
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.