Was ist referentielle Transparenz?

38

Ich habe das in imperativen Paradigmen gesehen

f (x) + f (x)

ist möglicherweise nicht dasselbe wie:

2 * f (x)

In einem funktionalen Paradigma sollte es jedoch dasselbe sein. Ich habe versucht, beide Fälle in Python und Schema zu implementieren , aber für mich sehen sie ziemlich einfach aus.

Was wäre ein Beispiel, das den Unterschied zur gegebenen Funktion aufzeigen könnte?

Asgard
quelle
7
Sie können und tun dies häufig, indem Sie referenziell transparente Funktionen in Python schreiben. Der Unterschied ist, dass die Sprache es nicht erzwingt.
Karl Bielefeldt
5
in C und gleich: f(x++)+f(x++)nicht die gleiche sein könnte 2*f(x++)(? in C ist es besonders schön , wenn Sachen wie , dass innerhalb von Makros versteckt ist - habe ich an , dass meine Nase brach wette , Sie)
gnat
Meines Erachtens ist das Beispiel von @ gnat der Grund, warum funktionsorientierte Sprachen wie R Pass-by-Reference verwenden und Funktionen, die ihre Argumente ändern, explizit vermeiden. Zumindest in R kann es tatsächlich schwierig sein, diese Einschränkungen zu umgehen (zumindest auf stabile, tragbare Weise), ohne sich in das komplizierte System der Umgebungen, Namespaces und Suchpfade der Sprache einzuarbeiten.
Shadowtalker
4
@ssdecontrol: Wenn Sie referenzielle Transparenz haben, liefern Wertübergabe und Referenzübergabe immer genau das gleiche Ergebnis, sodass es keine Rolle spielt, welche Sprache verwendet wird. Funktionale Sprachen werden häufig mit einem Wert angegeben, der der semantischen Klarheit halber dem Vorbeigehen ähnelt. Bei ihrer Implementierung wird jedoch häufig ein Referenzvorbeigehen für die Leistung verwendet (oder sogar beides, je nachdem, welche Sprache für den jeweiligen Kontext schneller ist).
Jörg W Mittag
4
@gnat: Insbesondere f(x++)+f(x++)kann absolut alles sein, da es undefiniertes Verhalten hervorruft . Aber das hat nicht wirklich mit referentieller Transparenz zu tun - was für diesen Aufruf nicht hilfreich wäre, ist für referentiell transparente Funktionen wie in sin(x++)+sin(x++)auch undefiniert . Könnte 42 sein, könnte Ihre Festplatte formatieren, könnte Dämonen haben, die aus der Nase des Benutzers fliegen ...
Christopher Creutzig

Antworten:

62

Referenzielle Transparenz, auf eine Funktion bezogen, gibt an, dass Sie das Ergebnis der Anwendung dieser Funktion nur anhand der Werte ihrer Argumente bestimmen können. Sie können referenziell transparente Funktionen in jeder Programmiersprache schreiben, z. B. Python, Scheme, Pascal, C.

Andererseits können Sie in den meisten Sprachen auch nicht referenziell transparente Funktionen schreiben. Zum Beispiel diese Python-Funktion:

counter = 0

def foo(x):
  global counter

  counter += 1
  return x + counter

ist nicht referenziell transparent, in der Tat aufrufen

foo(x) + foo(x)

und

2 * foo(x)

erzeugt für jedes Argument unterschiedliche Werte x. Der Grund dafür ist, dass die Funktion eine globale Variable verwendet und ändert. Daher hängt das Ergebnis jedes Aufrufs von diesem sich ändernden Zustand ab und nicht nur vom Argument der Funktion.

Haskell, eine rein funktionale Sprache, trennt die Ausdrucksbewertung, in der reine Funktionen angewendet werden und die immer referenziell transparent ist , strikt von der Aktionsausführung (Verarbeitung von Sonderwerten), die nicht referenziell transparent ist, dh die jeweils gleiche Aktion ausführen kann anderes Ergebnis.

Also für jede Haskell-Funktion

f :: Int -> Int

und jede ganze Zahl x, es ist immer wahr, dass

2 * (f x) == (f x) + (f x)

Ein Beispiel für eine Aktion ist das Ergebnis der Bibliotheksfunktion getLine:

getLine :: IO String

Diese Funktion (eigentlich eine Konstante) liefert als Ergebnis der Ausdrucksauswertung zunächst einen reinen Wert vom Typ IO String. Werte dieses Typs sind Werte wie alle anderen: Sie können sie weitergeben, in Datenstrukturen einfügen, mit speziellen Funktionen zusammenstellen usw. Zum Beispiel können Sie eine Liste von Aktionen wie folgt erstellen:

[getLine, getLine] :: [IO String]

Aktionen sind insofern besonders, als Sie der Haskell-Laufzeit anweisen können, sie auszuführen, indem Sie Folgendes schreiben:

main = <some action>

In diesem Fall durchläuft die Laufzeit beim Starten Ihres Haskell-Programms die daran gebundene Aktion mainund führt sie aus, wobei möglicherweise Nebenwirkungen auftreten. Daher ist die Aktionsausführung nicht referenziell transparent, da die zweimalige Ausführung derselben Aktion je nach dem, was die Laufzeit als Eingabe erhält, zu unterschiedlichen Ergebnissen führen kann.

Dank des Typsystems von Haskell kann eine Aktion niemals in einem Kontext verwendet werden, in dem ein anderer Typ erwartet wird, und umgekehrt. Wenn Sie also die Länge eines Strings ermitteln möchten, können Sie die folgende lengthFunktion verwenden:

length "Hello"

gibt 5 zurück. Wenn Sie jedoch die Länge eines vom Terminal gelesenen Strings ermitteln möchten, können Sie nicht schreiben

length (getLine)

weil Sie einen Typfehler erhalten: lengthErwartet eine Eingabe von Typ Liste (und ein String ist in der Tat eine Liste), getLineist aber ein Wert von Typ IO String(eine Aktion). Auf diese Weise stellt das Typsystem sicher, dass ein Aktionswert wie getLine(dessen Ausführung außerhalb der Kernsprache erfolgt und der möglicherweise nicht referenziell transparent ist) nicht in einem Nicht-Aktionswert vom Typ verborgen werden kann Int.

BEARBEITEN

Um eine exakte Frage zu beantworten, ist hier ein kleines Haskell-Programm, das eine Zeile von der Konsole liest und ihre Länge ausgibt.

main :: IO () -- The main program is an action of type IO ()
main = do
          line <- getLine
          putStrLn (show (length line))

Die Hauptaktion besteht aus zwei Unteraktionen, die nacheinander ausgeführt werden:

  1. getlinevom Typ IO String,
  2. Die zweite wird konstruiert, indem die Funktion putStrLndes Typs String -> IO ()in ihrem Argument ausgewertet wird .

Genauer gesagt wird die zweite Aktion von erstellt

  1. Bindung linean den von der ersten Aktion gelesenen Wert,
  2. die reinen Funktionen auswerten length(Länge als ganze Zahl berechnen) und dann show(die ganze Zahl in eine Zeichenkette verwandeln),
  3. Aufbau der Aktion durch Anwenden der Funktion putStrLnauf das Ergebnis von show.

An diesem Punkt kann die zweite Aktion ausgeführt werden. Wenn Sie "Hallo" eingegeben haben, wird "5" ausgegeben.

Beachten Sie, dass Sie, wenn Sie einen Wert aus einer Aktion mit der <-Notation erhalten, diesen Wert nur in einer anderen Aktion verwenden können, z. B. können Sie nicht schreiben:

main = do
          line <- getLine
          show (length line) -- Error:
                             -- Expected type: IO ()
                             --   Actual type: String

weil show (length line)hat Typ, Stringwohingegen die do-Notation erfordert, dass einer Aktion ( getLinevom Typ IO String) eine andere Aktion (z . B. putStrLn (show (length line))vom Typ IO ()) folgt .

BEARBEITEN 2

Jörg W. Mittag definiert referentielle Transparenz allgemeiner als ich (ich habe seine Antwort positiv bewertet). Ich habe eine eingeschränkte Definition verwendet, da sich das Beispiel in der Frage auf den Rückgabewert von Funktionen konzentriert und ich diesen Aspekt veranschaulichen wollte. RT bezieht sich jedoch im Allgemeinen auf die Bedeutung des gesamten Programms, einschließlich Änderungen des globalen Status und Interaktionen mit der Umgebung (IO), die durch die Auswertung eines Ausdrucks verursacht werden. Um eine korrekte, allgemeine Definition zu erhalten, sollten Sie sich auf diese Antwort beziehen.

Giorgio
quelle
10
Kann der Downvoter vorschlagen, wie ich diese Antwort verbessern kann?
Giorgio
Wie kann man also die Länge eines Strings vom Terminal in Haskell abrufen?
sbichenko
2
Dies ist äußerst umständlich, aber der Vollständigkeit halber ist es nicht das Typensystem von Haskell, das sicherstellt, dass sich Aktionen und reine Funktionen nicht mischen. Es ist die Tatsache, dass die Sprache keine unreinen Funktionen bietet, die Sie direkt aufrufen können. Sie können Haskells IOTyp in jeder Sprache mit Lambdas und Generika ziemlich einfach implementieren , aber da jeder printlndirekt anrufen kann, IOgarantiert die Implementierung keine Reinheit. Es wäre nur eine Konvention.
Doval
Ich meinte, dass (1) alle Funktionen rein sind (natürlich sind sie rein, weil die Sprache keine unreinen liefert, obwohl es meines Wissens einige Mechanismen gibt, um dies zu umgehen), und (2) reine Funktionen und unreine Aktionen haben unterschiedliche Typen, daher können sie nicht gemischt werden. Übrigens, was meinst du mit direktem Anruf ?
Giorgio
6
Ihr Hinweis, dass Sie getLinenicht referenziell transparent sind, ist falsch. Sie präsentieren, getLineals würde es zu einer Zeichenfolge ausgewertet oder auf diese reduziert, wobei die jeweilige Zeichenfolge von der Eingabe des Benutzers abhängt. Das ist falsch. IO Stringenthält nicht mehr einen String als Maybe String. IO Stringist ein Rezept dafür, vielleicht einen String zu erhalten und als Ausdruck so rein wie jeder andere in Haskell.
LuxuryMode
25
def f(x): return x()

from random import random
f(random) + f(random) == 2*f(random)
# => False

Dies ist jedoch nicht das, was referenzielle Transparenz bedeutet. RT bedeutet, dass Sie jeden Ausdruck im Programm durch das Ergebnis der Auswertung dieses Ausdrucks ersetzen können (oder umgekehrt), ohne die Bedeutung des Programms zu ändern.

Nehmen Sie zum Beispiel das folgende Programm:

def f(): return 2

print(f() + f())
print(2)

Dieses Programm ist referenziell transparent. Ich kann eines oder beide Vorkommen von f()durch ersetzen 2und es wird immer noch dasselbe funktionieren:

def f(): return 2

print(2 + f())
print(2)

oder

def f(): return 2

print(f() + 2)
print(2)

oder

def f(): return 2

print(2 + 2)
print(f())

werden sich alle gleich verhalten.

Nun, eigentlich habe ich betrogen. Ich sollte in der Lage sein, den Aufruf von printdurch seinen Rückgabewert (der überhaupt kein Wert ist) zu ersetzen, ohne die Bedeutung des Programms zu ändern. Wenn ich jedoch nur die beiden printAnweisungen entferne , ändert sich die Bedeutung des Programms: Vorher druckte es etwas auf den Bildschirm, danach nicht. E / A ist nicht referenziell transparent.

Die einfache Faustregel lautet: Wenn Sie einen beliebigen Ausdruck, Unterausdruck oder Unterprogrammaufruf durch den Rückgabewert dieses Ausdrucks, Unterausdrucks oder Unterprogrammaufrufs an einer beliebigen Stelle im Programm ersetzen können, ohne dass das Programm seine Bedeutung ändert, haben Sie einen Verweis Transparenz. In der Praxis bedeutet dies, dass Sie keine E / A haben, keinen veränderlichen Zustand haben und keine Nebenwirkungen haben können. In jedem Ausdruck darf der Wert des Ausdrucks nur von den Werten der Bestandteile des Ausdrucks abhängen. Und in jedem Unterprogrammaufruf darf der Rückgabewert nur von den Argumenten abhängen.

Jörg W. Mittag
quelle
4
"Kann keinen veränderlichen Zustand haben": Nun, Sie können ihn haben, wenn er verborgen ist und das beobachtbare Verhalten Ihres Codes nicht beeinflusst. Denken Sie zB an das Auswendiglernen.
Giorgio
4
@Giorgio: Das ist vielleicht subjektiv, aber ich würde argumentieren, dass zwischengespeicherte Ergebnisse nicht wirklich "veränderlicher Zustand" sind, wenn sie verborgen sind und keine beobachtbaren Auswirkungen haben. Unveränderlichkeit ist immer eine Abstraktion, die auf veränderlicher Hardware implementiert ist. Häufig wird es von der Sprache bereitgestellt (wobei die Abstraktion "ein Wert" angegeben wird, auch wenn sich der Wert während der Ausführung zwischen Registern und Speicherstellen bewegen kann und verschwindet, sobald bekannt ist, dass er nie wieder verwendet wird), aber es ist nicht weniger gültig, wenn er verwendet wird bereitgestellt von einer Bibliothek oder so weiter. (Vorausgesetzt, es ist natürlich korrekt implementiert.)
Ruakh
1
+1 Ich mag das printBeispiel wirklich . Vielleicht ist eine Möglichkeit, dies zu sehen, dass das, was auf dem Bildschirm gedruckt wird, Teil des "Rückgabewerts" ist. Wenn Sie printmit seiner Funktion den Rückgabewert und die entsprechende Schreibweise auf dem Terminal ersetzen können, funktioniert das Beispiel.
Pierre Arlaud
1
@Giorgio Raum- / Zeitnutzung kann im Sinne der referentiellen Transparenz nicht als Nebeneffekt angesehen werden. Das würde machen 4und 2 + 2nicht austauschbar sein, da sie unterschiedliche Laufzeiten haben, und der springende Punkt der referenziellen Transparenz ist, dass Sie einen Ausdruck durch das ersetzen können, wonach er ausgewertet wird. Die wichtige Überlegung wäre die Fadensicherheit.
Doval
1
@overexchange: Referentielle Transparenz bedeutet, dass Sie jeden Unterausdruck durch seinen Wert ersetzen können, ohne die Bedeutung des Programms zu ändern. listOfSequence.append(n)kehrt zurück None, so dass Sie in der Lage sein sollten, jeden Aufruf von listOfSequence.append(n)durch zu ersetzen, Noneohne die Bedeutung Ihres Programms zu ändern. Können Sie das tun? Wenn nicht, ist es nicht referenziell transparent.
Jörg W Mittag
1

Teile dieser Antwort stammen direkt aus einem unvollendeten Tutorial zur funktionalen Programmierung , das auf meinem GitHub-Account gehostet wird:

Eine Funktion gilt als referenziell transparent, wenn sie bei gleichen Eingabeparametern immer die gleiche Ausgabe liefert (Rückgabewert). Wenn man eine Existenzberechtigung für reine funktionale Programmierung sucht, ist referentielle Transparenz ein guter Kandidat. Wenn Sie mit Formeln in Algebra, Arithmetik und Logik argumentieren, ist diese Eigenschaft - auch Substituierbarkeit von Gleichheit für Gleichheit genannt - von so grundlegender Bedeutung, dass sie normalerweise als selbstverständlich angesehen wird ...

Betrachten Sie ein einfaches Beispiel:

x = 42

In einer reinen funktionalen Sprache sind die linke und die rechte Seite des Gleichheitszeichens in beide Richtungen austauschbar. Das heißt, anders als in einer Sprache wie C behauptet die obige Notation wirklich eine Gleichheit. Dies hat zur Folge, dass wir über Programmcode wie über mathematische Gleichungen nachdenken können.

Aus dem Haskell-Wiki :

Reine Berechnungen liefern bei jedem Aufruf denselben Wert. Diese Eigenschaft wird als referentielle Transparenz bezeichnet und ermöglicht die Durchführung von Gleichungsargumenten für den Code ...

Im Gegensatz dazu wird die Art der von C-ähnlichen Sprachen ausgeführten Operation manchmal als destruktive Zuweisung bezeichnet .

Der Begriff pure wird häufig verwendet, um eine für diese Diskussion relevante Eigenschaft von Ausdrücken zu beschreiben. Damit eine Funktion als rein betrachtet wird,

  • Es dürfen keine Nebenwirkungen auftreten
  • es muss referenziell transparent sein.

Gemäß der Black-Box-Metapher, die in zahlreichen mathematischen Lehrbüchern zu finden ist, sind die Interna einer Funktion vollständig von der Außenwelt abgeschlossen. Ein Nebeneffekt ist, wenn eine Funktion oder ein Ausdruck gegen dieses Prinzip verstößt - das heißt, die Prozedur darf auf irgendeine Weise mit anderen Programmeinheiten kommunizieren (z. B. um Informationen auszutauschen und auszutauschen).

Zusammenfassend ist die referenzielle Transparenz ein Muss, damit sich Funktionen wie echte mathematische Funktionen verhalten , auch in der Semantik von Programmiersprachen.

yesthisisuser
quelle
dies scheint mit zu öffnen Wort- für -Wort - Kopie von hier genommen : „Eine Funktion referentiell transparent sein soll , wenn es die gleichen Eingangsparameter gegeben, immer die gleiche Ausgabe ...“ Stack Exchange hat Regeln für Plagiate sind Sind Sie sich dessen bewusst? „ Das Plagiat ist die seelenlos Akt der Brocken von jemand anderem zu arbeiten, schlug Ihrem Namen darauf und Leiten Sie sich als der ursprüngliche Autor Kopieren ...“
gnat
3
Ich habe diese Seite geschrieben.
Yesthisisuser
Wenn dies der Fall ist, sollten Sie erwägen, es weniger plagiatisch erscheinen zu lassen, da die Leser keine Möglichkeit haben, dies zu beurteilen. Wissen Sie, wie das bei SE geht? 1) Sie beziehen sich auf die Originalquelle, wie "Wie (ich habe) geschrieben [here](link to source)...", gefolgt von 2) der korrekten Formatierung des Zitats (verwenden Sie Anführungszeichen oder besser noch ein > Symbol dafür). Es würde auch nicht schaden, wenn Sie nicht nur eine allgemeine Anleitung geben, sondern auch konkrete Fragen beantworten, in diesem Fall über f(x)+f(x)/ 2*f(x), siehe Wie man antwortet - ansonsten könnte es so aussehen, als würden Sie einfach für Ihre Seite werben
Uhr
1
Theoretisch habe ich diese Antwort verstanden. Praktisch nach diesen Regeln muss ich jedoch die Hagelkörner-Sequenzliste in diesem Programm zurückgeben . Wie mache ich das?
Überaustausch