lambda 8cc
1.0.0
Lambda-8cc adalah kompiler x86 C yang ditulis sebagai istilah kalkulus lambda yang tidak diketik secara monolitik.
Ketika dicetak pada kertas berukuran huruf, itu menjadi 18.506 halaman panjang pada 22 MB PDF tanpa angka apa pun. PDF dapat dilihat di halaman GitHub saya di sini. Sumber lateks adalah 448 MB, dan file log kompilasi lateks main.log adalah 284 MB. Aku tidak percaya Latex bisa melakukan itu.
Istilah kalkulus lambda raksasa ini adalah kompiler C. Berikut ini ROT13.C, program yang dikompilasi pada GCC tanpa kesalahan. Program yang sama dapat dikompilasi menggunakan lambda-8cc memproduksi X86 yang dapat dieksekusi ROT13.bin, runnable pada x86/x86-64 Linux:
$ echo ' Hello, world! ' | ./rot13.bin
Uryyb, jbeyq !
$ echo ' Uryyb, jbeyq! ' | ./rot13.bin
Hello, world !Meskipun ukurannya besar, menyusun ROT13.C selesai dalam 8 menit pada mesin saya menggunakan interpreter kalkulus lambda. Anda dapat mencobanya di PC Anda sendiri dengan mengkloning repo ini. Statistik waktu berjalan dirangkum di bagian waktu berjalan dan penggunaan memori. Perhatikan bahwa meskipun kompilasi membutuhkan waktu, biner yang dikompilasi berjalan secara instan.
Sebagai fitur tambahan, Lambda-8cc tidak hanya dapat mengkompilasi C ke x86, tetapi juga dapat mengkompilasi C ke istilah kalkulus lambda, menghasilkan sesuatu seperti ROT13.LAM. Istilah lambda yang dikompilasi dijalankan pada interpreter kalkulus lambda yang sama yang digunakan untuk menjalankan lambda-8cc itu sendiri.
Menggunakan opsi kompilasi, Lambda-8cc dapat menyusun C ke 5 format yang berbeda. Berikut adalah daftar lengkap fitur -fiturnya:
Di antara daftarnya adalah malas k, bahasa minimal murni fungsional dengan hanya 4 operator bawaan, mirip dengan bahasa minimal BF yang hanya memiliki 8 instruksi. Saya telah membahas sedikit tentang hal itu di posting blog saya juga.
Lambda-8cc didasarkan pada 3 proyek berikut: yang pertama adalah lambdavm yang ditulis oleh penulis repo ini Hikaru Ikuta, CPU virtual yang dapat diprogram yang ditulis sebagai istilah kalkulus Lambda yang tidak diketik. Ini dikombinasikan dengan 8cc oleh Rui Ueyama, dan versi modifikasi dari ELVM oleh Shinichiro Hamaji.
Halaman pertama PDF terlihat seperti ini. Perhatikan jumlah halaman di kiri atas:
Grand finale -nya adalah tepuk tangan meriah dengan halaman yang penuh dengan tanda kurung kanan:
Lambda-8cc ditulis sebagai istilah kalkulus lambda yang tidak diketik tertutup
Di sini, bahkan string dikodekan sebagai istilah lambda. Karakter dan byte dikodekan sebagai daftar bit dengan
Oleh karena itu, segala sesuatu dalam proses perhitungan, bahkan termasuk bilangan bulat, ditutup di dunia istilah lambda murni, tanpa perlu memperkenalkan objek tipe non-Lambda apa pun. Itu tidak menggunakan tipe primitif selain lambdas. Lambda-8cc membuat pengurangan beta satu-satunya persyaratan untuk menyusun C ke x86. Perhatikan bahwa prosesnya tidak tergantung pada pilihan nama variabel juga. Alih -alih mengkode karakter A sebagai variabel dengan nama A dikodekan sebagai daftar bit dari ency -coding 01000001 .
Proses pengkodean sedikit rumit untuk dikatakan setidaknya untuk dilakukan dengan tangan. Ini dapat diselesaikan dengan menggunakan interpreter kalkulus Lambda. Berbagai penerjemah kalkulus lambda secara otomatis menangani format I/O ini sehingga berjalan pada terminal - input standar dikodekan ke dalam istilah lambda, dan istilah lambda output diterjemahkan dan ditampilkan pada terminal. Dengan menggunakan penerjemah ini, Lambda-8cc dapat dijalankan di terminal untuk menyusun program C seperti GCC.
Untuk perincian lebih lanjut tentang bagaimana I/O ditangani dan bagaimana program ditulis dalam kalkulus Lambda, silakan lihat detail implementasi proyek saya yang lain Lambdalisp, seorang penerjemah LISP yang ditulis sebagai istilah kalkulus Lambda yang tidak diketik.
Selain x86, Lambda-8cc dapat mengkompilasi C ke kalkulus lambda juga. Program output berjalan pada interpreter kalkulus Lambda yang sama yang digunakan untuk menjalankan lambda-8cc itu sendiri. Istilah Lambda yang dikompilasi juga berjalan pada penerjemah minimal seperti sektorlambda interpreter kalkulus 521-byte yang ditulis oleh Justine Tunney, dan penafsir IOCCC 2012 "paling fungsional" yang ditulis oleh John Tromp (sumbernya berbentuk λ). Ini membuat Lambda-8cc mandiri di ranah kalkulus Lambda.
Sudah lama diketahui dalam ilmu komputer bahwa kalkulus Lambda tidak lengkap. Lambda-8CC menunjukkan ini dengan cara yang agak langsung dengan menunjukkan bahwa program C dapat secara langsung dikompilasi ke dalam istilah kalkulus Lambda.
Hal yang menyenangkan tentang kalkulus Lambda adalah spesifikasi bahasa sangat sederhana. Dengan Lambda-8cc, kami menjaga pengetahuan tentang cara mengkompilasi C dalam metode abadi. Bahkan jika umat manusia kehilangan pengetahuan tentang set instruksi x86, selama kita ingat aturan untuk kalkulus lambda dan memiliki istilah lambda untuk lambda-8cc, kita masih dapat menggunakan seluruh bahasa C melalui lambda-8cc dan membangun semuanya di atasnya lagi.
Berikut adalah program ROT13.C yang mengkodekan/mendekode input standar ke/dari cipher ROT13. Ini mengkompilasi tanpa kesalahan menggunakan 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 ;
}Program yang sama dapat dikompilasi oleh Lambda-8cc di luar kotak sebagai berikut.
Pertama-tama bangun alat dan siapkan lambda-8cc:
$ 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++Persyaratannya adalah:
clang++ untuk membangun uni++gcc atau cc untuk membangun lam2bin dan asc2binAlat yang dibangun di sini adalah:
uni++ : Interpreter kalkulus Lambda yang sangat cepat ditulis oleh Melvin Zhang.lam2bin : Utilitas yang ditulis oleh Justine Tunney (tersedia di https://justine.lol/lambda/), yang mengubah notasi kalkulus Lambda plaintext seperti xx menjadi notasi kalkulus lambda biner, format yang diterima oleh Uni ++.asc2bin : Utilitas yang mengemas bitstream 0/1 ASCII ke byte.Alat -alat ini dibangun melalui Kit Pengembangan Kalkulus Lambda.
Konversi dari lambda-8cc.lam ke lambda-8cc.blc hanyalah transformasi notasi untuk format yang diterima oleh interpreter uni ++. Detail dijelaskan secara detail.
Kemudian ROT13.C dapat dikompilasi sebagai:
$ 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 ! Ini berjalan dalam waktu sekitar 8 menit di mesin saya. Tapi hati -hati - dibutuhkan 145 GB memori untuk menjalankannya! Jika Anda memiliki ruang penyimpanan gratis atau drive USB, Anda dapat menggunakan file swap dengan mkswap dan swapon untuk memperpanjang swap tanpa mengkonfigurasi pengaturan partisi. Juga, dengan menyusun perakitan dan x86 yang dapat dieksekusi secara terpisah, Anda dapat membagi dua penggunaan RAM hingga 65 GB, seperti yang ditunjukkan pada bagian penggunaan terperinci. Program kecil seperti Putchar.c hanya mengambil sekitar 40 GB memori. Saya menduga bahwa penggunaan RAM dapat dikurangi dengan memperkenalkan GC tanda-dan-sapu kepada penerjemah, meskipun saya belum mengkonfirmasi.
Statistik waktu yang lebih banyak tersedia tersedia di bagian waktu berjalan dan penggunaan memori. Lebih banyak contoh program C yang dapat dikompilasi oleh Lambda-8cc dapat ditemukan di bawah ./Examples.
Opsi kompilasi lainnya dijelaskan di bagian penggunaan terperinci.
Ditulis dalam kalkulus Lambda, secara alami, opsi kompilasi Lambda-8cc dinyatakan sebagai istilah lambda kalkulus juga. Opsi ini dapat digunakan untuk membuka kunci fitur lengkap Lambda-8cc.
Opsi kompilasi digunakan dengan menerapkan istilah opsional sebagai (lambda-8cc option) sebelumnya dari input. Ini mengubah perilaku istilah lambda lambda-8cc sehingga menerima/menghasilkan format input/output yang berbeda.
Berikut semua opsi kompilasi Lambda-8cc:
| Masukan | Keluaran | Opsi kompilasi |
|---|---|---|
| C | x86 dapat dieksekusi | |
| C | Istilah Kalkulus Lambda Plaintext | |
| C | Notasi kalkulus lambda biner (program BLC) | |
| C | Kalkulus Kombinator Ski (Program Lazy K) | |
| C | Majelis ELVM | |
| Majelis ELVM | x86 dapat dieksekusi | |
| Majelis ELVM | Istilah Kalkulus Lambda Plaintext | |
| Majelis ELVM | Notasi kalkulus lambda biner (program BLC) | |
| Majelis ELVM | Kalkulus Kombinator Ski (Program Lazy K) |
Setiap opsi dalam format 3-tuple
Opsi kompilasi yang ditunjukkan sebelumnya dapat digunakan di terminal sebagai berikut.
Untuk mengkompilasi C ke daftar perakitan ELVM 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 Untuk menyusun daftar perakitan ELVM as X86 yang dapat dieksekusi 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 Seperti yang dijelaskan sebelumnya, dengan mengkompilasi secara terpisah as a.out menggunakan perintah ini, penggunaan RAM maksimum dapat dipotong menjadi dua karena memori dibebaskan ketika setiap proses selesai.
Dengan menjalankan lambda-8cc tanpa input atau opsi, Anda dapat melihat pesan penggunaan yang menunjukkan set lengkap opsi:
$ 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
Tabel berikut menunjukkan waktu kompilasi dan penggunaan memori pada interpreter kalkulus Lambda Melvin Zhang.
| Program | Waktu kompilasi | Max. Penggunaan RAM pada waktu kompilasi | x86 Ukuran biner | Keterangan |
|---|---|---|---|---|
| putchar.c | 1,8 menit | 31 GB | 342 byte | Mencetak A |
| Hello.C | 2,4 mnt | 42 GB | 802 byte | Cetakan Hello, world! |
| Echo.C | 2,5 menit | 46 GB | 663 byte | Menggemakan input standar |
| ROT13.C | 7,7 menit | 84 GB | 2.118 byte | Encode/Decodes Stdin ke/dari ROT13 |
| fizzbuzz.c | 49,7 menit | 240 GB | 5.512 byte | Mencetak urutan fizzbuzz hingga 30 |
| Primes.C | 53,0 menit | 241 GB | 5.500 byte | Cetakan bilangan prima hingga 100 |
Nah, itu banyak memori! Untuk menyusun program yang membutuhkan RAM besar, Anda dapat memperpanjang wilayah swap Anda tanpa mengubah pengaturan partisi dengan menggunakan file swap. Jika Anda menjalankan Linux dan memiliki penyimpanan gratis atau drive USB, Anda dapat menggunakan penyimpanan itu untuk dengan mudah dan dinamis memperluas wilayah swap Anda menggunakan mkswap dan swapon . Statistik di meja ini dijalankan dengan wilayah swap yang diperluas dengan cara ini. Instruksi dijelaskan dalam utas Askubuntu ini. Saya menduga bahwa penggunaan RAM dapat dikurangi dengan memperkenalkan GC tanda-dan-sapu kepada penerjemah, meskipun saya belum mengkonfirmasi.
Perhatikan bahwa ini adalah waktu kompilasi - waktu berjalan untuk biner x86 yang dikompilasi adalah instan. Ini bahkan berlaku saat menyusun istilah C ke lambda. Istilah Lambda yang disusun juga berjalan secara instan dan hanya menggunakan beberapa gigabyte memori saat dijalankan pada interpreter kalkulus lambda.
Kompilasi untuk statistik ini dijalankan pada mesin Ubuntu 22.04.1 dengan RAM 48 GB, swap SSD 16GB (partisi default), dan pertukaran HDD 274GB (256GIB) (ditambahkan secara dinamis dengan mkswap dan swapon ). Waktu berjalan yang ditampilkan di sini adalah waktu berjalan jam dinding termasuk operasi memori. Untuk program swap-heavy, waktu berjalan dapat dikurangi dengan menggunakan perangkat dengan kecepatan I/O yang lebih cepat.
Statistik diukur dengan berlari
cp examples/[program].c ./input.c
make yang dikompilasi as dan a.out untuk input.c secara terpisah untuk menyimpan penggunaan memori total. Tabel statistik yang lebih rinci untuk setiap pass ditampilkan secara detail.
Silakan lihat detail.md.
Untuk detail tentang pembangunan dari sumber, silakan lihat detail.md.
Lambda-8cc adalah kombinasi dari 3 proyek, Lambdavm, Elvm, dan 8cc. Lambdavm ditulis oleh Hikaru Ikuta, penulis Repositori ini (Lambda-8cc). Arsitektur ELVM ditulis oleh Shinichiro Hamaji. 8cc ditulis oleh Rui Ueyama. Versi 8cc yang digunakan dalam Lambda-8cc adalah versi yang dimodifikasi dari 8cc termasuk sebagai bagian dari ELVM, dimodifikasi oleh Shinichiro Hamaji dan lainnya. Lambda-8cc juga termasuk ELC, bagian dari ELVM yang ditulis oleh Shinichiro Hamaji, dimodifikasi oleh Hikaru Ikuta sehingga dapat menyusun perakitan ELVM ke kalkulus Lambda. Backend Kalkulus Lambda untuk ELVM ditulis oleh Hikaru Ikuta, dengan mengintegrasikan Lambdavm ke dalam ELVM. Statistik waktu berjalan dan memori diukur menggunakan interpreter kalkulus Lambda yang ditulis oleh Melvin Zhang. Lam2bin ditulis oleh Justine Tunney.
