Page d'accueil encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Programmation fonctionnelle


image:Langage_progr.png
Cet article fait partie de
la série Langages de programmation
Langages orientés objet
Ada 95 - C++ - C#
Common lisp object system
Delphi - Eiffel - Java - Nice
Langages impératifs
APL - ASP
Assembleur
BASIC - C - Pascal
Perl - PHP - Python
Langages fonctionnels
ML/OCaml - Lisp/Common Lisp
Forth - Logo - Scheme
Langages déclaratifs
Clips - Prolog
Voir aussi
Conception - Codage
Tests - Optimisations


Un langage fonctionnel est un langage de programmation dont la syntaxe et les caractéristiques encouragent la programmation fonctionnelle. Le langage fonctionnel le plus ancien est le Lisp, créé en 1958 par Mac Carthy. Lisp a donné naissance à des variantes plus récentes telles que le Scheme (1975) et le Common Lisp (1984). D'autres langages fonctionnels récents incluent les langages ML (1973), Haskell (1987), Erlang, Clean et Oz. Dans la catégorie des langages non ML, il ne faut pas oublier XSLT.

Sommaire

Machine d'états et effets de bord

En programmation impérative, on travaille sur le modèle de la machine de Turing, avec une mémoire centrale et des instructions qui modifient son état grâce à des assignations successives. On peut représenter un programme par une machine d'é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 sont utilisées. On peut citer parmi ces techniques les variables dites automatiques, dont la portée (portée lexicale) se limite à la procédure dans laquelle elles ont été définies et qui sont désallouées par le compilateur à la sortie de la procédure, l'encapsulation des données, à l'origine de la programmation structurée, et la programmation orientée objet. Cependant, en programmation impérative, il est fréquent qu'une variable ou une zone de mémoire ait une portée ou une durée de vie supérieure à celle de la procédure dans laquelle elle a été créée, de façon à pouvoir être lue ou modifiée par d'autres procédures ou unités d'exécution. Il arrive cependant que des procédures doivent mettre à jour certaines variables ou zones de mémoire dans un but qui n'est pas directement lié à leur fonction, mais uniquement afin que les données partagées restent dans un état prévu par le programmeur. On regroupe ces modifications « invisibles » sous le terme générique d'effets de bord. Les effets de bord, en programmation impérative, qui sont plus la règle que l'exception, compliquent grandement les programmes et sont la source de nombreuses difficultés et de bogues : en effet, si on oublie de mettre à jour certaines données partagées, si l'ordre chronologique des assignations par les différentes parties 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.

La programmation fonctionnelle s'affranchit de façon radicale des effets de bord en interdisant toute opération d'assignation. Le paradigme fonctionnel n'utilise pas de machine d'états pour décrire un programme, mais une succession 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 tuple 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ématiques, qui ne donne qu'un seul résultat pour chaque ensemble de valeurs en entrée. Cette façon de penser, qui est très différente de la pensée habituelle en programmation impérative est l'une des causes principales de la difficulté qu'ont les programmeurs formés aux langages traditionnels pour aborder la programmation fonctionnelle. Cependant, il faut noter qu'elle ne pose généralement pas de difficultés particulières aux débutants qui n'ont jamais programmé auparavant. Un avantage important des fonctions sans effets 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 (garbage collector en anglais) 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 d'états, la plupart des 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 sont le nom de langages fonctionnels impurs. Les langages dit 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.

L'implémentation 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é, - le 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 (tail-recursion en anglais), 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 optimisent automatiquement les appels récursifs de cette manière.

Transparence référentielle

Les langages fonctionnels ont comme autre propriété la transparence référentielle. Ce terme apparemment compliqué couvre en fait 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 qui semble évident est pourtant violé dans le cas de procédures à effets de bord puisqu'une telle procédure ne dépendant pas uniquement de ses paramètres d'entrée, ne se comporte pas forcément de façon identique à deux instants donnés du programme. Pourtant, la transparence référentielle est, comme nous allons le voir, une propriété 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 inc(k) une fonction qui augmente la valeur de n de la quantité k :

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

Dans cet exemple, la fonction inc(i) ne retourne pas la même valeur lors des deux appels : l'un des paramètres 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 conséquent, 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'accroit aussi. A 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.

Une plus grande expressivité

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 liste, 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 et/ou retourner 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, un formalisme qui a grandement influencé le design de nombreux langages fonctionnels, en particulier Haskell.

Popularité du paradigme fonctionnel

Nombreux sont les programmeurs expérimentés qui pensent que la programmation fonctionnelle offre des avantages sans équivalent en impératif. Malgré cela, elle reste peu utilisée en dehors du milieu universitaire et des hobbyistes. Dans le milieu industriel, les langages Erlang (développé par Ericsson pour des besoins de programmation concurrentielle et des impératifs de robustesse) et Scheme sont utilisés. Mais le développement des langages fonctionnels est limité par le déficit en outils et en librairies de qualité commerciale et surtout par le manque de programmeurs formés.

Enfin, les langages fonctionnels souffrent encore d'une réputation de lenteur aujourd'hui complètement injustifiée : certains compilateurs Scheme, comme les compilateurs Stalin ou Bigloo, les compilateurs pour Common Lisp, les langages dans la lignée de ML, tels que Objective Caml, ou encore Haskell présentent des performances moyennes comparables ou supérieures à celles des compilateurs C++.

Cependant, les techniques de la programmation fonctionnelle commencent à être introduites dans des langages modernes populaires tels que Python.




This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the GNU Free Documentation License Page HistoryOriginal ArticleWikipedia