Ich habe in Go einen Compiler implementiert, der Lisp in C konvertiert (manchmal als Transpiler bezeichnet, im Folgenden jedoch als Compiler bezeichnet).
Die Ergebnisse sind auf PLC verfügbar.
In diesem Artikel habe ich den Prozess der Implementierung eines Lisp-Compilers zusammengefasst, der nur Ganzzahlen verarbeitet und Fibonacci-Zahlen berechnen kann.
** Haftungsausschluss ** Ich habe versucht, es mit Go zu schaffen, aber Go erscheint überhaupt nicht in der Hauptgeschichte.
Es ist nicht schwer, einen einfachen Compiler zu erstellen
Es scheint schwierig zu sein, einen eigenen Compiler zu erstellen, aber wenn es nicht so schwierig ist, können Sie es vielleicht.
Es ist jedoch zu rücksichtslos, einen Compiler zu erstellen, obwohl ich mit der C-Sprache selbst nicht vertraut bin.
Gibt es eine Sprache, die weniger schwierig zu sein scheint?
Also Lisp.
Es ist voller Klammern, aber es ist leicht zu analysieren.
Darüber hinaus sind die minimal erforderlichen Elemente
Alles was Sie brauchen ist dies. Nur neun. Es ist wunderbar, das ganze Bild erfassen zu können. Dies reicht für das Debuggen nicht aus. Fügen wir also Druck und Prognose hinzu.
Lassen Sie uns nun das Ausgabeformat festlegen.
8cc spuckt die Assembly aus, aber Human Resource Machine ) Ich habe nur das Wissen, mit dem ich spielen kann, also scheint es besser aufzuhören.
Betrachten Sie LLVM IR als einen Kandidaten, der freundlicher zu sein scheint als die Versammlung. Es ist mühsam, die Ausführungsergebnisse einzeln zu speichern, aber es scheint auch eine Struktur zu geben.
Ich habe versucht, print zu implementieren und es war geschafft. Dies kann möglich sein.
Für alle Fälle werde ich auch den sanfteren C-Ausgang ausprobieren.
Als ich es ausprobierte, war es überwältigend praktisch und die Codemenge betrug weniger als die Hälfte der LLVM-IR-Ausgabe. Ich habe nicht so viel Kraft Lassen Sie es uns vorerst mit C-Ausgabe implementieren und sagen wir, dass die IR-Ausgabe ein Entwicklungsproblem ist (hier nicht durchgeführt).
Versuchen Sie zunächst, von Hand zu kompilieren, um festzustellen, ob Probleme mit der Implementierungsrichtlinie vorliegen oder nicht, und integrieren Sie sie dann in die Implementierung des Compilers.
Am Beispiel von "print" lautet der eingegebene Lisp-Code
(print 1 2 3)
Dann ist der Ausgabe-C-Code
#include<stdio.h>
int main(void) {
printf("%d %d %d\n", 1, 2, 3);
}
Es wird sein. Es gibt kein Problem mit der Vorlagenausgabe außer der 4. Zeile, daher gibt es nichts zu denken. Das Herzstück der "print" -Implementierung ist, dass Sie sie schnell implementieren können, da Sie nur die Formatspezifikationen gemäß den Argumenten anordnen müssen.
Dies allein fehlt offensichtlich an Funktionalität. Lassen Sie uns also etwas wie "Drucken" erstellen, nachdem Sie etwas getan haben.
Wenn Sie beispielsweise das Ergebnis von "1 + 2" "drucken",
(print (+ 1 2) (+ 3 4 5))
Wenn dies kompiliert wird, lautet der Code ohne den Vorlagenteil
int plus_0 = 1 + 2;
int plus_1 = 3 + 4 + 5;
printf("%d %d\n", plus_0, plus_1);
Implementieren Sie das so Speichern Sie die Ergebnisse der Berechnungen nacheinander und übergeben Sie die gespeicherten Ergebnisse an "print". Übrigens implementiere ich "+" und ich implementiere es nur, indem ich alle Argumente auswerte und mit "+" verkette.
Dies führt dazu, dass eine große Anzahl von Variablen in der Hauptfunktion deklariert wird und der Speicher reserviert bleibt. Ursprünglich wäre es ein Ort, um GC zu implementieren, aber ich werde dies auch als Entwicklungsproblem belassen.
Nachdem die Implementierung von "Druck" abgeschlossen ist, fahren Sie mit der Implementierung von "Prognose" fort.
Da die Argumente jedoch nur in der richtigen Reihenfolge ausgewertet werden, gibt es keine besonderen Schwierigkeiten, und der endgültige Bewertungswert ist der Rückgabewert.
Nachdem wir nun mehrere Prozesse ausführen können, definieren wir define und behandeln Variablen.
(progn
(define a 1)
(print a))
int a = 1;
printf("%d\n", a);
Derzeit werden nur Ganzzahlen verarbeitet, sodass es kein Problem gibt, solange Sie Ganzzahlvariablen definieren. Zeichnen Sie hinter den Kulissen die Überprüfung der Variablendeklaration auf, damit sie von der internen Verarbeitung des Compilers überprüft werden kann.
Nachdem wir nun Variablen definieren können, werden wir mit der Implementierung von "Lambda" fortfahren, damit wir auch Funktionen definieren können.
Lassen Sie uns zunächst die sofortige Ausführung von lambda implementieren, bevor wir die Kombination mit define betrachten.
(print ((lambda (x) (+ x 1)) 2))
int lambda_0(int *args) {
int x = args[0];
int add_0 = x + 1;
return add_0;
}
int main(void) {
int lambda_0_args[] = {2};
printf("%d\n", lambda_0(lambda_0_args));
}
Wenn Sie "Lambda" verwenden, definieren wir es als sequentielle Funktion. Ich möchte also nicht die Anzahl der Argumente berücksichtigen Wir beschließen, es als Array zu empfangen und es den Variablen innerhalb der Funktion zuzuweisen. Wo Sie eine Funktion aufrufen Stellen Sie sicher, dass Sie die Argumente im Voraus in einem Array speichern.
Nachdem wir nun "Lambda" haben, implementieren wir die Funktionsdefinition in Kombination mit "Definieren". Wenn Sie dem Funktionszeiger jedoch nur die in "Lambda" definierte Funktion zuweisen, sieht es so aus.
(define add1 (lambda (x) (+ x 1)))
int (*add1)(int*);
int lambda_0(int *args) {
int x = args[0];
int add_0 = x + 1;
return add_0;
}
int main(void) {
add1 = lambda_0;
}
Als nächstes möchte ich die bedingte Verzweigung aktivieren, also werde ich "eq" und "if" implementieren. Was Sie mit eq machen, ist ähnlich wie +, verketten Sie einfach mit&&anstelle von +.
(eq 1 2 3)
bool eq_0 = 1==2 && 1==3;
Wir werden diese "Gleichung" verwenden, um mit der Implementierung von "if" zu beginnen.
(if (eq 1 2) 10 20)
int if_0;
int eq_0 = 1==2;
if (eq_0) {
if_0 = 10;
} else {
if_0 = 20;
}
Selbst wenn Sie es in C if konvertieren, wird es so funktionieren. Wenn Sie hier sowohl - als auch + hinzufügen, können Sie die Fibonacci-Zahl rekursiv berechnen.
Wenn ich es tatsächlich versuche,
(progn
(define fib (lambda (n)
(if (eq n 0)
0
(if (eq n 1)
1
(+ (fib (- n 1)) (fib (- n 2)))))))
(print (fib 10)))
#include<stdio.h>
int (*fib)(int*);
int lambda_1(int *args){
int n = args[0];
int if_1;
int eq_2 = n == 0;
if (eq_2) {
if_1 = 0;
} else {
int if_3;
int eq_4 = n == 1;
if (eq_4) {
if_3 = 1;
} else {
int minus_5 = n;
minus_5 -= 1;
int fib_args_6[] = {
minus_5
};
int minus_7 = n;
minus_7 -= 2;
int fib_args_8[] = {
minus_7
};
int plus_9 = 0;
plus_9 += fib(fib_args_6);
plus_9 += fib(fib_args_8);
if_3 = plus_9;
}
if_1 = if_3;
}
return if_1;
}
int main(void) {
fib = lambda_1;
int fib_args_2[] = {
10
};
printf("%d\n" , fib(fib_args_2));
}
Diese Art von redundantem Code wird generiert, aber wenn Sie ihn tatsächlich ausführen, wird er ordnungsgemäß berechnet.
Ich habe einen Compiler (Transpiler) erstellt, der lisp auf einfache Weise in C konvertiert.
Was wurde bisher in den Prozess umgesetzt
https://github.com/kawakami-o3/PLC/tree/7d825a5ccbab45919c701ebb66cd8d2409c9f45d
Sie können es von bekommen.
Um mich zu bewegen, habe ich es so entworfen und implementiert, dass die Montageschwierigkeiten so gering wie möglich sind. Ich konnte es so weit implementieren, dass ich die Anzahl der Fibonacci fast ohne Stolpersteine berechnen konnte.
Um die wenigen Stolperpunkte zusammenzufassen:
ifDieses Mal habe ich Lisp implementiert, das nur Ganzzahlen verarbeitet, und obwohl es Lisp war, konnte ich die Listenverarbeitung nicht richtig durchführen. Das nächste Mal werden wir die Datenstruktur überprüfen, damit die Listenverarbeitung durchgeführt werden kann, den Lisp-Code von "eval" kompilieren und einen Compiler implementieren, der "eval" zur Laufzeit ausführen kann.
Danke fürs Lesen.
Hier werden wir das verbleibende "Atom", "Zitat", "Auto", "CDR" und "Nachteile" ansprechen.
Der Grund, warum ich mich im Hauptteil nicht damit befasst habe, ist, dass der Rückgabewert in dem in diesem Artikel implementierten Lambda auf "int" gesetzt ist. Dies liegt daran, dass ein schwerwiegender Konstruktionsfehler aufgetreten ist, der nicht mit "cdr" oder "cons" verwendet werden konnte.
Es ist jedoch auch unangenehm, zum nächsten Ziel überzugehen, ohne es überhaupt zu tun. Deshalb habe ich es, wie hier erwähnt, auf eine flauschige Weise umgesetzt.
Für atom habe ich versucht, das Argument zur Kompilierungszeit auszuwerten und es mit 0 oder 1 zu initialisieren, je nachdem, ob es eine Ganzzahl ist oder nicht.
In quote sind die Argumente nur auf Ganzzahlen und Ganzzahllisten beschränkt.
Wenn es eine ganze Zahl ist
(quote 1)
int quote_0 = 1;
Wenn es sich um eine Ganzzahlliste handelt, wird sie in ein Ganzzahlarray konvertiert.
(quote (1 2 3))
int quote_0[] = {1,2,3};
Für car haben wir es intern implementiert, um den ersten Wert des Integer-Arrays zurückzugeben, genauso wie wir die Integer-Liste in ein Integer-Array mit quote konvertiert haben.
cdr hat die Implementierung implementiert, das zweite und nachfolgende Element in das neu definierte Array für die als Argument übergebene Ganzzahlliste einzufügen.
Für cons habe ich auch ein neues Array zum Einfügen von Elementen erstellt.
Ich habe mich entschlossen, in der nächsten Phase an verschachtelten Listen usw. zu arbeiten, und hier werde ich mich nur mit eindimensionalen Ganzzahllisten befassen.
Das Obige ist die Implementierung in dem in diesem Artikel behandelten Compiler.
Recommended Posts