Warum ist die Bestimmung, ob eine Funktion schwierig ist rein?

Question

war ich an der Stackoverflow Dev Tagen Konvention gestern, und einer der Redner über Python spricht. Er zeigte eine Memoize Funktion, und ich fragte, ob es eine Möglichkeit war, damit er nicht auf einer nicht reine Funktion verwendet wird. Er sagte, nein, das ist im Grunde unmöglich, und wenn jemand einen Weg finden, könnte es zu tun wäre es eine große Doktorarbeit machen.

Diese Art von mir verwirrt, weil es gar nicht so schwer scheint für einen Compiler / Interpreter rekursiv zu lösen. In Pseudo-Code:

function isPure(functionMetadata): boolean;
begin
   result = true;
   for each variable in functionMetadata.variablesModified
      result = result and variable.isLocalToThisFunction;
   for each dependency in functionMetadata.functionsCalled
      result = result and isPure(dependency);
end;

Das ist die Grundidee. Offensichtlich würden Sie irgendeine Art von Kontrolle müssen unendliche Rekursion auf beiden Seiten abhängige Funktionen zu vermeiden, aber das ist nicht zu schwierig einzurichten.

Funktionen höhere Ordnung, die Funktionszeiger nehmen könnten problematisch sein, da sie nicht statisch überprüft werden können, aber meine ursprüngliche Frage setzt voraus, dass der Compiler eine Art von Sprache Einschränkung hat um anzuzeigen, dass nur ein reinen Funktionszeiger kann übergeben werden ein bestimmte Parameter. Wenn man existiert, die verwendet werden, um die Bedingung zu erfüllen.

Natürlich wäre dies in einer kompilierten Sprache einfacher sein, als ein eine interpretiert, da all diese Zahl-Knirschen würde geschehen, bevor das Programm ausgeführt wird und so langsam etwas nicht nach unten, aber ich sehe wirklich keine grundlegende Probleme das würde macht es unmöglich, zu beurteilen.

Hat jemand mit ein bisschen mehr Wissen in diesem Bereich wissen, was ich bin fehlt?

Answer 1

Es ist besonders schwer in Python. Da anObject.aFunc beliebig zur Laufzeit geändert werden kann, können Sie nicht bei der Kompilierung festzustellen, welcher Funktionsaufruf anObject.aFunc() wird oder auch wenn es eine Funktion überhaupt sein.

Answer 2

Sie müssen auch alle Systemaufrufe mit Anmerkungen versehen, jedes FFI, ...

Und weiterhin die kleinste ‚Leck‘ neigt dazu, in die gesamte Codebasis zu lecken.

Es ist kein theoretisch unlösbares Problem, aber es ist sehr, sehr schwierig, in einer Art und Weise zu tun, dass das ganze System nicht spröde fühlt.

in der Praxis

Als beiseite, ich glaube nicht, das eine These gut PhD macht; Haskell effektiv bereits hat (eine Version), um diese mit dem IO Monade.

Und ich bin sicher, dass viele Leute in diesem ‚in der Praxis‘ suchen weiter. (Wilde Spekulation) In 20 Jahren können wir diese haben.

Answer 3

Zusätzlich zu den anderen ausgezeichneten Antworten hier: Ihr Pseudo-Code sieht nur auf, ob eine Funktionsvariablen ändert. Aber das ist nicht wirklich das, was „rein“ bedeutet. „Pure“ bedeutet in der Regel etwas näher an „referentiell transparent.“ Mit anderen Worten, ist der Ausgang auf den Eingang völlig abhängig. So etwas so Einfach wie die aktuelle Zeit zu lesen und zu machen, dass ein Faktor im Ergebnis (oder vom Eingang zu lesen, oder den Zustand der Maschine zu lesen, oder ...) macht die Funktion nicht rein, ohne Variablen zu verändern.

Auch Sie könnten eine „reine“ Funktion schreiben, die Variablen haben ändern.

Answer 4

Hier ist das erste, was mir in den Sinn kam, wenn ich Ihre Frage gelesen.

  

Klassenhierarchien

Die Bestimmung, ob eine Variable geändert wird, um den Akt der Graben durch jede einzelne Methode enthält, die auf die Variable aufgerufen wird, um zu bestimmen, wenn es mutiert. Dies ist ... etwas gerade nach vorne für eine abgedichtete mit einer nicht-virtuellen Methode.

Aber betrachten Sie virtuelle Methoden. Sie müssen jeden einzelnen abgeleiteten Typen finden und sicherstellen, dass jede einzelne Überschreibung dieser Methode Zustand nicht mutieren. Die Bestimmung ist dies einfach nicht möglich, in jeder Sprache / Rahmen, der für die dynamische Code-Generierung erlaubt oder ist einfach dynamisch (wenn es möglich ist, ist es extrem schwierig). Der Grund dafür ist, dass der Satz von abgeleiteten Typen ist nicht festgelegt, weil ein neues kann zur Laufzeit erzeugt werden.

C # als Beispiel nehmen. Es gibt nichts, mich von Stoppen einer abgeleiteten Klasse zur Laufzeit zu erzeugen, die die virtuelle Methode überschreibt und modifiziert Zustand. Ein statische verifiziert wäre nicht in der Lage, diese Art von Modifikation zu erkennen und daher nicht die Methode rein war validieren konnte oder nicht.

Answer 5

Ich denke, das Hauptproblem effizient tun würde.

D-Sprache reine Funktionen hat, aber sie haben sie selbst bestimmen, so würde der Compiler wissen, um sie zu überprüfen. Ich denke, wenn Sie sie manuell angeben dann wäre es einfacher zu machen.

Answer 6

Die Entscheidung, ob eine gegebene Funktion rein ist, in der Regel ist reduzierbar zu entscheiden, ob ein bestimmtes Programm anhalten wird -. Und es ist bekannt, dass das Halteproblem die Art von Problem, das nicht effizient gelöst werden kann,

Answer 7

Beachten Sie, dass die Komplexität hängt von der Sprache auch. Für die weitere dynamische Sprachen ist es möglich, jederzeit alles neu zu definieren. Zum Beispiel in Tcl

proc myproc {a b} {
    if { $a > $b } {
        return $a
    } else {
        return $b
    }
}

Jedes einzelne Stück davon kann jederzeit geändert werden. Zum Beispiel:

• die „if“ Befehl neu geschrieben werden können globale Variablen zu verwenden und aktualisieren
• die „return“ Befehl, auf der gleichen Linie, könnte das gleiche tun
• das könnte eine Ausführung Spur auf dem if-Befehl sein, dass, wenn „if“ verwendet wird, wird der Rückkehrbefehl basierend auf den Eingaben für den if-Befehl neu definiert

Zugegeben, Tcl ist ein Extremfall; einer der dynamischsten Sprachen gibt. Davon abgesehen, ist es unterstreicht das Problem, dass es schwierig sein kann, um die Reinheit einer Funktion, um zu bestimmen, selbst wenn Sie es eingegeben haben.