Exemples où le code fonctionnel optimisé par le compilateur fonctionne mieux que le code impératif

Question

Une des promesses de sans effets secondaires, referentially transparent de la programmation fonctionnelle, c'est que ce code peut être largement optimisé. Pour citer Wikipedia:

L'immuabilité de données peut, dans de nombreux cas, conduire à l'exécution de l'efficacité, en permettant au compilateur de faire des hypothèses qui sont dangereux dans un langage impératif, ainsi increasi*texte en gras*ng opportunités pour les expansion.

J'aimerais voir des exemples où un langage fonctionnel compilateur surpasse impérative par la production d'un meilleur code optimisé.

Edit: j'ai essayé de donner un scénario spécifique, mais apparemment ce n'était pas une bonne idée. Donc je vais essayer de l'expliquer d'une manière différente.

Les programmeurs de traduire des idées (algorithmes) dans des langues que les machines puissent comprendre. Dans le même temps, l'un des aspects les plus importants de la traduction est que les humains peuvent comprendre le code résultant. Malheureusement, dans de nombreux cas, il s'agit d'un compromis: Une concis, lisible le code souffre de ralentissement des performances et doit être optimisé manuellement. C'est sujette à des erreurs, beaucoup de temps, et il rend le code moins lisible (jusqu'à totalement illisible).

Les fondements des langages fonctionnels, tels que l'immuabilité et la transparence référentielle, compilateurs permettent d'effectuer d'importantes optimisations, ce qui pourrait remplacer le manuel de l'optimisation de code et de gratuit les programmeurs de ce compromis. Je suis à la recherche d'exemples d'idées (algorithmes) et de leur mise en œuvre, telles que:

1. l' (fonctionnelle) de la mise en œuvre est proche de l'idée originale et facile à comprendre,
2. il est largement optimisé par le compilateur du langage, et
3. il est difficile (voire impossible) d'écrire de même efficace du code dans un langage impératif, sans manuel d'optimisations qui permettent de réduire sa concision et de lisibilité.

Je m'excuse si c'est un peu vague, mais j'espère que l'idée est claire. Je ne veux pas donner des restrictions inutiles sur les réponses. Je suis ouvert aux suggestions si quelqu'un sait comment l'exprimer mieux.

Mon intérêt n'est pas seulement théorique. Je voudrais utiliser de tels exemples (entre autres choses) pour motiver les élèves à s'intéresser à la programmation fonctionnelle.

Au début, je n'étais pas satisfait par quelques exemples suggéré dans les commentaires. Sur la deuxième pensées, je prends mes objections dos, ceux sont de bons exemples. N'hésitez pas à les étendre à des réponses complètes, de sorte que les gens peuvent commenter et à voter pour eux.

---

(Une classe de ces exemples seront plus susceptibles code parallélisé, qui peut bénéficier de plusieurs cœurs de PROCESSEUR. Souvent dans les langages fonctionnels cela peut être fait facilement sans sacrifier la simplicité du code (comme en Haskell par l'ajout d' par ou pseq dans les endroits appropriés). Je' être intéressés par de tels exemples, mais aussi dans d'autres, non-parallèles.)

Answer 1

Il y a des cas où le même algorithme permettra de mieux optimiser dans une pure contexte. Plus précisément, flux de fusion permet à un algorithme qui consiste en une séquence de boucles qui peuvent être très divers forme: des cartes, des filtres, se plie, se déplie, pour être composées en une seule boucle.

L'équivalent d'optimisation dans un classique impératif, avec mutable données dans les boucles, aurait pour atteindre le plein effet de l'analyse, qui ne on ne.

Ainsi, au moins pour la classe des algorithmes sont implémentés comme des canalisations de ana - et catamorphisms sur les séquences, vous pouvez garantir l'optimisation des résultats qui ne sont pas possibles dans un impératif de réglage.

Answer 2

Un très récent article Haskell bat C généralisée flux de fusion par Geoff Continent, Simon Peyton Jones, Simon Marlow, Romain Leshchinskiy (soumis à ICFP 2013) décrit un exemple. Résumé (avec la partie intéressante en gras):

Flux de fusion [6] est une technique puissante pour transformer automatiquement de haut niveau de la séquence des fonctions de traitement efficace dans les implémentations. Il a été utilisé à bon escient dans Haskell bibliothèques pour la manipulation de tableaux d'octets, texte Unicode, et de décaissement des vecteurs. Toutefois, certaines opérations, comme vecteur d'ajouter encore de ne pas effectuer de bien dans le flux standard de fusion cadre. D'autres, comme SIMD calcul à l'aide de l'ESS et des instructions AVX sur moderne puces x86, ne semblent pas correspondre dans le cadre de tous les.

Dans ce papier, nous introduisons généralisée flux de la fusion, qui résout ces problèmes. L'idée clé est de bundle ensemble plusieurs flux des représentations, chacun à l'écoute pour une classe particulière de flux à la consommation. Nous décrivons également un flux de représentation adapté pour efficace calcul avec les instructions SSE. Nos idées sont mises en œuvre dans les versions modifiées du GHC du compilateur et de l' vectorbibliothèque. Les Benchmarks montrent que le haut niveau du code Haskell écrite à l'aide de notre compilateur et les bibliothèques peuvent produire du code qui est plus rapide que les deux le compilateur et de la main-vectorisé C.

Answer 3

C'est juste une remarque, pas une réponse: l' gcc a pure attribut ce qui suggère qu'il peut tenir compte de la pureté; la des raisons évidentes, on a fait remarquer dans le manuel ici.

Je pense que 'static single assignment" impose une forme de pureté -- voir les liens en http://lambda-the-ultimate.org/node/2860 ou de l'article de wikipédia.

Answer 4

les systèmes make et divers builds fonctionnent mieux pour les grands projets en supposant que les différentes étapes de build sont référentiellement transparentes; en tant que tels, ils ont seulement besoin de réexécuter des étapes dont les entrées ont été modifiées.

Pour les changements de petite à moyenne taille, cela peut être beaucoup plus rapide que la construction à partir de zéro.