Vorteile der reinen Funktion

81

Heute habe ich über reine Funktion gelesen und war verwirrt mit ihrer Verwendung:

Eine Funktion gilt als rein, wenn sie denselben Wertesatz für denselben Eingangssatz zurückgibt und keine beobachtbaren Nebenwirkungen aufweist.

zB strlen()ist eine reine Funktion, während rand()es eine unreine ist.

__attribute__ ((pure)) int fun(int i)
{
    return i*i;
}

int main()
{
    int i=10;
    printf("%d",fun(i));//outputs 100
    return 0;
}

http://ideone.com/33XJU

Das obige Programm verhält sich genauso wie ohne pureDeklaration.

Was sind die Vorteile der Deklaration einer Funktion als pure[wenn sich die Ausgabe nicht ändert]?

Grüner Kobold
quelle
7
Ja - sehen Sie sich die generierte Baugruppe an.
Philip Kendall
4
Ich denke nicht, dass diese Definition von Reinheit korrekt ist - printfzum Beispiel würde sie sich qualifizieren (zweimal mit denselben Argumenten aufzurufen, ergibt denselben Rückgabewert), aber sie ist nicht rein.
tdammers
14
@tdammers: In der Tat fehlt das ...and no side-effects...Teil.
Frerich Raabe
2
@ Ben: Woher kommt die Entropie? Wir haben es hier mit (theoretisch) deterministischen Maschinen zu tun. Die einzige Möglichkeit, echte Entropie in sie zu bringen, sind externe Quellen, was Nebenwirkungen bedeutet. Natürlich könnten wir Programmiersprachen erlauben, nicht deterministische Funktionen zu definieren, indem wir so tun, als ob die technischen Nebenwirkungen nicht vorhanden wären und die Funktionen wirklich nicht deterministisch sind. Wenn wir dies jedoch tun, gehen die meisten praktischen Vorteile der Verfolgung der Reinheit verloren.
tdammers
3
tdammers ist richtig - die oben angegebene Definition von pure ist falsch. Rein bedeutet, dass die Ausgabe nur von den Eingaben für die Funktion abhängt . Es dürfen auch keine beobachtbaren Nebenwirkungen auftreten. "Gleiche Ausgabe für gleiche Eingabe" ist eine sehr ungenaue Zusammenfassung dieser Anforderungen. en.wikipedia.org/wiki/Pure_function
Dancrumb

Antworten:

144

pure Lässt den Compiler wissen, dass er bestimmte Optimierungen an der Funktion vornehmen kann: Stellen Sie sich ein bisschen Code vor

for (int i = 0; i < 1000; i++)
{
    printf("%d", fun(10));
}

Mit einer reinen Funktion kann der Compiler wissen, dass er fun(10)nur einmal und nicht 1000-mal auswerten muss . Für eine komplexe Funktion ist das ein großer Gewinn.

Philip Kendall
quelle
Dh Sie können sicher Memoization verwenden
Joel Coehoorn
@mob Was meinst du? Warum nicht?
Konrad Rudolph
15
Da Sie die Zeichenfolge (Zeichenfolge ab einer bestimmten Adresse) ändern können, ohne die Eingabe (den Zeiger auf die Adresse, an der die Zeichenfolge beginnt) zu ändern, können Sie sie nicht speichern. Es wäre nur eine reine Funktion in einer Sprache mit unveränderlichen Zeichenfolgen (z. B. Java).
Mob
5
@KonradRudolph: Stellen Sie sich eine Saite mit einer Länge von 1000 vor. Rufen Sie strlenes an. Dann wieder. Gleiches ja? Ändern Sie nun das zweite Zeichen \0. Gibt strlenjetzt noch 1000 zurück? Die Startadresse ist dieselbe (== Eingabe ist dieselbe), aber die Funktion gibt jetzt einen anderen Wert zurück.
Mike Bailey
5
@mob Das ist ein guter Einwand, offensichtlich hast du recht. Ich wurde durch die Tatsache irregeführt, dass sogar Bücher behaupten, dass strlen(in GCC / glibc) tatsächlich rein ist. Ein Blick auf die glibc-Implementierung hat jedoch gezeigt, dass dies falsch ist.
Konrad Rudolph
34

Wenn Sie sagen, dass eine Funktion "rein" ist, garantieren Sie, dass sie keine äußerlich sichtbaren Nebenwirkungen hat (und wie ein Kommentar sagt, wenn Sie lügen, können schlimme Dinge passieren). Zu wissen, dass eine Funktion 'rein' ist, hat Vorteile für den Compiler, der dieses Wissen nutzen kann, um bestimmte Optimierungen vorzunehmen.

In der GCC-Dokumentation steht Folgendes zu dem pureAttribut:

rein

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 einer gemeinsamen Eliminierung von Unterausdrücken und einer Schleifenoptimierung unterliegen. Diese Funktionen sollten mit dem Attribut pure deklariert werden. Beispielsweise,

          int square (int) __attribute__ ((pure));

Die Antwort von Philip zeigt bereits, wie das Wissen, dass eine Funktion "rein" ist, bei Schleifenoptimierungen helfen kann.

Hier ist eine für die gemeinsame Eliminierung von Subausdrücken (angegeben fooist rein):

a = foo (99) * x + y;
b = foo (99) * x + z;

Kann werden:

_tmp = foo (99) * x;
a = _tmp + y;
b = _tmp + z;
ArjunShankar
quelle
3
Ich bin mir nicht sicher, ob dies jemand tut, aber reine Funktionen ermöglichen es dem Compiler auch, neu zu ordnen, wenn die Funktion aufgerufen wird, falls er eine Neuordnung für vorteilhaft hält. Wenn die Möglichkeit von Nebenwirkungen besteht, muss der Compiler konservativer sein.
mpdonadio
@MPD - Ja, das klingt vernünftig. Und da eine callAnweisung einen Engpass für superskalare CPUs darstellt, kann eine Hilfe des Compilers hilfreich sein.
ArjunShankar
Ich erinnere mich vage an die Verwendung eines DSP-Compilers vor einigen Jahren, der diese Technik verwendet hat, um früher / später Rückgabewerte zu erhalten. Dies ermöglichte es, Pipeline-Stillstände zu minimieren.
mpdonadio
1
Könnte "foo (99)" vorberechnet werden, da 99 eine Konstante ist und foo immer das gleiche Ergebnis zurückgibt? Vielleicht in einer Art zweistufiger Kompilierung?
Markwatson
1
@markwatson - Ich bin nicht sicher. Es kann Fälle geben, in denen dies einfach nicht möglich ist. zB wenn fooes Teil einer anderen Kompilierungseinheit (einer anderen C-Datei) oder in einer vorkompilierten Bibliothek ist. In beiden Fällen weiß der Compiler nicht, was er footut, und kann nicht vorberechnen.
ArjunShankar
28

Zusätzlich zu den möglichen Laufzeitvorteilen ist eine reine Funktion beim Lesen von Code viel einfacher zu überlegen. Darüber hinaus ist es viel einfacher, eine reine Funktion zu testen, da Sie wissen, dass der Rückgabewert nur von den Werten der Parameter abhängt.

Frerich Raabe
quelle
2
+1, Ihr Punkt zum Testen ist interessant. Kein Auf- und Abbau erforderlich.
ArjunShankar
15

Eine nicht reine Funktion

int foo(int x, int y) // possible side-effects

ist wie eine Erweiterung einer reinen Funktion

int bar(int x, int y) // guaranteed no side-effects

in dem Sie neben den expliziten Funktionsargumenten x, y den Rest des Universums (oder alles, mit dem Ihr Computer kommunizieren kann) als implizite potenzielle Eingabe haben. Ebenso ist neben dem expliziten ganzzahligen Rückgabewert alles, worauf Ihr Computer schreiben kann, implizit Teil des Rückgabewerts.

Es sollte klar sein, warum es viel einfacher ist, über eine reine Funktion nachzudenken als über eine nicht reine.

Giorgio
quelle
1
+1: Die Verwendung des Universums als potenzielle Eingabe ist eine sehr gute Möglichkeit, den Unterschied zwischen rein und nicht rein zu erklären.
ArjunShankar
in der Tat ist dies die Idee hinter Monaden.
Kristopher Micinski
7

Nur als Add-On möchte ich erwähnen, dass C ++ 11 die Dinge mit dem Schlüsselwort constexpr etwas codiert. Beispiel:

#include <iostream>
#include <cstring>

constexpr unsigned static_strlen(const char * str, unsigned offset = 0) {
        return (*str == '\0') ? offset : static_strlen(str + 1, offset + 1);
}

constexpr const char * str = "asdfjkl;";

constexpr unsigned len = static_strlen(str); //MUST be evaluated at compile time
//so, for example, this: int arr[len]; is legal, as len is a constant.

int main() {
    std::cout << len << std::endl << std::strlen(str) << std::endl;
    return 0;
}

Die Einschränkungen bei der Verwendung von constexpr machen es so, dass die Funktion nachweislich rein ist. Auf diese Weise kann der Compiler aggressiver optimieren (stellen Sie bitte sicher, dass Sie die Schwanzrekursion verwenden!) Und die Funktion zur Kompilierungszeit anstatt zur Laufzeit auswerten.

Um Ihre Frage zu beantworten: Wenn Sie C ++ verwenden (ich weiß, dass Sie C gesagt haben, aber sie sind verwandt), ermöglicht das Schreiben einer reinen Funktion im richtigen Stil dem Compiler, alle möglichen coolen Dinge mit der Funktion zu tun: -)

Robert Mason
quelle
4

Im Allgemeinen haben Pure-Funktionen drei Vorteile gegenüber unreinen Funktionen, die der Compiler nutzen kann:

Caching

Nehmen wir an, Sie haben eine reine Funktion f, die 100000 Mal aufgerufen wird. Da sie deterministisch ist und nur von ihren Parametern abhängt, kann der Compiler ihren Wert einmal berechnen und bei Bedarf verwenden

Parallelität

Reine Funktionen lesen oder schreiben nicht in einen gemeinsam genutzten Speicher und können daher ohne unerwartete Konsequenzen in separaten Threads ausgeführt werden

Referenzübergabe

Eine Funktion f(struct t)erhält ihr Argument tnach Wert, und andererseits kann der Compiler tunter Bezugnahme darauf übergeben, fob sie als rein deklariert ist, und gleichzeitig sicherstellen, dass sich der Wert von tnicht ändert und Leistungssteigerungen erzielt


Zusätzlich zu den Überlegungen zur Kompilierungszeit können reine Funktionen ziemlich einfach getestet werden: Rufen Sie sie einfach auf.

Sie müssen keine Objekte erstellen oder Verbindungen zu DBs / Dateisystemen herstellen.

Uri Goren
quelle