Programmation fonctionnelle - Functional programming

En informatique , la programmation fonctionnelle est un paradigme de programmation où les programmes sont construits en appliquant et en composant des fonctions . Il s'agit d'un paradigme de programmation déclarative dans lequel les définitions de fonctions sont des arbres d' expressions qui mappent des valeurs à d'autres valeurs, plutôt qu'une séquence d' instructions impératives qui mettent à jour l' état d'exécution du programme.

Dans la programmation fonctionnelle, les fonctions sont traitées comme des citoyens de première classe , ce qui signifie qu'elles peuvent être liées à des noms (y compris des identifiants locaux ), passées en arguments et renvoyées par d'autres fonctions, comme n'importe quel autre type de données . Cela permet aux programmes d'être écrits dans un style déclaratif et composable , où de petites fonctions sont combinées de manière modulaire .

La programmation fonctionnelle est parfois considérée comme synonyme de programmation purement fonctionnelle , un sous-ensemble de la programmation fonctionnelle qui traite toutes les fonctions comme des fonctions mathématiques déterministes , ou des fonctions pures . Lorsqu'une fonction pure est appelée avec des arguments donnés, elle renverra toujours le même résultat et ne pourra pas être affectée par un état mutable ou d'autres effets secondaires . Ceci est en contraste avec les procédures impures , courantes dans la programmation impérative , qui peuvent avoir des effets secondaires (comme la modification de l'état du programme ou la saisie d'une entrée d'un utilisateur). Les partisans de la programmation purement fonctionnelle prétendent qu'en limitant les effets secondaires, les programmes peuvent avoir moins de bogues , être plus faciles à déboguer et à tester , et être plus adaptés à la vérification formelle .

La programmation fonctionnelle a ses racines dans le monde universitaire , évoluant à partir du lambda calcul , un système formel de calcul basé uniquement sur des fonctions. La programmation fonctionnelle a toujours été moins populaire que la programmation impérative, mais de nombreux langages fonctionnels sont aujourd'hui utilisés dans l'industrie et l'éducation, notamment Common Lisp , Scheme , Clojure , Wolfram Language , Racket , Erlang , Elixir , OCaml , Haskell et F# . La programmation fonctionnelle est également la clé de certains langages qui ont connu du succès dans des domaines spécifiques, comme JavaScript dans le Web, R dans les statistiques, J , K et Q dans l'analyse financière et XQuery / XSLT pour XML . Les langages déclaratifs spécifiques à un domaine comme SQL et Lex / Yacc utilisent certains éléments de programmation fonctionnelle, tels que l' interdiction des valeurs mutables . De plus, de nombreux autres langages de programmation prennent en charge la programmation dans un style fonctionnel ou ont implémenté des fonctionnalités de programmation fonctionnelle, telles que C++11 , Kotlin , Perl , PHP , Python , Go , Rust , Raku , Scala et Java (depuis Java 8 ) .

Histoire

Le lambda calcul , développé dans les années 1930 par Alonzo Church , est un système formel de calcul construit à partir de l' application de fonctions . En 1937, Alan Turing a prouvé que le lambda-calcul et les machines de Turing sont des modèles de calcul équivalents, montrant que le lambda-calcul est complet de Turing . Le lambda calcul est à la base de tous les langages de programmation fonctionnels. Une formulation théorique équivalente, la logique combinatoire , a été développée par Moses Schönfinkel et Haskell Curry dans les années 1920 et 1930.

Church a développé plus tard un système plus faible, le calcul lambda simplement typé , qui a étendu le calcul lambda en attribuant un type à tous les termes. Ceci constitue la base de la programmation fonctionnelle à typage statique.

Le premier langage de programmation fonctionnel, LISP , a été développé à la fin des années 1950 pour la série d'ordinateurs scientifiques IBM 700/7000 par John McCarthy alors qu'il travaillait au Massachusetts Institute of Technology (MIT). Les fonctions LISP ont été définies à l'aide de la notation lambda de Church, étendue avec une construction d'étiquette pour permettre les fonctions récursives . Lisp a d'abord introduit de nombreuses fonctionnalités paradigmatiques de la programmation fonctionnelle, bien que les premiers Lisp aient été des langages multi-paradigmes et aient incorporé la prise en charge de nombreux styles de programmation à mesure que de nouveaux paradigmes évoluaient. Des dialectes ultérieurs, tels que Scheme et Clojure , et des ramifications telles que Dylan et Julia , ont cherché à simplifier et à rationaliser Lisp autour d'un noyau proprement fonctionnel, tandis que Common Lisp a été conçu pour préserver et mettre à jour les caractéristiques paradigmatiques des nombreux dialectes plus anciens qu'il a remplacés.

Information Processing Language (IPL), 1956, est parfois cité comme le premier langage de programmation fonctionnel informatique. C'est un langage de style assembleur pour manipuler des listes de symboles. Il a une notion de generator , qui équivaut à une fonction qui accepte une fonction comme argument, et, puisqu'il s'agit d'un langage de niveau assembleur, le code peut être des données, donc IPL peut être considéré comme ayant des fonctions d'ordre supérieur. Cependant, il repose fortement sur la structure de la liste en mutation et des fonctionnalités impératives similaires.

Kenneth E. Iverson a développé APL au début des années 1960, décrit dans son livre de 1962 A Programming Language ( ISBN 9780471430148 ). APL était la principale influence sur le FP de John Backus . Au début des années 1990, Iverson et Roger Hui créent J . Au milieu des années 1990, Arthur Whitney , qui avait déjà travaillé avec Iverson, a créé K , qui est utilisé commercialement dans les industries financières avec son descendant Q .

John Backus a présenté FP dans sa conférence du prix Turing de 1977 " Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs ". Il définit les programmes fonctionnels comme étant construits de manière hiérarchique au moyen de « formes de combinaison » qui permettent une « algèbre de programmes » ; en langage moderne, cela signifie que les programmes fonctionnels suivent le principe de compositionnalité . L'article de Backus a popularisé la recherche sur la programmation fonctionnelle, bien qu'il ait mis l'accent sur la programmation au niveau des fonctions plutôt que sur le style lambda-calcul désormais associé à la programmation fonctionnelle.

Le langage ML de 1973 a été créé par Robin Milner à l' Université d'Édimbourg , et David Turner a développé le langage SASL à l' Université de St Andrews . Toujours à Édimbourg dans les années 1970, Burstall et Darlington ont développé le langage fonctionnel NPL . Le NPL était basé sur les équations de récursion de Kleene et a été introduit pour la première fois dans leur travail sur la transformation de programme. Burstall, MacQueen et Sannella ont ensuite incorporé la vérification de type polymorphe de ML pour produire le langage Hope . ML s'est finalement développé en plusieurs dialectes, dont les plus courants sont maintenant OCaml et Standard ML .

Dans les années 1970, Guy L. Steele et Gerald Jay Sussman ont développé Scheme , tel que décrit dans les Lambda Papers et le manuel de 1985 Structure and Interpretation of Computer Programs . Scheme a été le premier dialecte de lisp à utiliser la portée lexicale et à exiger une optimisation des appels de queue , des fonctionnalités qui encouragent la programmation fonctionnelle.

Dans les années 1980, Per Martin-Löf a développé la théorie des types intuitionniste (également appelée théorie des types constructifs ), qui associait des programmes fonctionnels à des preuves constructives exprimées sous forme de types dépendants . Cela a conduit à de nouvelles approches de la preuve interactive de théorèmes et a influencé le développement de langages de programmation fonctionnels ultérieurs.

Le langage fonctionnel paresseux, Miranda , développé par David Turner, est apparu initialement en 1985 et a eu une forte influence sur Haskell . Miranda étant propriétaire, Haskell a commencé par un consensus en 1987 pour former un standard ouvert pour la recherche en programmation fonctionnelle ; les versions de mise en œuvre sont en cours depuis 1990.

Plus récemment, il a trouvé une utilisation dans des niches telles que la CAO paramétrique grâce au langage OpenSCAD construit sur le cadre géométrique CSG, bien que sa restriction sur la réaffectation des valeurs (toutes les valeurs sont traitées comme des constantes) a semé la confusion parmi les utilisateurs peu familiarisés avec la programmation fonctionnelle. en tant que concept.

La programmation fonctionnelle continue d'être utilisée dans les milieux commerciaux.

notions

Un certain nombre de concepts et de paradigmes sont spécifiques à la programmation fonctionnelle, et généralement étrangers à la programmation impérative (y compris la programmation orientée objet ). Cependant, les langages de programmation répondent souvent à plusieurs paradigmes de programmation, de sorte que les programmeurs utilisant des langages « principalement impératifs » peuvent avoir utilisé certains de ces concepts.

Fonctions de première classe et d'ordre supérieur

Les fonctions d'ordre supérieur sont des fonctions qui peuvent soit prendre d'autres fonctions comme arguments, soit les renvoyer comme résultats. En calcul, un exemple de fonction d'ordre supérieur est l' opérateur différentiel , qui renvoie la dérivée d'une fonction . ${\style d'affichage d/dx}$ ${\style d'affichage f}$

Les fonctions d'ordre supérieur sont étroitement liées aux fonctions de première classe en ce sens que les fonctions d'ordre supérieur et les fonctions de première classe autorisent toutes deux des fonctions en tant qu'arguments et résultats d'autres fonctions. La distinction entre les deux est subtile : « ordre supérieur » décrit un concept mathématique de fonctions qui opèrent sur d'autres fonctions, tandis que « première classe » est un terme informatique désignant des entités de langage de programmation qui n'ont aucune restriction quant à leur utilisation (donc première - les fonctions de classe peuvent apparaître n'importe où dans le programme que d'autres entités de première classe comme les nombres, y compris en tant qu'arguments d'autres fonctions et en tant que leurs valeurs de retour).

Les fonctions d'ordre supérieur permettent une application partielle ou currying , une technique qui applique une fonction à ses arguments un par un, chaque application renvoyant une nouvelle fonction qui accepte l'argument suivant. Cela permet à un programmeur d'exprimer succinctement, par exemple, la fonction successeur comme l'opérateur d'addition partiellement appliqué au nombre naturel un.

Fonctions pures

Les fonctions pures (ou expressions) n'ont pas d' effets secondaires (mémoire ou E/S). Cela signifie que les fonctions pures ont plusieurs propriétés utiles, dont beaucoup peuvent être utilisées pour optimiser le code :

Si le résultat d'une expression pure n'est pas utilisé, il peut être supprimé sans affecter les autres expressions.
Si une fonction pure est appelée avec des arguments qui ne provoquent aucun effet secondaire, le résultat est constant par rapport à cette liste d'arguments (parfois appelée transparence référentielle ou idempotence ), c'est-à-dire qu'appeler à nouveau la fonction pure avec les mêmes arguments renvoie le même résultat. (Cela peut permettre des optimisations de mise en cache telles que la mémorisation .)
S'il n'y a pas de dépendance de données entre deux expressions pures, leur ordre peut être inversé, ou elles peuvent être exécutées en parallèle et elles ne peuvent pas interférer les unes avec les autres (en d'autres termes, l'évaluation de toute expression pure est thread-safe ).
Si la langue entière ne permet pas d'effets secondaires, alors n'importe quelle stratégie d'évaluation peut être utilisée ; cela donne au compilateur la liberté de réorganiser ou de combiner l'évaluation des expressions dans un programme (par exemple, en utilisant déforestation ).

Alors que la plupart des compilateurs pour les langages de programmation impératifs détectent les fonctions pures et effectuent l'élimination des sous-expressions communes pour les appels de fonctions pures, ils ne peuvent pas toujours le faire pour les bibliothèques précompilées, qui n'exposent généralement pas ces informations, empêchant ainsi les optimisations impliquant ces fonctions externes. Certains compilateurs, tels que gcc , ajoutent des mots-clés supplémentaires pour qu'un programmeur marque explicitement les fonctions externes comme pures, afin de permettre de telles optimisations. Fortran 95 permet également de désigner les fonctions pures . C++11 a ajouté un constexprmot-clé avec une sémantique similaire.

Récursivité

L'itération (bouclage) dans les langages fonctionnels est généralement accomplie via la récursivité . Les fonctions récursives s'invoquent elles-mêmes, permettant à une opération d'être répétée jusqu'à ce qu'elle atteigne le cas de base . En général, la récursivité nécessite le maintien d'une pile , qui consomme de l'espace de manière linéaire jusqu'à la profondeur de la récursivité. Cela pourrait rendre la récursivité prohibitive à utiliser à la place des boucles impératives. Cependant, une forme spéciale de récursivité connue sous le nom de récursivité de queue peut être reconnue et optimisée par un compilateur dans le même code que celui utilisé pour implémenter l'itération dans les langages impératifs. L'optimisation de la récursivité de la queue peut être implémentée en transformant le programme en style de passage de continuation lors de la compilation, entre autres approches.

La norme du langage Scheme exige que les implémentations prennent en charge une récursivité de queue appropriée, ce qui signifie qu'elles doivent autoriser un nombre illimité d'appels de queue actifs. Une bonne récursivité de la queue n'est pas simplement une optimisation ; c'est une fonctionnalité de langage qui garantit aux utilisateurs qu'ils peuvent utiliser la récursivité pour exprimer une boucle et que cela serait sans danger pour l'espace. De plus, contrairement à son nom, il prend en compte tous les appels de queue, pas seulement la récursivité de queue. Alors que la récursivité de queue appropriée est généralement implémentée en transformant le code en boucles impératives, les implémentations peuvent l'implémenter d'autres manières. Par exemple, CHICKEN maintient intentionnellement une pile et laisse la pile déborder . Cependant, lorsque cela se produit, son ramasse-miettes réclamera de l'espace en arrière, permettant un nombre illimité d'appels de queue actifs même s'il ne transforme pas la récursivité de queue en boucle.

Les modèles courants de récursivité peuvent être abstraits à l'aide de fonctions d'ordre supérieur, les catamorphismes et les anamorphismes (ou « plis » et « dépliages ») étant les exemples les plus évidents. De tels schémas de récursivité jouent un rôle analogue aux structures de contrôle intégrées telles que les boucles dans les langages impératifs .

La plupart des langages de programmation fonctionnels à usage général autorisent une récursivité illimitée et sont complets de Turing , ce qui rend le problème d'arrêt indécidable , peut entraîner des erreurs de raisonnement équationnel et nécessite généralement l'introduction d' incohérences dans la logique exprimée par le système de types du langage . Certains langages à usage spécial tels que Coq n'autorisent qu'une récursivité bien fondée et sont fortement normalisants (les calculs non terminés ne peuvent être exprimés qu'avec des flux infinis de valeurs appelés codata ). En conséquence, ces langages ne sont pas Turing complets et il est impossible d'y exprimer certaines fonctions, mais ils peuvent toujours exprimer une large classe de calculs intéressants tout en évitant les problèmes introduits par la récursivité sans restriction. La programmation fonctionnelle limitée à une récursivité bien fondée avec quelques autres contraintes est appelée programmation fonctionnelle totale .

Évaluation stricte ou non stricte

Les langages fonctionnels peuvent être classés selon qu'ils utilisent une évaluation stricte (avide) ou non stricte (paresseux) , des concepts qui font référence à la façon dont les arguments de fonction sont traités lorsqu'une expression est évaluée. La différence technique réside dans la sémantique dénotationnelle des expressions contenant des calculs défaillants ou divergents. Sous une évaluation stricte, l'évaluation de tout terme contenant un sous-terme défaillant échoue. Par exemple, l'expression :

print length([2+1, 3*2, 1/0, 5-4])

échoue sous évaluation stricte en raison de la division par zéro dans le troisième élément de la liste. Sous l'évaluation paresseuse, la fonction de longueur renvoie la valeur 4 (c'est-à-dire le nombre d'éléments dans la liste), car son évaluation ne tente pas d'évaluer les termes composant la liste. En bref, l'évaluation stricte évalue toujours complètement les arguments de la fonction avant d'appeler la fonction. L'évaluation paresseuse n'évalue pas les arguments de fonction à moins que leurs valeurs ne soient requises pour évaluer l'appel de fonction lui-même.

La stratégie d'implémentation habituelle pour l'évaluation paresseuse dans les langages fonctionnels est la réduction de graphes . L'évaluation paresseuse est utilisée par défaut dans plusieurs langages fonctionnels purs, notamment Miranda , Clean et Haskell .

Hughes 1984 plaide en faveur de l'évaluation paresseuse comme mécanisme d'amélioration de la modularité du programme par la séparation des préoccupations , en facilitant la mise en œuvre indépendante des producteurs et des consommateurs de flux de données. Launchbury 1993 décrit certaines difficultés que l'évaluation paresseuse introduit, en particulier dans l'analyse des besoins de stockage d'un programme, et propose une sémantique opérationnelle pour aider à une telle analyse. Harper 2009 propose d'inclure à la fois l'évaluation stricte et paresseuse dans le même langage, en utilisant le système de types du langage pour les distinguer.

Systèmes de types

Surtout depuis le développement de l' inférence de type Hindley-Milner dans les années 1970, les langages de programmation fonctionnels ont eu tendance à utiliser le calcul lambda typé , rejetant tous les programmes invalides au moment de la compilation et risquant de fausses erreurs positives , par opposition au calcul lambda non typé , qui accepte tous les programmes valides. programmes au moment de la compilation et risque de fausses erreurs négatives , utilisées dans Lisp et ses variantes (telles que Scheme ), bien qu'ils rejettent tous les programmes invalides au moment de l'exécution lorsque les informations sont suffisantes pour ne pas rejeter les programmes valides. L'utilisation de types de données algébriques facilite la manipulation de structures de données complexes ; la présence d'une solide vérification de type au moment de la compilation rend les programmes plus fiables en l'absence d'autres techniques de fiabilité telles que le développement piloté par les tests , tandis que l' inférence de type libère le programmeur de la nécessité de déclarer manuellement les types au compilateur dans la plupart des cas.

Certains langages fonctionnels orientés vers la recherche tels que Coq , Agda , Cayenne et Epigram sont basés sur la théorie des types intuitionniste , qui permet aux types de dépendre des termes. De tels types sont appelés types dépendants . Ces systèmes de types n'ont pas d'inférence de type décidable et sont difficiles à comprendre et à programmer. Mais les types dépendants peuvent exprimer des propositions arbitraires dans la logique d'ordre supérieur . Grâce à l' isomorphisme de Curry-Howard , les programmes bien typés dans ces langages deviennent un moyen d'écrire des preuves mathématiques formelles à partir desquelles un compilateur peut générer du code certifié . Bien que ces langages intéressent principalement la recherche universitaire (y compris en mathématiques formalisées ), ils ont également commencé à être utilisés en ingénierie. Compcert est un compilateur pour un sous-ensemble du langage de programmation C écrit en Coq et formellement vérifié.

Une forme limitée de types dépendants appelés types de données algébriques généralisées (GADT) peut être implémentée d'une manière qui offre certains des avantages de la programmation à typage dépendant tout en évitant la plupart de ses inconvénients. Les GADT sont disponibles dans le compilateur Glasgow Haskell , en OCaml et en Scala , et ont été proposés en tant qu'ajouts à d'autres langages, notamment Java et C#.

Transparence référentielle

Les programmes fonctionnels n'ont pas d'instructions d'affectation, c'est-à-dire que la valeur d'une variable dans un programme fonctionnel ne change jamais une fois définie. Cela élimine tout risque d'effets secondaires car toute variable peut être remplacée par sa valeur réelle à tout moment de l'exécution. Ainsi, les programmes fonctionnels sont référentiellement transparents.

Considérez l' instruction d'affectation Cx = x * 10 , cela change la valeur affectée à la variable x. Disons que la valeur initiale de xétait 1, puis deux évaluations consécutives de la variable xdonnent respectivement 10et 100. Clairement, le remplacement x = x * 10par soit 10ou 100donne à un programme un sens différent, et donc l'expression n'est pas référentiellement transparente. En fait, les instructions d'affectation ne sont jamais référentielles transparentes.

Maintenant, considérons une autre fonction, comme est transparente, car elle ne change pas implicitement l'entrée x et n'a donc pas de tels effets secondaires . Les programmes fonctionnels utilisent exclusivement ce type de fonction et sont donc référentiellement transparents. int plusone(int x) {return x+1;}

Structures de données

Les structures de données purement fonctionnelles sont souvent représentées d'une manière différente de leurs homologues impératifs . Par exemple, le tableau avec des temps d'accès et de mise à jour constants est un composant de base de la plupart des langages impératifs, et de nombreuses structures de données impératives, telles que la table de hachage et le tas binaire , sont basées sur des tableaux. Les tableaux peuvent être remplacés par des cartes ou des listes d'accès aléatoires, qui admettent une implémentation purement fonctionnelle, mais ont des temps d' accès et de mise à jour logarithmiques . Les structures de données purement fonctionnelles ont une persistance , une propriété de conserver les versions précédentes de la structure de données non modifiées. Dans Clojure, les structures de données persistantes sont utilisées comme alternatives fonctionnelles à leurs homologues impératifs. Les vecteurs persistants, par exemple, utilisent des arbres pour une mise à jour partielle. L'appel de la méthode insert entraînera la création de certains nœuds, mais pas tous.

Comparaison avec la programmation impérative

La programmation fonctionnelle est très différente de la programmation impérative . Les différences les plus significatives proviennent du fait que la programmation fonctionnelle évite les effets secondaires , qui sont utilisés dans la programmation impérative pour implémenter l'état et les E/S. La programmation fonctionnelle pure évite complètement les effets secondaires et offre une transparence référentielle.

Les fonctions d'ordre supérieur sont rarement utilisées dans les anciennes programmations impératives. Un programme impératif traditionnel peut utiliser une boucle pour parcourir et modifier une liste. Un programme fonctionnel, d'autre part, utiliserait probablement une fonction « map » d'ordre supérieur qui prend une fonction et une liste, générant et renvoyant une nouvelle liste en appliquant la fonction à chaque élément de la liste.

Programmation impérative vs programmation fonctionnelle

Les deux exemples suivants (écrits en JavaScript ) obtiennent le même effet : ils multiplient tous les nombres pairs d'un tableau par 10 et les additionnent tous, en stockant la somme finale dans la variable "résultat".

Boucle impérative traditionnelle :

const numList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let result = 0;
for (let i = 0; i < numList.length; i++) {
  if (numList[i] % 2 === 0) {
    result += numList[i] * 10;
  }
}

Programmation fonctionnelle avec des fonctions d'ordre supérieur :

const result = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
               .filter(n => n % 2 === 0)
               .map(a => a * 10)
               .reduce((a, b) => a + b);

État de simulation

Il y a des tâches (par exemple, maintenir un solde de compte bancaire) qui semblent souvent le plus naturellement mises en œuvre avec l'État. La programmation fonctionnelle pure effectue ces tâches, ainsi que les tâches d'E/S telles que l'acceptation des entrées de l'utilisateur et l'impression à l'écran, d'une manière différente.

Le langage de programmation fonctionnel pur Haskell les implémente à l'aide de monades , dérivées de la théorie des catégories . Les monades offrent un moyen d'abstraire certains types de modèles de calcul, y compris (mais sans s'y limiter) la modélisation des calculs avec un état mutable (et d'autres effets secondaires tels que les E/S) de manière impérative sans perdre en pureté. Alors que les monades existantes peuvent être faciles à appliquer dans un programme, étant donné des modèles et des exemples appropriés, de nombreux étudiants les trouvent difficiles à comprendre conceptuellement, par exemple lorsqu'on leur demande de définir de nouvelles monades (ce qui est parfois nécessaire pour certains types de bibliothèques).

Les langages fonctionnels simulent également des états en contournant des états immuables. Cela peut être fait en faisant en sorte qu'une fonction accepte l'état comme l'un de ses paramètres et renvoie un nouvel état avec le résultat, en laissant l'ancien état inchangé.

Les langages fonctionnels impurs incluent généralement une méthode plus directe de gestion des états mutables. Clojure , par exemple, utilise des références gérées qui peuvent être mises à jour en appliquant des fonctions pures à l'état actuel. Ce type d'approche permet la mutabilité tout en favorisant l'utilisation de fonctions pures comme moyen privilégié pour exprimer les calculs.

Des méthodes alternatives telles que la logique de Hoare et l' unicité ont été développées pour suivre les effets secondaires dans les programmes. Certains langages de recherche modernes utilisent des systèmes d'effets pour rendre explicite la présence d'effets secondaires.

Problèmes d'efficacité

Les langages de programmation fonctionnels sont généralement moins efficaces dans leur utilisation du processeur et de la mémoire que les langages impératifs tels que C et Pascal . Ceci est lié au fait que certaines structures de données mutables comme les tableaux ont une implémentation très simple en utilisant le matériel actuel. Les tableaux plats peuvent être accédés très efficacement avec des processeurs profondément pipelines, préchargés efficacement via des caches (sans poursuite de pointeur complexe ) ou gérés avec des instructions SIMD. Il n'est pas non plus facile de créer leurs homologues immuables à usage général tout aussi efficaces. Pour les langages purement fonctionnels, le ralentissement le plus défavorable est logarithmique dans le nombre de cellules mémoire utilisées, car la mémoire mutable peut être représentée par une structure de données purement fonctionnelle avec un temps d'accès logarithmique (comme un arbre équilibré). Cependant, de tels ralentissements ne sont pas universels. Pour les programmes qui effectuent des calculs numériques intensifs, les langages fonctionnels tels que OCaml et Clean ne sont que légèrement plus lents que C selon The Computer Language Benchmarks Game . Pour les programmes qui gèrent de grandes matrices et des bases de données multidimensionnelles , des langages fonctionnels de tableaux (tels que J et K ) ont été conçus avec des optimisations de vitesse.

L'immuabilité des données peut dans de nombreux cas conduire à l'efficacité de l'exécution en permettant au compilateur de faire des hypothèses qui ne sont pas sûres dans un langage impératif, augmentant ainsi les opportunités d' expansion en ligne .

L'évaluation paresseuse peut également accélérer le programme, même asymptotiquement, alors qu'elle peut le ralentir au plus d'un facteur constant (cependant, elle peut introduire des fuites de mémoire si elle est mal utilisée). Launchbury 1993 discute des problèmes théoriques liés aux fuites de mémoire dues à une évaluation paresseuse, et O'Sullivan et al. 2008 donne quelques conseils pratiques pour les analyser et les corriger. Cependant, les implémentations les plus générales de l'évaluation paresseuse faisant un usage intensif de code et de données déréférencés fonctionnent mal sur les processeurs modernes avec des pipelines profonds et des caches à plusieurs niveaux (où un manque de cache peut coûter des centaines de cycles).

Programmation fonctionnelle dans des langages non fonctionnels

Il est possible d'utiliser un style de programmation fonctionnel dans des langages qui ne sont pas traditionnellement considérés comme des langages fonctionnels. Par exemple, D et Fortran 95 prennent tous deux explicitement en charge les fonctions pures.

JavaScript , Lua , Python et Go avaient des fonctions de première classe dès leur création. Python a pris en charge " lambda ", " map ", " reduce " et " filter " en 1994, ainsi que les fermetures dans Python 2.2, bien que Python 3 ait relégué " reduce " au functoolsmodule de bibliothèque standard. Des fonctions de première classe ont été introduites dans d'autres langages courants tels que PHP 5.3, Visual Basic 9 , C# 3.0, C++11 et Kotlin .

En PHP , les classes anonymes , les fermetures et les lambdas sont entièrement pris en charge. Des bibliothèques et des extensions de langage pour les structures de données immuables sont en cours de développement pour faciliter la programmation dans le style fonctionnel.

En Java , des classes anonymes peuvent parfois être utilisées pour simuler des fermetures ; cependant, les classes anonymes ne remplacent pas toujours correctement les fermetures car elles ont des capacités plus limitées. Java 8 prend en charge les expressions lambda en remplacement de certaines classes anonymes.

En C# , les classes anonymes ne sont pas nécessaires, car les fermetures et les lambdas sont entièrement pris en charge. Des bibliothèques et des extensions de langage pour les structures de données immuables sont en cours de développement pour faciliter la programmation dans le style fonctionnel en C#.

De nombreux modèles de conception orientés objet sont exprimables en termes de programmation fonctionnelle : par exemple, le modèle de stratégie dicte simplement l'utilisation d'une fonction d'ordre supérieur, et le modèle de visiteur correspond approximativement à un catamorphisme , ou pli .

De même, l'idée de données immuables issues de la programmation fonctionnelle est souvent incluse dans les langages de programmation impératifs, par exemple le tuple en Python, qui est un tableau immuable, et Object.freeze() en JavaScript.

Applications

Feuilles de calcul

Les feuilles de calcul peuvent être considérées comme une forme de système de programmation fonctionnel pur, d' ordre zéro et à évaluation stricte. Cependant, les feuilles de calcul manquent généralement de fonctions d'ordre supérieur ainsi que de réutilisation de code, et dans certaines implémentations, manquent également de récursivité. Plusieurs extensions ont été développées pour les tableurs afin de permettre des fonctions d'ordre supérieur et réutilisables, mais restent jusqu'à présent principalement de nature académique.

Académique

La programmation fonctionnelle est un domaine de recherche actif dans le domaine de la théorie des langages de programmation . Il existe plusieurs sites de publication à comité de lecture axés sur la programmation fonctionnelle, notamment la Conférence internationale sur la programmation fonctionnelle , le Journal of Functional Programming et le Symposium on Trends in Functional Programming .

Industrie

La programmation fonctionnelle a été utilisée dans une grande variété d'applications industrielles. Par exemple, Erlang , qui a été développé par la société suédoise Ericsson à la fin des années 1980, était à l'origine utilisé pour mettre en œuvre des systèmes de télécommunications tolérants aux pannes , mais est depuis devenu populaire pour créer une gamme d'applications dans des entreprises telles que Nortel , Facebook , Électricité de France et WhatsApp . Scheme , un dialecte de Lisp , a été utilisé comme base pour plusieurs applications sur les premiers ordinateurs Apple Macintosh , et a été appliqué à des problèmes tels que les logiciels de simulation d' entraînement et le contrôle de télescope . OCaml , qui a été introduit au milieu des années 1990, a été utilisé commercialement dans des domaines tels que l'analyse financière, la vérification des pilotes , la programmation de robots industriels et l'analyse statique de logiciels embarqués . Haskell , bien qu'initialement conçu comme un langage de recherche, a également été appliqué par un éventail d'entreprises, dans des domaines tels que les systèmes aérospatiaux, la conception de matériel informatique et la programmation Web.

D'autres langages de programmation fonctionnels qui ont été utilisés dans l'industrie incluent Scala , F# , Wolfram Language , Lisp , Standard ML et Clojure .

Les « plates-formes » fonctionnelles sont populaires en finance pour l'analyse des risques (en particulier auprès des grandes banques d'investissement). Les facteurs de risque sont codés en tant que fonctions qui forment des graphiques interdépendants (catégories) pour mesurer les corrélations dans les changements de marché, un peu comme les optimisations de base de Gröbner, mais aussi pour la conformité réglementaire telle que l'analyse et l'examen complets du capital . Compte tenu de l'utilisation des variantes OCAML ou CAML en finance, ces systèmes sont parfois considérés comme liés à une machine abstraite catégorielle ou CAM. En effet, la programmation fonctionnelle est fortement influencée par la théorie des catégories .

Éducation

De nombreuses universités enseignent ou ont enseigné la programmation fonctionnelle dans le cadre de leurs diplômes de premier cycle en informatique. Certains l'utilisent comme introduction à la programmation, tandis que d'autres l'enseignent après avoir enseigné la programmation impérative.

En dehors de l'informatique, la programmation fonctionnelle est utilisée comme méthode pour enseigner la résolution de problèmes, l'algèbre et les concepts géométriques. Il a également été utilisé comme outil pour enseigner la mécanique classique dans la structure et l'interprétation de la mécanique classique .

Voir également

Les références

Lectures complémentaires

Abelson, Hal ; Sussman, Gerald Jay (1985). Structure et interprétation des programmes informatiques . Presse MIT.
Cousineau, Guy et Michel Mauny. L'approche fonctionnelle de la programmation . Cambridge, Royaume-Uni : Cambridge University Press , 1998.
Curry, Haskell Brooks et Feys, Robert et Craig, William. Logique combinatoire . Volume I. North-Holland Publishing Company, Amsterdam, 1958.
Curry, Haskell B. ; Hindley, J. Roger ; Seldin, Jonathan P. (1972). Logique combinatoire . Vol. II. Amsterdam : Hollande du Nord. ISBN 978-0-7204-2208-5. |volume=a du texte supplémentaire ( aide )
Dominus, Mark Jason. Perl d'ordre supérieur . Morgan Kaufmann . 2005.
Felleisen, Matthias; Findler, Robert; Flatt, Matthieu ; Krishnamurthi, Shriram (2001). Comment concevoir des programmes . Presse MIT.
Graham, Paul. LISP commun ANSI . Englewood Cliffs, New Jersey : Prentice Hall , 1996.
MacLennan, Bruce J. Programmation fonctionnelle : pratique et théorie . Addison-Wesley, 1990.
O'Sullivan, Brian ; Stewart, Don ; Goerzen, John (2008). Haskell du monde réel . O'Reilly.
Pratt, Terrence, W. et Marvin V. Zelkowitz. Langages de programmation : conception et implémentation . 3e éd. Englewood Cliffs, New Jersey : Prentice Hall , 1996.
Salus, Peter H. Langages de programmation fonctionnels et logiques . Vol. 4 du Manuel des langages de programmation. Indianapolis, Indiana : Macmillan Technical Publishing , 1998.
Thompson, Simon. Haskell : l'art de la programmation fonctionnelle . Harlow, Angleterre : Addison-Wesley Longman Limited , 1996.

Liens externes

Écoutez cet article ( 28 minutes )

Ce fichier audio a été créé à partir d'une révision de cet article datée du 25 août 2011 et ne reflète pas les modifications ultérieures.

Ford, Neal (2012-01-29). « Pensée fonctionnelle : pourquoi la programmation fonctionnelle est à la hausse » . Récupéré le 2013-02-24 .
Akhmechet, Slava (2006-06-19). "defmacro - Programmation fonctionnelle pour le reste d'entre nous" . Récupéré le 2013-02-24 . Une introduction
Programmation fonctionnelle en Python (par David Mertz) : partie 1 , partie 2 , partie 3

Languages

In other projects