Programmation fonctionnelle

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La programmation fonctionnelle est un paradigme de programmation qui considère le calcul en tant qu'évaluation de fonctions mathématiques et rejette le changement d'état et la mutation des données. Elle souligne l'application des fonctions, contrairement au modèle de programmation impérative qui met en avant les changements d'état[1].

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)[2] qui, comme Lisp, ne sont pas ou peu typés. Des langages fonctionnels plus récents tels ML (1973), Haskell (1987), OCaml, Erlang, Clean et Oz, CDuce (2003) ou F# sont fortement typés.

Machine à états et effets secondaires[modifier | modifier le code]

Programmation impérative et effets de bord[modifier | modifier le code]

Article détaillé : programmation impérative.

La programmation impérative s'appuie sur le modèle des machines à états (cf. aussi machine de Turing et Architecture de von Neumann), avec une mémoire centrale et des instructions qui modifient son état grâce à des affectations successives. On peut représenter un tel programme par une machine à états qui représente les états successifs de la mémoire. Cela nécessite pour le programmeur de connaître à tout instant un modèle exact de l'état de la mémoire que le programme modifie.

Afin de réduire la difficulté que représente cette tâche, de nombreuses techniques destinées à réduire le nombre de variables à gérer à un même instant sont utilisées, la plupart relevant de la programmation structurée et de l'encapsulation de données:

  • les variables dites automatiques ou locales, sont définies dans le seul domaine (procédure, méthode, etc.) dans lequel elles sont utiles. Leur portée est alors strictement limitée à ce domaine.
  • l'encapsulation de données, notamment en programmation orientée objet, peut restreindre les manipulations sur des variables à des méthodes circonscrites (utilisation d'attributs privés)

Ces variables ont alors vocation à être désallouées par le compilateur ou interpréteur, immédiatement en sortie de procédure ou via un ramasse-miettes.

Cependant, il arrive que la conception choisie par le programmeur l'amène à mettre à jour dans certaines procédures, volontairement ou non, des variables ou zones de mémoire 'partagées', ne relevant pas structurellement de la procédure. Ces modifications «périphériques», désignées sous le terme générique d'effets secondaires (ou effets de bord), sont en programmation impérative de facto davantage la règle que l'exception. Ils compliquent grandement la compréhension des programmes et sont la source de nombreuses difficultés et de bugs : en effet, si on oublie de mettre à jour certaines données partagées ou qu'au contraire on les modifie sans mesurer tous les effets de bord, si l'ordre chronologique des assignations par les différents composants du logiciel est incorrect, ou si une zone de mémoire a été désallouée au mauvais moment, le programme se retrouve dans un état imprévu, incohérent voire instable.

Programmation fonctionnelle[modifier | modifier le code]

La programmation fonctionnelle s'affranchit de façon radicale des effets secondaires (ou effets de bord) en interdisant toute opération d'affectation.

Le paradigme fonctionnel n'utilise pas de machine à états pour décrire un programme, mais un emboîtement de fonctions que l'on peut voir comme des « boîtes noires » que l'on peut imbriquer les unes dans les autres. Chaque boîte possédant plusieurs paramètres en entrée mais une seule sortie, elle ne peut sortir qu'une seule valeur possible pour chaque n-uplet de valeurs présentées en entrée. Ainsi, les fonctions n'introduisent pas d'effets de bord. Un programme est donc une application, au sens mathématique, qui ne donne qu'un seul résultat pour chaque ensemble de valeurs en entrée. Cette façon de penser, très différente de la démarche de la programmation impérative, est l'une des causes principales de la difficulté qu'ont les programmeurs formés aux langages impératifs pour aborder la programmation fonctionnelle. Cependant, elle ne pose généralement pas de difficultés particulières aux débutants qui n'ont jamais été exposés à des langages impératifs[3]. Un avantage important des fonctions sans effet de bord est la facilité que l'on a à les tester unitairement. Par ailleurs, l'usage généralisé d'une gestion de mémoire automatique par l'intermédiaire d'un ramasse-miettes (en anglais : garbage collector) simplifie la tâche du programmeur.

En pratique, pour des raisons d'efficacité, et du fait que certains algorithmes s'expriment aisément avec une machine à états, certains langages fonctionnels autorisent la programmation impérative en permettant de spécifier que certaines variables sont assignables (ou mutables selon la dénomination habituelle), et donc la possibilité d'introduire localement des effets de bord. Ces langages sont regroupés sous le nom de langages fonctionnels impurs.

Les langages dits purement fonctionnels n'autorisent pas la programmation impérative. De fait, ils sont dénués d'effets de bord et protégés contre les problèmes que pose l'exécution concurrente. On peut voir par exemple ce qui a été fait dans le cadre du langage Erlang.

La mise en œuvre des langages fonctionnels fait un usage sophistiqué de la pile car, afin de s'affranchir de la nécessité de stocker des données temporaires dans des tableaux, ils font largement appel à la récursivité (fait d'inclure l'appel d'une fonction dans sa propre définition). La récursivité peut être rendue plus efficace à l'aide d'une technique dénommée récursion terminale (en anglais : tail-recursion), qui consiste à accumuler les résultats intermédiaires dans une case mémoire de la pile et à la passer en paramètre dans l'appel récursif. Ceci permet d'éviter d'empiler les appels récursifs dans la pile en les remplaçant par une simple succession de sauts. Le code généré par le compilateur est alors similaire à celui généré par une boucle en impératif. Certains langages comme Scheme, OCaml et Anubis optimisent automatiquement les appels récursifs de cette manière.

Transparence référentielle[modifier | modifier le code]

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. La transparence référentielle est extrêmement utile.

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[modifier | modifier le code]

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 argument (aussi appelées callback) et/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. Elles 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. Anubis est un langage fonctionnel s'appuyant sur cette théorie.

Impact du paradigme fonctionnel[modifier | modifier le code]

Récemment, 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 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 et disponible sous licence de logiciel libre[4] en 2010[5].

Enfin, les langages fonctionnels souffrent encore d'une réputation de lenteur aujourd'hui complètement injustifiée [réf. nécessaire] : 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 à ceux produits par les compilateurs C ou C++ [réf. nécessaire]. 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 dehors des universités et de secteurs industriels spécifiques, XSLT est 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[modifier | modifier le code]

  1. (en) Paul Hudak, « Conception, evolution, and application of functional programming languages », ACM Computing Surveys, vol. 21, no 3,‎ septembre 1989, p. 359-411 (lire en ligne)
  2. auxquels il faut ajouter XSLT et Anubis.
  3. Manuel M. T. Chakravarty, Gabriele Keller, « The risks and benefits of teaching purely functional programming in first year. », J. Funct. Program,‎ 2004
  4. Plus précisément sous la licence Apache
  5. (en)Announcing the F# Compiler + Library Source Code Drop, par Don Syme le 4 Nov 2010: « This source code is under the Apache 2.0 license and is published as part of the F# PowerPack codeplex project, which is now also under the Apache 2.0 license. The F# PowerPack now includes libraries, tools and the compiler/library source code drops. »

Voir aussi[modifier | modifier le code]