lambda 8cc
1.0.0
Lambda-8cc ist ein X86-C-Compiler, der als monolithisch geschlossene Lambda Calculus-Begriff geschrieben wurde.
Wenn es auf Buchstaben in Buchstaben gedruckt wird, wird es auf einem 22-MB-PDF ohne Zahlen 18.506 Seiten lang. Die PDF ist auf meinen Github -Seiten hier zu sehen. Die Latexquelle beträgt 448 MB und die Latex -Kompilierungsprotokolldatei main.log 284 MB. Ich konnte nicht glauben, dass Latex dazu in der Lage war.
Dieser gigantische Lambda -Kalkül ist ein C -Compiler. Hier ist Rot13.c, ein Programm, das GCC ohne Fehler kompiliert. Das gleiche Programm kann mit Lambda-8cc kompiliert werden, um den ausführbaren X86-ausführbaren Rot13.bin zu erzeugen, der auf x86/x86-64 Linux ausgeführt wird:
$ echo ' Hello, world! ' | ./rot13.bin
Uryyb, jbeyq !
$ echo ' Uryyb, jbeyq! ' | ./rot13.bin
Hello, world !Trotz seiner massiven Größe endet das Kompilieren von ROT13.C in 8 Minuten auf meiner Maschine mit einem Lambda Calculus -Dolmetscher. Sie können es auf Ihrem eigenen PC ausprobieren, indem Sie dieses Repo klonen. Die Laufzeitstatistiken sind im Abschnitt Laufzeiten und Speicherverbrauch zusammengefasst. Beachten Sie, dass die Kompilierung zwar Zeit in Anspruch nimmt, der kompilierte Binärbild sofort ausgeführt wird.
Als zusätzliches Merkmal kann nicht nur Lambda-8cc C bis x86 kompilieren, sondern auch C zu Lambda-Kalkül-Begriffen kompilieren und so etwas wie rot13.lam erzeugen. Kompilierte Lambda-Begriffe, die auf demselben Lambda Calculus-Interpreter ausgeführt werden, mit dem Lambda-8cc selbst ausgeführt wird.
Mit seinen Kompilierungsoptionen kann Lambda-8cc C bis 5 verschiedene Formate kompilieren. Hier finden Sie eine vollständige Liste seiner Funktionen:
Unter der Liste befindet sich faul K, eine minimale rein funktionale Sprache mit nur 4 integrierten Operatoren, ähnlich der minimalen imperativen Sprache BF, die nur 8 Anweisungen enthält. Ich habe auch in meinem Blog -Beitrag ein wenig darüber abgedeckt.
Lambda-8cc basiert auf den folgenden 3 Projekten: Der erste ist Lambdavm, der vom Autor dieses Repo Hikaru Ikuta geschrieben wurde, einer programmierbaren virtuellen CPU, die als untypter Lambda-Kalkül-Begriff geschrieben wurde. Dies wird mit 8cc von Rui Ueyama und einer modifizierten Version von ELVM von Shinichiro Hamaji kombiniert.
Die erste Seite des PDF sieht so aus. Beachten Sie, dass die Seitenzahl oben links zählt:
Sein großes Finale ist eine Applaus mit einer Seite mit rechten Klammern:
Lambda-8cc ist als geschlossener Lambda Calculus-Begriff geschrieben
Hier werden sogar Saiten als Lambda -Begriffe kodiert. Zeichen und Bytes werden als eine Liste von Bits mit kodiert
Daher ist alles im Berechnungsprozess, auch auch von Ganzzahlen, in der Welt der reinen Lambda-Begriffe geschlossen, ohne dass ein Objekt vom Typ Nicht-Lambda eingesetzt werden muss. Es verwendet keine anderen primitiven Typen als Lambdas. Lambda-8cc macht die Beta-Reduzierung zu dem alleinigen Anforderungen für das Zusammenstellen von C bis x86. Beachten Sie, dass der Prozess auch nicht von der Auswahl der variablen Namen abhängt. Anstatt das Zeichen A als Variable mit dem Namen zu codieren A wird als eine Liste von Bits seiner ASCII -Codierung 01000001 codiert.
Der Codierungsprozess ist ein wenig umständlich, um zumindest von Hand zu sagen. Dies kann durch die Verwendung eines Lambda Calculus -Interpreter gelöst werden. Verschiedene Lambda Calculus -Dolmetscher verarbeiten dieses E/A -Format automatisch so, dass es auf dem Terminal ausgeführt wird. Die Standardeingabe wird in Lambda -Begriffe codiert, und der Ausgangslambda -Term wird dekodiert und am Klemme angezeigt. Mit diesen Dolmetschern kann Lambda-8cc auf dem Terminal durchgeführt werden, um C-Programme genau wie GCC zu erstellen.
Weitere Einzelheiten darüber, wie E/A behandelt wird und wie Programme in Lambda Calculus geschrieben werden, finden Sie in den Implementierungsdetails meines anderen Projekts Lambdalisp, einem LISP -Dolmetscher, der als Untyped Lambda Calculus -Begriff geschrieben wurde.
Zusätzlich zu X86 kann Lambda-8cc auch C zu Lambda Calculus zusammenstellen. Das Ausgabeprogramm läuft auf demselben Lambda Calculus-Interpreter aus, der zum Ausführen von Lambda-8cc selbst verwendet wird. Zusammengestellte Lambda-Begriffe werden auch auf minimalen Dolmetschern wie dem von Justine Tunney geschriebenen 521-Byte-Lambda Calculus-Interpreter-Interpreter-Sektorlambda ausgeführt. Dies macht Lambda-8cc in der Reich von Lambda Calculus in sich geschlossen.
In der Informatik ist seit langem bekannt, dass Lambda Calculus turbetrieben ist. Lambda-8cc zeigt dies auf eine ziemlich einfache Weise, indem sie zeigt, dass C-Programme direkt in Lambda Calculus-Begriffe zusammengestellt werden können.
Das Schöne an Lambda Calculus ist, dass die Sprachspezifikationen extrem einfach sind. Mit Lambda-8cc erhalten wir Wissen darüber, wie C C in einer zeitlosen Methode kompiliert werden kann. Selbst wenn die Menschheit das Wissen über den X86-Anweisungssatz verliert, solange wir uns an die Regeln für Lambda Calculus erinnern und den Lambda-Begriff für Lambda-8cc haben, können wir die gesamte C-Sprache immer noch über Lambda-8cc verwenden und alles wieder darüber aufbauen.
Hier ist ein Programm ROT13.C, das die Standardeingabe an/aus der ROT13 -Chiffre codiert/decodiert. Es kompiliert ohne Fehler mit GCC:
// rot13.c: Encodes/decodes standard input to/from the ROT13 cipher
#define EOF -1
int putchar ( int c );
char getchar ( void );
char c ;
int offset ;
int main ( void ) {
for (;;) {
c = getchar ();
if ( c == EOF ) {
break ;
}
offset = 0 ;
if (( 'a' <= c && c < 'n' ) || ( 'A' <= c && c < 'N' )) {
offset = 13 ;
} else if (( 'n' <= c && c <= 'z' ) || ( 'N' <= c && c <= 'Z' )) {
offset = -13 ;
}
putchar ( c + offset );
}
return 0 ;
}Das gleiche Programm kann von Lambda-8cc wie folgt aus dem Box zusammengestellt werden.
Erstellen Sie zuerst die Werkzeuge und bereiten Sie Lambda-8cc vor:
$ make tools # Build the interpreter uni++ and the tools lam2bin, asc2bin
$ unzip bin/lambda-8cc.lam.zip
$ cat lambda-8cc.lam | bin/lam2bin | bin/asc2bin > lambda-8cc.Blc # Prepare format for uni++Die Anforderungen sind:
clang++ zum Aufbau uni++gcc oder cc zum Bau lam2bin und asc2binDie hier erstellten Werkzeuge sind:
uni++ : Ein sehr schneller Lambda Calculus -Interpreter von Melvin Zhang.lam2bin : Ein Dienstprogramm von Justine Tunney (erhältlich unter https://justine.lol/lambda/), das Plaintext Lambda Calculus Notation wie xx in Binär -Lambda -Kalkulus -Notation umwandelt, das von Uni ++ akzeptierte Format akzeptiert.asc2bin : Ein Dienstprogramm, das den 0/1 ASCII -Bitstream in Bytes verpackt.Die Werkzeuge werden über das Lambda Calculus Development Kit erstellt.
Die Umwandlung von Lambda-8cc.lam in Lambda-8cc.blc ist einfach eine Transformation der Notation für ein Format, das vom Interpreter Uni ++ akzeptiert wird. Details werden ausführlich beschrieben.
Dann kann rot13.c zusammengestellt werden wie:
$ cat lambda-8cc.Blc examples/rot13.c | bin/uni++ -o > a.out
$ chmod 755 a.out
$ echo ' Hello, world! ' | ./a.out
Uryyb, jbeyq !
$ echo ' Uryyb, jbeyq! ' | ./a.out
Hello, world ! Dies läuft in ungefähr 8 Minuten auf meiner Maschine. Aber seien Sie vorsichtig - es dauert 145 GB Speicher, um es auszuführen! Wenn Sie einen kostenlosen Speicherplatz oder ein USB -Laufwerk haben, können Sie eine Swap -Datei mit mkswap und swapon verwenden, um den Swap zu erweitern, ohne die Partitionseinstellungen zu konfigurieren. Durch Kompilieren der Baugruppe und der X86 -ausführbaren Datei können Sie die RAM -Verwendung auf 65 GB halbieren, wie im Abschnitt "detaillierte Verwendung" gezeigt. Kleine Programme wie Putchar.c nehmen nur etwa 40 GB Speicher. Ich vermute, dass die RAM-Verwendung durch Einführung eines Mark-and-Sweep-GC in den Dolmetscher verringert werden kann, obwohl ich es noch nicht bestätigt habe.
Weitere Laufzeitstatistiken finden Sie im Abschnitt Laufen und Speicherverbrauch. Weitere Beispiele für C-Programme, die von Lambda-8cc kompiliert werden können, finden Sie unter ./Examples.
Weitere Kompilierungsoptionen werden im Abschnitt "Detaillierter Verwendungs" beschrieben.
In Lambda Calculus wurden natürlich auch Lambda-8CC-Kompilierungsoptionen auch als Lambda Calculus-Begriffe ausgedrückt. Diese Optionen können verwendet werden, um die vollständigen Funktionen von Lambda-8cc zu entsperren.
Kompilierungsoptionen werden verwendet, indem ein optionaler Begriff as (lambda-8cc option) vorhanden der Eingabe angewendet wird. Dies ändert das Verhalten des Lambda-Term lambda-8cc so dass es ein anderes Eingangs-/Ausgangsformat akzeptiert/erzeugt.
Hier sind alle Zusammenstellungsoptionen von Lambda-8cc:
| Eingang | Ausgabe | Kompilierungsoption |
|---|---|---|
| C | x86 ausführbare Datei | |
| C | Plaintext Lambda Calculus Term | |
| C | Binärer Lambda Calculus Notation (BLC -Programm) | |
| C | Ski -Kombinatorrechnung (Lazy K -Programm) | |
| C | ELVM -Baugruppe | |
| ELVM -Baugruppe | x86 ausführbare Datei | |
| ELVM -Baugruppe | Plaintext Lambda Calculus Term | |
| ELVM -Baugruppe | Binärer Lambda Calculus Notation (BLC -Programm) | |
| ELVM -Baugruppe | Ski -Kombinatorrechnung (Lazy K -Programm) |
Jede Option befindet sich im Format eines 3-Tupels
Die zuvor gezeigten Zusammenstellungsoptionen können wie folgt im Terminal verwendet werden.
Um C zu einer ELVM -Baugruppe zu kompilieren as :
( ( cat lambda-8cc.lam ; printf ' (\f.(f (\x.\y.x) (\x.\y.\z.\a.\b.b) (\x.x))) ' )
| bin/lam2bin | bin/asc2bin ; cat input.c ) | bin/uni++ -o > a.s So kompilieren Sie eine ELVM -Montage -Auflistung as auf x86 ausführbare a.out :
( ( cat lambda-8cc.lam ; printf ' (\f.(f (\x.\y.y) (\x.\y.\z.\a.\b.x) (\x.x))) ' )
| bin/lam2bin | bin/asc2bin ; cat a.s ) | bin/uni++ -o > a.out
chmod 755 a.out Wie bereits beschrieben, kann durch separates Kompilieren as und a.out unter Verwendung dieser Befehle die maximale RAM -Verwendung in zwei Hälften abgeschnitten werden, da der Speicher nach Abschluss jedes Vorgangs befreit wird.
Wenn Sie Lambda-8cc ohne Eingabe oder Optionen ausführen, können Sie eine Nutzungsnachricht sehen, die die vollständigen Optionen mit Optionen zeigt:
$ cat lambda-8cc.lam | bin/lam2bin | bin/asc2bin | bin/uni++ -o
lambda-8cc v1.0.0
Usage:
apply lambda-8cc.lam [input-file]
apply lambda-8cc.lam [option] [input-file]
Options:
(f.(f [input] [output] (x.x)))
(f.(f (x.y.x) (x.y.z.a.b.x) (x.x))) : C to x86 (defualt)
(f.(f (x.y.x) (x.y.z.a.b.y) (x.x))) : C to *.lam (plaintext lambda calculus program)
(f.(f (x.y.x) (x.y.z.a.b.z) (x.x))) : C to *.blc (binary lambda calculus program)
(f.(f (x.y.x) (x.y.z.a.b.a) (x.x))) : C to *.lazy (SKI combinator calculus, as a Lazy K program)
(f.(f (x.y.x) (x.y.z.a.b.b) (x.x))) : C to ELVM assembly
(f.(f (x.y.y) (x.y.z.a.b.x) (x.x))) : ELVM assembly to x86
(f.(f (x.y.y) (x.y.z.a.b.y) (x.x))) : ELVM assembly to *.lam
(f.(f (x.y.y) (x.y.z.a.b.z) (x.x))) : ELVM assembly to *.blc
(f.(f (x.y.y) (x.y.z.a.b.a) (x.x))) : ELVM assembly to *.lazy
lambda-8cc includes the following projects. All of the following projects
are released under the MIT license. See the LICENSE in each location for details.
8cc: By Rui Ueyama - https://github.com/rui314/8cc
ELVM: By Shinichiro Hamaji - https://github.com/shinh/elvm
LambdaVM: By Hikaru Ikuta - https://github.com/woodrush/lambdavm
lambda-8cc: By Hikaru Ikuta - https://github.com/woodrush/lambda-8cc
Die folgende Tabelle zeigt die Kompilierungszeit und den Speicherverbrauch von Melvin Zhangs Lambda Calculus Interpreter.
| Programm | Kompilierungszeit | Max. RAM -Nutzung zur Kompilierungszeit | x86 binäre Größe | Beschreibung |
|---|---|---|---|---|
| putchar.c | 1,8 min | 31 GB | 342 Bytes | Drucke A |
| Hallo.c | 2,4 min | 42 GB | 802 Bytes | Drucke Hello, world! |
| echo.c | 2,5 min | 46 GB | 663 Bytes | Echoes Standardeingabe |
| ROT13.C | 7,7 min | 84 GB | 2.118 Bytes | Codiert/decodert Stdin bis/von Rot13 |
| fizzbuzz.c | 49,7 min | 240 GB | 5.512 Bytes | Druckt Fizzbuzz -Sequenz bis zu 30 |
| Primes.C | 53,0 min | 241 GB | 5.500 Bytes | Druckt Primes bis zu 100 |
Das ist eine Menge Erinnerung! Um Programme zu kompilieren, die einen riesigen RAM erfordern, können Sie Ihre Swap -Region erweitern, ohne die Partitionseinstellungen mithilfe einer Swap -Datei zu ändern. Wenn Sie Linux ausführen und einen kostenlosen Speicher oder ein USB -Laufwerk haben, können Sie diesen Speicher mit mkswap und swapon einfach und dynamisch Ihren Swap -Bereich erweitern. Die Statistiken in dieser Tabelle werden auf diese Weise mit einem erweiterten Tauschbereich ausgeführt. In diesem Askubuntu -Thread werden Anweisungen erläutert. Ich vermute, dass die RAM-Verwendung durch Einführung eines Mark-and-Sweep-GC in den Dolmetscher verringert werden kann, obwohl ich es noch nicht bestätigt habe.
Beachten Sie, dass dies die Kompilierungszeiten sind - die Laufzeiten für den kompilierten X86 -Binär sind augenblicklich. Dies gilt sogar beim Kompilieren von C -zu Lambda -Kalkülbegriffen. Kompilierte Lambda -Begriffe werden auch sofort ausgeführt und verwenden nur ein paar Gigabyte Speicher, wenn Sie auf einem Lambda Calculus -Interpreter ausgeführt werden.
Die Zusammenstellungen für diese Statistiken wurden auf einer Ubuntu 22.04.1 -Maschine mit 48 GB RAM, 16 GB SSD -SWAP (Standardpartition) und 274 GB (256 GB) HDD -Swap (dynamisch mit mkswap und swapon hinzugefügt) ausgeführt. Die hier gezeigte Laufzeit ist die Wandtakt -Laufzeit einschließlich Speicheroperationen. Bei Swap-strengen Programmen könnte die Laufzeit durch die Verwendung eines Geräts mit einer schnelleren E/A-Geschwindigkeit verringert werden.
Die Statistiken wurden durch Laufen gemessen
cp examples/[program].c ./input.c
make welche as und a.out für input.c separat zusammenstellen, um die Gesamtspeicherverwendung zu speichern. Eine detailliertere Tabelle mit Statistiken für jeden Pass wird ausführlich angezeigt.
Bitte beachten Sie Details.md.
Weitere Informationen zum Erstellen von Quelle finden Sie in Details.md.
Lambda-8cc ist eine Kombination aus 3 Projekten, Lambdavm, ELVM und 8cc. Lambdavm wurde von Hikaru Ikuta, dem Autor dieses Repositorys (Lambda-8cc), geschrieben. Die ELVM -Architektur wurde von Shinichiro Hamaji geschrieben. 8cc wurde von Rui Ueyama geschrieben. Die in Lambda-8cc verwendete Version von 8cc ist eine modifizierte Version von 8cc, die als Teil von ELVM enthalten ist und von Shinichiro Hamaji und anderen geändert wird. Lambda-8cc umfasst auch ELC, ein Teil von ELVM von Shinichiro Hamaji, das von Hikaru Ikuta modifiziert wurde, damit sie die ELVM-Assemblierung zu Lambda Calculus zusammenstellen kann. Das Lambda Calculus -Backend für ELVM wurde von Hikaru Ikuta geschrieben, indem Lambdavm in ELVM integriert wurde. Die Laufzeit- und Speicherverbrauchsstatistiken wurden unter Verwendung eines von Melvin Zhang geschriebenen Lambda Calculus -Dolmetschers gemessen. Lam2bin wurde von Justine Tunney geschrieben.
