Wie LISP in der Montagesprache implementiert? [abgeschlossen

StackOverflow https://stackoverflow.com/questions/5865868

Frage

Viele (können alle sein?) Programmiersprache bestehen aus der Versammlungssprache

Wie LISP in der Montagesprache implementiert?

Gibt es eine gute Referenz, Handbuch, Tutorial oder Schlüsselwort für Google?

Irgendwelche offizielle Regel/Konvention für den Aufbau einer eigenen Lisp -Implementierung?

wie die Schwanzrekursion sollte einer Verkörperungsregel oder so etwas folgen.

Danke

War es hilfreich?

Lösung

Obwohl die anderen Kommentare und Beiträge richtig sind, ist diese Frage übermäßig vage und vielleicht ein bisschen verwirrt. Ich kann nicht anders, als einige Empfehlungen zu teilen. Ich habe eine Reihe von Links und Büchern über die Implementierung von LiSP gesammelt, da ich kürzlich ein bisschen faszinierend für die Sprachimplementierung entwickelt habe. Es ist natürlich ein tiefes Thema, aber es ist besonders überzeugend, das Lesen des Lesens in Bezug auf LISP zu lesen read. Dies ermöglicht es den Autoren, schnell zum Fleisch der Zusammenstellung oder Interpretation zu gelangen. Diese Empfehlungen sind Bücher, die ich gelesen oder begonnen habe oder lese und hauptsächlich mit Schema zu tun hat, nicht mit gemeinsamem Lisp, aber möglicherweise immer noch von Interesse.

Wenn Sie keinen Hintergrund in der Sprachimplementierung haben und noch nie das Vergnügen hatten, über das klassische Lisp- und Schema "Metaccircular Evaluatoren" zu lesen, würde ich empfehlen, Struktur und Interpretation von Computerprogrammen. Wenn Sie Lisp-in-in-lisp (oder Schema in Scheme ...) gesehen haben, können Sie vorne überspringen. In den letzten beiden Kapiteln von SICP präsentieren die Autoren einige verschiedene Dolmetscher für Lisp/Schema und einige Varianten sowie einen Byte-Code-Compiler und eine virtuelle Maschine. Es ist einfach ein brillantes Buch und kostenlos.

Wenn Sie keine Zeit haben, SICP zu lesen oder nicht durchzuschlagen, nur um die Interpretations- und Zusammenstellungskapitel zu erreichen, würde ich empfehlen, Der kleine Schemier. Auch wenn es sehr kurz und für Newcomer vorgesehen ist, um Lisp und Scheme zu sein. Wenn Sie noch nie einen Lisp -Dolmetscher in Lisp gesehen haben, präsentieren sie einen und es ist ein ziemlich entzückendes Buch, aber möglicherweise nicht für jeden aufgrund des niedlichen Stils. .

Es gibt ein weiteres kostenloses Buch über ein ähnliches Schema wie SICP, genannt Eine Einführung in das Schema und seine Umsetzung, was ich nicht gelesen habe, aber als Referenz für ein paar Teile verwendet wurde. Es gibt Abschnitte zu Dolmetschern und Compilern, und es scheint etwas tiefer zu gehen als SICP, der sich auch mit haarigeren Dingen wie Parsen befasst. Vielleicht brauchte es einen Redakteur, aber es ist dennoch ein beeindruckendes Angebot.

Mit einer angemessenen Vorstellung, wie man Lisp in LiSP macht, können Sie sich an die Implementierung von Lisp in etwas niedrigerem Niveau wenden.

LISP in kleinen Stücken wird häufig empfohlen. Ich habe das meiste davon gelesen und kann sagen, dass es definitiv ein großartiges Buch ist, voller kiesiger Dinge. Ich gehe mit einem feinen Kamm zurück, weil es leicht zu überfliegen ist, wenn Sie Sachen nicht verstehen. Ich hatte auch Probleme, den Code von der Website des Autors auszuführen. Wenn Sie es erhalten, empfehle ich, das Gambit -Schema zu verwenden und den Code auszuführen, der auf Meroonet mit Meroon stützt, von Dies Verteilung. LISP in kleinen Stücken zeigt eine Reihe von Dolmetschern, die in Schema geschrieben sind, sowie einen Byte-Code-Compiler und einen Compiler-to-C.

LISP in kleinen Stücken bewegt sich schnell und ist ziemlich dicht. Wenn es zu viel für Sie ist, beginnen Sie vielleicht mit Das Wesentliche der Programmiersprachen. Ich habe etwas davon gelesen und es ist ziemlich gut, aber es sind mehr Dolmetscher. Anscheinend enthielt eine der älteren Ausgaben (1.? Ich bin mir nicht sicher ...) einen Compiler. Es scheint eine Menge Veränderungen zwischen den 3 Editionen zu geben, aber der erste ist bei Amazon super billig, also schau es dir an.

Für die Zusammenstellung von C ist dies eine Art grobes Thema mit vielen haarigen Teilen. Die Zusammenstellung von C bringt all diese seltsamen Eckprobleme hervor, wie man Schwanzberechtigungen optimieren und Verschlüsse, erstklassige Kontinuationen und Müllsammlung umgehen, aber es ist ziemlich interessant, und viele "echte" Implementierungen des Schemas gehen auf diese Route. Marc Feeleys Präsentation darüber ist ziemlich interessant, mit dem Titel " Das 90 -minütige Schema für C -Compiler.

Ich habe weniger Ressourcen, um bis zur Montage zusammenzustellen, aber es gibt ein oft empfohlenes Papier, das die Zusammenstellung des Schemas zu x86 nennt, genannt Ein inkrementeller Ansatz zur Compiler -Konstruktion. Es nimmt wenig von dem Leser an, aber ich fand, dass es einfach zu schnell geht und nicht genügend Details ausgibt. Vielleicht haben Sie mehr Glück.

Viele der oben genannten Empfehlungen stammen aus diesem Monster -Kommentar zu Hacker News von vor über einem Jahr, von Mahmud. Es bezieht sich auf eine Reihe von ML -Ressourcen und die Zusammenstellung unter Verwendung von Kontinuationen. Ich bin in meinem Studium nicht so weit gekommen, also kann ich nicht sagen, was gut ist oder nicht. Aber es ist ein unglaublich wertvoller Kommentar. Zu den referenzierten Werken gehören Andrew Appels "Zusammenstellung mit Kontinuationen" und Paul Wilsons "Uniprocessor Müllsammeltechniken" -Papier.

Viel Glück!

Andere Tipps

Ich habe in der Vergangenheit ein bisschen darüber nachgedacht (dann griff stattdessen ein C -Kernel). Natürlich gibt es keine einzige "Montage", aber für x86/32bit war dies das, was ich geplant habe:

Die Grundwerte werden in 64-Bit-Knoten mit drei niedrigsten Bits gespeichert, die als Tag mit der folgenden Bedeutung verwendet werden:

000 -> cell (64 bits are basically two pointers: car/cdr)
001 -> fixnum (64-3-1 bits usable for values)
010 -> vector (32-3 bits for size and 32 bit for pointer to first element)
011 -> symbol (32 bits pointing to values in global env, 32 pointing to name)
100 -> native code (32 bits pointing to executable machine code, 32 bits to args)
101 -> float (using 64-3-1 bit by dropping 4 bits from mantissa)
110 -> string (using 32-3 bits for size and 32 bits pointing to bytes)
111 -> struct (32 bits pointing to definition, 32 bits pointing to content)

3 Bits bleiben nutzbar, wenn Sie Zeiger in Betracht ziehen, wenn angenommen wird, dass alle Zuweisungen ein Vielfaches von 8 Bytes sind (vernünftig mit einer Zellgröße von 8 Bytes). Für die Implementierung eines einfachen Müllsammlers (das "lebendige" Bit) wäre ein zusätzliches Stück erforderlich. In der C -Implementierung habe ich je nach Knotentyp dieses Bit in verschiedenen Teilen (z.

Meine Idee war es, sich an zwei Typen zu erinnern: "Knotenspeicher" (mit dem oben beschriebenen Layout), das auf Seiten zugeordnet und mit einer freien Liste wiederverwendet wurde, und "Binärspeicher", um für Zeichenfolgen/Code/Arrays mit variabler Größe zu werden.

Der spezifische Code wird je nach Knotentyp zur Implementierung a benötigt touch Funktion, die rekursiv als lebendige Knoten markiert, die von einem lebendigen Knoten bezeichnet werden.

All dies ist natürlich nur ein naiver Ansatz, aber ich habe es trotzdem in "C" zum Laufen gebracht und ich bin sicher, ich hätte das auch in der Montage tun können (mein C -Code verwendet verwendet void * Überall ist es im Grunde nur ein tragbarer 32-Bit-Assembler). Für Faulheit in meiner C -Implementierung habe ich nur 32 Bit für Floats und für Ganzzahlen (mit den höheren 32 Bit) anstatt alle verfügbaren Bits zu verwenden.

Sich ansehen Clozure Common Lisp Für ein Beispiel für die Montagesprache, die bei der Implementierung eines LISP verwendet wird. Clozure CL wird größtenteils in einem gemeinsamen Lisping selbst implementiert, aber es gibt einen Kernel in C und einige Funktionen auf niedriger Ebene in der Montage.

Zum Beispiel hier ist ein Makro von Compiler/x86/x86-lapmacros.lisp Implementierung eines Primitiven CAR Funktion auf X86 -Hardware mit einer Montageanweisung für 32bit bzw. 64bit:

(defx86lapmacro %car (src dest)
    (target-arch-case
       (:x8632
          `(movl (@ x8632::cons.car (% ,src)) (% ,dest)))
       (:x8664
          `(movq (@ x8664::cons.car (% ,src)) (% ,dest)))))

Wie gezeigt, ist der Montagecode selbst in Lisp -Form codiert. Das Portieren auf einer anderen Plattform beinhaltet (unter anderem), um diese Vorgänge auf niedriger Ebene in eine andere Versammlungssprache zu übersetzen, und das Cross-Compile, um eine Laufzeit auf der neuen Plattform zu erstellen.

ECL (eingebettbares gemeinsames Lisp) Verfolgt einen anderen Ansatz, indem es in C zusammenstellt. Dies macht es bequem, die Implementierung auf Plattformen mit einem C -Compiler zu portieren.

Ihre Frage basiert auf sehr veralteten Annahmen. Heutzutage sind fast keine Sprachimplementierungen in der Versammlungssprache geschrieben, und ich kenne keine LiSP -Implementierungen. Neben Selbsthost-Implementierungen ist C heutzutage eine gemeinsame Implementierungssprache.

Wenn Sie eine Montagesprachdarstellung einer Lisp -Funktion sehen möchten, gibt es die Demontagefunktion.

Dass es eine große Frage ist, gut zu antworten.

Kurze Antwort: Jit.

Große Antwort: Drachenbuch.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top