Nous introduisons les principes de bases de la programmation fonctionnelle, ceux qu'il faudra garder à l'esprit tout au long du cours. Nous établissons donc en quoi la programmation fonctionnelle se distingue de la programmation impérative.
Un avertissement préalable : OCaml est un langage multi-paradigme, on peut donc l'utiliser pour la programmation impérative, objet ou fonctionnelle. Ce qui suit n'est valide pour OCaml que lorsqu'on se restreint à la partie fonctionnelle du langage, ce que nous ferons la plupart du temps dans le cadre de ce cours, mais qui n'est pas toujours le cas des ressources disponibles sur Internet (le programmeur OCaml est en général pragmatique et utilise le style le plus approprié à ses besoins).
On peut différencier programmation impérative et fonctionnelle en distinguant deux motivations.
Prenons un exemple plus parlant : le calcul de la somme des éléments d'une liste. En Java (tout du moins avant la version 8), on écrirait :
ce qui se comprend comme : appelle une case mémoire sum avec un contenu $0$, puis pour chaque élément de la liste, ajoute la valeur de cette élément au contenu de sum et stocke le résultat dans sum. Après l'énumération, le résultat du calcul est le contenu de sum.
En OCaml, il existe deux manières de le faire. La première est simplement de dire : le résultat de l'addition des éléments de la liste. Ce qui avec la syntaxe donne :
Cela semble ésotérique pour le moment, mais c'est juste une retranscription de la formule mathématique $\sum \texttt{integers}$ (ou bien $\sum_{i \in \texttt{integer}} i$) dans la syntaxe d'OCaml.
La deuxième façon décrit le résultat selon la nature de la liste : vide ou non.
En ligne 2 , la fonction définit le cas de la liste vide. En ligne 3 , elle définit le cas de la liste non-vide, en donnant un nom au premier élément, et un nom à la liste des éléments suivants. Le résultat est donc la somme du premier élément avec la somme des autres éléments. Il n'y a pas eu besoin de décrire une suite d'opérations.
Puisqu'un programme décrit une construction, et non une suite d'actions, les programmes fonctionnels ne contiennent pas d'instructions. On rappelle les principales instructions en programmation impérative : assignations, sauts, boucles (while, for, etc.), instructions conditionnelles (if), entrée-sorties. Ainsi, les programmes fonctionnels ne contiennent que des expressions, par exemple les expressions arithmétiques ou booléennes, l'expression conditionnelle (en C, <condition> ? <valeur si vrai> : <valeur si faux>). À cela, on ajoute les définitions de fonctions, qui sont aussi considérés comme des expressions. Clairement, ce sont donc les fonctions qui vont nous fournir le potentiel d'écrire des programmes intéressants (ce qui peut expliquer le terme de programmation fonctionnelle).
Un programme fonctionnel est donc une suite d'expressions, dont les valeurs seront calculées, lors de l'interprétation, ou lors de l'exécution du programme compilé. L'interpréteur écrit le résultat de ces évaluations (ce qui n'est pas le cas du programme compilé). Voici un exemple très simple de programme :
Nous avons dit que les calculs ne dépendent pas de l'environnement. Du coup, toute expression, lorsqu'elle est calculée (on dit plutôt évaluée), fournit toujours le même résultat, la même valeur. À chaque expression est donc associée sa valeur. Pour certaines expressions, par exemple celle correspondant à un nombre, cela semble assez naturel. Ce l'est peut-être moins pour les expressions correspondant à des fonctions : nous considérerons en effet que les fonctions sont aussi des valeurs, au même titre que les entiers. Une deuxième raison d'appeler fonctionnel ce style de programmation.
Plus exactement, la valeur d'une expression dépend de la valeur des variables apparaissant dans cette expression, mais définies à l'extérieur de l'expression. On dit que ces variables sont libres dans l'expression. La valeur d'un expression est toujours la même pour un choix de valeurs des variables libres. Par exemple l'expression x+3 a pour valeur 3 si x vaut 0 , et a pour valeur 4 si x vaut 1 . En revanche l'expression let x = 1 in x+3 vaut toujours 4 , puisque x est défini à l'intérieur de cette expression.
Prenons un exemple plus compliqué. Supposons une fonction $f$ déjà définie, avec un argument entier et retournant un entier. Considérons l'expression
Quelle que soit la définition de la fonction f, are_equals sera nécessairement vrai. Ce qui n'est pas vrai en programmation impérative. L'expression f 5 + 3, qu'elle soit en ligne 2 ou en ligne 3 , aura nécessairement la même valeur, puisque dans les deux cas f désigne la même valeur. Donc are_equals sera true. Peu importe la définition de f.
En Java, cela ne fonctionne pas :
En ce sens, en programmation fonctionnelle, dans un même contexte (dans notre exemple, si f est fixé) une expression s'évalue toujours en la même valeur. Ce qui peut sembler être une restriction s'avère être en réalité un avantage déterminant : cette propriété garantit que toute partie du programme peut être comprise localement, indépendamment du reste du programme. Il est alors plus facile de raisonner sur le programme puisque rien n'est caché, et de le refactorer puisque tout est local.
La notion d'instruction n'existe donc pas en programmation fonctionnelle. Un programme fonctionnel n'est pas une suite d'instructions à exécuter les unes après les autres. Si on retrouvera certaines formes qui sont des instructions dans les langages impératifs, ce sont en OCaml des expressions aussi. Par exemple, on peut construire une expression avec if <expr> then <expr> else <expr>, cette phrase est une expression, pas une instruction.
Cela permet d'écrire légalement (mais on évitera car ce n'est pas lisible, et qu'on peut faire plus simple), pour vérifier si a est plus grand que b et c :
Ainsi, l'expression conditionnelle entre parenthèses peut apparaître comme membre droit d'une comparaison, ce qui n'est pas possible avec l'instruction conditionnelle de Java ou de C (on utiliserait du coup une expression conditionnelle b > c ? b : c ).
C'est donc un principe simple : en programmation fonctionnelle, tout fragment bien formé de programme est une expression. Chaque expression peut être évaluée (par l'interprêteur ou lors de l'exécution), le résultat de l'évaluation est une valeur. Par exemple, l'expression 19 + 23 s'évalue en 42. Chaque valeur a un type, dans cet exemple 42 est de type int, le type des entiers. Du coup, à toute expression on peut aussi associer un type, qui correspond au type de la valeur prise par l'évaluation de cette expression. Dans l'exemple du test de maximalité de a, l'expression conditionnelle possède donc une valeur et un type (ce qui est heureux si on souhaite évaluer la comparaison).
Ainsi toutes les expressions sont typés. Bien sûr les types doivent respecter certaines règles, qui assurent que le programme est bien typé. Le rôle des types est le même qu'en programmation impérative : s'assurer que le programme a du sens. Une erreur de type signale une incompréhension importante de la part du programmeur. Les types sont donc une aide pour écrire des programmes corrects (bien sûr, un programme correctement typé n'est pas nécessairement correct, mais s'il n'est pas correctement typé, il est certainement faux).
En OCaml, les types sont automatiquement déduits par le compilateur. Le programmeur n'a pas besoin d'indiquer les types des variables qu'il définit, le compilateur trouvera tout seul dans la majorité des cas (semblable à l'annotation auto de C++). S'il ne trouve pas de type, c'est que le programme n'est pas typable, donc faux. C'est possiblement l'aspect le plus frustrant d'OCaml pour un débutant : attendez-vous à avoir de très nombreux messages d'erreurs du compilateur, qui vous indiquera les expressions non-typables.
Puisque les fonctions sont des valeurs, au même titre que les entiers par exemple, les fonctions ont aussi des types. Attention, nous ne parlons pas là du type de retour de la fonction, c'est bien la fonction elle-même qui possède un type. L'univers des types envisageables est donc plus vaste et significativement plus riche qu'en programmation impérative. Nous verrons que les types peuvent se combiner entre eux pour créer d'autres types. En fait, les types vont prendre une place importante dans le travail de programmation, ce sont eux qui nous guideront dans l'écriture des programmes, en plus de leur rôle usuel de vérification du bon-sens du programme.
Notons enfin que certains langages fonctionnels sont non-typés, par exemple Lisp, Clojure ou Erlang. On pourrait donc dire que les types sont orthogonaux à la programmation fonctionnelle, mais nous verrons qu'en fait, les deux concepts s'enrichissent mutuellement au point qu'il serait dommage de ne pas les utiliser ensemble.
Les programmes sont organisés en modules. Chaque module contient un morceau cohérent du programme, généralement assurant un rôle ou une responsabilité précis. En ce sens, les modules ont un rôle proche des objets en programmation objet.
Tout fichier source définit un module, mais on peut aussi définir des modules à l'intérieur de chaque fichier. Un module est une liste de définitions de valeurs, de types, et d'autres modules. Il est possible de restreindre les valeurs visibles depuis l'extérieur d'un module, un peu à la façon des méthodes publiques et privées des objets.
Les modules eux-mêmes sont des expressions, même si on ne les utilisera pas en tant qu'expressions dans le cadre de ce cours. Les modules ont donc aussi des types.
Nous expliquerons avec plus de détails les modules par la suite, mais pour l'instant, retenons que tout morceau de programme fait partie d'un module, et qu'un module est une liste de définitions de valeurs et de types.
On retient donc bien les principes fondamentaux suivants. En OCaml :
