Ich habe einen teilweise fertiggestellten Interpreter für eine lexikalisch begrenzte 'reine Lisp' (no set! ), die ein Call-by-Need-Evaluierungsmodell verwendet, das auf call-by-name mit einfachem Caching läuft, dem Interpreter natürlich verwendet ein umweltbasiertes Bewertungsmodell.
Die Standardmethode zur Bewertung von Lambda-Abstraktionen, wie in der Konstruktion einer neuen Umgebung aus den formalen Parametern und der Umgebung, in der die Abstraktion ausgewertet wird, und einfach die Bewertungen der Argumente in ihre eigene Umgebung einfügen. Dann würde der Körper der Abstraktion in der neuen Umgebung nicht funktionieren, weil es eine Call-by-Value-Semantik bedeuten würde.
Meine Lösung für dieses Problem war, die Idee von "Umgebungen" durch "Nachschlagefunktionen" zu ersetzen, die einfach ein Symbol als Argument nehmen und ein zugehöriges Datum erzeugen. Das kann leicht aus einer Umgebung gemacht werden. Lambda-Anwendungen werden nur ausgeführt, indem der Körper erneut mit einer Nachschlagefunktion evaluiert wird, die sowohl aus der Umgebung, in der die Definition liegt, und in der das Argument liegt, gemacht wird. Die wertet sie faul und nur bei Bedarf aus.
Was ich allerdings frage ist, was der Overhead dieses Modells ist, wie teuer es ist, diese Lookups für jede Anwendung zu generieren, der Code für diese Lookups ist ziemlich groß. Ich weiß, dass Lambda-Anwendung und -Erstellung in Scheme ziemlich billig ist, und viele Quellen empfehlen, sie in großem Umfang zu verwenden, um die Lesbarkeit von Code beizubehalten, obwohl sie in vielen Fällen einen geringen Overhead hätten. Aber da Lambda-Anwendungen in jedem Lisp allgegenwärtig sind, frage ich mich, wie viel Leistung durch die Verwendung eines möglicherweise anderen Modells eingespart werden könnte. Ich habe versucht, dies auf Google zu suchen, aber alle Modelle für Call-by-Need-Dolmetscher, die ich fand, waren noch peinlicher, aber oft so für set! unterzubringen.
Einige relevante Teile meines Codes:
Der Bewerter, der die Suchfunktion verwendet:
%Vor% Und die Funktion, die die fortgeschritteneren Lookups erzeugt. Das beunruhigt mich besonders, obwohl es tail-rekursiv ist und sehr günstige eq? und null? Vergleiche verwendet, es sieht nicht so effizient aus wie einfach assq in einer Umgebungsliste zu verwenden, und manchmal sogar das Fehlen von Zufälliger Zugriff auf diese beunruhigt mich ein wenig.
Es sollte offensichtlich sein, dass der Evaluator mit einem einfachen Terminreduktionssystem arbeitet, das bei der Auswertung von Ausdrücken in einer Liste diese einfach durch ihr Ergebnis ersetzt und sie zitiert, wenn das Ergebnis nicht als selbstevaluierend betrachtet wird. Was möglich ist, weil es ein rein funktionelles Lispeln ist. Es erfasst auch Caching und den größten Teil der Garbage Collection auf einmal.
Ich sollte hinzufügen, dass eines der Dinge, die ich immer sehr schlecht verstanden habe, die Overhead- und Komplexitätstheorie ist. Für diejenigen, die sagen: "Wenn Sie Performance wollen, warum machen Sie Ihren Interpreter in Lisp?", Es ist nur ein Test der allgemeinen Struktur, um zu sehen, ob es funktioniert, ich werde es in C - bald wieder schreiben.
Ah, ich konnte das noch nicht einmal einreichen, weil das Tag "call-by-need" noch nicht existiert und viel versprechend ist.
Eine andere Sache, die Sie tun können, ist, jedes einzelne Datum mit einer eigenen Umgebung zu markieren, die in der Datenstruktur abgerufen werden kann. Es mag erschöpfend erscheinen, aber am Ende müssen Sie alles markieren Denken Sie daran, es sind Listen und ein ganz besonderer Fall, dass der Körper der Lambda-Abstraktion nur ein Symbol enthält. Für andere Daten in "Ihrem" Modell ist seine Bewertung unabhängig von seiner Umgebung.
Dies löst auch ein großes Problem mit faulen Cons-Zellen und Listen, die nur an andere Stellen im Programm weitergegeben werden.
Wenn also eine Liste selbst mit einer Umgebung markiert ist, können Sie die Umgebung einfach extrahieren, wenn Sie sie evaluieren.
Tags und Links performance scheme lisp interpreter