Programmation fonctionnelle - Définition

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 argument (aussi appelées callback) 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 qui a influencé la conception de plusieurs langages fonctionnels, notamment celle d'Haskell. Toutefois la Théorie des Catégories Cartésiennes Fermées caractérise les fonctions d'une façon plus moderne à l'aide de la notion de problème universel.

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. 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 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.