Wird eine auswendig gelernte reine Funktion selbst als rein betrachtet?

47

Nehmen wir an, es fn(x)handelt sich um eine reine Funktion, die etwas Teuereres bewirkt, beispielsweise die Rückgabe einer Liste der Primfaktoren von x.

Nehmen wir an, wir erstellen eine auswendig gelernte Version derselben Funktion namens memoizedFn(x). Es gibt immer das gleiche Ergebnis für eine bestimmte Eingabe zurück, verwaltet jedoch einen privaten Cache früherer Ergebnisse, um die Leistung zu verbessern.

Formell gilt memoizedFn(x)als rein?

Oder wird in RP-Diskussionen ein anderer Name oder ein anderer qualifizierender Begriff verwendet, um sich auf eine solche Funktion zu beziehen? (dh eine Funktion mit Nebenwirkungen, die die Komplexität der nachfolgenden Aufrufe beeinflussen, die Rückgabewerte jedoch möglicherweise nicht beeinflussen.)

Callum
quelle
24
Vielleicht ist es nicht puristisch, aber "puristisch genug" für pragmatische Menschen ;-)
Doc Brown
2
@ DocBrown Ich stimme zu, frage mich nur, ob es einen formelleren Begriff für "rein genug" gibt
Callum
13
Das Ausführen einer reinen Funktion wird höchstwahrscheinlich den Anweisungscache, die Verzweigungsvorhersage usw. des Prozessors ändern. Aber das ist wahrscheinlich auch für Puristen "rein genug" - oder Sie können reine Funktionen ganz vergessen.
gnasher729
10
@callum Nein, es gibt keine formale Definition von "rein genug". Wenn Sie über Reinheit und die semantische Äquivalenz von zwei "referenziell transparenten" Aufrufen streiten, müssen Sie immer genau angeben, welche Semantik Sie anwenden möchten. Bei einer geringen Detailgenauigkeit der Implementierung kommt es immer zu einem Ausfall und unterschiedlichen Speichereffekten oder Zeitpunkten. Deshalb muss man pragmatisch sein: Welche Detailebene ist nützlich, um über Ihren Code nachzudenken?
Bergi
3
Aus Gründen des Pragmatismus würde ich dann sagen, dass die Reinheit davon abhängt, ob Sie die Rechenzeit als Teil der Ausgabe betrachten oder nicht. funcx(){sleep(cached_time--); return 0;}Gibt jedes Mal den gleichen Wert zurück, führt aber zu einer anderen Leistung
Mars,

Antworten:

41

Ja. Die gemerkte Version einer reinen Funktion ist auch eine reine Funktion.

Alles, was die Funktionsreinheit betrifft, ist die Auswirkung, die Eingabeparameter auf den Rückgabewert der Funktion (das Übergeben derselben Eingabe sollte immer dieselbe Ausgabe erzeugen) und alle für globale Zustände relevanten Nebenwirkungen (z. B. Text an das Terminal oder die Benutzeroberfläche oder das Netzwerk). . Rechenzeit und zusätzliche Speichernutzung spielen für die Funktionsreinheit keine Rolle.

Caches mit einer reinen Funktion sind für das Programm so gut wie unsichtbar. Eine funktionale Programmiersprache kann eine reine Funktion automatisch auf eine gespeicherte Version der Funktion optimieren, wenn sie dies als nützlich erachtet. In der Praxis ist das automatische Bestimmen, wann das Auswendiglernen vorteilhaft ist, tatsächlich ein ziemlich schwieriges Problem, aber eine solche Optimierung wäre gültig.

Lüge Ryan
quelle
19

Wikipedia definiert eine "reine Funktion" als eine Funktion mit den folgenden Eigenschaften:

  • Der Rückgabewert ist für dieselben Argumente gleich (keine Variation mit lokalen statischen Variablen, nicht lokalen Variablen, veränderlichen Referenzargumenten oder Eingabestreams von E / A-Geräten).

  • Die Auswertung hat keine Nebenwirkungen (keine Mutation von lokalen statischen Variablen, nicht lokalen Variablen, veränderlichen Referenzargumenten oder E / A-Strömen).

Tatsächlich gibt eine reine Funktion die gleiche Ausgabe bei gleicher Eingabe zurück und beeinflusst nichts anderes außerhalb der Funktion. Aus Gründen der Reinheit spielt es keine Rolle, wie die Funktion ihren Rückgabewert berechnet, solange dieselbe Ausgabe bei derselben Eingabe zurückgegeben wird.

Funktionsreine Sprachen wie Haskell verwenden routinemäßig die Speicherung , um eine Funktion durch Zwischenspeichern der zuvor berechneten Ergebnisse zu beschleunigen.

Robert Harvey
quelle
16
Ich könnte etwas vermissen, aber wie werden Sie Cache ohne Nebenwirkungen halten?
val
1
Indem Sie es in der Funktion behalten.
Robert Harvey
4
"Keine Mutation der lokalen statischen Variablen" scheint auch lokale Variablen auszuschließen, die zwischen den Aufrufen bestehen bleiben.
val
3
Dies beantwortet die Frage nicht wirklich, auch wenn Sie den Eindruck haben, dass sie rein ist.
Mars
6
@val Du hast Recht: Dieser Zustand muss etwas gelockert werden. Die rein funktionale Speicherung, auf die er sich bezieht, weist keine sichtbare Veränderung irgendwelcher statischer Daten auf. Das Ergebnis wird dann beim ersten Aufruf der Funktion berechnet und gespeichert und gibt bei jedem Aufruf denselben Wert zurück. Viele Sprachen haben ein Idiom dafür: eine static constlokale Variable in C ++ (aber nicht in C) oder eine träge ausgewertete Datenstruktur in Haskell. Es gibt eine weitere Bedingung, die Sie benötigen: Die Initialisierung muss threadsicher sein.
Davislor
7

Ja, gespeicherte reine Funktionen werden allgemein als rein bezeichnet. Dies ist besonders häufig in Sprachen wie Haskell der Fall, in denen gemerkte, träge bewertete, unveränderliche Ergebnisse ein integriertes Merkmal sind.

Es gibt eine wichtige Einschränkung: Die Memo-Funktion muss thread-sicher sein. Andernfalls kann es zu einer Race-Bedingung kommen, wenn zwei Threads versuchen, sie aufzurufen.

Ein Beispiel für einen Informatiker, der den Begriff "rein funktional" auf diese Weise verwendet, ist dieser Blog-Beitrag von Conal Elliott über das automatische Auswendiglernen:

Vielleicht überraschend, kann Memoization einfach und rein funktional in einer faulen funktionalen Sprache implementiert werden.

Es gibt viele Beispiele in der Fachliteratur, und das schon seit Jahrzehnten. In diesem Artikel aus dem Jahr 1995, „Verwenden der automatischen Speicherung als Software-Engineering-Tool in realen KI-Systemen“, wird in Abschnitt 5.2 eine sehr ähnliche Sprache verwendet, um das zu beschreiben, was wir heute als reine Funktion bezeichnen würden:

Memoization funktioniert nur für echte Funktionen, nicht für Prozeduren. Das heißt, wenn das Ergebnis einer Funktion nicht vollständig und deterministisch durch ihre Eingabeparameter spezifiziert ist, führt die Verwendung von Memoization zu falschen Ergebnissen. Die Anzahl der Funktionen, die erfolgreich gespeichert werden können, wird erhöht, indem die Verwendung eines funktionalen Programmierstils im gesamten System gefördert wird.

Einige imperative Sprachen haben eine ähnliche Redewendung. Beispielsweise wird eine static constVariable in C ++ nur einmal initialisiert, bevor ihr Wert verwendet wird, und mutiert niemals.

Davislor
quelle
3

Es hängt davon ab, wie Sie es tun.

Normalerweise wollen die Leute es sich merken, indem sie eine Art Cache-Wörterbuch mutieren. Dies hat alle Probleme, die mit einer unreinen Mutation verbunden sind, z. B. die Sorge um Parallelität, die Sorge um einen zu großen Cache usw.

Sie können jedoch ohne unreine Speichermutation speichern. Ein Beispiel ist in dieser Antwort , wo ich die gespeicherten Werte extern mit Hilfe eines lengthsArguments nachverfolge .

In dem bereitgestellten Link Robert Harvey wird eine verzögerte Bewertung verwendet, um Nebenwirkungen zu vermeiden.

Eine andere Technik, die manchmal beobachtet wird, besteht darin, das Merken als unreinen Nebeneffekt im Kontext eines IOTyps zu kennzeichnen , z. B. mit der Merkfunktion des Katzeneffekts .

Letzteres bringt den Punkt auf den Punkt, dass das Ziel manchmal eher darin besteht, Mutationen einzukapseln, als sie zu eliminieren. Die meisten funktionalen Programmierer halten es für "rein genug", um Verunreinigungen explizit und gekapselt darzustellen.

Wenn Sie möchten, dass sich ein Begriff von einer wirklich reinen Funktion unterscheidet, reicht es meiner Meinung nach aus, nur "mit einem veränderlichen Wörterbuch auswendig gelernt" zu sagen. So wissen die Leute, wie man es sicher benutzt.

Karl Bielefeldt
quelle
Ich glaube nicht, dass eine der reineren Lösungen die oben genannten Probleme löst: Während Sie alle Sorgen um die Nebenläufigkeit verlieren, verlieren Sie auch die Chance, dass zwei Anrufe gleichzeitig gestartet werden collatz(100)und collatz(200)zusammenarbeiten. Und IIUIC, das Problem, dass der Cache zu groß wird, bleibt bestehen (obwohl Haskell vielleicht ein paar nette Tricks dafür hat?).
Maaartinus
Hinweis: IOist rein. Alle unreinen Methoden auf IOund Katzen sind benannt unsafe. Async.memoizeist auch rein, so müssen wir uns nicht mit "rein genug" zufrieden geben :)
Samuel
2

In der Regel ist eine Funktion, die eine Liste zurückgibt, überhaupt nicht rein, da sie die Zuweisung von Speicherplatz erfordert und dadurch fehlschlagen kann (z. B. durch Auslösen einer Ausnahme, die nicht rein ist). Bei einer Sprache mit Wertetypen, die eine Liste als Wertetyp mit begrenzter Größe darstellen kann, tritt dieses Problem möglicherweise nicht auf. Aus diesem Grund ist Ihr Beispiel wahrscheinlich nicht rein.

Im Allgemeinen ist es sinnvoll, eine solche Funktion in Betracht zu ziehen, wenn die Speicherung fehlerfrei durchgeführt werden kann (z. B. durch statisch zugewiesenen Speicher für gespeicherte Ergebnisse und interne Synchronisierung, um den Zugriff auf diese zu steuern, wenn die Sprache Threads zulässt) rein.

R ..
quelle
0

Mit der State Monad können Sie Memoization ohne Nebenwirkungen implementieren .

[Zustandsmonade] ist im Grunde eine Funktion S => (S, A), wobei S der Typ ist, der Ihren Zustand repräsentiert, und A das Ergebnis ist, das die Funktion erzeugt - Cats State .

In Ihrem Fall wäre der Status der gespeicherte Wert oder nichts (dh Haskell Maybeoder Scala Option[A]). Wenn der gespeicherte Wert vorhanden ist, wird er als zurückgegeben A, andernfalls Awird er berechnet und sowohl als Übergangszustand als auch als Ergebnis zurückgegeben.

Samuel
quelle