Ersetzen von Funktionen mit Table Lookups

Brian hat gerade gezeigt, dass Funktionen auch Daten sind. Funktionen im Allgemeinen sind nur eine Zuordnung eines Satzes zu einem anderen: y = f(x) ist die Zuordnung von Menge {x} zu Menge {y}: f:X->Y . Die Tabellen sind auch Abbildungen: [x1, x2, ..., xn] -> [y1, y2, ..., yn] .

Wenn die Funktion auf einer endlichen Menge operiert (dies ist bei der Programmierung der Fall), dann kann sie durch eine Tabelle ersetzt werden, die diese Zuordnung darstellt. Wie Brian erwähnte, durchläuft jeder imperative Programmierer diese Phase des Verständnisses, dass die Funktionen nur aus Leistungsgründen durch die Tabellen-Lookups ersetzt werden können.

Aber es bedeutet nicht, dass alle Funktionen leicht mit den Tabellen ersetzt werden können oder sollten. Es bedeutet nur, dass Sie das theoretisch für jede Funktion tun können. Also die Schlussfolgerung wäre, dass die Funktionen Daten sind, weil Tabellen (im Zusammenhang mit der Programmierung natürlich).

Es gibt einen schönen Trick in Mathematica, der eine Tabelle als Nebeneffekt der Evaluierung von Funktionsaufrufen als Umschreibungsregeln erstellt. Betrachten Sie die klassischen langsamen Fibonacci

Die ersten beiden Zeilen erzeugen Tabelleneinträge für die Eingaben 1 und 2. Das ist genau so, als würde man

in JavaScript. Die dritte Zeile von Mathematica sagt: "Bitte installieren Sie eine Rewrite-Regel, die jedes Vorkommen von fib[n_] ersetzt, nachdem die Mustervariable n_ durch das tatsächliche Argument des Vorkommens durch fib[n-1] + fib[n-2] ersetzt wurde." Der Rewriter wird diese Prozedur iterieren und schließlich den Wert von fib[n] nach einer exponentiellen Anzahl von Neuschreibvorgängen erzeugen. Dies ist genau wie das rekursive Funktionsaufrufformular, das wir in JavaScript mit

Beachten Sie, dass die Tabelle zuerst auf die zwei Werte überprüft wird, die wir explizit gespeichert haben, bevor Sie die rekursiven Aufrufe vornehmen. Der Mathematica-Evaluator überprüft diese Überprüfung automatisch, da die Reihenfolge der Darstellung der Regeln wichtig ist - Mathematica überprüft zuerst die spezifischeren Regeln und später die allgemeineren Regeln. Deshalb hat Mathematica zwei Zuweisungsformen, = und := : Ersteres ist für bestimmte Regeln, deren rechte Seiten zum Zeitpunkt der Definition der Regel ausgewertet werden können; Letzteres ist für allgemeine Regeln, deren rechte Seiten ausgewertet werden müssen, wenn die Regel angewendet wird.

Nun, in Mathematica, wenn wir

es wird in

dann zu

dann zu

und schließlich bis 3, was sich beim nächsten Neuschreiben nicht ändert. Sie können sich vorstellen, dass wir, wenn wir fib[35] sagen, enorme Ausdrücke erzeugen, Speicher füllen und die CPU schmelzen werden. Aber der Trick besteht darin, die endgültige Umschreiberegel durch die folgenden zu ersetzen:

Dies bedeutet "Bitte ersetzen Sie jedes Vorkommen von fib[n_] durch einen Ausdruck, der eine neue spezifische Regel für den Wert von fib[n] installiert und auch den Wert erzeugt." Dieser läuft viel schneller, weil er die Regelbasis - die Wertetabelle - erweitert! - zur Laufzeit.

Das können wir auch in JavaScript tun

Dies läuft viel schneller als die vorherige Definition von fib.

Dies wird "Automemisierung" genannt - nicht "Memorisierung", sondern "Memoisierung" wie beim Erstellen eines Memos für sich selbst.

Natürlich müssen Sie in der realen Welt die Größe der Tabellen verwalten, die erstellt werden. Um die Tabellen in Mathematica zu überprüfen,

Um sie in JavaScript zu prüfen, tun Sie einfach

in einer REPL, wie sie von Node.JS unterstützt wird.

Im Kontext der funktionalen Programmierung gibt es das Konzept der referentiellen Transparenz. Eine Funktion, die referenziell transparent ist, kann durch ihren Wert für ein beliebiges Argument (oder einen Satz von Argumenten) ersetzt werden, ohne das Verhalten des Programms zu ändern.

referentielle Transparenz

Betrachten Sie zum Beispiel eine Funktion F , die 1 Argument n akzeptiert. F ist referenziell transparent, daher kann F (n) durch den Wert F ersetzt werden, der bei n ausgewertet wird. Es macht keinen Unterschied für das Programm.

In C # würde das wie folgt aussehen:

(Ich bin nicht sehr vertraut mit C #, von einem Java-Hintergrund kommend, also wirst du mir vergeben müssen, wenn dieses Beispiel nicht sehr syntaktisch korrekt ist).

Es ist offensichtlich, dass die Funktion apply keinen anderen Wert als 4 haben kann, wenn sie mit einem Argument von 2 aufgerufen wird, da sie nur das Quadrat ihres Arguments zurückgibt. Der Wert der Funktion only hängt von seinem Argument n ab; mit anderen Worten, referentielle Transparenz.

Ich frage Sie dann, was der Unterschied zwischen Console.WriteLine(Square.apply(2)) und Console.WriteLine(4) ist. Die Antwort ist, dass es überhaupt keinen Unterschied gibt, denn alle Absichten sind Zwecke. Wir könnten das gesamte Programm durchgehen und alle Instanzen von Square.apply(n) durch den von Square.apply(n) zurückgegebenen Wert ersetzen, und die Ergebnisse wären genau dieselben.

Was also meinte Brian Beckman mit seiner Aussage über das Ersetzen von Funktionsaufrufen durch eine Tabellensuche? Er bezog sich auf diese Eigenschaft von referentiell transparenten Funktionen. Wenn Square.apply(2) durch 4 ohne Auswirkungen auf das Programmverhalten ersetzt werden kann, dann sollten Sie die Werte beim ersten Aufruf einfach zwischenspeichern und in eine Tabelle einfügen, die von den Argumenten für die Funktion indiziert wird. Eine Nachschlagetabelle für Werte von Square.apply(n) würde etwa so aussehen:

Und für jeden Aufruf von Square.apply(n) können wir einfach den zwischengespeicherten Wert für n in der Tabelle finden und den Funktionsaufruf durch diesen Wert ersetzen, anstatt die Funktion aufzurufen. Es ist ziemlich offensichtlich, dass dies höchstwahrscheinlich zu einer großen Geschwindigkeitssteigerung des Programms führen wird.