Bootstrap masih membutuhkan dukungan dari luar

Saya pernah mendengar tentang ide bootstrap suatu bahasa, yaitu menulis kompiler / juru bahasa untuk bahasa itu sendiri. Saya bertanya-tanya bagaimana ini bisa dilakukan dan melihat sekeliling sedikit, dan melihat seseorang berkata bahwa itu hanya bisa dilakukan oleh keduanya.

• menulis kompiler awal dalam bahasa berbeda.
• hand-coding kompiler awal di Assembly, yang tampaknya seperti kasus khusus dari yang pertama

Bagi saya, tidak satu pun dari ini tampaknya benar-benar bootstrap bahasa dalam arti keduanya membutuhkan dukungan dari luar. Apakah ada cara untuk benar-benar menulis kompiler dalam bahasanya sendiri?

Apakah ada cara untuk benar-benar menulis kompiler dalam bahasanya sendiri?

Anda harus memiliki beberapa bahasa untuk menulis kompilator baru Anda. Jika Anda menulis kompilator baru, katakanlah, C ++, Anda cukup menulisnya dalam C ++ dan mengkompilasinya dengan kompilator yang sudah ada terlebih dahulu. Di sisi lain, jika Anda membuat kompilator untuk bahasa baru, sebut saja Yazzleof, Anda perlu menulis kompilator baru dalam bahasa lain terlebih dahulu. Secara umum, ini akan menjadi bahasa pemrograman lain, tetapi tidak harus seperti itu. Ini bisa berupa perakitan, atau jika perlu, kode mesin.

Jika Anda sedang akan bootstrap sebuah compiler untuk Yazzleof, biasanya Anda tidak akan menulis compiler untuk bahasa penuh awalnya. Sebagai gantinya Anda akan menulis kompiler untuk Yazzle-lite, subset sekecil mungkin dari Yazzleof (yah, setidaknya subset yang cukup kecil ). Kemudian di Yazzle-lite, Anda akan menulis kompiler untuk bahasa lengkap. (Jelas ini dapat terjadi secara berulang, bukan dalam satu lompatan.) Karena Yazzle-lite adalah bagian yang tepat dari Yazzleof, Anda sekarang memiliki kompiler yang dapat dikompilasi sendiri.

Ada tulisan yang sangat bagus tentang bootstrap kompiler dari tingkat serendah mungkin (yang pada mesin modern pada dasarnya adalah editor hex), berjudul Bootstrap kompiler sederhana dari nol . Ini dapat ditemukan di https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html .

Penjelasan yang Anda baca benar. Ada diskusi tentang ini di Penyusun: Prinsip, Teknik, dan Alat (Buku Naga):

• Tulis kompiler C1 untuk bahasa X dalam bahasa Y
• Gunakan kompilator C1 untuk menulis kompilator C2 untuk bahasa X dalam bahasa X.
• Sekarang C2 adalah lingkungan hosting mandiri sepenuhnya.

Sebuah super menarik diskusi tentang ini adalah di Unix co-creator Ken Thompson 's Turing Award kuliah.

Dia memulai dengan:

Apa yang akan saya gambarkan adalah salah satu dari banyak masalah "ayam dan telur" yang muncul ketika penyusun ditulis dalam bahasa mereka sendiri. Dalam kemudahan ini, saya akan menggunakan contoh spesifik dari kompiler C.

dan hasil untuk menunjukkan bagaimana dia menulis versi kompiler Unix C yang akan selalu mengizinkannya untuk masuk tanpa kata sandi, karena kompiler C akan mengenali program login dan menambahkan kode khusus.

Pola kedua ditujukan untuk kompiler C. Kode pengganti adalah program mereproduksi diri Tahap I yang memasukkan kedua kuda Troya ke dalam kompilator. Ini membutuhkan fase pembelajaran seperti pada contoh Tahap II. Pertama kita mengkompilasi sumber yang dimodifikasi dengan kompilator C normal untuk menghasilkan biner yang disadap. Kami menginstal biner ini sebagai C resmi. Kami sekarang dapat menghapus bug dari sumber kompilator dan biner baru akan memasukkan kembali bug setiap kali dikompilasi. Tentu saja, perintah login akan tetap disadap tanpa jejak di sumber mana pun.

Cara yang pernah saya dengar adalah menulis kompiler yang sangat terbatas dalam bahasa lain, kemudian menggunakannya untuk mengkompilasi versi yang lebih rumit, yang ditulis dalam bahasa baru. Versi kedua ini kemudian dapat digunakan untuk mengkompilasi dirinya sendiri, dan versi berikutnya. Setiap kali dikompilasi, versi terakhir digunakan.

Inilah definisi bootstrap:

proses sistem sederhana mengaktifkan sistem yang lebih rumit yang melayani tujuan yang sama.

EDIT: Artikel Wikipedia tentang kompiler bootstrap mencakup konsep lebih baik dari saya.

Lihat podcast Software Engineering Radio episode 61 (2007-07-06) yang membahas internal compiler GCC, serta proses bootstrap GCC.

Donald E. Knuth sebenarnya membangun WEB dengan menulis compiler di dalamnya, dan kemudian mengompilasinya secara manual ke kode assembly atau mesin.

Seperti yang saya pahami, penerjemah Lisp pertama di -bootstrap dengan menyusun tangan fungsi konstruktor dan pembaca token. Penerjemah lainnya kemudian membaca dari sumber.

Anda dapat memeriksa sendiri dengan membaca koran McCarthy asli, Fungsi Rekursif Ekspresi simbolik dan Komputasi mereka oleh mesin, Bagian I .

Alternatif lain adalah membuat mesin bytecode untuk bahasa Anda (atau menggunakan yang sudah ada jika fiturnya tidak terlalu aneh) dan menulis compiler ke bytecode, baik dalam bytecode, atau dalam bahasa yang Anda inginkan menggunakan perantara lain - seperti a toolkit parser yang mengeluarkan AST sebagai XML, lalu mengompilasi XML ke bytecode menggunakan XSLT (atau bahasa pencocokan pola dan representasi berbasis pohon lainnya). Itu tidak menghapus ketergantungan pada bahasa lain, tetapi bisa berarti bahwa lebih banyak pekerjaan bootstrap berakhir di sistem akhir.

Ini adalah versi ilmu komputer dari paradoks ayam-dan-telur. Saya tidak bisa memikirkan cara untuk tidak menulis kompiler awal di assembler atau bahasa lain. Jika itu bisa dilakukan, saya harus Lisp bisa melakukannya.

Sebenarnya, menurutku Lisp hampir memenuhi syarat. Lihat entri Wikipedia-nya . Menurut artikel tersebut, fungsi eval Lisp dapat diimplementasikan pada IBM 704 dalam kode mesin, dengan kompiler lengkap (ditulis dalam Lisp itu sendiri) yang muncul pada tahun 1962 di MIT .

Setiap contoh bootstrap bahasa yang dapat saya pikirkan ( C , PyPy ) dilakukan setelah ada kompiler yang berfungsi. Anda harus mulai dari suatu tempat, dan menerapkan ulang bahasa itu sendiri membutuhkan penulisan kompiler dalam bahasa lain terlebih dahulu.

Bagaimana lagi cara kerjanya? Saya pikir tidak mungkin secara konseptual untuk melakukan sebaliknya.

Beberapa kompiler atau sistem bootstrap menyimpan baik bentuk sumber maupun bentuk objek dalam repositori mereka:

• ocaml adalah bahasa yang memiliki interpreter bytecode (yaitu kompilator untuk bytecode Ocaml) dan kompiler asli (ke x86-64 atau ARM, dll ... assembler). Repositori svnnya berisi kode sumber (file */*.{ml,mli}) dan bentuk bytecode (file boot/ocamlc) dari kompilator. Jadi, saat Anda membangunnya, pertama-tama gunakan bytecode-nya (dari versi compiler sebelumnya) untuk mengompilasi dirinya sendiri. Nanti bytecode yang baru dikompilasi dapat mengkompilasi kompiler asli. Jadi repositori Ocaml svn berisi *.ml[i]file sumber dan boot/ocamlcfile bytecode.

• The karat download compiler (menggunakan wget, sehingga Anda memerlukan koneksi internet kerja) versi biner untuk mengkompilasi sendiri.

• MELT adalah bahasa mirip Lisp untuk menyesuaikan dan memperluas GCC . Ini diterjemahkan ke kode C ++ oleh penerjemah bootstrap. Kode C ++ penerjemah yang dihasilkan didistribusikan, sehingga repositori svn berisi *.meltfile sumber dan file melt/generated/*.cc"objek" penerjemah.

• Sistem kecerdasan buatan CAIA J. Pitrat sepenuhnya dihasilkan sendiri. Ini tersedia sebagai kumpulan dari ribuan [A-Z]*.cfile yang dihasilkan (juga dengan dx.hfile header yang dihasilkan ) dengan kumpulan ribuan _[0-9]*file data.

• Beberapa kompiler Skema juga di-bootstrap. Scheme48, Skema Ayam, ...