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
%Vor%Die ersten beiden Zeilen erzeugen Tabelleneinträge für die Eingaben 1 und 2. Das ist genau so, als würde man
sagen %Vor%in JavaScript. Die dritte Zeile von Mathematica sagt: "Bitte installieren Sie eine Rewrite-Regel, die jedes Vorkommen von %code% ersetzt, nachdem die Mustervariable %code% durch das tatsächliche Argument des Vorkommens durch %code% ersetzt wurde." Der Rewriter wird diese Prozedur iterieren und schließlich den Wert von %code% nach einer exponentiellen Anzahl von Neuschreibvorgängen erzeugen. Dies ist genau wie das rekursive Funktionsaufrufformular, das wir in JavaScript mit
erhalten %Vor%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, %code% und %code% : 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
sagen %Vor%es wird in
umgeschrieben %Vor%dann zu
%Vor%dann zu
%Vor%und schließlich bis 3, was sich beim nächsten Neuschreiben nicht ändert. Sie können sich vorstellen, dass wir, wenn wir %code% 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:
%Vor%Dies bedeutet "Bitte ersetzen Sie jedes Vorkommen von %code% durch einen Ausdruck, der eine neue spezifische Regel für den Wert von %code% 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
%Vor%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,
%Vor%Um sie in JavaScript zu prüfen, tun Sie einfach
%Vor%in einer REPL, wie sie von Node.JS unterstützt wird.
Brian hat gerade gezeigt, dass Funktionen auch Daten sind. Funktionen im Allgemeinen sind nur eine Zuordnung eines Satzes zu einem anderen: %code% ist die Zuordnung von Menge {x} zu Menge {y}: %code% . Die Tabellen sind auch Abbildungen: %code% .
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).
Ich habe mir dieses MSDN-Video mit Brian Beckman angesehen und ich möchte etwas besser verstehen, was er sagt:
Jeder imperitive Programmierer durchläuft diese Phase des Lernens Funktionen können durch Tabellennachfragen ersetzt werden
Nun, ich bin ein C # -Programmierer, der nie zur Universität gegangen ist, also habe ich irgendwo auf der Linie etwas verpasst, was jeder andere zu verstehen gelernt hat.
Was bedeutet Brian mit:
Funktionen können durch Tabellennachfragen ersetzt werden
Gibt es dafür praktische Beispiele und gilt das für alle Funktionen? Er gibt das Beispiel der Sündenfunktion, die ich verstehen kann, aber wie mache ich das in allgemeineren Begriffen?
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.
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:
%Vor%(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 %code% und %code% 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 %code% durch den von %code% 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 %code% durch %code% 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 %code% würde etwa so aussehen:
%Vor%Und für jeden Aufruf von %code% 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.