Efficacité de la programmation purement fonctionnelle

Question

Quelqu'un sait-il quel est le pire ralentissement asymptotique possible qui peut se produire lorsque l'on programme de manière purement fonctionnelle et non impérative (c'est-à-dire en autorisant les effets de bord) ?

Clarification du commentaire de itowlson : existe-t-il un problème pour lequel l'algorithme non destructeur le plus connu est asymptotiquement pire que l'algorithme destructeur le plus connu, et si oui, de combien ?

Answer 1

Selon Pippenger [1996] Lorsque l'on compare un système Lisp purement fonctionnel (et doté d'une sémantique d'évaluation stricte, et non paresseuse) à un système capable de modifier les données, un algorithme écrit pour le Lisp impur qui s'exécute en O( n ) peut être traduit en un algorithme dans le Lisp pur qui s'exécute en O( n journal n ) temps (sur la base des travaux de Ben-Amram et Galil [1992] sur la simulation de la mémoire à accès aléatoire en utilisant uniquement des pointeurs). Pippenger établit également qu'il existe des algorithmes pour lesquels c'est le mieux que l'on puisse faire ; il existe des problèmes qui sont O( n ) dans le système impur qui sont Ω( n journal n ) dans le système pur.

Il y a quelques mises en garde à faire au sujet de ce document. La plus importante est qu'il ne traite pas des langages fonctionnels paresseux, tels que Haskell. Bird, Jones et De Moor [1997]. démontrent que le problème construit par Pippenger peut être résolu dans un langage fonctionnel paresseux en O( n ), mais ils n'établissent pas (et pour autant que je sache, personne ne l'a fait) si un langage fonctionnel paresseux peut ou non résoudre tous les problèmes dans le même temps d'exécution asymptotique qu'un langage avec mutation.

Le problème construit par Pippenger requiert Ω( n journal n ) est spécifiquement construit pour atteindre ce résultat, et n'est pas nécessairement représentatif des problèmes pratiques du monde réel. Il y a quelques restrictions sur le problème qui sont un peu inattendues, mais nécessaires pour que la preuve fonctionne ; en particulier, le problème exige que les résultats soient calculés en ligne, sans pouvoir accéder à l'entrée future, et que l'entrée consiste en une séquence d'atomes d'un ensemble non limité d'atomes possibles, plutôt qu'un ensemble de taille fixe. De plus, l'article n'établit des résultats (borne inférieure) que pour un algorithme impur de temps d'exécution linéaire ; pour les problèmes qui nécessitent un temps d'exécution plus long, il est possible que le temps supplémentaire de O(log n ) observé dans le problème linéaire peut être "absorbé" dans le processus des opérations supplémentaires nécessaires aux algorithmes ayant des temps d'exécution plus importants. Ces clarifications et questions ouvertes sont explorées brièvement par Ben-Amram [1996] .

En pratique, de nombreux algorithmes peuvent être implémentés dans un langage purement fonctionnel avec la même efficacité que dans un langage avec des structures de données mutables. Pour une bonne référence sur les techniques à utiliser pour implémenter efficacement des structures de données purement fonctionnelles, voir Chris Okasaki, "Purely Functional Data Structures" [Okasaki 1998]. (qui est une version étendue de sa thèse [Okasaki 1996] ).

Tous ceux qui ont besoin de mettre en œuvre des algorithmes sur des structures de données purement fonctionnelles devraient lire Okasaki. Vous pouvez toujours obtenir au pire un résultat O(log n ) par opération en simulant une mémoire mutable avec un arbre binaire équilibré, mais dans de nombreux cas, vous pouvez faire beaucoup mieux que cela, et Okasaki décrit de nombreuses techniques utiles, des techniques amorties aux techniques en temps réel qui effectuent le travail amorti de manière incrémentielle. Les structures de données purement fonctionnelles peuvent être un peu difficiles à utiliser et à analyser, mais elles offrent de nombreux avantages, comme la transparence référentielle, qui sont utiles pour l'optimisation des compilateurs, le calcul parallèle et distribué et la mise en œuvre de fonctionnalités telles que le versioning, l'undo et le rollback.

Notez également que tout ceci ne traite que des temps d'exécution asymptotiques. De nombreuses techniques d'implémentation de structures de données purement fonctionnelles entraînent un certain ralentissement en facteur constant, dû à la comptabilité supplémentaire nécessaire à leur fonctionnement et aux détails d'implémentation du langage en question. Les avantages des structures de données purement fonctionnelles peuvent l'emporter sur ces ralentissements à facteur constant. Vous devrez donc généralement faire des compromis en fonction du problème en question.

Références

• Ben-Amram, Amir et Galil, Zvi 1992. "Sur les pointeurs et les adresses" Journal of the ACM, 39(3), pp. 617-648, juillet 1992
• Ben-Amram, Amir 1996. "Notes sur la comparaison entre Lisp pur et Lisp impur de Pippenger" Manuscrit non publié, DIKU, Université de Copenhague, Danemark.
• Bird, Richard, Jones, Geraint, et De Moor, Oege 1997. "Plus de hâte, moins de rapidité : évaluation paresseuse contre évaluation empressée" Journal of Functional Programming 7, 5 pp. 541-547, septembre 1997
• Okasaki, Chris 1996. "Structures de données purement fonctionnelles" Thèse de doctorat, Université Carnegie Mellon
• Okasaki, Chris 1998. "Structures de données purement fonctionnelles" Cambridge University Press, Cambridge, Royaume-Uni
• Pippenger, Nicholas 1996. "Pure Versus Impure Lisp" Symposium de l'ACM sur les principes des langages de programmation, pages 104-109, janvier 1996.

Answer 2

Il existe en effet plusieurs algorithmes et structures de données pour lesquels aucune solution purement fonctionnelle asymptotiquement efficace (c'est-à-dire implémentable en lambda-calcul pur) n'est connue, même avec la paresse.

• L'union-trouvée susmentionnée
• Tables de hachage
• Tableaux
• Quelques algorithmes de graphes
• ...

Cependant, nous supposons que dans les langages "impératifs", l'accès à la mémoire est O(1) alors qu'en théorie, ce n'est pas le cas asymptotiquement (c'est-à-dire pour des problèmes de taille non limitée) et l'accès à la mémoire dans un énorme ensemble de données est toujours O(log n), ce qui peut être émulé dans un langage fonctionnel.

Il faut également se rappeler que tous les langages fonctionnels modernes fournissent des données mutables, et que Haskell le fait même sans sacrifier la pureté (la monade ST).

Answer 3

Cet article prétend que les implémentations connues purement fonctionnelles de l'algorithme de recherche d'union ont tous une complexité asymptotique pire que celui qu'ils publient, qui a une interface purement fonctionnelle mais utilise des données mutables en interne.

Le fait que d'autres réponses affirment qu'il ne peut jamais y avoir de différence et que, par exemple, le seul "inconvénient" du code purement fonctionnel est qu'il peut être parallélisé vous donne une idée de l'information/objectivité de la communauté de la programmation fonctionnelle sur ces questions.

EDIT :

Les commentaires ci-dessous soulignent qu'une discussion biaisée sur les avantages et les inconvénients de la programmation fonctionnelle pure peut ne pas provenir de la "communauté de la programmation fonctionnelle". C'est un bon point. Peut-être que les défenseurs que je vois sont simplement, pour citer un commentaire, "illettrés".

Par exemple, je pense que cette article de blog est écrit par quelqu'un dont on peut dire qu'il est représentatif de la communauté de la programmation fonctionnelle, et puisqu'il s'agit d'une liste de "points pour l'évaluation paresseuse", ce serait un bon endroit pour mentionner tout inconvénient que la programmation paresseuse et purement fonctionnelle pourrait avoir. Un bon endroit aurait été à la place du rejet suivant (techniquement vrai, mais biaisé au point de ne pas être drôle) :

Si une fonction stricte a une complexité O(f(n)) dans un langage strict, alors elle a aussi une complexité O(f(n)) dans un langage paresseux. Pourquoi s'inquiéter ? :)

Answer 4

Avec une limite supérieure fixe sur l'utilisation de la mémoire, il ne devrait pas y avoir de différence.

Esquisse de la preuve : Étant donné une limite supérieure fixe sur l'utilisation de la mémoire, on devrait pouvoir écrire une machine virtuelle qui exécute un jeu d'instructions impératives avec la même complexité asymptotique que si vous exécutiez réellement sur cette machine. Il en est ainsi parce que vous pouvez gérer la mémoire mutable comme une structure de données persistante, ce qui donne O(log(n)) de lecture et d'écriture, mais avec une limite supérieure fixe sur l'utilisation de la mémoire, vous pouvez avoir une quantité fixe de mémoire, ce qui entraîne une décroissance à O(1). Ainsi, l'implémentation fonctionnelle peut être la version impérative s'exécutant dans l'implémentation fonctionnelle de la VM, et donc ils devraient tous deux avoir la même complexité asymptotique.

Answer 5

Je vous suggère de lire sur les performances de Haskell puis de jeter un coup d'œil à Alioth Language Shootout les performances des langages fonctionnels par rapport aux langages procéduraux/OO.