Fonction d'ordre supérieur

En mathématiques et en informatique, les fonctions d'ordre supérieur sont des fonctions qui ont au moins une des propriétés suivantes : elles prennent une ou plusieurs fonctions en entrée ; elles renvoient une fonction. En mathématiques, on les appelle des opérateurs ou des fonctionnelles. L'opérateur de dérivation en calcul infinitésimal est un exemple classique, car elle associe une fonction (la dérivée) à une autre fonction (la fonction que l'on dérive). Dans le lambda-calcul non typé, toutes les fonctions sont d'ordre supérieur. Dans le lambda-calcul typé, dont la plupart des langages de programmation fonctionnels sont issus, les fonctions d'ordre supérieur sont généralement celles dont le type contient plus d'une flèche (Flèches dans la programmation fonctionnelle). En programmation fonctionnelle, les fonctions d'ordre supérieur qui retournent d'autres fonctions sont dites curryfiées. La fonction map présente dans de nombreux langages de programmation fonctionnelle est un exemple de fonction d'ordre supérieur. Elle prend une fonction f comme argument, et retourne une nouvelle fonction qui prend une liste comme argument et applique f à chaque élément. Un autre exemple très courant est celui d'une fonction de tri qui prend en argument une fonction de comparaison ; on sépare ainsi l'algorithme de tri de la comparaison des éléments à trier. D'autres exemples de fonction d'ordre supérieur sont la composition de fonctions et l'intégration. Les langages de programmation peuvent obtenir les mêmes résultats algorithmiques que ceux qui sont obtenus par des fonctions d'ordre supérieur en exécutant dynamiquement du code dans la portée de l'évaluation. Cela se fait généralement par un appel à la commande eval ou à la commande execute. Cette approche a cependant des défauts : Le code argument à exécuter n'est généralement pas typé statiquement. Les langages évaluant dynamiquement du code dépendent du typage dynamique pour déterminer la correction et la sécurité du code à exécuter.