Berechnen Sie, ob eine Funktion rein ist

11

Laut Wikipedia:

In der Computerprogrammierung kann eine Funktion als rein beschrieben werden, wenn beide Aussagen über die Funktion gelten: Die Funktion wertet immer den gleichen Ergebniswert bei gleichen Argumentwerten aus. Der Funktionsergebniswert kann weder von versteckten Informationen oder Zuständen abhängen, die sich im Verlauf der Programmausführung oder zwischen verschiedenen Programmausführungen ändern können, noch von externen Eingaben von E / A-Geräten. Die Auswertung des Ergebnisses verursacht keine semantisch beobachtbaren Nebenwirkungen oder Ausgaben, wie z. B. die Mutation veränderlicher Objekte oder die Ausgabe an E / A-Geräte.

Ich frage mich, ob es möglich ist, eine Funktion zu schreiben, die berechnet, ob eine Funktion rein ist oder nicht. Beispielcode in Javascript:

function sum(a,b) {
    return a+b;
}

function say(x){
    console.log(x);
}

isPure(sum) // True
isPure(say) // False
Oni
quelle
7
Dies könnte ein Kandidat für den Computer Science Stack Exchange sein . Dies tendiert eher zum Bereich der Theorie ("möglich") als zum praktischen und gestalterischen Bereich ... Es ist ein bisschen jenseits meines Wissens.
... und obwohl es "möglich" und "theoretisch" ist, gibt es sehr wahrscheinlich eine echte Antwort darauf (eine gute Passform für Fragen und Antworten), die sogar einen Beweis beinhalten kann ... der sie wieder in die Welt der Informatik zurückbringt .
Ich denke, Sie können feststellen, ob eine Funktion rein ist, indem Sie sich die Art der Funktionen ansehen, die in ihrer Definition aufgerufen werden. Ich meine, Sie können Reinheit durch Induktion der Funktionsstruktur definieren.
Giorgio
7
Auf plattformspezifische Reflection-Hacks kann nicht verzichtet werden. Wenn eine Funktion eine Black Box ist, kann kein Experiment beweisen, dass sie rein ist. Wenn es beispielsweise so etwas gibt if (rand(1000000)<2) return WRONG_ANSWER, hilft es nicht, die Funktion viele Male auf ein konsistentes Verhalten zu prüfen. Wenn Sie jedoch Zugriff auf die Funktionsdefinition haben, ist der Beweis trivial.
SK-Logik
1
@ user470365 Aus der Definition einer reinen Funktion - "Die Auswertung des Ergebnisses verursacht keine semantisch beobachtbaren Nebenwirkungen oder Ausgaben, wie z. B. die Mutation veränderlicher Objekte oder die Ausgabe an E / A-Geräte." - Alles, was in IO schreibt, ist per Definition unrein. In dem Beispiel sind sayAnrufe, console.logdie unrein saysind, auch unrein.

Antworten:

17

Ja, das ist je nach Sprache möglich.

In JavaScript können Sie anhand der folgenden Kriterien feststellen, ob eine Funktion rein ist:

  • Es werden nur Parameter und Einheimische gelesen.

  • Es schreibt nur Einheimische;

  • Bei Nicht-Einheimischen werden nur reine Funktionen aufgerufen.

  • Alle Funktionen, die implizit aufgerufen werden, sind rein, z toString. und

  • Es werden nur Eigenschaften von Einheimischen geschrieben, wenn sie keine Nicht-Einheimischen als Alias ​​verwenden.

Aliasing kann im allgemeinen Fall in JavaScript nicht ermittelt werden, da Sie die Eigenschaften eines Objekts immer dynamisch nachschlagen können ( object["property"]). Vorausgesetzt, Sie tun das nie und Sie haben die Quelle des gesamten Programms, dann denke ich, dass das Problem nachvollziehbar ist. Sie benötigen außerdem Informationen darüber, welche nativen Funktionen Nebenwirkungen haben, z. B. console.logoder fast alles, was das DOM betrifft.

Der Begriff „rein“ könnte auch einer Klarstellung bedürfen. Selbst in einer stark statisch typisierten, rein funktionalen Programmiersprache, in der alle Funktionen referenziell transparent sind, kann eine Funktion immer noch nicht beendet werden. Wenn wir also darüber sprechen id :: a -> a, sagen wir wirklich nicht:

Bei einem bestimmten Typwert erzeugt adie Funktion ideinen Typwert a.

Sondern:

Gegeben einen gewissen Wert des Typs a, die Funktion idist nicht erzeugen einen Wert, der ist nicht vom Typ a.

Weil eine gültige Implementierung von idist error "Not implemented!". Wie Peteris betont, könnte diese Nichttotalität als eine Art Verunreinigung angesehen werden. Koka ist eine funktionale Programmiersprache mit einer auf JavaScript modellierten Syntax, die auf mögliche Auswirkungen wie Divergenz (Nichtterminierung), referenzielle Transparenz, Auslösen von Ausnahmen und E / A-Aktionen schließen kann.

Jon Purdy
quelle
+1 - Angesichts der Antwort von Peteris bekam so viele positive Stimmen .....
Mattnz
Ich nehme an, Sie müssten der Liste der Kriterien "Es werden nur reine Funktionen aufgerufen" hinzufügen.
Greg Hewgill
1
@ GregHewgill: Guter Fang. Ich habe die Antwort entsprechend aktualisiert. Es ist in Ordnung, Mutationsfunktionen für Einheimische aufzurufen , solange sie ansonsten keine Nebenwirkungen haben. "Pure" ist ein Begriff zu überladen ...
Jon Purdy
Sie müssen auch überprüfen, ob toStringes für ein Objekt, das Sie als Zeichenfolge verwenden, rein ist.
Oleg V. Volkov
Ich denke nicht, dass diese Antwort richtig ist, da es nur eine Teilmenge von Umständen gibt, unter denen Sie diese Bestimmungen tatsächlich treffen können. Bedenken Sie: Ist diese Funktion rein? function a (o) { return o.method(); }- Wir können dies nicht beantworten, da es davon abhängt, welcher Parameter übergeben owird. Wir können auch nicht berücksichtigen, was passiert, wenn eine zuvor zertifizierte reine Funktion in eine nicht reine Implementierung geändert wird, was bei Javascript immer ein potenzielles Problem darstellt.
Jules
11

Nein. Sie können leicht überprüfen, ob eine Funktion nur "rein sichere" Operationen ausführt, wie in Jon Purdys Antwort beschrieben, aber das ist IMO nicht genug, um die Frage zu beantworten.

Betrachten Sie diese Funktion:

function possiblyPure(x) {
    if (someCheck(x)) {
        return x+1; // pure code path
    }
    else {
        console.log("I'm so unpure..."); // unpure code path
    }
}

Wenn someCheckes unrein ist, ist es natürlich auch so possiblyPure. Aber wenn someCheckes rein ist und truefür jeden möglichen Wert von zurückgibt x, possiblyPureist es rein, da der unreine Codepfad nicht erreichbar ist!

Und hier kommt der schwierige Teil: Bestimmen, ob someCheckfür jede mögliche Eingabe true zurückgegeben wird oder nicht . Der Versuch, diese Frage sofort zu beantworten, führt Sie in den Bereich des Halteproblems und ähnlicher unentscheidbarer Probleme.

EDIT: Beweis, dass es unmöglich ist

Es besteht eine gewisse Unsicherheit, ob eine reine Funktion bei jeder möglichen Eingabe enden muss oder nicht. In beiden Fällen kann das Stoppproblem jedoch verwendet werden, um zu zeigen, dass die Reinheitsprüfung unmöglich ist.

Fall A) Wenn eine reine Funktion erforderlich ist , jede mögliche Eingabe zu beenden, du hast , um das Halteproblem zu lösen , um zu bestimmen , ob die Funktion rein ist. Da bekannt ist, dass dies unmöglich ist, kann nach dieser Definition die Reinheit nicht berechnet werden.

Fall B) Wenn eine reine Funktion bei einigen Eingaben nicht enden darf, können wir so etwas konstruieren: Nehmen wir an, dass isPure(f)computes if feine Zeichenfolge ist, die eine reine Funktion definiert.

function halts(f) {
   var fescaped = f.replace(/\"/g, '\\"');
   var upf = 'function() { '+f+'("'+fescaped+'\); console.log("unpure"); }';
   return isPure(upf);
}

Jetzt isPuremuss festgestellt werden, ob die fEingabe an der eigenen Quelle angehalten wird oder nicht . Wenn es anhält, upfist es unrein; Wenn es nicht endet, upfist es rein, wenn fes rein ist.

Wenn es isPurewie erwartet funktioniert hätte (liefert korrekte Ergebnisse und wird bei jeder Eingabe beendet), hätten wir das Stoppproblem (*) gelöst! Da dies als unmöglich bekannt ist, isPurekann es nicht existieren.

(*) für reine JavaScript-Funktionen, was ausreicht, um es auch für die Turingmaschine zu lösen.

user281377
quelle
3
Wahr. Es ist immer möglich, eine konservative Analyse durchzuführen - um zu überprüfen, ob eine Funktion definitiv rein ist, aber nicht, um zu überprüfen, ob sie definitiv nicht rein ist.
SK-Logik
Viele Fälle sind trivial entscheidbar - jene reinen Funktionen, die von Jon Purdy beschrieben wurden, oder unreine Funktionen, die bedingungslos etwas Schmutziges bewirken; aber im Allgemeinen kann man Fälle konstruieren, die unentscheidbar sind.
user281377
1

Diese Stackoverflow-Frage hat eine Antwort von yfeldblum, die hier relevant ist. (Und hat aus irgendeinem Grund eine Ablehnung, die ich nicht ergründen kann. Wäre es eine schlechte Etikette, etwas zu bewerten, das 3 Jahre alt ist?) Er gibt in einem Kommentar den Beweis, dass die Frage, ob eine Funktion rein ist, auf das Problem des Anhaltens reduziert werden kann.

Ich denke, aus praktischer Sicht wäre es für einige Sprachen nicht allzu schwierig, wenn Sie die Funktion ja, nein oder vielleicht zurückgeben lassen. Ich habe vor ein paar Tagen ein Video über Clojure gesehen, und der Sprecher hatte eine Reihe von Verunreinigungen in einer Codebasis gezählt, indem er nach ungefähr 4 verschiedenen Zeichenfolgen gesucht hatte (wie "ref"). Aufgrund der Betonung von Clojure auf Reinheit und Trennung unreiner Dinge war es trivial, aber es war nicht genau das, wonach Sie suchen.

Theoretisch unmöglich, praktisch möglich, wenn Sie die Frage ein wenig optimieren, und ich denke, wie schwer es sein würde, hängt stark von der Sprache ab. Einfachere / sauberere Sprachen mit Schwerpunkt auf Unveränderlichkeit und guter Reflexion wären einfacher.

Michael Shaw
quelle
Ich denke, es wurde abgelehnt, weil es falsch ist. bottomist ein gültiger, erstklassiger Wert, der es nicht verdient, auf diese Weise diskriminiert zu werden.
SK-Logik
0

Gute Frage.

Das Beste, was Sie in der Praxis tun können, vorausgesetzt, Sie können keine E / A-Aktionen abhören, um die Funktion so oft wie möglich aufzurufen. Überprüfen Sie dann, ob der Rückgabewert konsistent ist.

Dies ist jedoch im Allgemeinen nicht möglich. Nicht anhaltende Programme sind wohl nicht rein, und wir können das Problem des Anhaltens nicht entscheiden.

Peter ist
quelle
1
-1: Es wäre nicht trivial, eine Funktion zu schreiben, die diesen Test besteht und alles andere als rein ist.
Mattnz
3
Nach dieser Logik voidwäre jede Funktion "rein", was eindeutig falsch ist.
Greg Hewgill
1
@ Greg: Im weiteren Sinne müsste void foo (void) auch rein sein.
Mattnz
0

Im allgemeinen Fall nicht möglich. Siehe Problem beim Anhalten . Kurz gesagt, es ist unmöglich, ein Programm zu schreiben, das bei einer beliebigen Funktion und Eingabe bestimmt, ob das Programm für immer angehalten oder ausgeführt wird. Wenn es für immer läuft, ist es keine reine Funktion , die der von Ihnen angegebenen Definition entspricht.

dbkk
quelle
5
Das ewige Laufen scheint eine Funktion nicht davon abzuhalten, seine Kriterien für eine reine Funktion zu erfüllen.
Whatsisname
+1: Es ist implizit erforderlich, dass die Funktion mit "Die Funktion wertet immer den gleichen Ergebniswert give ...."
endet
2
Konsequent für immer zu laufen, ohne einen Zustand zu ändern, ist vollkommen "rein". Aber hier handelt es sich natürlich um ein Terminologieproblem.
SK-Logik
@mattnz, eine solche Funktion wird immer auf den bottomWert ausgewertet .
SK-Logik
1
Ich kann sehen, wo das Terminologieproblem ins Spiel kommt. In einigen Interpretationen ist eine "reine" Funktion eine, die deterministisch ist und während ihrer Ausführung niemals einen Zustand oder Wert mit der Außenwelt kommuniziert. In anderen Interpretationen wird den Anforderungen ein Anhalten hinzugefügt. Bei der ersten Interpretation ist es leicht festzustellen, ob eine Funktion rein ist: Eine Maschine, die eine bestimmte Sprache ausführt, sollte feststellen können, ob ein Programm in dieser Sprache mit der Außenwelt kommuniziert.
Rwong