Objective Caml/Bases

Objectifs du chapitre

Ce chapitre vous enseignera

• comment installer OCaml
• comment lancer et manipuler OCaml en ligne de commande
• comment lire, définir et manipuler des valeurs et des fonctions simples et d'ordre supérieur.

À l'issue de ce chapitre, vous pourrez utiliser OCaml comme une super-calculatrice programmable.

Matériel nécessaire pour ce chapitre

Pour ce qui suit, vous allez avoir besoin d'une installation d'Objective Caml 3.11 ou ultérieur avec Batteries Included et peut-être de quelques outils. Objective Caml est disponible sur de nombreuses plate-formes.

Note Il est fort probable que tout ce qui suit fonctionne aussi avec une version plus ancienne de OCaml. Ceci n'a pas été testé.

Power Users (Linux, MacOS X, BSD, Cygwin)

Si la notion de dépendances et l'idée d'installer des logiciels en ligne de commande ne vous pose pas de problèmes, la méthode recommandée est d'utiliser la distribution GODI d'OCaml, disponible sous toutes les plate-formes Unix, Windows y compris (par le biais de la couche Unix Cygwin).

Windows uniquement

• Commencez par installer Cygwin. Si vous avez des problèmes au cours de l'installation de GODI, vous devrez revenir à ce point et installer les paquets Cygwin manquants.

Toutes les plate-formes

Tout ce qui suit doit se dérouler sous votre compte utilisateur courant.

• Téléchargez la dernière version de l'installateur GODI.
• Décompressez l'archive que vous venez de récupérer.
• Prendre son éditeur favori, et éditer le fichier .bash_profile dans $HOME, par exemple en faisant

vim ~/.bash_profile

afin d'ajouter les lignes suivantes:

     if [ -d ${HOME}/godi/bin -a -d ${HOME}/godi/sbin ] ; then 
         PATH=${HOME}/godi/bin:${HOME}/godi/sbin:${PATH}
     fi
     if [ -d ${HOME}/godi/man ] ; then
         MANPATH=${HOME}/godi/man:${MANPATH}
     fi
     # Spécifique Windows + Cygwin
     TTY=`tty`

(<PREFIX> est ici ${HOME}/godi)

N.B.: Étendre la variable $PATH en rajoutant les chemins des binaires produit par l'installation de GODI est une bonne idée, peu importe le shell et l'OS ;-)

• En ligne de commande, rendez-vous dans le répertoire créé par la décompression et lancez l'installateur en tapant

./bootstrap --prefix <PREFIX> --section=3.12

(remplacez <PREFIX> par le chemin complet vers le répertoire dans lequel vous souhaitez installer GODI).

• Modifiez votre chemin de recherche pour permettre de trouver GODI. Généralement, vous emploierez pour ce faire

les commandes suivantes :

PATH=$PATH:<PREFIX>/bin:<PREFIX>/sbin; export PATH

• Lancez l'installation en tapant, toujours dans le même répertoire

./bootstrap_stage2

Une fois l'installation de GODI terminée, vous pourrez ajouter des bibliothèques OCaml en tapant

godi_console perform -build godi-batteries

pour installer Batteries Included par exemple.

Spécifique à Cygwin

Sous Windows™, la commande permettant l'initialisation du bootstrap installe le portage pour Cygwin (vos applications auront besoin de cygwin.dll pour fonctionner). Il faudra néanmoins faire un

  export PATH=/usr/local/bin:/usr/bin

avant cette commande pour ne pas avoir d'espaces dans les chemins de la variable $PATH.

Pour avoir une installation qui fonctionne sans Cygwin, il faut spécifier un autre portage sur la ligne de commande.

Spécifique à MinGW32

Pour MinGW32 (à installer par Cygwin), installer d'abord gcc et ensuite gcc-mingw en version 3. Et ensuite remplacer la commande d'initialisation du bootstrap par:

  export PATH=/usr/local/bin:/usr/bin
./bootstrap --prefix <PREFIX> --section=3.12 --w32port=mingw

Attention: le portage pour MinGW32 permet générer des binaires natifs pour Windows™ plus rapide mais au prix d'avoir quelques appels systèmes en moins et d'avoir un certain nombre de soucis avec les chemins.

Alternative, sous Unix

Des paquets pour OCaml sont disponibles pour :

• Ubuntu
• Debian
• Fedora
• Mageia
• Archlinux
• Gentoo
• ...

Vous pouvez les trouver à l'aide des mécanismes habituels de gestion de paquets de votre distribution.

En plus de ce qui précède, il est recommandé d'installer soit le logiciel ledit (disponible sous GODI), soit le logiciel rlwrap (disponible sous votre gestionnaire de paquets), qui vous simplifieront le travail lors de l'utilisation d'OCaml en ligne de commande.

Alternative, sous Windows

La distribution minimale pour Windows, avec un installateur graphique, est disponible sur le site officiel. Insistons sur le fait que cette distribution est minimale et donc peu utilisable.

Le mode calculatrice d'OCaml

OCaml dispose de deux modes principaux d'utilisation :

• le compilateur, que nous verrons au prochain chapitre
• la ligne de commande, ou "mode calculatrice".

C'est ce dernier que nous allons utiliser le temps d'un chapitre. Ce mode calculatrice, bien que limité par rapport à un compilateur et beaucoup plus lent que le compilateur-optimisateur d'OCaml, est très pratique pour tester des extraits de code ou lancer des calculs.

Pour lancer ce mode calculatrice, la manière la plus simple minimale est d'ouvrir un terminal puis de taper

ocaml

mais l'édition et les fonctions de bases sont alors limitées, il est donc recommandé d'utiliser plutôt

rlwrap ocamlfind batteries/ocaml

ou, si vous avez installé ledit au lieu de rlwrap,

ledit ocamlfind batteries/ocaml

Cette instruction demande à votre système d'exploitation de trouver et d'exécuter la version de OCaml Batteries Included installée sur votre ordinateur. Sur cette ligne, ocamlfind est le gestionnaire de versions de OCaml et des bibliothèques OCaml, qui permet de manipuler diverses versions de OCaml, batteries/ocaml est le nom du mode calculatrice d'OCaml avec Batteries Included et rlwrap/ledit est un petit outil qui simplifie l'édition de texte.

Premiers pas avec OCaml

À l'ouverture en mode calculatrice OCaml affiche le message suivant :

        Objective Caml version 3.12.0


----------------------------------------------
|                                            |
|     This is OCaml, Batteries Included.     |
|                                            |
|                                            |
|      If you need help, type '#help;;'      |
|                                            |
----------------------------------------------


# 

La première ligne confirme que OCaml 3.12 a bien été chargé. La suite confirme que vous utilisez bien OCaml Batteries Included et non pas une distribution plus minimaliste de OCaml. Enfin, le symbole # est l'invite de commande, qui signifie que la ligne de commande est prête et attend vos instructions. Au cours de ce chapitre, nous ferons figurer ce symbole au début de chaque ligne tapée par l'utilisateur. Insistons sur le fait que c'est à OCaml d'afficher ce symbole et non pas à vous de le taper.

Note Si jamais vous avez besoin d'interrompre un programme en cours d'exécution dans la calculatrice, utilisez la combinaison de touches Ctrl+C. Si vous avez besoin de quitter la calculatrice, écrivez #quit;;.

La ligne de commande accepte

• des calculs (ou 'évaluations')
• des définitions de valeurs
• des directives spéciales, qui permettent notamment de quitter ou d'ouvrir l'aide.

Pour commencer, intéressons-nous aux évaluations.

Calculer avec OCaml

Pour évaluer 0 + 1, écrivons

# 0 + 1 ;;

Le symbole ;; constitue la "fin de phrase". Dans la calculatrice, chaque évaluation doit être suivie d'une fin de phrase.

Convention Les conventions syntaxiques de OCaml veulent qu'on insère une espace avant l'opérateur et une espace après l'opérateur. Ces conventions évitent certaines erreurs de relecture de programmes lors de l'utilisation d'opérateurs personnalisés. On insèrera de même une espace avant et après chaque parenthèse.

L'expression arithmétique précédente produira la réponse

- : int = 1

Cette réponse se lit "le résultat du dernier calcul est un entier, sa valeur est 1". Nous reviendrons plus tard sur la définition des entiers en OCaml.

OCaml dispose des opérations arithmétiques habituelles sur les entiers : addition (+), soustraction (-), multiplication (*), division entière (/), reste de la division entière (mod), négation (~-), avec les priorités mathématiques habituelles. Tous ces opérateurs sont infixes. Ainsi, on écrira

# 2 mod 3 ;;
- : int = 2

Notons que toutes ces opérations acceptent uniquement des entiers et produisent uniquement des entiers. Ainsi, on obtiendra

# 2 / 3 ;;
- : int = 0

De même, OCaml dispose des opérations arithmétiques habituelles sur les nombres à virgule : addition (+.), soustraction (-.), multiplication (*.), division (/.), puissance (**). Ces opérations, de nouveau, sont infixes et respectent les priorités mathématiques habituelles. On écrira donc

# 2. ** 3. ;;
- : float = 8

De nouveau, toutes ces opérations acceptent uniquement des nombres à virgule flottante et renvoient uniquement des nombres à virgule flottante. Si l'on tente de combiner entiers et nombres à virgule flottante, on obtiendra

# 2.0 / 3 ;;
  ^^^
This expression has type float but is here used with type int

# 2 /. 3.0 ;;
  ^
This expression has type int but is here used with type float

Note En cas d'erreur de syntaxe ou la compilation, OCaml souligne la zone sur laquelle porte l'erreur à l'aide soit de symboles ^^^, soit de traits, selon l'environnement utilisé, voire la surligne en couleur. Il arrive malheureusement que les symboles soient décalé de quelques caractères.

Pour mélanger entiers et nombres à virgule, on emploie les fonctions de conversion int_of_float et float_of_int.

# float_of_int ( 2 ) /. 3.;;
- : float = 0.666666666667

# 2 / int_of_float( 1.5 );;
- : int = 2

Quelques autres fonctions complètent l'attirail :

• des fonctions sur les entiers telles que la valeur absolue (abs), successeur (succ), prédécesseur (pred), etc.
• des fonctions sur les nombres flottants, telles que les fonctions trigonométriques, la racine carrée (sqrt), l'exponentielle (exp), les fonctions hyperboliques (tanh, cosh et sinh), etc.

Pour consulter la documentation sur chacune de ces fonctions, utilisez la directive #man, comme suit :

#man "cosh";;

Limitations et précautions

Limites de calcul

Comme dans la majorité des langages de programmation, les entiers sont bornés par la capacité de calcul du microprocesseur. Avec OCaml, sur un ordinateur à processeur 32 bits, les limites sont de

# min_int ;;
- : int = -1073741824
# max_int;;
- : int = 1073741823

c'est-à-dire $[-2^{30},2^{30}[$. Sur un ordinateur à processeur 64 bits, les limites sont de

# min_int ;;
- : int =  -4611686018427387904
# max_int;;
- : int = 4611686018427387903

c'est-à-dire $[-2^{62},2^{62}[$.

Note pour lecteurs avancés : à la lecture, un programmeur habitué aux limites des systèmes s'interrogera sur le destin du dernier bit. Celui-ci sert à différencier les 'entiers' et les 'références' lors de la récupération de la mémoire vive. Cette astuce limite la gamme des entiers utilisables sur le système mais évite

• d'une part l'imprécision et la lenteur des ramasse-miettes sans support du langage, tels que le très utilisé ramasse-miette de Boehm ou certaines versions de Java, qui sont contraints de considérer les nombres entiers comme des pointeurs ;
• d'autre part le gaspillage de mémoire vive et la lenteur d'autres ramasse-miettes, dont certaines versions de Java, qui sont contraints d'ajouter un mot de mémoire après chaque valeur pour différencier entiers et références.

Pour les applications ayant besoin d'une gamme d'entiers plus grande que ce que OCaml propose par défaut, plusieurs alternatives existent. Notamment, OCaml est fourni avec une bibliothèque de calcul sur 64 bits et une bibliothèque de calculs sur entiers de taille illimitée. D'autres bibliothèques sont disponibles, pour faire face à d'autres circonstances.

Dépassements de capacité

Par défaut, les opérations arithmétiques sur les entiers ne préviennent pas en cas de dépassement. Ainsi, on aura

# min_int - 1 ;;  (* Un nombre qui devrait être négatif *)
- : int = 1073741823

Il est possible de modifier la définition des opérations arithmétiques de manière à prévenir (lancer une exception) en cas de dépassement mais la solution est lente et reste imparfaite. Nous verrons ultérieurement comment demander à OCaml Batteries Included d'utiliser cette version des opérations.

Conversion automatique

Un entier n'est pas un nombre flottant et un nombre flottant n'est pas un entier. Il a été plusieurs fois question de permettre en OCaml la conversion automatique d'un entier en un flottant ou d'un flottant en entier, comme dans certains autres langages de programmation, mais les développeurs d'OCaml ont rejeté l'idée, pour plusieurs raisons :

• la conversion automatique est une source invisible d'erreurs et de ralentissements pour les logiciels d'analyse numérique, qui constituent l'une des raisons principales d'être d'OCaml
• la philosophie des concepteurs d'OCaml est de ne pas résoudre de problèmes à moitié, or, à partir du moment où deux types peuvent être automatiquement convertis l'un en l'autre, le monde de la Recherche ne connaît pas encore de méthode automatique et exacte pour permettre systématiquement de déterminer durant la compilation le type d'une expression -- introduire la conversion automatique interdirait donc l'analyse automatique de types, qui est primordiale en OCaml.

À retenir

• Le type des nombres entiers est int.
• Le type des nombres à virgule est float.
• Un entier n'est pas un nombre à virgule, un nombre à virgule n'est pas un entier. Pour convertir l'un en l'autre, il convient d'employer les fonctions float_of_int et int_of_float.
• Le message

This expression has type xxxxx but is here used with type yyyyy

signale une erreur de typage : l'analyse de type a déterminé que l'expression soulignée porte le type xxxxx, alors que le contexte dans lequel elle est utilisée est prévu uniquement pour des valeurs de type yyyyy.

Booléens

Deux entiers ou deux nombres à virgule peuvent être comparés à l'aide des opérateurs =, <, <= et >, >=, <>, !=.

# 1 = 0;;
- : bool = false

# 1. = 0.;;
- : bool = false

# 1. = 0;;
       ^
This expression has type int but is here used with type float

Note : l'opérateur = procède à une comparaison au sens mathématique du terme (comparaison structurelle) et non au sens de l'identité (égalité des références), contrairement à ce qui se produit dans l'essentiel des langages de programmation, et ne dépend pas de l'éventuelle null-ité d'un pointeur. En d'autres termes, si vous avez besoin de vérifier l'égalité de deux valeurs, et à moins d'avoir une très bonne raison de changer la définition de l'égalité, vous pouvez utiliser sans crainte l'opérateur =.

Le résultat d'une comparaison est une valeur true ou false, de type bool.

Deux booléens peuvent eux-même être comparés à l'aide de l'opérateur = -- en fait, comme nous le reverrons plus loin, les opérateurs de comparaison peuvent être appliqués à n'importe quel couple de valeurs de même type. En plus de la comparaison, les booléens sont dotés des opérateurs et fonctions habituelles : le 'et logique' paresseux (&&), le 'ou logique' paresseux (||) et la négation (not).

Les booléens sont employés notamment dans les opérations de contrôle de flot (presque) habituelles d'OCaml :

# if 1 = 0 then 2 else 3 ;;
- : int = 3

Nous reviendrons un peu plus tard sur ces instructions de contrôle de flot.

À retenir

• Pour comparer deux valeurs de même type, on emploie =.
• Le type des booléens est bool.
• Les deux booléens se notent true et false.

Déclaration de valeurs

Valeurs simples

Déclarer une valeur consiste à donner un nom au résultat d'une expression. Ainsi, l'extrait

# let pi = 3.1415927 ;;
val pi : float = 3.1415927

'lie', pour toute la suite de l'exécution du programme, le nom pi à la valeur '3.1415927'. La réponse d'OCaml se lit d'ailleurs "Dorénavant, le nom pi désigne un nombre flottant dont la valeur est 3.1415927."

Ce nom peut être réutilisé dans n'importe quelle expression :

# cos ( pi ) ;;
- : float = -0.999948994965

Note : insistons sur le fait que la valeur de pi ne peut changer. Pour être plus précis, il est possible de masquer pi par une nouvelle définition mais pas de réaffecter une nouvelle valeur à pi. En d'autres termes, les valeurs OCaml fonctionnent comme les constantes dans de nombreux langages. On les appelle cependant des variables, car il s'agit bien de variables au sens mathématique du terme.

Note : un nom lié est toujours lié à une valeur. En d'autres termes, en OCaml, il n'est jamais nécessaire de vérifier si une valeur est null, undefined, etc. Dans les cas où il est nécessaire de manipuler une valeur qui peut ou non être définie, on emploiera le mécanisme des options, que nous verrons plus tard.

Tenter d'utiliser un nom qui n'est pas lié provoque une erreur. Ainsi, on aura

# cos ( pi' ) ;;
        ^^^
Unbound value pi'

Nous verrons plus tard que, comme les erreurs de type ou de syntaxe, les erreurs de liaison sont détectées à la compilation, comme en Java ou C# et par opposition à Python, JavaScript ou Ruby.

Bien entendu, un nom peut être donné au résultat d'une expression plus complexe que la constante 3.1415. Ainsi, pour définir pi, on utilisera plutôt le calcul plus précis suivant :

# let pi = 2. *. acos ( 0. ) ;;
val pi : float = 3.14159265359

Note : La liaison let x = ... ;; calcule immédiatement le résultat de l'expression. Si nécessaire, OCaml propose aussi des expressions paresseuses, qui ne sont calculées que lorsque leur résultat est effectivement consulté. Nous en rediscuterons plus tard.

Plusieurs noms peuvent être définis simultanément

# let  x = 1 
  and  y = 2;;
val x : int = 1
val y : int = 2

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

Notons que le nom n'est lié qu'à partir de la fin de sa déclaration. En d'autres termes, à l'intérieur de la définition de x, x n'a pas de sens :

# let x = x + 1 ;;
          ^
Unbound identifier x

Il est aussi possible de lier un nom localement. Ainsi, on écrira

# let x = 50 in
  3 * x * x + 4 * x + 5 = 0 ;;
- : bool = false

ou encore

# 3 * x * x + 4 * x + 5 = 0
  where x = 50;;
- : bool = false

Dans cet extrait, le nom x n'est lié que le temps de calculer 3 * x * x + 4 * x + 5 et de comparer ce résultat à 0. On dit que la portée de x est 3 * x * x + 4 * x + 5 = 0. La réponse de OCaml, qui commence par un tiret, confirme qu'aucune nouvelle variable n'a été liée globalement par cette expression. Ainsi, essayer ensuite d'utiliser x hors de sa portée expression provoquera une erreur

# x ;;
  ^
Unbound value x

# let x = x in 3 * x * x + 4 * x + 5 = 0 ;;
          ^
Unbound value x

Comme le montre notre exemple précédent, let...in... est une expression et a donc un résultat. On peut donc combiner let...in et let ... de manière à donner un nom global au résultat d'un calcul qui utilise des noms locaux :

# let y =
   let x = 50 in
    3 * x * x + 4 * x + 5 = 0 ;;
val y : bool = False

On peut de même définir des couples ou partager des valeurs entre plusieurs résultats de manière à éviter de les recalculer :

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

Sans surprise, si une liaison globale peut contenir des liaisons locales et si une liaison locale peut elle-même contenir d'autres liaisons locales, une liaison globale a toujours lieu au plus haut niveau, jamais à l'intérieur d'une expression. En d'autres termes, un calcul ne peut pas avoir comme effet secondaire de faire apparaître une nouvelle liaison globale. Ce comportement est similaire à celui de Java ou C#, par opposition à celui de JavaScript, Python ou Ruby.

Ce mécanisme de liaison locale est utilisé notamment :

• à l'intérieur de fonctions
• pour retenir des valeurs intermédiaires mais pas intéressantes lors d'un calcul
• pour masquer des informations et des fonctions avec plus de finesse que protected ou private dans les langages objets (la technique est en fait plus proche du masquage utilisé en JavaScript).

Note Un nom de variable commence toujours par une minuscule ou le caractère _. Les identificateurs commençant par des majuscules sont réservées aux constructeurs et aux noms de modules, dont nous discuterons plus tard. Tenter d'utiliser un nom commençant par une majuscule en tant que variable provoque une erreur de syntaxe parfois difficilement lisibles.

# let Pi = 3.14;
      ^^
Error: Unbound constructor Pi

Nous verrons plus tard ce que sont les constructeurs en OCaml.

À retenir

• L'instruction let sert à lier un nom globalement.
• Les instructions let ... in ... et ... where ... servent à lier un nom localement.
• Les variables ne changent pas de valeur durant le temps de leur définition.
• Le nom d'une variable commence toujours par une minuscule.
• Le message

Unbound value xxxxx

signifie que le nom xxxxx n'est pas lié (ou défini) dans ce contexte.

Fonctions

Syntaxe

Dans ce qui précède, nous avons déjà manipulé quelques fonctions

# float_of_int ( 5 ) ;;
- : float = 5

# abs ( -5 );;
- : int = 5

En OCaml, les fonctions sont des valeurs comme les autres, qui peuvent être déclarées à l'aide de let, manipulées, évaluées, passées en tant qu'argument ou qui peuvent elles-mêmes être le résultat de l'évaluation d'expressions ou d'autres fonctions. Pour définir une fonction, OCaml propose plusieurs syntaxes, entre lesquelles nous choisirons selon des critères essentiellement esthétiques :

# let  ajouter_un          = fun x -> x + 1 
  and  ajouter_deux ( x )  = x + 2 
  and  ajouter_trois x     = x + 3 
  and  (ajouter_quatre x)  = x + 4;;

val ajouter_un     : int -> int = <fun>
val ajouter_deux   : int -> int = <fun>
val ajouter_trois  : int -> int = <fun>
val ajouter_quatre : int -> int = <fun>

Avant de nous intéresser à la réponse d'OCaml, commençons par détailler ces quatre syntaxes. Notons aussi que nous aurions pu déclarer les quatre fonctions séparément ou sous la forme d'un quadruplet mais nous avons préféré utiliser let...and... pour habituer le lecteur à lire et à utiliser cette construction.

Vocabulaire Dans ces fonctions, on appelle x argument ou paramètre formel de la fonction, x+1 corps de la fonction et fun x -> x + 1 fonction anonyme, abstraction ou λ-expression. Tout comme une valeur liée à l'aide de let...in, l'argument x a une portée limitée au corps de la fonction. En fait, x est lié à l'intérieur de la fonction.

La première syntaxe fait appel au mot-clé fun (pour "function") et s'énonce "Le nom ajouter_un est lié à la fonction qui à tout x associe x + 1", soit encore, en langage plus mathématique, $ajouter\_un:x\longmapsto x+1$. Cette formulation met l'accent sur le fait qu'une fonction est une valeur comme une autre.

La deuxième syntaxe s'énonce "Pour tout x, la valeur de ajouter_deux ( x ) est x + 2", soit encore, en langage mathématique, $\forall x,ajouter\_deux(x)=x+2$." Le résultat est absolument équivalent à celui qu'on obtient avec la première syntaxe et le vocabulaire est le même, mais cette formulation met l'accent sur la présentation d'une fonction comme une famille de valeurs.

La troisième et la quatrième syntaxe sont des variantes sur la deuxième, et s'énoncent de la même manière. Nous nous sommes contentés de jouer sur le placement des parenthèses afin d'illustrer la signification de celles-ci. En effet, contrairement à la majorité des langages, dans lesquels il est obligatoire d'encadrer les arguments d'une fonction entre des parenthèse, en OCaml, ces dernières ne sont obligatoires que pour forcer les priorités et résoudre d'éventuelles ambiguïtés, tout comme les parenthèses dans une expression arithmétique ne sont obligatoires que pour forcer la priorité des opérations.

Note En OCaml, dans presque tous les cas, la syntaxe idiomatique est la plus courte. On définira donc généralement une fonction sous une forme proche de ajouter_trois.

Cette conception des parenthèses s'applique aussi lors de l'invocation de fonctions :

# ajouter_un (10) * 2 ;;
- : int = 22
# ajouter_un 10 * 2 ;;
- : int = 22
# ( ajouter_un 10 ) * 2 ;;
- : int = 22
# ajouter_un (10 * 2) ;;
- : int = 21
# 2 * ajouter_un (10) ;;
- : int = 22
# 2 * ajouter_un 10 ;;
- : int = 22
# 2 * ( ajouter_un 10 );;
- : int = 22
# ( 2 * ajouter_un ) 10 ;;
      ^
This function is applied to too many arguments, maybe you forgot a `;'

Nous nous intéresserons à ce message d'erreur un peu plus tard. Pour le moment, contentons-nous d'en déduire qu'une fonction -- qui n'est, par définition, pas un nombre -- ne peut pas être multipliée par 2 à l'aide de l'opérateur *. Du reste de l'échantillon, nous pouvons déduire que l'invocation de fonction est plus prioritaire que la multiplication et que le parenthésage n'est nécessaire que pour forcer la priorité.

Note En cas de doute sur la priorité des opérateurs et des opérations, ajoutez des parenthèses. C'est ce que font tous les programmeurs OCaml et ça évite bien des erreurs, surtout à partir du moment où vous définirez vos propres opérateurs.

Insistons sur le fait qu'une fonction est une valeur comme une autre. Ainsi, on peut parfaitement écrire une fonction dont le résultat est une autre fonction

# let multiplication = fun x ->
    fun y ->
      x * y ;;
let multiplication : int -> int -> int = <fun>

Ce résultat se lit "Le nom multiplication est lié à une fonction dont l'argument est un entier et dont le résultat est une fonction de l'ensemble des entiers vers l'ensemble des entiers." Cette fonction multiplication se manipule naturellement :

# let multiplication_par_5 = multiplication 5;;
val multiplication_par_5 : int -> int = <fun>

# multiplication_par_5 10 ;;
- : int = 50

En une seule étape, nous écririons

# ( multiplication 5 ) 10 ;;
- : int = 50

# multiplication 5 10 ;;
- : int = 50

Vocabulaire Dans ce qui précède, une fonction de la forme fun y -> x * y est appelée "clôture". Le terme désigne une fonction définie à l'intérieur d'une autre fonction et qui utilise des variables locales ou des arguments de la fonction qui la contient. On emploie parfois le terme (improprement) pour désigner n'importe quelle fonction locale.

De même, nous pouvons définir une fonction qui prend en argument une fonction et produit comme résultat une fonction :

# let appliquer_operation_postfixe =
   fun x ->
   fun y ->
   fun o ->
    o x y ;;
val appliquer_operation_postfixe : 'a -> 'b -> ('a -> 'b -> 'c) -> 'c = <fun>

# appliquer_operation_postfixe 5 10 multiplication;;
- : int = 50

# appliquer_operation_postfixe 5 10 max;;
- : int = 10

Nous reviendrons sous peu sur la manipulation de fonctions par des fonctions et sur le sens de ce type 'a -> 'b -> ('a -> 'b -> 'c) -> 'c.

Il est à noter que, tout comme une fonction peut être définie globalement à l'aide de let, elle peut être définie localement avec let...in.

Exercices

1. Définissez une fonction f qui accepte en argument un nombre à virgule x et calcule $x^{2}-2\times x+1$ .
2. Définissez une fonction presque_zero qui accepte en argument un nombre flottant epsilon et produit comme résultat une fonction qui, pour tout nombre flottant x, vérifie si -epsilon < x et x < epsilon.
3. À l'aide de f et de presque_zero, définissez une fonction presque_racine qui accepte en argument un nombre à virgule x et produit une deuxième fonction qui accepte en argument un nombre à virgule epsilon et vérifie si -epsilon < f(x) < epsilon .

Types

Maintenant que nous avons examiné la syntaxe, revenons à la réponse de OCaml lors de la définition de chacune des fonctions :

val ajouter_un     : int -> int = <fun>
val ajouter_deux   : int -> int = <fun>
val ajouter_trois  : int -> int = <fun>
val ajouter_quatre : int -> int = <fun>

La première ligne s'énonce "Nous venons de définir la valeur globale ajouter_un. Cette valeur est de type int -> int et il s'agit d'une fonction, que nous n'afficherons pas."

Note OCaml n'affichera jamais le contenu d'une fonction.

Plus en détail, le type int -> int est le type des fonctions à un seul argument, qui est un entier, et dont le résultat est un entier. Mathématiquement, en considérant int comme l'ensemble des entiers OCaml, ce type signifie que la fonction est prise dans l'ensemble $int\longrightarrow int$, ou encore $int^{int}$.

En Java, on écrirait :

public static int ...(int ...)

À l'inverse, en OCaml, c'est l'ordinateur qui détermine le type de la fonction en analysant ses arguments et son corps. Ici, l'analyseur de types a remarqué la présence d'une addition sur les entiers, qui détermine que x, le seul argument de la fonction, est un entier et que le résultat de la fonction est un entier. La fonction est donc de type int -> int.

Vocabulaire Lorsqu'un analyseur de types déduit automatiquement le type des valeurs au lieu de recourir à des annotations, on appelle ce processus l'inférence de types.

On peut s'interroger sur le comportement de l'analyseur lorsqu'il est confronté à des contraintes différentes, par exemple des contraintes qui imposent que x soit à la fois un entier et un nombre flottant. Observons :

# let f x = ( x + 1, x +. 1.0 ) ;;
                     ^
This expression has type int but is here used with type float

L'analyseur a conclu que le programme était erroné, puisqu'il partait à la fois du principe que x était un entier (pour additionner 1) et du principe que x était un nombre flottant (pour additionner 1.0). La réponse d'OCaml est donc que la fonction contient une erreur de types et que cette définition doit être refusée. En effet, on constate que f n'est pas définie :

# f 5 ;;
  ^
Unbound value f

On peut aussi s'interroger sur le comportement de l'analyseur lorsque x n'est pas contraint. Observons :

# let id x = x;;
val id : 'a -> 'a = <fun>

La réponse d'OCaml s'énonce "Nous venons de définir la valeur globale id. Cette valeur est de type pour tout type α, α -> α. Il s'agit d'une fonction."

Le type de la fonction id est dit polymorphe sur le paramètre α. Ainsi, on pourra utiliser id sur des entiers, des booléens ou n'importe quel autre type de données, fonctions y compris.

# id 5;;
- : int = 5
# id true;;
- : bool = true
# id 3.2;;
- : float = 3.2
# id ajouter_deux ;;
- : int -> int = <fun>
# id ( fun x -> x + 1 ) ;;
- : int -> int = <fun>

En Java ou C#, le polymorphisme paramétrique est connu sous le nom de "généricité" et est à la fois moins puissant, plus compliqué, plus lent, plus long à écrire et moins robuste que le polymorphisme paramétrique d'OCaml. Nous revisiterons fréquemment le polymorphisme, qui est présent à tous les niveaux d'OCaml, et qui constitue un outil puissant de réutilisation de code.

Note Dans le dernier exemple, nous avons passé comme argument à la fonction id la fonction ajouter_deux puis, plus tard, une λ-expression fun x -> x + 1. Passer en argument des fonctions nommées ou anonymes est une pratique courante en OCaml. On s'en sert notamment pour les parcours de structures de données, les boucles, etc.

Exercices

1. Que signifie le type de la fonction max de la bibliothèque standard d'OCaml ?
2. Que signifie le type de la fonction appliquer_operation définie précédemment ?
3. Sans écrire la fonction suivante, déterminez son type et déterminez ce qu'elle fait

let multiplie n f = 
  fun x -> n * ( f x ) ;;

1. Quel est le type d'une fonction à deux arguments qui ignore son premier argument et produit comme résultat son deuxième argument ?

Arguments supplémentaires

Jusqu'à présent, nous n'avons défini et manipulé que des fonctions acceptant un seul argument. Bien entendu, comme tous les autres langages de programmation, OCaml permet de manipuler des fonctions à plusieurs arguments.

En fait, ce n'est pas tout à fait vrai. Nous avons déjà manipulé une fonction à plusieurs arguments : la multiplication

# multiplication ;;
- : int -> int -> int

Comme nous pouvons le remarquer, le type de multiplication est int -> int -> int. Nous l'avons lu "La fonction multiplication accepte un argument de type int et produit un résultat qui est une fonction qui accepte à son tour un argument de type int et produit un résultat de type int." De fait, ce type peut aussi se lire "La fonction multiplication accepte deux arguments de type int et produit un résultat de type int."

Si nous souhaitons définir une fonction dont l'effet sera identique à multiplication, nous pouvons de nouveau employer plusieurs syntaxes équivalentes :

# let multiplication_2 = fun x y -> x * y ;;
val multiplication_2 : int -> int -> int = <fun>

# let mutiplication_2 = fun x -> fun y -> x * y ;;
val mutiplication_2 : int -> int -> int = <fun>

# let multiplication_2 x = fun y -> x * y ;;
val multiplication_2 : int -> int -> int = <fun>

# let multiplication_2 x y = x * y ;;
val multiplication_2 : int -> int -> int = <fun>

# let multiplication_2 = multiplication ;;
val multiplication : int -> int -> int = <fun>

La première syntaxe met en valeur le fait que multiplication_2 est une fonction à deux arguments dont le résultat est de multiplier ses arguments. La deuxième syntaxe met en avant le fait que multiplication_2 est une fonction à un argument dont le résultat est une fonction qui à son tour attend un argument avant de multiplier ces deux arguments. La troisième syntaxe insiste sur le fait que, pour tout x, multiplication_2 x est de nouveau une fonction qui à son tour attend un argument avant de multiplier cet arguments par x. La quatrième syntaxe présente la famille des valeurs multiplication_2 x y pour tout entier x et tout entier y, qui vaut alors x * y. Enfin, la dernière formulation présente le fait que multiplication_2 est la même opération que multiplication.

Ces quatre syntaxes sont presque équivalentes et tout aussi valables. Comme précédemment, on préfèrera la plus courte, c'est-à-dire ici la dernière. Lorsqu'un tel raccourci n'est pas possible, on se rabattra sur la syntaxe précédente.

Insistons donc sur un fait : en OCaml, une fonction à plusieurs arguments est une fonction à un argument et dont le résultat est encore une fonction.

L'une des conséquences de cette conception des fonctions et qu'il est possible, avec une fonction à plusieurs arguments, de pré-appliquer la fonction certaines des valeurs de manière à obtenir une fonction spécialisée. Ainsi, on pourra écrire

# multiplication 2;;
- : int -> int = <fun>

# let f = multiplication 2 in f 4 ;;
- : int = 8

Vocabulaire La transformation d'une fonction à n arguments en une fonction à n-1 arguments s'appelle la currification. C'est une technique fréquemment employée en OCaml. Elle permet de composer aisément des fonctions et sert notamment pour construire aisément des fonctions à passer en argument à d'autres fonctions. Nous y reviendrons sous peu.

Une autre conséquence de cette conception des fonctions est qu'il n'existe pas, en OCaml, de fonction sans arguments. Nous reviendrons sur ce point un peu plus tard.

Exercices

1. Réécrivez les fonctions appliquer_operation, presque_zero et presque_racine sous une forme plus concise.
2. Définissez une fonction presque_racine_generique qui acceptera en argument une fonction f des nombres flottants vers les nombres flottants, une valeur flottante epsilon et une valeur flottante x et déterminera si -epsilon < f x et f x < epsilon .
3. Réécrivez la fonction presque_racine à partir de la fonction presque_racine_generique.

Fonctions et opérateurs

Avant d'approfondir notre étude des fonctions et d'introduire la notion de récursivité, arrêtons-nous un instant sur la définition des opérateurs. Tout comme en C++ ou en Python, en OCaml, les opérateurs sont en fait des fonctions. Ainsi, chaque utilisation de l'opérateur * est en fait un appel à la fonction ( * ) (les espaces et les parenthèses font partie du nom de la fonction), chaque utilisation de + est un appel à la fonction ( + )...

Nous pouvons donc écrire

# ( * ) ;;
- : int -> int -> int = <fun>

# ( * ) 5 10 ;;
- : int = 50

# ( +. ) 1.5 2.10 ;;
- : float = 3.6

# ( = ) 5 3 ;;
- : bool = False

# let multiplication = ( * ) ;;
val multiplication : int -> int -> int = <fun>

Vocabulaire L'opérateur * est la forme infixe de la multiplication alors que la fonction ( * ) est la forme préfixe de la multiplication. De base, en OCaml, il n'existe pas de formes postfixes.

En fait, lorsque l'analyseur syntaxique d'OCaml rencontre une expression de la forme x * y, celle-ci est comprise comme l'appel de fonction ( * ) x y. Ceci est important à savoir pour plusieurs raisons :

• les opérateurs d'OCaml peuvent être masqués tout comme les autres valeurs, ce qui permet de redéfinir localement la syntaxe des expressions arithmétiques, par exemple pour écrire naturellement des opérations sur des nombres complexes, des vecteurs, des fonctions ...
• de nouveaux opérateurs peuvent être ajoutés à OCaml, localement ou globalement, avec le même genre d'applications
• cette définition des opérateurs est la cause de messages d'erreur parfois surprenants.

Ainsi, revenons à l'erreur que nous avons rencontrée plus tôt :

# ( 2 * ajouter_un ) 10 ;;
      ^
This function is applied to too many arguments, maybe you forgot a `;'

On pourrait s'attendre à ce que 2 * ajouter_un provoque une erreur d'analyse de type -- rappelons que l'opérateur * ne concerne que des entiers et que ajouter_un n'est visiblement pas un entier. On peut aisément confirmer que la multiplication d'une fonction par deux n'est pas légale :

# 2 * ajouter_un ;;
      ^^^^^^^^^^
This expression has type int -> int but is here used with type int

Cependant, ce n'est pas l'erreur que nous rapporte OCaml. En fait, pour comprendre ce message, il faut se souvenir que l'extrait

( 2 * ajouter_un ) 10

est compris comme

( ( * ) 2 ajouter_un ) 10

ou encore, en supprimant les parenthèses inutiles,

( * ) 2 ajouter_un 10

En d'autres termes, la fonction ( * ) est bien appliquée à trois arguments, 2, ajouter_un et 10. Comme la fonction ( * ) n'accepte que deux arguments, l'erreur rencontrée par OCaml est effectivement une erreur sur le nombre d'arguments.

Récursivité

De nombreuses fonctions mathématiques et informatiques nécessitent la répétition d'une opération un grand nombre de fois ou jusqu'à ce qu'une condition soit remplie. Ainsi, pour calculer le nème terme d'une suite définie par récurrence, on aura souvent besoin de commencer par calculer tous les termes précédents. De même, pour chercher numériquement la limite d'une fonction ou d'une suite, on aura souvent besoin de répéter des approximations jusqu'à obtenir deux termes successifs suffisamment proches, ou pour calculer le contour de l'ensemble de Mandelbrot, on répétera des calculs complexes un nombre limité de fois ou jusqu'à avoir dépassé un module donné. Du côté informatique du terme, pour traiter un grand nombre d'informations en provenance d'un périphérique tel que le clavier ou un capteur, on appliquera une fonction à chaque information reçue jusqu'à l'arrivée d'un contre-ordre ou d'un changement de configuration. Enfin, pour de nombreux problèmes mathématiques et informatiques, chercher la solution nécessite de se ramener constamment à des sous-problèmes de plus en plus simples jusqu'à être confronté à des questions élémentaires. C'est ainsi que l'on trouve la solution à des problèmes de recherche de chemins dans des cartes géographiques (méthode A* hiérarchique), qu'on calcule la valeur d'une expression arithmétique ou logique complexe, qu'on localise une valeur dans un arbre ou qu'on analyse les interactions entre corps célestes dans une approximation numérique du problème des n corps par quad-trees.

Tous ces comportements se traitent de la même manière. Dans la majorité des langages de programmation, on emploie les boucles impératives for et while ou repeat -- nous laisserons provisoirement de côté les boucles for-each et autres compréhensions présentes dans certains langages récents dont OCaml Batteries Included. En Objective Caml, si tous ces mécanismes sont disponibles, nous allons commencer par étudier le mécanisme plus général de récursivité, qui reprend en informatique les notions mathématiques de récurrence et d'induction structurelle.

Le principe de la récursivité est simple :

• si vous savez ce qu'est la récursivité, vous avez votre réponse
• si vous ne savez pas ce qu'est la récursivité, trouvez quelqu'un qui est plus proche que vous de Douglas Hofstadter et posez-lui la question. (Citation en substance, attribuée à Andrew Plotkin).

En pratique, on considérera plutôt l'approche suivante :

• si le problème est suffisamment simple pour pouvoir déterminer la solution par une manipulation simple, procéder à cette manipulation
• si le problème est plus complexe, commencer par le simplifier en un ou plusieurs problèmes plus simples de même structure, résoudre chacun de ces sous-problèmes, puis combiner les sous solutions pour les transformer en une solution au problème complet.

Illustrons ceci par le calcul de la somme des nombres de m à n :

• si n est inférieur à m, cette somme est nulle
• sinon, il suffit de calculer la somme des nombres de m + 1 à n et de lui ajouter m.

En OCaml, cette définition se traduira par

# let rec somme_des_nombres m n =
    if n < m then
      0
    else
      m + ( somme_des_nombres ( m + 1 ) n ) ;;
val somme_des_nombres : int -> int -> int = <fun>

# somme_des_nombres 1 5 ;;
- : int = 15

Le mot-clé rec introduit une fonction récursive, c'est-à-dire donc une fonction qui peut s'appeler elle-même. Sans ce rec, somme_des_nombres ne serait pas lié à l'intérieur du corps de la fonction. On obtiendrait donc :

# let somme_faux m n =
    if n < m then
      0
    else
      m + ( somme_faux ( m + 1 ) n ) ) ;;
            ^^^^^^^^^^
Unbound value somme_faux

Attardons-nous un moment sur l'évaluation de somme. Pour obtenir des détails sur l'utilisation d'une fonction, la ligne de commande OCaml dispose de l'instruction #trace :

# #trace somme ;;
somme_des_nombres is now traced.

# somme 1 3;;
somme <-- 1
somme --> <fun>
somme* <-- 3
somme <-- 2
somme --> <fun>
somme* <-- 3
somme <-- 3
somme --> <fun>
somme* <-- 3
somme <-- 4
somme --> <fun>
somme* <-- 3
somme* --> 0
somme* --> 3
somme* --> 5
somme* --> 6
- : int = 6

Cette réponse sera plus compréhensible avec quelques annotations :

# somme 1 3 ;;    (* Évaluons somme 1 3                                *)

(* Début de l'évaluation de somme 1 3                                  *)
somme <-- 1       (* pour ce faire, évaluons  somme 1                  *)
somme --> <fun>   (* le résultat est une fonction                      *)
somme* <-- 3      (* évaluons ce résultat appliqué à 3                 *)
                              (* l'évaluation de somme 1 3 commence                *)
                              (* cette évaluation fait appel à la valeur somme 2 3 *)

 (* Début de l'évaluation de somme 2 3                                 *)
 somme <-- 2      (* Évaluons donc somme 2                             *)
 somme --> <fun>  (* le résultat est une fonction                      *)
 somme* <-- 3     (* évaluons ce résultat appliqué à 3                 *)
                              (* l'évaluation de somme 2 3 commence                *)
                              (* cette évaluation fait appel à la valeur somme 3 3 *)

  (* Début de l'évaluation de somme 3 3                                            *)
  somme <-- 3     (* Évaluons donc somme 3                             *)
  somme --> <fun> (* le résultat est une fonction                      *)
  somme* <-- 3    (* évaluons ce résultat appliqué à 3                 *)
                              (* l'évaluation de somme 3 3 commence                *)
                              (* cette évaluation fait appel à la valeur somme 4 3 *)

   (* Début de l'évaluation de somme 4 3                               *)
   somme <-- 4    (* Évaluons donc somme 3                             *)
   somme --> <fun>(* le résultat est une fonction                      *)
   somme* <-- 3   (* évaluons ce résultat appliqué à 3                 *)
                              (* l'évaluation de somme 3 3 commence    *)
          (* Nous avons toutes les informations nécessaires pour évaluer somme 4 3 *)
   somme* --> 0   (* Le résultat de cette évaluation est 0             *)
   (* Fin de l'évaluation de somme 4 3                                 *)

          (* Nous avons toutes les informations nécessaires pour évaluer somme 3 3 *)
  somme* --> 3    (* Le résultat de cette évaluation est 3 + 0, soit 3 *)
  (* Fin de l'évaluation de somme 3 3                                  *)

          (* Nous avons toutes les informations nécessaires pour évaluer somme 2 3 *)
 somme* --> 5     (* Le résultat de cette évaluation est 2 + 3, soit 5 *)
 (* Fin de l'évaluation de somme 2 3                                   *)

          (* Nous avons toutes les informations nécessaires pour évaluer somme 1 3 *)
somme* --> 6      (* Le résultat de cette évaluation est 1 + 5, soit 6 *)
(* Fin de l'évaluation de somme 1 3                                    *)
- : int = 6

Ainsi, pour évaluer somme 1 3, OCaml aura commencé par se ramener au cas somme 2 3 puis au cas somme_des_nombres 3 3 puis encore au cas somme 3 4, qui lui se calcule directement. À partir du résultat de somme 3 4, il est aisé de reconstruire le résultat de somme 3 3, qui lui-même permet de reconstruire aisément le résultat de somme 3 2, qui lui-même permet de reconstruire aisément le résultat de somme 3 1.

Note En termes d'expressivité, le mécanisme de récursivité est exactement aussi puissant que les boucles impératives présentes dans la majorité des langages de programmation. En pratique, il est plus simple de traduire un programme écrit à l'aide d'une boucle impérative en un programme écrit à l'aide d'une boucle récursive que de faire la manipulation inverse. En effet, dans la majeure partie des cas, implanter un algorithme récursif à l'aide d'une boucle impérative nécessite de manipuler des structures de piles contenant elles-même des structures de données peu lisibles.

Notre boucle récursive n'a pas à être déclarée au plus haut niveau. On peut aussi la cacher à l'intérieur de la fonction, à l'aide de let...in. Ainsi, en appelant aux la boucle récursive, on obtiendra :

# let somme m n =
    let rec aux m' n' =
      if n' < m' then
        0
      else
        m' + ( aux ( m' + 1 ) n' ) ) 
    in
      aux m n;;

val somme : int -> int -> int = <fun>

Comme nous pouvons l'observer dans ce qui précède, à chaque appel récursif de aux, le nom n' reste lié à la valeur de n. Ainsi, au lieu d'utiliser n', nous pouvons donc utiliser directement m. Nous obtenons alors

# val somme m n =
    let rec aux m' =
      if n < m' then
        0
      else
        m' + ( aux ( m' + 1 ) n ) ) 
    in
      aux m;;

val somme : int -> int -> int = <fun>

Notons que le nom m' tient ici un rôle similaire à celui d'une variable compteur i dans une boucle impérative for(int i = 0; i <= ... ; ++i). Notons aussi que, dans cet exemple, l'intérêt principal d'avoir transformé la définition pour faire intervenir une boucle aux est de se débarrasser des arguments inutiles (ici n'). Dans des programmes complexes, il sera fréquemment utile de faire intervenir des fonctions/boucles de cette forme.

Note La somme des nombres de 1 à n peut très bien s'écrire en une seule ligne à l'aide de 1 -- n. Cette deuxième méthode est plus succinte et plus lisible mais fait appel à des concepts plus avancés et que nous ne rencontrerons que dans un chapitre ultérieur.

La structure employée sera la même lorsque nous chercherons à définir la fonction factorielle. Rappelons que, mathématiquement, la factorielle peut se définir par récurrence sur l'ensemble des entiers par

• si n < 1 alors factorielle(n) = 1
• si n >=1 alors factorielle(n) = n * factorielle ( n - 1 ).

On écrira donc de même

# let rec factorielle n =
   if n = 0 then 1
   else          n * ( factorielle ( n - 1 ) ) ;;
val factorielle : int -> int = <fun>

# factorielle 5 ;;
- : int = 120

Ce que nous pourrons aussi réécrire en cachant la boucle

# let factorielle n =
   let rec aux n' =
    if n' = 0 then 1
    else           n * ( aux ( n - 1 ) ) 
   in aux n ;;
val factorielle : int -> int = <fun>

# factorielle 5 ;;
- : int = 120

Dans les exemples qui précèdent, nous nous sommes toujours ramenés à un cas plus simple en incrémentant et en décrémentant un entier de 1, à l'image d'une boucle for. Bien entendu, la récursivité ne se limite pas à ce type de cas. Ainsi, l'algorithme d'exponentiation rapide, qui permet de calculer $a^{n}$ sans procéder à n multiplications, emploie une structure légèrement plus compliquée.

La définition mathématique de cet algorithme est la suivante :

• $a^{0}=1$
• $\forall k,a^{2\cdot k}=(a^{k})^{2}$
• $\forall k,a^{2\cdot k+1}=a\cdot (a^{k})^{2}$.

Rappelons que la notation "2k" signifie "un nombre pair n pour lequel nous noterons k = n/2. De même, "2k+1" signifie "un nombre impair n pour lequel nous noterons k = (n-1)/2." Cette définition se traduit par

• si n=0, le résultat est 1
• si n>0 et si n est pair, commençons par calculer $x=a^{n/2}$ ; le résultat est alors $x^{2}$
• si n>0 et si n est impair, commençons par calculer $x=a^{\lfloor n/2\rfloor }$ ; le résultat est alors $x^{2}\cdot a$

En OCaml, on écrira donc :

# let rec puissance a n =
   if n = 0 then 1
   else 
     if n mod 2 = 0 then let x = puissance a ( n / 2 ) in x * x
     else                let x = puissance a ( n / 2 ) in x * x * a ;;
val puissance : int -> int -> int = <fun>

En fait, on préfèrera modifier légèrement cette définition pour calculer x et x * x une seule fois :

# let rec puissance a n =
   if n = 0 then 1
   else 
     let x = puissance a ( n / 2 ) in
     let y = x * x                 in
       if n mod 2 = 0 then y
       else                y * a;;
val puissance : int -> int -> int = <fun>

Notons que la récursivité ne se limite pas à une fonction s'appelant elle-même. Ainsi, lors de l'analyse de langages de programmation, voire de langages humains, il est courant de se retrouver confronté à des dizaines ou des centaines de fonctions mutuellement récursives. Nous rencontrerons cec genre d'exemple à la fin du prochain chapitre. Pour le moment, nous nous contenterons d'une méthode extraordinairement complexe pour déterminer la parité d'un nombre positif :

# let rec pair   n = n <> 1 && ( n = 0 || impair ( n - 1 ) )
  and     impair n = n <> 0 && ( n = 1 || pair   ( n - 1 ) ) ;;
val pair   : int -> bool = <fun>
val impair : int -> bool = <fun>

# pair 5;;
- : bool = false
# pair 6;;
- : bool = true

Le mécanisme de récursivité reviendra à tous les niveaux dans OCaml.

Exercice

1. Définissez une fonction somme_des_carres m n qui calcule la somme des carrés des entiers entre m et n.
2. Réécrivez la fonction factorielle de manière à changer l'ordre d'intervention des nombres. Dans la version présentée plus haut, le cas de base renvoie 1, qu'on multiplie successivement par 2 ... n. Inversez cet ordre.
3. Écrivez une fonction pgcd en partant de la définition suivante :

• pgcd (2m, 2n) = 2 pgcd (m, n)
• pgcd (2m, 2n+1) = pgcd (m, 2n+1)
• pgcd (2m+1, 2n+1) = pgcd(n-m, 2m+1) lorsque m<n
• pgcd (m,m) = m.

Rappelons que la notation mathématique 2m signifie "un nombre pair p pour lequel nous noterons m = p/2", et 2m+1 signifie "un nombre impair i pour lequel nous noterons m = (i-1)/2".

1. De la même manière que pair et impair, écrivez trois fonctions mutuellement récursives pour déterminer si un nombre est divisible par 3 ou si le reste de sa division par 3 est 1 ou si le reste de sa division par 3 est 2.

Réutilisation de fonctions

De la même manière que nous avons défini la somme des nombres entre m et n, nous pouvons définir le produit des nombres entre ces bornes :

# let rec produit_des_nombres m n =
    if n <= m then      1
    else                m * ( produit_des_nombres ( m + 1 ) n ) ) ;;
val produit_des_nombres : int -> int -> int = <fun>

En tout et pour tout, nous avons changé

• le nom de la fonction
• le 0, remplacé par 1
• l'addition, remplacée par une multiplication.

Face à ces deux fonctions extrêmement proches, le réflexe du programmeur OCaml sera de chercher comment écrire une seule fonction qui pourra être spécialisée pour devenir l'une ou l'autre. C'est le processus d'abstraction, qui à la source de la réutilisation de code et du développement de bibliothèques puissantes de programmation.

Note Le terme de "patrons de conception" (design patterns) n'existe pas en programmation fonctionnelle. Cependant, s'il existait, le processus d'abstraction figurerait en deuxième place dans la liste des patrons de conception, juste après le développement de fonctions polymorphes paramétriques.

Pour écrire une telle fonction,

• choisissons un nom pour notre fonction abstraite -- mettons segment_fold_right
• faisons du 0 (devenu un 1 dans le produit) une valeur v, qui sera un argument de notre fonction
• faisons de l'addition (devenue une multiplication dans le produit) une valeur f, qui sera aussi un argument de notre fonction
• n'oublions pas de passer v et f à operation_sur_intervalle lors de l'invocation récursive.

La transformation produit donc :

# let rec operation_sur_intervalle f v m n =
    if n <= m then v
    else           f m ( operation_sur_intervalle f v ( m + 1 ) n ) ;;
val operation_sur_intervalle : (int -> 'a -> 'a) -> 'a -> int -> int -> 'a =
  <fun>

ou encore

# let operation_sur_intervalle f v m n =
    let rec aux m' =
      if n <= m' then v
      else            f m' ( aux ( m' + 1 ) )
    in aux m;;

À partir de là, nous pouvons obtenir de nouveau la somme et le produit des nombres en appliquant directement notre nouvelle fonction (rappelons que ( + ) et ( * ) sont les fonctions correspondant aux opérateurs + et *) :

# let somme_des_nombres_2   = operation_sur_intervalle ( + ) 0 ;;
val somme_des_nombres_2 : int -> int -> int = <fun>

# let produit_des_nombres_2 = operation_sur_intervalle ( * ) 1 ;;
val produit_des_nombres_2 : int -> int -> int = <fun>

À ce prix-là, nous pouvons définir en une ligne la fonction factorielle, la somme des carrés des entiers...

# let factorielle_2         = produit_des_nombres_2 1 ;;
val factorielle_2 : int -> int = <fun>

# let somme_des_carres_2    = operation_sur_intervalle ( fun x acc -> x * x + acc ) 0 ;;
val somme_des_carres_2 : int -> int -> int = <fun>

On peut aussi construire à partir de operation_sur_intervalle des fonctions similaires qui permettront de travailler sur les carrés des éléments d'un intervalle ou sur les nombres x de l'intervalle tels que p x est vrai ou sur les nombres impairs de l'intervalle...

# let operation_sur_carres_intervalle f v = operation_sur_intervalle ( fun x acc -> f ( x * x ) acc ) v ;;
val carres_fold_right : (int -> 'a -> 'a) -> 'a -> int -> int -> 'a = <fun>

# let operation_sur_intervalle_filtre f p v = operation_sur_intervalle (fun x acc -> if p x then f x acc else acc);;
val filtre_fold_right :
  (int -> 'a -> 'a) -> (int -> bool) -> 'b -> 'a -> int -> int -> 'a = <fun>

# let operation_sur_nombres_pairs_intervalle f = operation_sur_intervalle_filtre f ( fun x -> x mod 2 = 0 ) ;;
val operation_sur_nombres_pairs_intervalle : (int -> 'a -> 'a) -> 'b -> 'a -> int -> int -> 'a =
  <fun>

# let operation_sur_nombres_impairs_intervalle f = operation_sur_intervalle_filtre f ( fun x -> x mod 2 = 1 ) ;;
val operation_sur_nombres_impairs_intervalle : (int -> 'a -> 'a) -> 'b -> 'a -> int -> int -> 'a =
  <fun>

Cette possibilité d'abstraire des fonctions en des fonctions plus génériques qui seront plus tard spécialisées à l'aide d'arguments fonctionnels constitue l'un des avantages majeurs de la programmation fonctionnelle. On l'utilise notamment pour définir de nouveaux types de boucles sur des structures de données personnalisées -- tout comme ici sur les intervalles, les ensembles de nombres impairs, les ensembles de nombres impairs, etc. -- pour la gestion sûre des ressources externes, là où dans d'autres langages on emploierait try...finally, etc. Combiné avec la vérification de types d'OCaml, ceci permet de concevoir des bibliothèques sûres de manipulation de ressources et de structures de données.

Pour comparaison, en Java, cette notion d'intervalle s'écrirait de la manière suivante

//Définition de l'intervalle
public class Interval implements Iterable<Integer>
{
  //...
  public final int begin;
  public final int end;
  public Iterator<Integer> iterator ()
  {
    return new IntervalIterator(this.begin, this.end);
  }
}

//Définition de l'itération sur tous les entiers d'un intervalle d'entiers
public class IntervalIterator implements Iterator<Integer>
{
  private int current ;
  private final int end ;
  public IntervalIterator(int begin, int end)
  {
    this.current = begin;
    this.end     = end;
  }
  public final Integer next ()
  { 
    if(this.current < this.end)
      return this.current++;
    else
      throw new NoSuchElementException(this.current);
  }
  public void remove()
  {
     this.current++;
  }
  public bool hasNext()
  {
    return this.current < this.next ;
  }
}

//Calcul de la somme des entiers
public int sommeDesEntiers(int debut, int fin)
{
  int total = 0;
  for(Integer i : new Interval(debut, fin))
    total += i;
  return total;
}

Ajouter les filtres à cette version Java est possible mais compliquerait considérablement l'extrait.

D'autres langages, comme Python, emploient une syntaxe plus concise mais moins générique, spécialisée dans la définition de boucles sur les structures de données : les générateurs. Tout ceci est aussi disponible en OCaml, sous le nom d'énumérations, et sera détaillé plus tard.

Exercices

1. De la même manière que operation_sur_intervalle, définissez une fonction operation_sur_intervalle_inverse qui parcourra l'intervalle dans l'autre sens. Vous testerez qu'elle fonctionne en calculant à l'aide de cette fonction la somme des entiers dans divers intervalles.
2. Définissez une fonction similaire à operation_sur_intervalle_filtre mais qui n'applique son argument f qu'aux entiers x de l'intervalle tels que

• x soit divisible par 3 ou par 7
• et x vérifie le prédicat p (c'est-à-dire p x soit vrai).

Pour ce faire, vous réutiliserez operation_sur_intervalle_filtre.

Limitations et précautions

Affichage de fonctions

Comme nous l'avons noté, OCaml n'affiche jamais une fonction. En effet, les fonctions sont compilées immédiatement et leur représentation lisible oubliée. Après cela, il reste uniquement possible de consulter le type de la fonction.

Comparaison de fonctions

En OCaml, deux fonctions ne peuvent jamais être comparées à l'aide des opérateurs =, <, >, >=, <=, <>  :

# id < id ;
Exception: Invalid_argument "equal: functional value".

La raison à cette limitation est à l'intersection du monde des mathématiques et de celui de l'informatique. En effet, rappelons que, mathématiquement, si nous avons $\left\{{\begin{array}{cc}f:A\longrightarrow B\\g:A\longrightarrow B\end{array}}\right.$ alors, par définition, $\left\{{\begin{array}{cc}f=g\iff \forall x\in A,f(x)=g(x)\\f<g\iff \forall x\in A,f(x)<g(x)\\f>g\iff \forall x\in A,f(x)>g(x)\end{array}}\right.$ . En d'autres termes, pour comparer deux fonctions, il ne suffit pas de vérifier si elles ont été écrites de la même manière, mais il faut tester chacune des deux fonctions avec toutes les valeurs possibles. Ceci n'est pas faisable sur les machines actuelles -- et ne sera probablement jamais faisable, à moins que les machines quantiques fassent un jour leur apparition. Plutôt que de fournir une demi-solution, les programmeurs OCaml ont préféré jeter l'éponge et abandonner les comparaisons entre fonctions.

Malheureusement, l'analyseur de types d'OCaml n'est pas assez puissant pour déterminer lors de la compilation si l'opérateur = va être appliqué à deux fonctions. Cette vérification ne peut donc être effectuée que durant l'exécution, à l'instar des vérifications dynamiques de Java, C# ou de celles, omniprésentes, de Python, Ruby ou JavaScript.

Il reste possible de vérifier l'égalité physique entre deux fonctions à l'aide de l'opérateur ==. Cet opérateur, dont la sémantique est similaire à celle du même opérateur en Java, permet de vérifier si deux valeurs sont exactement la même (et non pas si elles ont le même résultat), comme suit :

# id == id ;;
- : bool = true
# id == ( fun x -> x );;
- : bool = false
# let x = id in id == x ;;
- : bool = true

Modulo

L'opérateur mod n'est pas associé à une fonction ( mod ). Il s'agit probablement du seul opérateur OCaml à ne pas être traduit sous la forme d'une fonction portant le même nom. Sans entrer dans les détails pour le moment, tous les autres opérateurs OCaml sont gérés par le même mécanisme d'analyse syntaxique, alors que mod dispose d'un mécanisme pour lui seul.

Il s'agit d'une irrégularité mineure dans le langage OCaml. Il semble probable que cette irrégularité sera corrigée dans la prochaine version majeure, dans laquelle la gestion des opérateurs est en cours de révision.

Couples d'arguments

Le premier réflexe d'un programmeur habitué à un autre langage de programmation est généralement de définir une fonction à plusieurs arguments avec la syntaxe suivante :

# let multiplication_2 ( x, y ) = x * y;;
val multiplication_2 : (int * int) -> int = <fun>

Cette syntaxe est tout à fait légitime mais, comme on peut le constater en examinant le type du résultat, elle ne produit pas la même fonction que multiplication. En effet, le type de multiplication place cette fonction dans l'ensemble $int\longrightarrow (int\longrightarrow int)$, c'est-à-dire $int^{int^{int}}$. À l'inverse, le type de multiplication_2 place cette fonction dans l'ensemble $(int\times int)\longrightarrow int$ ou encore $int^{int\times int}$.

Ceci est du au fait que ( x, y) représente, comme en mathématiques, le couple $(x,y)$, pris dans l'ensemble $int\times int$, c'est-à-dire le type int * int. En OCaml, on préférera généralement l'approche présentée avec multiplication, qui favorise la réutilisation et la composition de fonctions.

Mémoire des résultats

Précisons que, par défaut, OCaml ne garde pas en mémoire les résultats d'un calcul. Ainsi, si l'on invoque

# factorielle 5 ;;
- : int = 120

# factorielle 6 ;;
- : int = 720

Le calcul de factorielle 6 ne réutilisera aucun des résultats de factorielle 5. Ce comportement par défaut, commun à presque tous les langages de programmation (sauf Maple et quelques autres langages spécialisés dans les mathématiques), vise à éviter de gaspiller la mémoire vive à retenir des résultats qui seront a priori probablement inutiles. Il est cependant possible de demander à OCaml de conserver ces résultats en mémoire, c'est le processus de mémoification. Nous verrons comment ajouter la mémoification dans le chapitre consacré à l'optimisation.

Profondeur de récursivité

Généralement, une fonction récursive écrite de manière naïve consommera plus de mémoire vive qu'une boucle impérative, en raison de la nécessité de retenir des informations pour rassembler les résultats des sous-problèmes. En particulier, une telle boucle récursive, si elle est appelée sur un échantillon trop long, provoquera un débordement de pile, c'est-à-dire une erreur fatale qui interrompra le calcul. Si la situation est moins grave que dans beaucoup de langages de programmation, grâce à la faible consommation de mémoire de OCaml, on cherchera à tirer le plus possible parti de la notion de boucles récursives terminales, que le compilateur OCaml est capable d'optimiser pour supprimer ce problème.

Nous discuterons plus avant cette récursivité terminale dans le chapitre consacré à l'optimisation. Pour le moment, nous nous contenterons de la définition informelle suivante : une fonction est récursive terminale si le résultat est entièrement construit lors de la division en sous-problèmes et non pas dans une phase ultérieure de reconstitution.

Les boucles récursives terminales ont exactement le même pouvoir expressif que les boucles impératives.

À retenir

• Les fonctions sont des valeurs comme les autres.
• Les appels de fonctions sont associatifs à gauche.
• Les parenthèses servent uniquement à forcer la priorité des opérations.
• Le message

This function is applied to too many arguments, maybe you forgot a `;'

désigne une erreur de typage : la fonction soulignée est appliquée à plus d'arguments qu'elle n'en accepte.

• Les valeurs sont typées automatiquement, y compris les fonctions polymorphes.
• Une fonction à plusieurs arguments est une fonction à un argument dont le résultat est encore une fonction.
• Un type qui fait intervenir 'a est dit polymorphe et la valeur de 'a peut être remplacé par n'importe quel type.
• Pour répéter un traitement, on fait appel à des boucles récursives, introduites par let rec....

À propos de la programmation fonctionnelle

Plus haut dans ce chapitre, nous avons défini la somme des nombres

# let rec somme_des_nombres m n =
    if n < m then       0
    else                m + ( somme_des_nombres ( m + 1 ) n ) ;;
val somme_des_nombres : int -> int -> int = <fun>

Comparons ceci à un équivalent écrit dans un langage impératif, ici Java :

public static int sommeDesNombres(int m, int n)
{
  int total = 0;
  for(int i = m; i <= n; ++i)
    total += i;
  return total;
}

Les deux extraits sont de taille sensiblement équivalente et beaucoup de programmeurs auront plus de facilité à lire le code Java, peut-être parce qu'ils ont généralement été formés sur des langages impératifs.

La philosophe impérative de Java recommande d'utiliser deux variables intermédiaires total et i, dont la valeur va changer plusieurs fois au cours de l'exécution de la fonction. Au contraire, la philosophie fonctionnelle d'OCaml recommande de ne jamais réaffecter une valeur à une variable existante mais plutôt de se ramener au cas où la valeur de la variable est différente, de la même manière qu'en mathématiques -- ici en appelant récursivement la fonction somme_des_nombres.

Dans l'absolu, aucune des deux philosophies n'est meilleure. L'une d'entre elles provient du monde de la Physique, dans lequel il est normal que l'état de l'univers change en permanence. L'autre provient du monde des Mathématiques, dans lesquelles le modèle est immuable mais on peut se placer dans des cas différents. Peut-être l'histoire de l'informatique aurait-elle été différente si les premiers programmeurs avaient été plus mathématiciens que physiciens, mais depuis la machine de Von Neumann le modèle sous-jacent à la partie électronique des ordinateurs est un modèle dans lequel l'univers change effectivement en permanence, sous la forme de modifications de la mémoire vive ou du disque dur.

Employer l'approche physique/impérative permet de représenter naturellement des interactions avec le monde extérieur au programme (afficher quelque chose à l'écran ou sauvegarder un fichier, par exemple), qui n'ont pas de contrepartie simple en mathématiques. Cependant, comme c'est fréquemment le cas dès qu'il s'agit de l'interaction entre Physique et Mathématiques, si l'approche Physique permet d'avancer plus rapidement vers un résultat qui semble correct à première vue, l'approche Mathématique est nécessaire dès qu'il s'agit de s'assurer que les résultats sont effectivement corrects et réutilisables. Dans le monde de l'informatique, cela signifie qu'un développeur lambda produira souvent plus vite un programme impératif qu'un programme fonctionnel, mais qu'il sera plus difficile d'être certain que le programme fonctionne effectivement et que le programme sera fréquemment moins réutilisable. En effet, l'approche plus rigoureuse de la programmation fonctionnelle demandera au développeur plus de réflexion avant d'écrire son programme -- ou en tout cas avant d'arriver à le compiler -- mais vérifiera automatiquement plus de propriétés de sûreté et garantira par construction des propriétés telles que la réutilisabilité du code (un code qui ne modifie pas l'état de l'univers peut être utilisé dans n'importe quelles circonstances) ou l'optimisation du code (un code qui ne modifie pas l'état de l'univers peut être transformé en code parallèle, exécuté sur un autre microprocesseur ou un autre ordinateur, sans avoir à changer le reste du programme).

Encore une fois, cela ne signifie pas qu'une philosophie est meilleure que l'autre. Les deux états d'esprit sont nécessaires pour faire progresser un projet ou l'informatique dans son ensemble.

Bilan du chapitre

Au cours de ce chapitre, nous avons couvert

• l'installation d'OCaml
• le lancement d'OCaml en ligne de commande
• l'utilisation d'OCaml en tant que calculatrice, les entiers, les nombres à virgule flottante et les booléens
• la définition et l'utilisation de nouvelles valeurs et la notion de liaison
• la définition et l'utilisation de fonctions
• la currification de fonctions
• l'abstraction de fonctions pour permettre leur réutilisabilité
• la notion de types, de types de fonctions, de types polymorphes.
• les messages d'erreur qui vont avec tout cela.

Dans le prochain chapitre, nous allons couvrir plus en profondeur la notion de types et de structures de données.