Gibt es eine kanonische Definition der „reinen“ Funktion?

9

StackOverflow hat mich hier gezeigt, daher könnte die Frage für Laien etwas zutreffend sein.

Wikipedia definiert reine Funktionen als

In der Computerprogrammierung kann eine Funktion als reine Funktion beschrieben werden, wenn beide Aussagen über die Funktion gelten:

  1. 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.
  2. 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.

Es scheint jedoch keine Quellen zu zitieren - daher ist es schwer zu sagen, ob dies eine akzeptierte Definition ist oder wer sie so definiert hat.

Wenn ich mir anschaue, was die Sprachen tun, wenn sie eine Syntax / Anmerkung für "reine" Funktionen enthalten, gibt es einige verschiedene Ansätze:

  1. In D ist die einzige Einschränkung die Nichtmutation des globalen Zustands. "Reine" Funktionen können ihre Argumente mutieren.
  2. In GCC gibt es zwei Arten von "rein": pure(keine Nebenwirkungen, kann aber den globalen Zustand lesen) und const(streng rein gemäß Wikipedia-Definition).
  3. In C # ist definiert als "nimmt keine sichtbaren Zustandsänderungen vor" (was auch immer das ist).
  4. Haskell folgt der Wikipedia-Definition.

Meine Frage ist also: Gibt es eine kanonische Definition der reinen Funktion?
Und wenn ja, woher stammt sie?

Andrey Shchekin
quelle
Verwandte historische Perspektive, obwohl niemand eindeutige oder bezogene Antworten zu geben scheint.
Guildenstern
1
Dies ist keine Antwort wert, aber hier ist meine Definition: Wenn x = y (per Definition), dann ist fx = fy wahr und f verursacht keine extern messbare Zustandsänderung (dh jede Zustandsänderung ist intern in x, y, und f). Haskell nutzt dies aus. Es implementiert eine verzögerte Auswertung, indem Thunks mutiert und durch Funktionen ersetzt werden, die das Ergebnis sofort zurückgeben. Das heißt, wenn Sie (fx) auswerten, können sich f und x unter der Haube tatsächlich ändern, aber Sie können es nie sagen.
Jake

Antworten:

3

Wie in diesem Artikel Imperative Functional Programming (1993) von Peyton-Jones und Wadler (aus der Gruppe der Forscher, die Haskell geschaffen haben) erwähnt:

Wir konzentrieren uns aus zwei Gründen auf rein funktionale Lösungen, die Nebenwirkungen ausschließen. Erstens ermöglicht das Fehlen von Nebenwirkungen die uneingeschränkte Verwendung von Gleichstellungsgründen und Programmtransformationen ...

Der Schwerpunkt liegt auf dem Fehlen von Nebenwirkungen, um Programmtransformationen (dh Compiler-Optimierungen) zu ermöglichen.

Was sind Nebenwirkungen? Dieses Papier verweist wiederum auf die Integration der funktionalen und imperativen Programmierung (1986) von Gifford und Lucassen, in der vier Arten von Effektklassen erwähnt werden : Pure, Function, Observer und Procedure. Der Begriff "reine Funktion" leitet sich also aus dieser Arbeit ab.

  • Ein PURE ist referenziell transparent: Es verursacht keine Nebenwirkungen, sein Wert wird nicht durch Nebenwirkungen beeinflusst und es gibt bei jeder Auswertung denselben Wert zurück.

Beachten Sie jedoch, dass Peyton-Jones und Wadler Mängel in diesem Ansatz erwähnt haben. Bemerkenswert ist die Programmiersprache Clean , die lineare Typen verwendet, um Nebenwirkungen auf sichere Weise einzuführen (dh sicher für den Compiler). Grundsätzlich fädelt es die Welt als Variable in alle E / A-bezogenen Funktionen ein, einschließlich des Haupteinstiegspunkts .

Damit ist es möglich, dass eine reine funktionale Sprache mit der Welt interagiert und Nebenwirkungen hat (E / A, Betriebssystem, Fenstersystem usw.), die teilweise Ihrer Wikipedia-Definition widersprechen. Man kann tatsächlich sagen, dass Haskell Clean als einen seiner Einflussfaktoren hat; obwohl es von linearen Typen abweicht und ein anderes Konstrukt auf Typebene (Monaden) verwendet, um Linearität zu gewährleisten, dh jederzeit eine einzelne Referenz.

Carlosayam
quelle
"Im Grunde fädelt es die Welt als Variable ein ...". Meinen Sie eigentlich "Threads". Gibt es einen informellen Bericht darüber im Web?
Babou
Ich habe "Threading" als Metapher verwendet. Dies bedeutet, dass Sie die World- Variable von einer Funktion an eine andere übergeben müssen. Und lineare Typisierung bedeutet , dass eine solche Welt Variable nicht mehr als einmal verwendet. Dies impliziert beispielsweise, dass zum Öffnen einer Datei in einer gewünschten Funktion (f_handle, world2) = fopen file_name, world(Pseudocode) ein nächster Aufruf verwendet werden muss world2. Im Wesentlichen wird davon ausgegangen, dass Programme auf das gesamte Universum angewendet werden. Anders ausgedrückt, es gibt keine Nebenwirkungen, wenn Sie im Universum operieren :-)
Carlosayam
Wie Sie sagen, scheint das Einfädeln der Welt die Standardmethode zu sein (wie ich mich erinnere), um mit der Umgebung in der Denotationssemantik umzugehen. Der entscheidende Punkt muss also die Linearität sein. Aber dann soll die Denotationssemantik (DS) rein funktional sein, ohne Linearitätsbeschränkung. Ich denke, DS ist eine mathematische Abstraktion und hat keine Bedenken, viele Welten zu jonglieren. Computing ist physikalisch und Linearität ermöglicht die Evolution der Welt, aber es kann immer nur eine Welt gleichzeitig existieren (was wahrscheinlich die Bewertung sequentiell macht). Was ist die Semantik von 2 Clean-Programmen, die gleichzeitig ausgeführt werden :-)?
Babou
Ist das Papier von Gifford und Lucassen im Internet verfügbar?
Babou
Ich habe Zugang über die Uni.
Carlosayam
-1

Die Definition von Wikipedia ist kanonisch. Die zwei entscheidenden Anforderungen sind:

  • Der Rückgabewert und das Verhalten der Funktion sind eine deterministische Funktion der Argumente, die explizit an die Funktion übergeben wurden.

  • Ein Aufruf der Funktion hat keine beobachtbaren Nebenwirkungen.

Genau genommen sollten D und gcc das Wort "rein" nicht so verwenden, wie sie es tun. Es ist ein Missbrauch der Standardterminologie.

DW
quelle