Pour chaque impératif fonction, est-il une contrepartie fonctionnelle avec des performances identiques voire des instructions?

Question

Actuellement, je n'ai pas appris un langage fonctionnel qui permet d'atteindre les mêmes performances que le C/C++.Et j'ai appris que certaines langues qui sont en faveur de la programmation fonctionnelle, de la programmation impérative, comme la Scala et de la Rouille, de l'utilisation de l'impératif des moyens à mettre en œuvre leurs fonctions de la bibliothèque, pour une meilleure efficacité.

Donc voici ma question, aujourd'hui comptuters qui exécutent impératif instructions, est-ce une limitation du compilateur ou de la programmation fonctionnelle elle-même?Pour chaque impératif de la fonction, sans effets secondaires, soit dans une langue sans GC tels que C/C++/Rouille/assemblée ou de l'un avec le GC, tels que Java, est-il un pur contrepartie fonctionnelle en Haskell, Scala, etc.qui peut être compilé pour fonctionner avec des performances identiques dans le temps et dans l'espace (et pas seulement asymptotique mais exactement le même) ou même les mêmes instructions, avec une fonctionnelle optimale compilateur qui utilise tout le confort moderne et même inconnues des techniques d'optimisation telles que la queue de la récursivité, la paresse, l'analyse statique, vérification formelle, et donc sur lequel je ne le sais pas?

Je suis conscient de l'équivalence entre le λ-calcul et Turing calculable, mais je ne pouvais pas trouver une réponse à cette question en ligne.Si il y a, s'il vous plaît partager un compilateur, par exemple, ou d'une preuve.Si non, veuillez expliquer pourquoi et de montrer un contre-exemple.Ou est-ce un non-trivial question ouverte?

---

Supplémentaire modifie comme suggéré par Andrej Bauer:

Pour être plus précis, voici 2 exemples qui conduit dans la réflexion sur cette question.

Par exemple, la queue de la récursivité et les accumulateurs peuvent améliorer la performance de certaines fonctions récursives être identique à un impératif de mise en œuvre de l'aide for.Dans certains cas, ils pourraient même avoir les mêmes instructions.

Un autre exemple est le sujet de la paresse en Haskell.La paresse peut aider à éviter la copie de structures de données et de faire mieux.Cependant, la paresse feuilles d'emballages, bouchons, etc.dans le moteur d'exécution et ne peut toujours pas faire le programme que rapide comme un impératif de mise en œuvre où il n'y a pas de telles choses.Donc, je me demande si de telles choses peuvent ętre retiré avant l'exécution lors de la compilation.

Supplémentaire modifie comme suggéré par Nearoo:

La question peut aussi être déclaré de cette manière:est-il un langage qui prend en charge à la fois pure, de la programmation fonctionnelle et programmation impérative, jumelé avec une optimisation du compilateur, dans lequel chaque fonction, sans effets secondaires mis en œuvre impérativement peut être remplacé par une mise en œuvre purement fonctionnel, sans frais de rendement ou même compilé les mêmes instructions?

Answer 1

1. La Performance n'est pas une propriété de la langue, c'est une propriété de programmes spécifiques à l'intérieur d'une langue.Certaines langues peuvent être très rapide à certaines choses, et lent à d'autres.

   Par exemple, Chez-Régime peut parfois trouver des performances comparables à celles de C, non pas parce que la langue est plus efficace, mais parce que des pratiques défensives que les programmeurs utilisent souvent en C sont de moins en moins nécessaire dans le schéma.

   De même, il ya des moments où Haskell peut faire de très efficace du parallélisme ou de simultanéité, non pas parce qu'il est plus rapide que le C, mais parce que l'immutabilité des garanties de la langue permettent au programmeur d'éviter des choses comme des serrures et d'autres techniques de synchronisation.

   Et, le rendement varie de mise en œuvre de la mise en œuvre.Je peux rouler un C interprète, mais il ne sera certainement pas être rapide.C est pas rapide, GCC et Clang sont.

2. Ce qui est considéré comme un "fonctionnelle" de la langue?Chaque pratique et fonctionnelle de la langue a des installations pour les mutable état:OCaml, Haskell, Scala, Lisp, Scheme, etc.La récursivité Tail donne quelque chose d'à peu près équivalent à une mutation à l'intérieur d'une boucle.Mais quand cela ne suffit pas, les langages fonctionnels de donner le programmeur de l'accès à mutable état.Dans le cas de Haskell, c'est contrôlée par le système de type, donc il n'y a jamais implicite de l'état mutable, mais la mutation est très autorisé, et même encouragé, en Haskell.Regardez n'importe quel code Haskell, et vous verrez le IO monade partout.De même, ML langues distinction entre les différents types T et ref T, de sorte que vous pouvez dire par les types de savoir si une variable est modifiable ou non.

3. Il n'est pas "optimale" du compilateur, grâce à Riz du théorème.Tous les compilateurs, impératif ou fonctionnelle, sont des "best effort:" l'utilisation prudente des approximations pour optimiser le code.

   Si nous avons eu un optimal compilateur, la réponse serait que chaque programme a toujours couru à l'aide de la plus efficace des instructions possible, et il ne serait pas question quelle langue vous avez codé votre problème.La séquence optimale des instructions de calcul d'un problème ne dépend pas de la langue source.Mais si nous avions ce, puis ce compilateur compiler tous les non-arrêt de programme en while(0), ce qui signifie que nous avons pu détecter le non-arrêt des programmes, ce qui est impossible.

4. Pour les Machines de Turing et le lambda calcul, je pense que c'est assez trivial à mettre en œuvre un lambda calcul interprète pour des Machines de Turing qui est asymptotiquement équivalent à une universelle de Turing machine.Big-O de la complexité n'est pas ce que les gens veulent dire quand ils disent "les langages Fonctionnels sont lents".Généralement, ils parlent de la constante de frais généraux, ce qui est très différent.Nous n'avons pas de bonnes façons de modéliser mathématiquement cela, donc nous avons l'habitude de simplement en utilisant des expériences pour mesurer les performances précises.