Gibt es für jede imperative Funktion ein funktionales Gegenstück mit identischer Leistung oder sogar Anweisungen?

Question

Derzeit habe ich nichts über eine funktionale Sprache gelernt, die die gleiche Leistung wie C / C ++ erzielen kann.Und ich habe gelernt, dass einige Sprachen, die funktionale Programmierung der imperativen Programmierung vorziehen, wie Scala und Rust, imperative Methoden verwenden, um ihre Bibliotheksfunktionen für eine bessere Effizienz zu implementieren.

Hier kommt also meine Frage: Ist dies bei heutigen Computern, die imperative Anweisungen ausführen, eine Einschränkung des Compilers oder der funktionalen Programmierung selbst?Für jede imperative Funktion ohne Nebenwirkungen, entweder in einer Sprache ohne GC wie C / C ++ / Rust / Assembly oder einer mit GC wie Java, gibt es ein rein funktionales Gegenstück in Haskell, Scala usw.das kann kompiliert werden, um mit identischer Leistung in Zeit und Raum (nicht nur asymptotisch, sondern genau gleich) oder sogar nach denselben Anweisungen zu laufen, mit einem optimalen funktionalen Compiler, der alle modernen und sogar unentdeckten Optimierungstechniken wie Schwanzrekursion, Faulheit, statische Analyse, formale Verifikation und so weiter, von denen ich nichts weiß?

Mir ist die Äquivalenz zwischen λ-berechenbar und Turing-berechenbar bekannt, aber ich konnte online keine Antwort auf diese Frage finden.Wenn ja, teilen Sie uns bitte ein Compiler-Beispiel oder einen Beweis mit.Wenn nicht, erklären Sie bitte warum und zeigen Sie ein Gegenbeispiel.Oder ist das eine nicht triviale offene Frage?

---

Ergänzende Änderungen, wie von vorgeschlagen Andreas Bauer:

Um genauer zu sein, hier sind 2 Beispiele, die zum Nachdenken über diese Frage geführt haben.

Zum Beispiel können Schwanzrekursion und Akkumulatoren die Leistung einiger rekursiver Funktionen verbessern, um mit einer imperativen Implementierung identisch zu sein, die verwendet wird for.In einigen Fällen haben sie möglicherweise sogar die gleichen Anweisungen.

Ein anderes Beispiel ist die Faulheit in Haskell.Faulheit kann dazu beitragen, unnötiges Kopieren von Datenstrukturen zu vermeiden und die Leistung zu verbessern.Faulheit hinterlässt jedoch Verpackungen, Verschlüsse usw.zur Laufzeit und kann das Programm immer noch nicht so schnell machen wie eine imperative Implementierung, bei der es solche Dinge nicht gibt.Ich frage mich also, ob solche Dinge vor der Laufzeit während der Kompilierung statisch entfernt werden können.

Ergänzende Änderungen, wie von vorgeschlagen Nearoo:

Die Frage kann auch so gestellt werden:gibt es eine Sprache, die sowohl reine funktionale Programmierung als auch imperative Programmierung unterstützt, gepaart mit einem optimierten Compiler, in dem jede zwingend implementierte Funktion ohne Nebenwirkungen durch eine rein funktional implementierte ersetzt werden kann, ohne Leistungskosten oder sogar kompiliert zu den gleichen Anweisungen?

Answer 1

1. Leistung ist keine Eigenschaft der Sprache, sondern eine Eigenschaft bestimmter Programme innerhalb einer Sprache.Einige Sprachen sind möglicherweise in einigen Dingen sehr schnell und in anderen langsam.

   Zum Beispiel kann Chez-Scheme manchmal eine Leistung finden, die mit C vergleichbar ist, nicht weil die Sprache effizienter ist, sondern weil defensive Praktiken, die Programmierer oft in C verwenden, in Scheme weniger notwendig sind.

   Ebenso gibt es Zeiten, in denen Haskell sehr effiziente Parallelität oder Parallelität ausführen kann, nicht weil es schneller als C ist, sondern weil die Unveränderlichkeitsgarantien der Sprache es dem Programmierer ermöglichen, Dinge wie Sperren und andere Synchronisationstechniken zu vermeiden.

   Und die Leistung variiert von Implementierung zu Implementierung.Ich kann einen C-Interpreter von Hand rollen, aber es wird sicherlich nicht schnell gehen.C ist nicht schnell, GCC und Clang sind es.

2. Was ist eine "funktionale" Sprache?Jede praktische funktionale Sprache hat einige Möglichkeiten für einen veränderlichen Zustand:OCaml, Haskell, Scala, Lisp, Schema usw.Die Schwanzrekursion ergibt etwas, das in etwa einer Mutation innerhalb einer for-Schleife entspricht.Wenn dies jedoch nicht ausreicht, geben funktionale Sprachen dem Programmierer Zugriff auf einen veränderlichen Zustand.Im Fall von Haskell wird dies vom Typsystem gesteuert, es gibt also niemals impliziter veränderlicher Zustand, aber Mutationen sind in Haskell sehr erlaubt und sogar gefördert.Schauen Sie sich einen beliebigen Haskell-Code an, und Sie werden die IO-Monade überall sehen.Ebenso unterscheiden ML-Sprachen zwischen Typen T und ref T, so dass Sie anhand der Typen erkennen können, ob eine Variable veränderbar ist oder nicht.

3. Dank des Satzes von Rice gibt es keinen "optimalen" Compiler.Alle Compiler, imperativ oder funktional, sind "Best Effort": Sie verwenden konservative Annäherungen, um Code zu optimieren.

   Wenn wir einen optimalen Compiler hätten, wäre die Antwort, dass jedes Programm immer mit den effizientesten Anweisungen ausgeführt wird und es keine Rolle spielt, in welcher Sprache Sie Ihr Problem codiert haben.Die optimale Reihenfolge der Anweisungen, die ein Problem berechnen, hängt nicht von der Ausgangssprache ab.Aber wenn wir das hätten, dann würde dieser Compiler jedes nicht stoppende Programm in kompilieren while(0), was bedeutet, dass wir nicht stoppende Programme erkennen könnten, was unmöglich ist.

4. Für Turingmaschinen und den Lambda-Kalkül halte ich es für ziemlich trivial, einen Lambda-Kalkül-Interpreter für Turingmaschinen zu implementieren asymptotisch entspricht einer universellen Turing-Maschine.Big-O-Komplexität ist nicht das, was die Leute meinen, wenn sie sagen "Funktionale Sprachen sind langsam".Normalerweise sprechen sie von konstantem Overhead, was sehr unterschiedlich ist.Wir haben nicht so gute Möglichkeiten, dies mathematisch zu modellieren, daher verwenden wir normalerweise nur Experimente, um die genaue Leistung zu messen.