Worldlex Wiki En informatique , un langage de programmation est dit posséder des fonctions de première classe s'il traite les fonctions comme des objets de première classe . Cela signifie que le langage permet de passer des fonctions en arguments à d'autres fonctions, de les renvoyer comme valeurs depuis d'autres fonctions, et de les affecter à des variables ou de les stocker dans des structures de données. Certains théoriciens des langages de programmation exigent également la prise en charge des fonctions anonymes (littéraux de fonction). Dans les langages possédant des fonctions de première classe, les noms des fonctions n'ont aucun statut particulier ; ils sont traités comme des variables ordinaires de type fonction . Le terme a été forgé par Christopher Strachey dans le contexte des « fonctions comme objets de première classe » au milieu des années 1960.
Les fonctions de première classe sont essentielles à la programmation fonctionnelle , où l'utilisation de fonctions d'ordre supérieur est une pratique courante. Un exemple simple de fonction d'ordre supérieur est la fonction `map` , qui prend comme arguments une fonction et une liste, et renvoie la liste obtenue en appliquant la fonction à chaque élément de la liste. Pour qu'un langage prenne en charge `map` , il doit permettre de passer une fonction en argument.
Il existe certaines difficultés d'implémentation liées au passage de fonctions en arguments ou à leur retour en tant que résultats, notamment en présence de variables non locales introduites dans les fonctions imbriquées et anonymes . Historiquement, ces difficultés étaient appelées « problèmes funarg » , du terme dérivé de « function argument » (argument de fonction ). Dans les premiers langages impératifs, ces problèmes étaient contournés soit en n'autorisant pas les fonctions comme types de résultats (par exemple, ALGOL 60 , Pascal ), soit en omettant les fonctions imbriquées et donc les variables non locales (par exemple, C ). Le langage fonctionnel Lisp, à ses débuts , adoptait l'approche de la portée dynamique : les variables non locales font référence à la définition la plus proche de cette variable au point d'exécution de la fonction, et non à son emplacement de définition. La prise en charge adéquate des fonctions de première classe à portée lexicale a été introduite dans Scheme et nécessite de gérer les références aux fonctions comme des fermetures plutôt que comme de simples pointeurs de fonction , ce qui rend le ramasse-miettes indispensable.Haskell ) par rapport à un langage impératif où les fonctions sont des citoyens de seconde classe ( C ).
Fonctions d'ordre supérieur : passage de fonctions comme arguments
map :: ( a -> b ) -> [ a ] -> [ b ] map f [] = [] map f ( x : xs ) = f x : map f xs
Les langages où les fonctions ne sont pas de première classe permettent souvent d'écrire des fonctions d'ordre supérieur grâce à des fonctionnalités telles que les pointeurs de fonction ou les délégués . En C :
int.Fonctions anonymes et imbriquées
f avait été imbriquée , nous aurions rencontré le même problème, et c'est pourquoi elles ne sont pas prises en charge en C. Fonctions d'ordre supérieur : renvoyer des fonctions comme résultats
Lorsqu'on retourne une fonction, on retourne en réalité sa fermeture. Dans l'exemple en C, toutes les variables locales capturées par la fermeture sortiront de la portée une fois que l'on aura quitté la fonction qui a créé la fermeture. Forcer la fermeture ultérieurement entraînera un comportement indéfini, pouvant corrompre la pile. C'est ce qu'on appelle le problème de l'argument funarg ascendant .
Affecter des fonctions à des variables
L'affectation de fonctions à des variables et leur stockage dans des structures de données (globales) peuvent potentiellement souffrir des mêmes difficultés que le retour de fonctions.
f :: [[ Entier ] -> [ Entier ]] f = soit a = 3 b = 1 dans [ map ( \ x -> a * x + b ), map ( \ x -> b * x + a )]
Égalité des fonctions
Puisqu'il est possible de tester l'égalité de la plupart des littéraux et des valeurs, il est naturel de se demander si un langage de programmation peut prendre en charge le test d'égalité des fonctions. À y regarder de plus près, cette question apparaît plus complexe et il convient de distinguer plusieurs types d'égalité de fonctions :
- égalité extensionnelle
- Deux fonctions f et g sont dites extensionnellement égales si leurs valeurs de sortie sont identiques pour toutes les entrées (∀ x . f ( x ) = g ( x )). Selon cette définition de l'égalité, par exemple, deux implémentations quelconques d'un algorithme de tri stable , comme le tri par insertion et le tri fusion , seraient considérées comme égales. Déterminer l'égalité extensionnelle est indécidable en général et souvent impossible, même pour les fonctions à domaine fini. C'est pourquoi aucun langage de programmation n'implémente l'égalité des fonctions comme une égalité extensionnelle.
- égalité tensionnelle
- En vertu de l'égalité intensionnelle, deux fonctions f et g sont considérées comme égales si elles possèdent la même structure interne. Ce type d'égalité peut être implémenté dans les langages interprétés en comparant le code source des corps de fonction (comme dans Interpreted Lisp 1.5) ou le code objet dans les langages compilés . L'égalité intensionnelle implique l'égalité extensionnelle (à condition que les fonctions soient déterministes et ne possèdent pas d'entrées cachées, telles qu'un compteur de programme ou une variable globale mutable ).
- la transparence référentielle et n'est donc pas prise en charge par les langages purs , tels que Haskell.
Théorie des types
Dans les approches catégorielles de la programmation, l'existence de fonctions de première classe correspond à l' hypothèse de catégorie fermée . Par exemple, le lambda-calcul simplement typé correspond au langage interne des catégories cartésiennes fermées .
Soutien linguistique
Les langages de programmation fonctionnelle, tels qu'Erlang , Scheme , ML , Haskell , F# et Scala , possèdent tous des fonctions de première classe. Lors de la conception de Lisp , l'un des premiers langages fonctionnels, tous les aspects des fonctions de première classe n'étaient pas encore bien compris, ce qui a conduit à une portée dynamique des fonctions. Les dialectes plus récents de Scheme et Common Lisp possèdent quant à eux des fonctions de première classe à portée lexicale.
De nombreux langages de script, notamment Perl , Python , PHP , Lua , Tcl /Tk, JavaScript et Io , possèdent des fonctions de première classe.
Pour les langages impératifs, il convient de distinguer Algol de ses descendants tels que Pascal, la famille C traditionnelle et les variantes modernes avec ramasse-miettes. La famille Algol autorise les fonctions imbriquées et les fonctions d'ordre supérieur prenant une fonction comme argument, mais pas les fonctions d'ordre supérieur renvoyant une fonction (à l'exception d'Algol 68, qui le permet). Cette limitation s'explique par l'impossibilité de gérer les variables non locales lorsqu'une fonction imbriquée est renvoyée (Algol 68 générant des erreurs d'exécution dans ce cas).
La famille de langages C autorisait à la fois le passage de fonctions en arguments et leur retour en résultats, mais évitait tout problème en ne prenant pas en charge les fonctions imbriquées. (Le compilateur gcc les autorise en tant qu'extension.) L'utilité du retour de fonctions résidant principalement dans la possibilité de retourner des fonctions imbriquées ayant capturé des variables non locales, plutôt que des fonctions de premier niveau, ces langages ne sont généralement pas considérés comme possédant des fonctions de première classe.
Les langages impératifs modernes prennent souvent en charge le ramasse-miettes, ce qui rend possible l'implémentation de fonctions de première classe. Ces fonctions n'ont généralement été prises en charge que dans les versions plus récentes du langage, notamment C# 2.0 et l'extension Blocks d'Apple pour C, C++ et Objective-C. C++11 a introduit la prise en charge des fonctions anonymes et des fermetures, mais en raison de l'absence de ramasse-miettes, il convient d'être particulièrement vigilant quant au traitement des variables non locales renvoyées par les fonctions (voir ci-dessous).
| Langue | Fonctions d'ordre supérieur | Fonctions imbriquées | Variables non locales | Notes | ||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Arguments | Résultats | Nommé | Anonyme | Fermetures | Demande partielle | |||||||||||||||||||||||||||
| Famille Algol | ALGOL 60 | Avoir des types de fonctions . | ||||||||||||||||||||||||||||||
| ALGOL 68 | Pascal | Ada | Oberon | Delphes | Famille C | C | Blocs ). | Blocs ). | des pointeurs de fonction . | |||||||||||||||||||||||
| C++ | des objets fonction . (Voir aussi ci-dessous.) Application partielle explicite possible avec | |||||||||||||||||||||||||||||||
| C# | des délégués (2.0) et des expressions lambda (3.0). | |||||||||||||||||||||||||||||||
| Objectif-C | Java | des classes internes anonymes . | ||||||||||||||||||||||||||||||
| Aller | Limbo | Newsqueak | Rouiller | Langages fonctionnels | Zézayer | Schème | Julia | Clojure | ML | Haskell | jq | Scala | Erlang | Élixir | Fa# | OCaml | Langages de script | Io | JavaScript | Lua | PHP | Perl | Python | Rubis | Autres langues | Fortran | Érable | Mathematica | MATLAB | Conversation | Rapide | En C++11, les fermetures peuvent capturer des variables non locales par copie, par référence (sans prolonger leur durée de vie) ou par déplacement (la variable est conservée tant que la fermeture est active). La première option est sûre si la fermeture est retournée, mais elle nécessite une copie et ne permet pas de modifier la variable d'origine (qui peut ne plus exister au moment de l'appel de la fermeture). La deuxième option permet d'éviter une copie coûteuse et autorise la modification de la variable d'origine, mais elle est dangereuse si la fermeture est retournée (voir les références orphelines ). La troisième option est sûre si la fermeture est retournée et ne nécessite pas de copie, mais ne permet pas non plus de modifier la variable d'origine.functiondoit être utilisé pour récupérer la fonction en tant que valeur : ` (function foo)__init__` renvoie un objet fonction. `__init__` #'fooexiste comme notation abrégée. Pour appliquer un tel objet fonction, il faut utiliser la funcallfonction `__init__` (funcall #'foo bar baz).functools.partialdepuis la version 2.5 et operator.methodcallerdepuis la version 2.6.Methodou ` std Proc::function` pour pouvoir être utilisé comme donnée de premier ordre. La syntaxe d'appel d'un tel objet fonction diffère de celle utilisée pour appeler une méthode classique. |