Kann ein Compiler reine Funktionen ohne die Typinformationen zur Reinheit automatisch erkennen?

Question 1

Ich argumentiere also mit meinem Freund, der behauptet, dass ein Compiler wie GCC eine reine Funktion automatisch ohne Typinformationen erkennen kann. Ich bezweifle das.

Sprachen wie D oder Haskell haben Reinheit in ihren Typsystemen und ein Programmierer definiert explizit, welche Funktion rein ist oder nicht. Eine reine Funktion hat keine Nebenwirkungen und kann daher sehr einfach parallelisiert werden.

Die Frage ist also: Ist das alles nötig oder nicht? Könnte ein Compiler Reinheit ohne Meta- oder Typinformationen erkennen, indem er einfach annimmt, dass alles, was IO ausführt oder automatisch auf globale Variablen zugreift, nicht rein ist?

Question 2

Sicher, man kann in manchen Fällen reine Funktionen erkennen. Zum Beispiel,

int f(int x)
{
    return x*2;
}

kann mit einfacher statischer Analyse als rein nachgewiesen werden. Die Schwierigkeit besteht darin, dies im Allgemeinen zu tun, und das Erkennen von Schnittstellen, die einen “internen” Zustand verwenden, aber extern rein sind, ist im Grunde unmöglich.

GCC hat die Warnmöglichkeiten -Wsuggest-attribute=pure und -Wsuggest-attribute=constdie Funktionen vorschlagen, die Kandidaten für die sein könnten pure und const Attribute. Ich bin mir nicht sicher, ob es sich dafür entscheidet, konservativ zu sein (dh viele reine Funktionen zu vermissen, es aber nie für eine nicht reine Funktion vorzuschlagen) oder den Benutzer entscheiden lässt.

Beachten Sie, dass die GCC-Definition von pure ist “nur von Argumenten und globalen Variablen abhängig”:

Viele Funktionen haben außer dem Rückgabewert keine Auswirkungen und ihr Rückgabewert hängt nur von den Parametern und/oder globalen Variablen ab. Eine solche Funktion kann genau wie ein arithmetischer Operator der Eliminierung gemeinsamer Unterausdrücke und der Schleifenoptimierung unterzogen werden. Diese Funktionen sollten mit dem Attribut deklariert werden pure.

— GCC-Handbuch

Strikte Reinheit, dh gleiche Ergebnisse für gleiche Argumente unter allen Umständen, wird durch die repräsentiert const -Attribut, aber eine solche Funktion kann nicht einmal einen an sie übergebenen Zeiger dereferenzieren. Also die Parallelisierungsmöglichkeiten z pure Funktionen sind begrenzt, aber viel weniger Funktionen können es sein const im Vergleich zu den reinen Funktionen kann man in einer Sprache wie Haskell schreiben.

Übrigens ist die automatische Parallelisierung reiner Funktionen nicht so einfach, wie Sie vielleicht denken; der schwierige Teil wird entscheiden was zu parallelisieren. Parallelisieren Sie Berechnungen, die zu billig sind, und Overhead macht es sinnlos. Wenn Sie nicht genug parallelisieren, profitieren Sie nicht von den Vorteilen. Ich kenne keine praktische funktionale Sprachimplementierung, die aus diesem Grund eine automatische Parallelisierung durchführt, obwohl Bibliotheken dies mögen Repa Parallelisieren Sie viele Operationen hinter den Kulissen ohne explizite Parallelität im Benutzercode.

Question 3

Es gibt ein weiteres Problem. In Betracht ziehen

int isthispure(int i) {
   if (false) return getchar();
   return i + 42;
}

Die Funktion ist effektiv rein, obwohl sie unreinen Code enthält, aber dieser Code kann nicht erreicht werden. Nun nehme an false wird ersetzt durch g(i) aber wir wissen ziemlich sicher, dass g(i) falsch ist (zum Beispiel könnte g prüfen, ob sein Argument a ist Lychrel-Nummer). Um zu beweisen, dass Isthispur tatsächlich rein ist, müsste der Compiler beweisen, dass keine Lychrel-Zahlen existieren.

(Ich gebe zu, dass dies eine ziemlich theoretische Überlegung ist. Man könnte auch entscheiden, dass eine Funktion, die einen unreinen Code enthält, selbst unrein ist. Dies wird jedoch meiner Meinung nach nicht durch das C-Typ-System gerechtfertigt.)

Question 4

Die Bestimmung, ob eine Funktion rein ist (selbst in dem von GCC verwendeten begrenzten Sinne), entspricht dem Halteproblem, daher lautet die Antwort “nicht für beliebige Funktionen”. Es ist möglich, automatisch zu erkennen, dass einige Funktionen rein und andere nicht rein sind, und den Rest als „unbekannt“ zu kennzeichnen, was in einigen Fällen eine automatische Parallelisierung ermöglicht.

Meiner Erfahrung nach sind selbst Programmierer nicht sehr gut darin, solche Dinge herauszufinden, also möchte ich, dass das Typsystem dabei hilft, den Überblick zu behalten Für michnicht nur für den Optimierer.

Question 5

Ich entdeckte beim Schreiben eines Artikels Vergleich der Leistung von C# und C++ dass Visual C++ tatsächlich eine reine Funktion mittlerer Komplexität erkennen kann, während a aufgerufen wird Funktion, die ein Polynom berechnet.

Ich habe die Polynomfunktion in einer Schleife aufgerufen, um Zeit auf der Uhr zu verschlingen. Der Compiler hat den Aufruf so optimiert, dass er einmal ausgeführt wird, bevor die Schleife gestartet wird, und das Ergebnis innerhalb der Schleife wiederverwendet. Dazu müsste es wissen, dass es keine Nebenwirkungen gibt.

Ich muss aber sagen, es ist schön, dazu in der Lage zu sein Garantie dass der Compiler eine Optimierung vornehmen kann, indem er eine Funktion als rein markiert, und es dient auch als Form der Dokumentation.