La programmation fonctionnelle est un paradigme de programmation de type déclaratif qui considère le calcul en tant qu'évaluation de fonctions mathématiques.

Comme le changement d'état et la mutation des données ne peuvent pas être représentés par des évaluations de fonctions^[1] la programmation fonctionnelle ne les admet pas, au contraire elle met en avant l'application des fonctions, contrairement au modèle de programmation impérative qui met en avant les changements d'état^[2].

Un langage fonctionnel est donc un langage de programmation dont la syntaxe et les caractéristiques encouragent la programmation fonctionnelle. Alors que l'origine de la programmation fonctionnelle peut être trouvée dans le lambda-calcul, le langage fonctionnel le plus ancien est Lisp, créé en 1958 par McCarthy. Lisp a donné naissance à des variantes telles que Scheme (1975) et Common Lisp (1984)^[3] qui, comme Lisp, ne sont pas ou peu typées. Des langages fonctionnels plus récents tels ML (1973), Haskell (1987), OCaml, Erlang, Clean et Oz, CDuce, Scala (2003), F# ou PureScript (2013), Agda (en) sont fortement typés.

Machine à états et effets secondaires

Transparence référentielle

Les langages fonctionnels ont comme autre propriété la transparence référentielle. Ce terme recouvre le principe simple selon lequel le résultat du programme ne change pas si on remplace une expression par une expression de valeur égale. Ce principe est violé dans le cas de procédures à effets de bord puisqu'une telle procédure, ne dépendant pas uniquement de ses arguments d'entrée, ne se comporte pas forcément de façon identique à deux instants donnés du programme.

Prenons un exemple. En C, si n désigne une variable globale contenant un entier à incrémenter (donc une case mémoire visible par tout le programme), et si inc(k) est une fonction qui augmente la valeur de n de la quantité k :

int n = 2;
int inc(int k) { /* incrémentation par effet de bord */
  n = n + k;
  return n;
}
f(inc(1) + inc(1));

Dans cet exemple, la fonction inc(i) ne renvoie pas la même valeur lors des deux appels : l'un des arguments de la fonction f vaudra 2 + 1 = 3 et l'autre 3 + 1 = 4. Il s'avère donc impossible de remplacer inc(i) + inc(i) par 2 * inc(i) car la valeur de inc(i) diffère à chaque appel. Ce comportement est fondamentalement différent de celui d'une fonction mathématique. À l'échelle d'un programme important, cela signifie que le remplacement d'une fonction par une autre peut nécessiter des modifications à d'autres endroits du programme, et qu'il peut s'avérer nécessaire de retester l'intégralité du système, car on n'est pas assuré qu'un tel remplacement n'a pas modifié son comportement global. Au fur et à mesure que la complexité du système augmente, le coût d'un changement s'accroît aussi. À l'inverse, la propriété de transparence référentielle permet d'assurer que le remplacement d'une fonction par une autre équivalente ne risque pas de modifier le comportement global du programme. Autrement dit, elles sont mathématiquement égales. Cette propriété facilite la maintenance logicielle. Elle permet aussi d'appliquer de façon automatique des preuves de fonctionnement. Elle a enfin pour autre avantage de sensiblement réduire l'importance de l'ordre d'exécution, celui-ci étant assuré par l'ordre d'appel des fonctions ; un corollaire est que la parallélisation d'un programme fonctionnel peut être réalisée de façon automatique et que les optimisations que peuvent effectuer les compilateurs sont plus faciles à mettre en œuvre.

Des fonctions passées en paramètre

Les langages fonctionnels emploient des types et des structures de données de haut niveau comme les listes extensibles. Il est ainsi généralement possible de réaliser facilement des opérations comme la concaténation de listes, ou l'application d'une fonction à une liste — le parcours de la liste se faisant de façon récursive —, en une seule ligne de code.

Un mécanisme puissant des langages fonctionnels est l'usage des fonctions d'ordre supérieur. Une fonction est dite d'ordre supérieur lorsqu'elle peut prendre des fonctions comme arguments (aussi appelées callback) ou renvoyer une fonction comme résultat. On dit aussi que les fonctions sont des objets de première classe, ce qui signifie qu'elles sont manipulables aussi simplement que les types de base. Les programmes ou fonctions qui manipulent des fonctions correspondent, en mathématiques, aux fonctionnelles. Les opérations de dérivation et d'intégration en sont deux exemples simples. Les fonctions d'ordre supérieur ont été étudiées par Alonzo Church et Stephen Kleene dans les années 1930, à partir du formalisme du lambda-calcul, qui a influencé la conception de plusieurs langages fonctionnels, notamment celle d'Haskell. La théorie des catégories cartésiennes fermées constitue une autre approche pour caractériser les fonctions, à l'aide de la notion de problème universel. Le langage Anubis s'appuie sur cette théorie.

Impact du paradigme fonctionnel

Au début des années 2000, la programmation fonctionnelle a commencé à sortir du milieu académique. Dans le milieu industriel, les langages Erlang (développé par Ericsson pour des besoins de programmation concurrentielle et des impératifs de robustesse), Common Lisp, OCaml et Scheme sont utilisés. Mais le développement des langages fonctionnels est limité par le déficit en outils et en bibliothèques de qualité commerciale, et surtout par le manque de programmeurs formés. Notons aussi le langage F# développé par Microsoft Research est disponible sous licence de logiciel libre^[5] en 2010^[6].

Quoique les palmarès de la (en) compétition ICFP démontrent le contraire, les langages fonctionnels souffrent dans le premier quart du XXI^e siècle d'une réputation de lenteur aujourd'hui complètement injustifiée^[7] : certains compilateurs Scheme, comme les compilateurs Stalin ou Bigloo, les compilateurs pour Common Lisp, les langages dans la lignée de ML, tels que OCaml, Haskell ou encore CDuce produisent des exécutables dont les performances moyennes sont comparables, en termes de temps d'exécution et d'espace, à ceux produits par les compilateurs C ou C++. Un code sans effet de bord étant beaucoup plus robuste et plus facile à maintenir, on le préférera à un programme dont la gestion de la mémoire et la prédiction du comportement seront difficiles à maîtriser, quitte à perdre un peu en efficacité. En outre, il faut aussi signaler les travaux de Chris Okasaki sur les structures de données purement fonctionnelles^[8] qui rivalisent avec les structures mutables en efficacité et les outrepassent largement quand il s'agit de la robustesse.

En dehors des universités et de secteurs industriels spécifiques, XSLT peut être un vecteur de popularisation du paradigme fonctionnel. Dédié au traitement XML, il permet à un programmeur de conserver ses langages impératifs ou objets, tout en découvrant une autre logique de programmation.

De même les langages Scala et OCaml, qui se veulent des langages fonctionnels, permettent au programmeur qui en aurait besoin de rester dans une logique de programmation impérative.

Notes et références

Voir aussi