Objective Caml - Définition

Histoire

Le langage Caml est né de la rencontre du langage de programmation ML, auquel s'est intéressé l'équipe Formel de l'INRIA depuis le début des années 1980, et de la machine abstraite catégorique CAM de Guy Cousineau, fondée sur les travaux de Pierre-Louis Curien en 1984. La première implantation, écrite par Ascander Suarez (à l'époque doctorant à l'Université Paris Diderot) puis maintenue par Pierre Weis et Michel Mauny, a été publiée en 1987. 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 de Standard ML.

Les limitations de la CAM ont conduit à la création d'une nouvelle implantation, mise au point par Xavier Leroy dès 1990, sous le nom de Caml Light. Cette implantation, dont une version récente est encore utilisée dans l'enseignement de nos jours, bien que le système ne soit plus maintenu par l'INRIA, fonctionne grâce à un interpréteur de code octet (bytecode) codé en C, qui lui assure une grande portabilité. Le système de gestion de la mémoire, conçu par Damien Doligez, a aussi fait son apparition dans Caml Light.

En 1995, Xavier Leroy publie une version de Caml nommée Caml Special Light, qui introduit un compilateur de code natif, et un système de modules inspiré des modules de Standard ML.

Objective Caml, publié pour la première fois en 1996, apporte à Caml un système objet conçu par Didier Rémy et Jérôme Vouillon. Certaines fonctionnalités avancées, comme les variantes polymorphes ou les labels (permettant de distinguer les arguments donnés à une fonction par leur nom, plutôt que leur position) ont été introduites en 2000 par Jacques Garrigue.

Objective Caml s'est relativement stabilisé depuis (malgré l'absence d'une spécification, le document en vigueur étant le manuel officiel maintenu 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 du XML…) ; voir la section .

Présentation du langage

Déclarations et valeurs de base

En mode interactif le code peut être entré simplement à la suite de l'invite « # » qui figure en début de ligne. Par exemple, pour définir une variable x contenant le résultat du calcul 1 + 2 * 3, on écrira :

      # let x = 1 + 2 * 3 ;;      

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

      val x : 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 ceci provoque une erreur lors de la compilation :

        # 2.3 + 1.;;          Characters 0 - 3:           2.3 + 1.;;           ^^          This expression has type float but is here used with type int      

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 écrit « 2.3 + 1. », nous avons ajouté les réels 2.3 et 1. avec l'operateur + des entiers, ce qui pose 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'ajouter 2.3 et 1 car 1 est un entier contrairement à 1. ou 2.3), et d'autre part employer la loi de composition interne + appliquée aux réels, notée « +. » en Caml. 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 (Procedure et Function en Pascal, Sub et Function en Visual Basic, etc.). Caml, 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 :

      # let id = function x -> 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 de x, aussi la fonction apparaît-elle comme polymorphe (à tout élément de l'ensemble 'a, elle associe une image id(x) qui est élément de l'ensemble 'a) :

      val id : 'a -> 'a = <fun>      

Récursivité

La ré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 Caml, les fonctions récursives sont introduites à l'aide du mot-clef rec. Par exemple, pour définir la factorielle, nous pouvons écrire :

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

Définitions internes

Il est possible de définir des valeurs ou des fonctions à l'intérieur d'une fonction. On utilise pour cela la syntaxe suivante :

      # let factorielle n =          let rec auxiliaire resultat = function               0 -> resultat             | n -> auxiliaire (n * resultat) (n - 1)           in auxiliaire 1 n ;;      

Récursivité terminale, appels terminaux

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 la récursion terminale. Par exemple, la deuxième fonction factorielle ci-dessus (avec un paramètre auxiliaire résultat) 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

Les listes sont très utilisées en programmation, en particulier pour les traitements récursifs. Pour construire une liste, plusieurs écritures sont possibles :

      # 1 :: 2 :: 3 :: [] ;;      # [1 ; 2 ; 3] ;;      

Ce faisant, on obtient une liste d'entiers, que Caml note de la façon suivante :

      - : int list = [1 ; 2 ; 3]      

Pour connaître la longueur d'une liste sans utiliser la fonction du module List définie à cet effet, on peut écrire :

      (* Longueur d'une liste *)      # let rec longueur = function            [] -> 0          | t :: q -> 1 + longueur q ;;      

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, de sorte que la fonction possède le type suivant :

      val longueur : 'a list -> int = <fun>      

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.

      # let rec couple l1 l2 =          match (l1, l2) with            ([],_) | (_,[]) -> []          | (a :: q, b :: p) -> (a, b) :: couple q p;;      

A noter le caractère _ qui indique que le premier (ou le deuxième) élément du couple n'a pas d'importance. i.e. il suffit qu'une des deux listes du couple soit vide pour que la fonction se termine.

      (* Typage *)      val couple : 'a list -> 'b list -> ('a * 'b) list = <fun>      

Le type des éléments de chaque liste n'est pas forcément le même : 'a et 'b. On peut donc avoir (int list) et (float list) pour former (int * float) list

Fonctions d'ordre supérieur

Les fonctions d'ordre supérieur sont des fonctions qui prennent une ou plusieurs fonctions en entrée et/ou renvoient une fonction. La plupart des langages fonctionnels possèdent des fonctions d'ordre supérieur. Concernant Caml, on peut en trouver des exemples dans les fonctions prédéfinies des modules Array, List, etc. Par exemple, l'expression suivante :

      # List.map (fun i -> i * i) [0; 1; 2; 3; 4; 5] ;;      

produira le résultat suivant :

      - : int list = [0; 1; 4; 9; 16; 25]      

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

Autre exemple :

      let double f i = f (f i)      

La fonction double prend en paramètre une fonction f et une valeur i et applique deux fois f à i.

      let trois = double (fun i -> i+1) 1             (* renvoie la fonction "incrémentation de 1" *)      let augmente_2 = double (fun i -> i+1)             (* renvoie [3;2;3] *)      let liste = double (function [] -> [] | e::l -> (e+1)::l) [1;2;3]      

Voici encore un exemple :

      let rec parcours f e = function        [] -> e        | x::l -> f x (parcours f e l)             (* Exemple d'application *)      (* calcule la somme des éléments de la liste = 4 *)      let somme = parcours (+) 0 [1;1;2]             (* renvoie une fonction calculant la somme des éléments (int) d'une liste *)      let fonction_somme = parcours (+) 0             (* renvoie une fonction calculant le produit des éléments (float) d'une liste *)      let fonction_produit = parcours ( *. ) 1.      

Arbres et types récursifs

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

      type 'a arbre =        Feuille      | Branche of 'a arbre * 'a * 'a arbre;;      

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 :

             let rec hauteur = function        Feuille -> 0      | Branche (gauche, _, droite) -> 1 + max (hauteur gauche) (hauteur droite);;      

Recherche de racine par dichotomie

      let rec dicho f min max eps =        let fmin = f min and fmax = f max in          if fmin *. fmax > 0.          then failwith "Aucune racine"          else if max -. min < eps then (min, max) (* retourne un intervalle *)          else let mil = (min +. max) /. 2. in            if (f mil) *. fmin < 0.            then dicho f min mil eps            else dicho f mil max eps ;;               (* Approximation de la racine carrée de 2 *)        # dicho (fun x -> x *. x -. 2.) 0. 10. 0.000000001;;        - : float * float = (1.4142135618, 1.41421356238)