OCaml

OCaml
Date de première version	1987 (CAML), 1996 (OCaml)
Paradigme	Multiparadigme:impérative,fonctionnelle,orientée objet
Développeur	Inria
Dernière version	5.2.0 (13mai2024)
Typage	Fort,statique
Dialectes	JoCaml, Fresh OCaml, GCaml, MetaOCaml, OCamlDuce, OcamlP3L
Influencé par	ML
A influencé	F#,Rust,OPA,Scala
Écrit en	OCaml etC
Système d'exploitation	Multiplate-forme
Licence	LGPL2.1
Site web	ocaml.org
Extension de fichier	ml et mli

OCaml,anciennement connu sous le nom d'Objective Caml,est l'implémentationla plus avancée dulangage de programmationCaml,créé parXavier Leroy,Jérôme Vouillon,Damien Doligez(en),Didier Rémyet leurs collaborateurs en1996.Ce langage, de la famille des langagesML,est un projetopen sourcedirigé et maintenu essentiellement par l'Inria.

OCaml est le successeur deCaml Light,auquel il a ajouté entre autres une couche deprogrammation objet.L'acronyme CAML provient deCategorical Abstract Machine Language,un modèle demachine abstraitequi n'est cependant plus utilisé dans les versions récentes de OCaml.

Portableet performant, OCaml est utilisé dans des projets aussi divers que le logiciel desynchronisation de fichiersUnison,l'assistant de preuves formellesCoqou la version Web deFacebook Messenger.Il dispose d'un écosystème de développement varié, avec notamment le framework Web et mobileOcsigenet l'unikernelMirageOS.Les facilités de traitement symbolique du langage permettent le développement d'outils de vérification statique, comme le projet SLAMpour despilotesWindowsécrits parMicrosoft,ouASTRÉEpour certainssystèmes embarquésdesAirbus A380.

Principes

Camlest unlangage fonctionnelaugmenté de fonctionnalités permettant laprogrammation impérative.OCaml étend les possibilités du langage en permettant laprogrammation orientée objetet laprogrammation modulaire.Pour toutes ces raisons, OCaml entre dans la catégorie deslangages multi-paradigme.

Il intègre ces différents concepts dans un système de types hérité de ML, caractérisé par untypage statique,fortetinféré.

Le système de types permet une manipulation aisée destructures de donnéescomplexes: on peut aisément représenter destypes algébriques,c'est-à-dire des types hiérarchisés et potentiellementrécursifs(listes,arbres…), et les manipuler aisément à l'aide dufiltrage par motif.Cela fait de OCaml un langage de choix dans les domaines demandant la manipulation de structures de données complexes, par exemple lescompilateurs.

Letypage fort,ainsi que l'absence de manipulation explicite de lamémoire(présence d'unramasse-miettes) font de OCaml un langage très sûr. Il est aussi réputé pour ses performances, grâce à la présence d'un compilateur decode natif.

Histoire

L'équipe de développement d'OCaml recevant un prix à la conférence POPL 2024

Le langage Caml est né de la rencontre du langage de programmation ML, auquel s'est intéressée l'équipeFormelde l'Inriadepuis le début desannées 1980,et de lamachine abstraitecatégorique CAM deGuy Cousineau,fondée sur les travaux de Pierre-Louis Curienen1984.La première implémentation, écrite parAscander Suarez(à l'époque doctorant à l'université Paris Diderot) puis maintenue par Pierre Weis et Michel Mauny, a été publiée en1987.Le langage s'est peu à peu différencié de son père ML car l'équipe de l'Inria voulait adapter un langage à ses propres besoins, et continuer à le faire évoluer, ce qui entrait en conflit avec la « stabilité » de ML imposée par les efforts de standardisation deStandard ML.

Les limitations de la CAM ont conduit à la création d'une nouvelle implémentation, mise au point par Xavier Leroy dès1990,sous le nom deCaml Light.Cette implémentation — dont une version a été utilisée dans l'enseignement supérieurfrançais jusqu’en 2017, bien après la fin de sa maintenance par l'Inria— fonctionne grâce à un interpréteur decode octet(bytecode) codé enC,ce qui lui assure une grandeportabilité.Le système degestion de la mémoire,conçu par Damien Doligez, a aussi fait son apparition dans Caml Light. En1995,Xavier Leroy publie une version de Caml nomméeCaml Special Light,qui introduit uncompilateurde code natif, et un système demodulesinspiré des modules de Standard ML.

OCaml, publié pour la première fois en1996,apporte à Caml un système objet conçu par Didier Rémy et Jérôme Vouillon. Certaines fonctionnalités avancées, comme les variantespolymorphesou les labels (permettant de distinguer les arguments donnés à une fonction par leur nom, plutôt que leur position) ont été introduites en2000par Jacques Garrigue. OCaml s'est relativement stabilisé depuis (malgré l'absence d'une spécification, le document en vigueur étant lemanuel officielmaintenu par l'Inria). De nombreux dialectes de OCaml sont apparus, et continuent d'explorer des aspects spécifiques des langages de programmation (concurrence,parallélisme,évaluation paresseuse,intégration duXML…); voir la sectionLangages dérivés.

Principales caractéristiques

Langage fonctionnel

OCaml possède la plupart des caractéristiques communes des langages fonctionnels, en particulier desfonctions d'ordre supérieuretfermetures(closures), et un bon support de larécursion terminale.

Typage

Letypagestatique d'OCaml détecte au moment de la compilation un grand nombre d'erreurs de programmation qui pourraient poser des problèmes au moment de l'exécution. Toutefois, contrairement à la plupart des autres langages, il n'est pas nécessaire de préciser le type des variables que l'on utilise. En effet, Caml dispose d'un algorithme d'inférence de typesqui lui permet de déterminer le type des variables à partir du contexte dans lequel elles sont employées.

Le système de typage ML supporte lepolymorphismeparamétrique, c'est-à-dire des types dont des parties seront indéterminées au moment de la définition de la valeur. Cette fonctionnalité, automatique, permet d'obtenir unegénéricitécomparable à celle desgenericsdeJavaouC#ou destemplatesdeC++.

Cependant, les extensions du typage ML requises par l'intégration de fonctionnalités avancées, comme laprogrammation orientée objet,complexifient dans certains cas le système de types: l'utilisation de ces fonctionnalités peut alors demander un temps d'apprentissage au programmeur, qui n'est pas forcément familier des systèmes de types sophistiqués.

Filtrage

Lefiltrage par motif(enanglais:pattern matching) est un élément essentiel du langage Caml. Il permet d'alléger le code grâce à une écriture plus souple que des conditions classiques, et l'exhaustivité fait l'objet d'une vérification: le compilateur propose un contre-exemple lorsqu'un filtrage incomplet est décelé. Par exemple, le code suivant est compilé mais il provoque un avertissement:

#typeetat=Actif|Inactif|Inconnu;;
typeetat=Actif|Inactif|Inconnu

#letest_actif=function
#|Actif->true
#|Inactif->false;;
valest_actif:etat->bool=<fun>
WarningP:thispattern-matchingisnotexhaustive.Hereisanexampleofa
valuethatisnotmatched:Inconnu

Ainsi, le programme fonctionne lorsque la fonctionest_actifest appelée avec un état valantActifouInactif,mais s'il vautInconnu,la fonction renvoie l'exceptionMatch_failure.

Modules

Lesmodulespermettent de décomposer le programme en une hiérarchie de structures contenant des types et des valeurs logiquement reliés (par exemple, toutes les fonctions de manipulation delistesvont dans le module List). Les descendants de la famille ML sont les langages ayant actuellement les systèmes de modules les plus perfectionnés, qui permettent, en plus de disposer d'espaces de noms, de mettre en œuvre l'abstraction(valeurs accessibles dont l'implémentation est cachée) et la composabilité (valeurs qui peuvent être construites par-dessus différents modules, du moment qu'ils répondent à une interface donnée).

Ainsi, les trois unités syntaxiques de construction syntaxique sont les structures, les interfaces et les modules.

Les structures contiennent l'implémentation des modules.

Les interfaces décrivent les valeurs qui en sont accessibles. Les valeurs dont l'implémentation n'est pas exposée sont des valeurs abstraites. Les valeurs qui n'apparaissent pas du tout dans l'implémentation du module sont inaccessibles, à l'instar des méthodes privées enprogrammation orientée objet).

Un module peut avoir plusieurs interfaces (du moment qu'elles sont toutes compatibles avec les types de l'implémentation), et plusieurs modules peuvent vérifier une même interface.

Les foncteurs sont des structures paramétrées par d'autres structures; par exemple, lestables de hachage(module Hashtbl) de la bibliothèque standard OCaml sont utilisables comme un foncteur, qui prend en paramètre toute structure implémentant l'interface composée d'un type, d'une fonction d'égalité entre les clés, et d'unefonction de hachage.

Orienté objet

OCaml se distingue particulièrement par son extension du typage ML vers unsystème objetcomparable à ceux utilisés par les langages objets classiques. Cela permet unsous-typage structurel,dans lequel les objets sont de types compatibles si les types de leurs méthodes sont compatibles, indépendamment de leurs arbres d'héritagerespectifs. Cette fonctionnalité, que l'on peut considérer comme l'équivalent duduck typingdes langages dynamiques, permet une intégration naturelle des concepts objets dans un langage globalement fonctionnel.

Ainsi, à la différence des langages orientés objet telsC++ouJavapour lesquels toute classe définit un type, les classes OCaml définissent plutôt des abréviations de types. En effet, pour peu que le type des méthodes soit compatible, deux objets de deux classes différentes peuvent être utilisés indifféremment dans un même contexte. Cette caractéristique de la couche objet de OCaml rompt bon nombre de principes communément admis: il est en effet possible de faire du sous-typage sans héritage, par exemple. Le côté polymorphe rompt le principe inverse. Des exemples de code, bien que rares, exhibant des cas d'héritage sans sous-typage existent également. La force de la couche objet tient à son homogénéité et sa parfaite intégration dans la philosophie et l'esprit même du langage OCaml. Des objets fonctionnels, dont les attributs ne peuvent être modifiés et dont les méthodes, le cas échéant, en retournent une copie avec la mise à jour des attributs, ou encore la définition d'objets immédiats, ou à la volée, sont également possibles.

Distribution

La distribution OCaml contient:

• uninterpréteurinteractif (ocaml);
• uncompilateurbytecode(ocamlc) et l'interpréteur debytecode(ocamlrun);
• un compilateur natif (ocamlopt);
• des générateurs d'analyseurs lexicaux(ocamllex) etsyntaxiques(ocamlyacc);
• unpréprocesseur(camlp4), qui permet des extensions ou modifications de la syntaxe du langage;
• undébogueurpas à pas, avec retour en arrière (ocamldebug);
• des outils deprofiling;
• ungénérateur de documentation(ocamldoc);
• un gestionnaire de compilation automatique (ocamlbuild), depuis OCaml 3.10;
• unebibliothèquestandard variée.

Les outils OCaml sont régulièrement utilisés sousWindows,GNU/LinuxouMacOS,mais existent aussi sur d'autres systèmes comme lesBSD.

Le compilateurbytecodepermet de créer des fichiers qui sont ensuite interprétés par ocamlrun. Lebytecodeétant indépendant de la plate-forme, cela assure une grandeportabilité(ocamlrun pouvanta prioriêtre compilé sur toute plate-forme supportant un compilateur C fonctionnel). Le compilateur natif produit un code assembleur spécifique à la plate-forme, ce qui sacrifie la portabilité de l'exécutable produit pour des performances grandement améliorées. Un compilateur natif est présent pour les plates-formesIA-32,PowerPC,AMD64,Alpha,Sparc,Mips,IA-64,HPPAetStrongARM.

Une interface de compatibilité permet de lier du code OCaml à des primitives enC,et le format des tableaux denombres flottantsest compatible avec C etFortran.OCaml permet aussi l'intégration de code OCaml dans un programme en C, ce qui permet de distribuer des bibliothèques OCaml à des programmeurs en C sans qu'ils aient besoin de connaître ou même d'installer OCaml.

Les outils OCaml sont majoritairement codés en OCaml, à l'exception de quelques bibliothèques et de l'interpréteurbytecode,qui sont codés en C. En particulier, le compilateur natif est entièrement codé en OCaml.

Gestion de la mémoire

OCaml dispose, comme Java, d'une gestion automatisée de la mémoire, grâce à unramasse-miettesincrémental générationnel. Celui-ci est spécialement adapté à un langage fonctionnel(optimisé pour un rythme rapide d'allocation/libération de petits objets) et n'a donc pas d'impact sensible sur les performances des programmes. Il est configurable pour rester efficace dans des situations atypiques d'utilisation de la mémoire.

Performances

OCaml se distingue de la plupart des langages développés dans des milieux académiques par d'excellentes performances^{[source insuffisante]}.En plus des optimisations locales « classiques » effectuées par legénérateur de code natif,les performances profitent avantageusement de la nature fonctionnelle et statiquement et fortement typéedu langage.

Ainsi, les informations de typage sont complètement déterminées à la compilation, et n'ont pas besoin d'être reproduites dans le code natif, ce qui permet entre autres de retirer complètement les tests de typage au moment de l'exécution. D'autre part, certains algorithmes de la bibliothèque standard exploitent les propriétés intéressantes des structures de données fonctionnelles pures: ainsi, l'algorithme d'union d'ensembles est asymptotiquement plus rapide que celui des langages impératifs, car il utilise leur non-mutabilité pour réutiliser une partie des ensembles de départ pour constituer l'ensemble de sortie (c'est la technique depath copyingpour les structures de données persistantes).

Historiquement, les langages fonctionnels ont été considérés comme lents par certains programmeurs, car ils nécessitent naturellement la mise en œuvre de concepts (récupération de la mémoire, application partielle…) qu'on ne savait pas compiler efficacement; les progrès des techniques de compilation ont depuis permis de rattraper l'avantage initial des langages impératifs. OCaml, en optimisant efficacement ces parties du langage et en implémentant unramasse-miettesadapté aux allocations fréquentes des langages fonctionnels, a été un des premiers langages fonctionnels à démontrer l'efficacité retrouvée de la programmation fonctionnelle.

En général, la rapidité d'exécution est légèrement inférieure à celle d'un code équivalent enC.Xavier Leroy parle prudemment de « performances d'au moins 50 % de celles d'un compilateur C raisonnable ».Ces prévisions ont depuis été confirmées par de nombreux benchmarks.En pratique, les programmes restent en général dans cette fourchette (de 1 à 2 fois celle du code C), avec des extrêmes dans les deux directions (parfois plus rapide que le C, parfois fortement ralenti par une interaction malheureuse avec leramasse-miettes.Dans tous les cas, cela reste plus rapide que la plupart des langages récents qui ne sont pas compilés nativement, commePythonouRuby,et comparable aux langages statiques compilés à la volée commeJavaouC#.

Utilisation

Le langage OCaml, issu des milieux de recherche, ne bénéficie pas de la puissance publicitaire de certains langages de programmation actuels. Il reste donc relativement peu connu du grand public informatique (ainsi que la plupart des langages fonctionnels) mais est cependant solidement implanté dans quelques niches dans lesquelles les qualités du langage priment sur son absence de popularité.^{[réf. nécessaire]}

Enseignement

OCaml est le langage utilisé par certainesclasses préparatoiresfrançaises, et imposé en option informatique, où il a succédé à Caml Light,dans l'optique des épreuves d'option informatique des concours d'entrée auxgrandes écoles.Les documents utilisés dans le cadre de cet enseignementmettent en avant les liens entreprogrammation fonctionnelleet mathématiques, et l'aisance avec laquelle les langages de la famille ML manipulent les structures de donnéesrécursives,utiles pour enseigner l'algorithmique.

Il souffre dans le milieu universitaire de la concurrence du langageHaskell,qui lui est préféré dans certains cours de programmation fonctionnelle, parce qu'entre autres choses, il ne reprend aucun concept de laprogrammation impérative.

Recherche

OCaml est un langage assez utilisé dans le milieu de la recherche.Historiquement, les langages de la branche ML ont toujours été étroitement liés au domaine des systèmes de preuves formelles (le ML initial deRobin Milnerest ainsi apparu pour être utilisé dans le système de preuves LCF). OCaml est le langage utilisé par un des logiciels majeurs du domaine, l'assistant de preuvesCoq.

OCaml est présent dans de nombreux autres domaines de la recherche informatique, dont la recherche en langages de programmation et compilateurs (voir la sectionLangages dérivés), ou le logiciel de synchronisation de fichierUnison.

Industrie

Malgré sa communication relativement timide, OCaml a acquis une solide base d'utilisateurs dans des domaines spécifiques de l'industrie. Ainsi, l'industrie aéronautiqueutilise OCaml pour sa sûreté de programmation et son efficacité pour la formulation d'algorithmes complexes. On peut citer dans ce domaine le projetASTRÉE,utilisé entre autres par l'entrepriseAirbus.Le compilateur du langage de programmationtemps-réelsynchroneLustre,utilisé pour les systèmes critiques tels les systèmes d'avionique des Airbus ou de contrôle de certaines centrales nucléaires, est également écrit en OCaml.

OCaml est utilisé pour le développement d'applications Webetmobiles,notamment le réseau socialBe Sport.

OCaml est utilisé par des acteurs importants de l'industrie du logiciel, commeMicrosoftouXenSource,tous deux membres duConsortiumCaml.Il trouve aussi des applications dans l'informatique financière, comme l'a montré l'entrepriseJane Street,qui emploie de nombreux programmeurs OCaml, ou encore LexiFi, entreprise française, spécialisée dans la conception de langages de programmation dédiés à la finance.

Enfin, il est aussi utilisé par des projets libres généralistes, commeMLDonkey,GeneWeb,le client pourwebradiosLiquidsoap,la bibliothèque FFTW,ainsi que certains logiciels de l'environnement de bureauKDE.Enfin, les formules mathématiques du logicielMediaWikisont générées par un programme écrit en OCaml.

Présentation du langage

Hello world

Soit le programme hello.ml suivant:

print_endline"Hello world!"

Il peut être compilé enbytecodeexécutable avec le compilateurbytecodeocamlc:

$ ocamlc -o hello hello.ml

Il peut être également compilé en code natif optimisé exécutable avec le compilateur natif ocamlopt:

$ ocamlopt -o hello hello.ml

Le programme peut ensuite être exécuté par l'interpréteur debytecodeocamlrun:

$./hello
Hello world!

ou

$ ocamlrun hello
Hello world!

Variables

L'interpréteur interactif ocaml peut être utilisé. Il lance uneinvite de commandes« # » à la suite duquel les instructions OCaml peuvent être saisies, terminées par les caractères;;(ces caractères de fin d'instruction ne doivent être utilisés que dans l'interpréteur interactif, ils ne font pas partie de la syntaxe du langage). Par exemple, pour définir une variablexcontenant le résultat du calcul1 + 2 * 3,on écrit:

$ocaml

#letx=1+2*3;;

Après avoir saisi et validé cette expression, OCaml détermine le type de l'expression (en l'occurrence, il s'agit d'un entier) et affiche le résultat du calcul:

valx:int=7

On peut être tenté d'effectuer toutes sortes de calculs. Cependant, il faut prendre garde à ne pas mélanger les entiers et les réels, ce que l'on fait couramment dans de nombreux langages, car en OCaml ils ne sont pas automatiquement convertis (il faut utiliser une fonction qui va prendre un entier et retourner un réel, ou l'inverse si l'opérateur utilise des entiers). Dans l'exemple qui suit, l'opérateur + s'attend à additionner deux entiers, alors qu'il s'agit de deux réels:

#2.3+1.;;
Error:Thisexpressionhastypefloatbutanexpressionwasexpectedoftypeint

Cet exemple simple permet de se faire une première idée du fonctionnement de l'algorithme d'inférence de types. En effet, lorsque nous avons écrit2.3 + 1.,nous avons ajouté les réels2.3et1.avec l'opérateur+des entiers, ce qui pose un problème. En fait, pour effectuer ce calcul, nous devons nous assurer que tous les nombres ont le même type d'une part (par exemple il est impossible d'ajouter2.3et1car1est un entier contrairement à1.ou2.3), et d'autre part employer la loi de composition interne+appliquée aux réels, notée+.en OCaml. Nous aurions donc dû écrire:

#2.3+.1.;;
-:float=3.3

Fonctions

Les programmes sont souvent structurés en procédures et en fonctions. Les procédures sont composées d'un ensemble de commandes utilisées plusieurs fois dans le programme, et regroupées par commodité sous un même nom. Une procédure ne renvoie pas de valeur, ce rôle étant dévolu aux fonctions. De nombreux langages disposent de mots-clefs distincts pour introduire une nouvelle procédure ou une nouvelle fonction (procedureetfunctionenPascal,subetfunctionenVisual Basic…). OCaml, quant à lui, ne possède que des fonctions, et celles-ci se définissent de la même manière que les variables. Par exemple, pour définir l'identité, on peut écrire:

#letidx=x;;

Après saisie et validation de l'expression, l'algorithme de synthèse de types détermine le type de la fonction. Cependant, dans l'exemple que nous avons donné, rien ne présage du type dex,aussi la fonction apparaît-elle comme polymorphe (à tout élément de l'ensemble'a,elle associe une imageid xqui est élément de l'ensemble'a):

valid:'a->'a=<fun>

Pour appeler une fonction on utilise la syntaxe suivante:

#id5;;
-:int=5

OCaml permet également d'utiliser des fonctions anonymes, c'est-à-dire des fonctions non liées à un identifiant, grâce au mot-cléfunctionoufun:

#functionx->x;;
-:'a->'a=<fun>

Les fonctions anonymes peuvent être appelées immédiatement ou utilisées pour définir une fonction:

#(functionx->x+1)4;;
-:int=5

#letid=functionx->x;;
valid:'a->'a=<fun>

Filtrage par motif

Une fonctionnalité puissante de OCaml est le filtrage par motif (pattern matchingen anglais). Il peut-être défini avec les mots-clématch withou avec une fonction anonyme, suivis pour chaque motif d'une barre verticale|,du motif, d'une flèche->et de la valeur renvoyée:

#letest_nulx=
#matchxwith
#|0->true(* la première barre verticale est facultative *)
#|_->false;;
valest_nul:int->bool=<fun>

#function
#|0->true(* la première barre verticale est facultative *)
#|_->false;;
-:int->bool=<fun>

Le tiret bas_représente le motif par défaut. Il est possible de donner la même valeur à plusieurs motifs en une seule fois:

#letcontient_zero(x,y)=
#matchx,ywith
#|(0,_)|(_,0)->true
#|_->false;;
valcontient_zero:int*int->bool=<fun>

Le mot-cléwhenpermet d'exprimer une condition sur le motif:

#letcontient_zero(x,y)=
#matchx,ywith
#|(x,y)when(x=0||y=0)->true
#|_->false;;
valcontient_zero:int*int->bool=<fun>

Les caractères..permettent d'exprimer un motif filtrant les plages de caractères:

#letest_capitalec=
#matchcwith
#|'a'..'z'->false
#|'A'..'Z'->true
#|_->failwith"lettre invalide";;
valest_capitale:char->bool=<fun>

Le mot-cléaspermet de nommer la valeur filtrée:

#letmettre_en_capitalec=
#matchcwith
#|'a'..'z'aslettre->Char.uppercase_asciilettre
#|'A'..'Z'aslettre->lettre
#|_->failwith"lettre invalide";;
valmettre_en_capitale:char->char=<fun>

Récursivité

Larécursivitéconsiste à rédiger une fonction qui fait référence à elle-même, sur le modèle de la récurrence mathématique. En OCaml, lesfonctions récursivessont introduites à l'aide du mot-clefrec.

Par exemple, on peut définir la fonctionfactorielle:

#letrecfactn=
#matchnwith
#|0->1
#|_->n*fact(n-1);;
valfact:int->int=<fun>

On peut définir lasuite de Fibonaccipar:

#letrecfibn=
#matchnwith
#|0->0
#|1->1
#|_->fib(n-1)+fib(n-2);;
valfib:int->int=<fun>

Définition interne

Il est possible de définir des variables et des fonctions à l'intérieur d'une fonction à l'aide du mot-cléin.

Par exemple, on peut définir la fonction factorielle:

#letfactn=
#letrecfact_auxma=
#matchmwith
#|0->a
#|_->fact_aux(m-1)(m*a)
#infact_auxn1;;
valfact:int->int=<fun>

On peut définir la suite de Fibonacci par:

#letfibn=
#letrecfib_auxmab=
#matchmwith
#|0->a
#|_->fib_aux(m-1)b(a+b)
#infib_auxn01;;
valfib:int->int=<fun>

Récursivité terminale

Le compilateur OCaml optimise les appels terminaux: quand, pendant l'évaluation d'une fonction, la dernière étape à effectuer est l'appel d'une (autre) fonction, OCaml saute directement à cette nouvelle fonction sans conserver en mémoire l'appel de la première, devenu inutile.

En particulier, OCaml optimise larécursion terminale.Par exemple, la deuxième fonctionfactci-dessus (avec un paramètre auxiliairea) est une fonction terminale, équivalente à une boucle, et produira un résultat équivalent, égalant ainsi les performances du code impératif correspondant.

La récursion terminale est aussi performante que l'itération; elle est donc à préférer quand elle permet d'écrire des programmes plus clairs ou plus faciles à manipuler.

Manipulation de listes

Leslistessont très utilisées en programmation, en particulier pour les traitements récursifs. Les éléments d'une liste possèdent tous le même type. Pour construire une liste, deux écritures sont possibles, l'une avec l'opérateur de chaînage::et l'autre avec l'opérateur;:

#1::2::3::[];;
-:intlist=[1;2;3]

#[1;2;3];;
-:intlist=[1;2;3]

L'opérande de droite du dernier opérateur de chaînage::d'une expression doit être une liste:

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

Il est possible de concaténer des listes avec l'opérateur de concaténation@:

#[1;2;3]@[4;5];;
-:intlist=[1;2;3;4;5]

Pour connaître la longueur d'une liste sans utiliser la fonctionList.lengthdéfinie à cet effet, on peut écrire:

#letreclongueurl=
#matchlwith
#|[]->0
#|_::q->1+longueurq;;
vallongueur:'alist->int=<fun>

Lors de l'analyse de cette fonction par l'algorithme d'inférence de type, il apparaît que la liste peut contenir n'importe quel type de données'a.

La fonction suivante crée une liste de couples à partir de deux listes: la longueur de cette liste sera égale à la longueur de la liste passée en paramètre qui est la plus courte.

#letreccouplel1l2=
#matchl1,l2with
#|([],_)|(_,[])->[]
#|(t1::q1,t2::q2)->(t1,t2)::coupleq1q2;;
valcouple:'alist->'blist->('a*'b)list=<fun>

La fonction suivante récupère le premier élément d'une liste:

#letpremier_elementl=
#matchlwith
#|[]->failwith"liste vide"
#|e::_->e;;
valpremier_element:'alist->'a=<fun>

La fonction suivante récupère le deuxième élément d'une liste:

#letdeuxieme_elementl=
#matchlwith
#|[]->failwith"liste vide"
#|[_]->failwith"liste à un élément"
#|_::e::_->e;;
valdeuxieme_element:'alist->'a=<fun>

La fonction suivante récupère le premier élément de la première sous liste:

#letsous_premier_elementl=
#matchlwith
#|[]->failwith"liste vide"
#|[]::_->failwith"sous liste vide"
#|(e::_)::_->e;;
valsous_premier_element:'alistlist->'a=<fun>

Fonctions d'ordre supérieur

Lesfonctions d'ordre supérieursont des fonctions qui prennent une ou plusieurs fonctions en entrée et/ou renvoient une fonction (on parle alors de fonctionnelle). La plupart des langages fonctionnels possèdent des fonctions d'ordre supérieur. Concernant OCaml, on peut en trouver des exemples dans les fonctions prédéfinies des modulesArray,List,etc. Par exemple, l'expression suivante:

#List.map(functioni->i*i)[0;1;2;3;4;5];;
-:intlist=[0;1;4;9;16;25]

La fonctionmapprend en argument la fonction anonyme qui, à tout entieri,associe son carré, et l'applique aux éléments de la liste, construisant ainsi la liste des valeurs élevées au carré.

Autre exemple:

#letdoublefi=f(fi);;
valdouble:('a->'a)->'a->'a=<fun>

La fonctiondoubleprend en paramètre une fonctionfet une valeuriet applique deux foisfài.

#lettrois=double(functioni->i+1)1;;
valtrois:int=3

#letaugmente_2=double(functioni->i+1);;
valaugmente_2:int->int=<fun>

#letliste=
#double(
#function
#|[]->[]
#|e::l->(e+1)::l
#)[1;2;3];;
valliste:intlist=[3;2;3]

Voici encore un exemple:

#letrecparcoursfel=
#matchlwith
#|[]->e
#|t::q->ft(parcoursfeq);;
valparcours:('a->'b->'b)->'b->'alist->'b=<fun>

#(* somme des éléments de la liste [1; 1; 2] *)
#parcours(+)0[1;1;2];;
-:int=4

#(* fonction calculant la somme des éléments d'une liste *)
#letsomme_liste=parcours(+)0;;
valsomme_liste:intlist->int=<fun>

#(* fonction calculant le produit des éléments d'une liste *)
#letproduit_liste=parcours(*.)1.;;
valproduit_liste:floatlist->float=<fun>

Enfin, un dernier exemple. Ici, on se charge de définir un nouvel opérateur noté$.Cette opérateur effectue la composée de deux fonctions.

#let($)fg=functionx->f(gx)
val($):('a->'b)->('c->'a)->'c->'b=<fun>

#letfx=x*x;;
valf:int->int=<fun>

#letgx=x+3;;
valg:int->int=<fun>

#leth=f$g;;
valh:int->int=<fun>

#(* affiche 36 *)
#print_int(h3);;

Arbres et types récursifs

Pour définir unarbrebinaire de type quelconque, on se sert d'un type récursif. On peut ainsi avoir recours à l'écriture suivante:

#type'aarbre=
#|Feuille
#|Brancheof'aarbre*'a*'aarbre;;
type'aarbre=Feuille|Brancheof'aarbre*'a*'aarbre

Cet arbre se compose de branches qui se ramifient à souhait, et se terminent par des feuilles. Pour connaître la hauteur d'un arbre, on utilise alors:

#letrechauteur=
#function
#|Feuille->0
#|Branche(gauche,_,droite)->1+max(hauteurgauche)(hauteurdroite);;
valhauteur:'aarbre->int=<fun>

Recherche de racine par dichotomie

#letrecdichofminmaxeps=
#letfmin=fminandfmax=fmaxin
#iffmin*.fmax>0.thenfailwith"Aucune racine"
#elseifmax-.min<epsthen(min,max)(* retourne un intervalle *)
#elseletmil=(min+.max)/.2.in
#if(fmil)*.fmin<0.thendichofminmileps
#elsedichofmilmaxeps;;
valdicho:(float->float)->float->float->float->float*float=<fun>

(* approximation de la racine carrée de 2 *)
#dicho(functionx->x*.x-.2.)0.10.0.000000001;;
-:float*float=(1.4142135618,1.41421356238)

Mémoïsation

Voici un exemple de fonction qui utilise lamémoïsation.Il s'agit d'une fonction qui calcule len-ième terme de lasuite de Fibonacci.Contrairement à la fonction récursive classique, celle-ci mémorise les résultats et peut les ressortir en temps constant grâce à la table de hachage.

(* Taille de la table de hachage. *)
let_HASH_TABLE_SIZE=997

(* Retourne le n-ième terme de la suite de Fibonacci. *)
letrecfibo=
(* Pré-définitions. Ce code est exécuté une fois lors de la définition de la
fonction, mais ne l'est pas à chaque appel. Cependant, `h` reste dans
l'environnement de cette fonction pour chaque appel. *)
leth=Hashtbl.create_HASH_TABLE_SIZEin
(* Premiers termes. *)
Hashtbl.addh00;
Hashtbl.addh11;
function
|nwhenn<0->invalid_arg"fibo"(* Pas de nombre négatif. *)
|n->
try
Hashtbl.findhn(* On a déjà calculé `fibo n`, on ressort donc le
résultat stocké dans la table `h`. *)
withNot_found->(* Si l'élément n'est pas trouvé,… *)
letr=fibo(n-1)+fibo(n-2)in(*… on le calcule,… *)
Hashtbl.addhnr;(*… on le stocke,… *)
r(*… et on renvoie la valeur. *)

Dérivation d'un polynôme

On se propose ici d'implémenter une fonction simple permettant de dériver un polynôme de degré quelconque. Il faut d'abord spécifier le type qui représentera notre polynôme:

#typepolyn=
#|Numoffloat(* constante *)
#|Varofstring(* variable *)
#|Negofpolyn(* négation *)
#|Addofpolyn*polyn(* addition *)
#|Subofpolyn*polyn(* soustraction *)
#|Mulofpolyn*polyn(* multiplication *)
#|Divofpolyn*polyn(* division *)
#|Powofpolyn*int;;(* exponentiation *)
typepolyn=Numoffloat|Varofstring|Negofpolyn|Addofpolyn*polyn|Subofpolyn*polyn|Mulofpolyn*polyn|Divofpolyn*polyn|Powofpolyn*int

Maintenant, voici la fonction qui dérive ce polynôme par rapport à la variable x spécifiée en paramètre.

#letrecderivx=function
#|Num_->Num0.
#|Varywheny=x->Num1.
#|Var_->Num0.
#|Negp->Neg(derivxp)(* -p' *)
#|Add(p,q)->Add(derivxp,derivxq)(* p' + q' *)
#|Sub(p,q)->Sub(derivxp,derivxq)(* p' - q' *)
#|Mul(p,q)->Add(Mul(derivxp,q),Mul(p,derivxq))(* p'q + pq' *)
#|Div(p,q)->Div(Sub(Mul(derivxp,q),Mul(p,derivxq)),Pow(q,2))(* (p'q - pq')/q^2 *)
#|Pow(p,0)->Num0.
#|Pow(p,1)->derivxp
#|Pow(p,n)->Mul(Num(float_of_intn),Mul(derivxp,Pow(p,n-1)))(* n * p' * p^(n - 1) *)
valderiv:string->polyn->polyn=<fun>

Différentes cibles de compilation

L'implémentation OCaml a été adaptée par d'autres auteurs à des cibles de compilation autres que lebytecodeet le code natif. On trouvera:

• OCaml-Java, une distribution pour la JVM contenant ocamlc, ocamlrun, ocamldep, ocamldoc, ocamllex, menhir, un compilateur ocamljava vers laJVM;
• OCamIL, un prototype debackendpour l'environnement.NET.Elle contient un compilateur vers dubytecodeOCaml (exécutable par ocamlrun), un compilateur vers.NET et un outil comme ocamlyacc nommé ocamilyacc.

Langages dérivés

De nombreux langages étendent OCaml pour lui ajouter des fonctionnalités.

• F#est un langage de la plateforme.NET développé parMicrosoft Research,fondé sur OCaml (et en partie compatible).
• MetaOCaml ajoute un mécanisme dequotationset degénération de codeauruntime,qui apporte des fonctionnalités demétaprogrammationà OCaml.
• Fresh OCaml (fondé sur AlphaCaml, un autre dérivé de OCaml) facilite la manipulation denoms symboliques.
• JoCaml ajoute à OCaml un support du Join Calculus, orienté vers lesprogrammes concurrentsoudistribués.
• OcamlP3L apporte une forme particulière de parallélisme, fondée sur les « squelettes » (skeleton programming).
• GCaml ajoute le polymorphismead-hocà OCaml, permettant la surcharge des opérateurs ou unmarshallingconservant les informations de typage.
• OCamlDuce permet au système de types de représenter des valeursXMLou liées à desexpressions régulières.C'est un intermédiaire entre OCaml et le langage CDuce, spécialisé dans la manipulation du XML.
• Opaest un langage de développement d'applications et services web implanté en OCaml et dont le noyau reprend les fonctionnalités du langage OCaml. Par ailleurs, le compilateur Opa utilise le backend du compilateur OCaml pour générer des serveurs natifs.
• ReasonML développé par Facebook, est un langage utilisant le compilateur OCaml, permettant la compilation du code Reason (.re) et OCaml (.ml) en code source JavaScript (.js), qui peut-être à son tour compilé en bytecode, utilisé dans le navigateur web ou via un interpréteur comme Node.js.

Voir aussi

Articles connexes

• Ocsigen

Liens externes

• Site OCaml officiel
• Site OCaml de la communauté
• Ouvrages en français