Saya sangat senang mengumumkan penyelesaian kompiler pertama saya untuk bahasa pemrograman! Malcc adalah kompilator Lisp AOT tambahan yang ditulis dalam C.

Secara singkat saya akan berbicara tentang perkembangannya selama bertahun-tahun dan apa yang saya pelajari dalam proses itu. Judul artikel alternatif: "Cara menulis kompiler dalam sepuluh tahun atau kurang."

(Pada akhirnya ada TL; DR , jika Anda tidak peduli dengan latar belakang).

Demo penyusun

tim ~/pp/malcc master 0 → ./malcc Mal [malcc] user> (println "hello world") hello world nil user> (+ 1 2) 3 user> (def! fib2 (fn* (n) (let* (f (fn* (n1 n2 c) (if (= cn) n2 (f n2 (+ n1 n2) (+ c 1))))) (f 0 1 1)))) <lambda> user> (fib2 25) 75025 user> ^D% tim ~/pp/malcc master 0 → ./malcc examples/hello.mal hello world tim ~/pp/malcc master 0 → ./malcc --compile examples/hello.mal hello gcc -g -I ./tinycc -I . -o hello hello.c ./reader.c ./printer.c ./hashmap.c ./types.c ./util.c ./env.c ./core.c ./tinycc/libtcc.a -ledit -lgc -lpcre -ldl tim ~/pp/malcc master 0 → ./hello hello world tim ~/pp/malcc master 0 → 

Kegagalan yang berhasil

Selama hampir sepuluh tahun, saya bermimpi menulis kompiler. Saya selalu terpesona oleh karya bahasa pemrograman, terutama kompiler. Meskipun aku membayangkan kompiler itu sebagai sihir gelap dan mengerti bahwa mustahil bagi manusia biasa sepertiku untuk membuatnya dari awal.

Tetapi saya masih mencoba dan belajar sepanjang jalan!

Pertama, penerjemah

Pada 2011, saya mulai mengerjakan penerjemah sederhana untuk bahasa fiksi Airball (airball dapat diterjemahkan sebagai “muff”). Dengan nama Anda dapat mengevaluasi tingkat ketidakpastian saya bahwa itu akan berhasil. Itu adalah program Ruby yang cukup sederhana yang mem-parsing kode dan berjalan melalui pohon sintaksis abstrak (AST). Ketika penerjemah masih bekerja, saya menamainya menjadi Lydia dan menulis ulang untuk C agar lebih cepat.



Saya ingat sintaksis Lydia tampak sangat cerdas bagi saya! Saya masih menikmati kesederhanaannya.

Meskipun Lydia jauh dari kompiler yang sempurna, itu mengilhami saya untuk terus bereksperimen. Namun, saya masih tersiksa oleh pertanyaan, bagaimana cara membuat kompiler bekerja: apa yang harus dikompilasi? apakah saya perlu belajar assembler?

Kedua, kompiler bytecode dan interpreter

Sebagai langkah berikutnya, pada tahun 2014, saya mulai mengerjakan skema-vm , mesin virtual untuk Skema yang ditulis dalam Ruby. Saya berpikir bahwa mesin virtual dengan stack dan bytecode sendiri akan menjadi tahap transisi dari seorang interpreter dengan AST pass dan kompiler penuh. Dan karena Skema didefinisikan secara formal , tidak perlu menemukan apa pun.

Saya telah bermain-main dengan skema-vm selama lebih dari tiga tahun dan telah belajar banyak tentang kompilasi. Pada akhirnya, saya menyadari bahwa saya tidak dapat menyelesaikan proyek ini. Kode berubah menjadi kekacauan nyata, tetapi tidak ada akhir yang terlihat. Tanpa seorang mentor atau pengalaman, saya sepertinya berkeliaran di kegelapan. Ternyata, spesifikasi bahasa tidak sama dengan manual untuk itu. Pelajaran yang dipetik!

Pada akhir 2017, saya menunda skema-vm untuk mencari sesuatu yang lebih baik.

Bertemu dengan Mal

Suatu waktu di tahun 2018, saya bertemu Mal , seorang penerjemah Lisp gaya Clojure.

Mal ditemukan oleh Joel Martin sebagai alat pelatihan. Sejak itu, lebih dari 75 implementasi dalam berbagai bahasa telah dikembangkan! Ketika saya melihat implementasi ini, saya menyadari bahwa mereka banyak membantu: jika saya macet, maka saya bisa mencari tip di versi Ruby atau Python. Akhirnya, setidaknya seseorang berbicara dalam bahasa saya!

Saya juga berpikir bahwa jika saya bisa menulis juru bahasa untuk Mal, saya bisa mengulangi langkah yang sama - dan membuat kompiler untuk Mal.

Mal penerjemah di Rust

Pertama, saya mulai mengembangkan penerjemah sesuai dengan panduan . Pada saat itu, saya secara aktif mempelajari Rust (saya akan meninggalkannya untuk artikel lain), jadi saya menulis implementasi Mal saya sendiri di Rust: mal-rust . Lihat di sini untuk lebih lanjut tentang percobaan ini.

Itu adalah kesenangan yang sempurna! Saya tidak tahu bagaimana harus berterima kasih atau memuji Joel karena membuat panduan hebat untuk Mal. Setiap langkah dijelaskan secara terperinci , ada diagram alur, kode semu, dan tes ! Semua yang dibutuhkan pengembang untuk membuat bahasa pemrograman dari awal hingga akhir.

Menjelang akhir tutorial, saya berhasil menjalankan implementasi Mal saya untuk Mal, ditulis dalam Mal, di atas implementasi Rust saya. (dua tingkat kedalaman, wow). Ketika dia bekerja untuk pertama kalinya, saya melompat ke atas kursi dengan gembira!

Kompiler Mal C

Segera setelah saya membuktikan kelayakan dari karat, saya segera mulai meneliti bagaimana menulis kompiler. Kompilasi ke assembler? Bisakah saya mengkompilasi kode mesin secara langsung?

Saya melihat assembler x86 ditulis dalam Ruby. Dia menggelitik saya, tetapi pemikiran untuk bekerja dengan assembler membuat saya berhenti.

Pada satu titik, saya menemukan komentar ini di Hacker News , yang menyebut Tiny C Compiler sebagai "kompilasi backend." Sepertinya ide yang bagus!

TinyCC memiliki file uji yang menunjukkan cara menggunakan libtcc untuk mengkompilasi kode C. Dari program C. Ini adalah titik awal untuk "hello world".

Kembali lagi ke panduan Mal, mengingat pengetahuan saya tentang C, dalam beberapa bulan bebas malam dan akhir pekan, saya bisa menulis kompilator Mal. Itu adalah kenikmatan nyata.



Jika Anda terbiasa berkembang melalui pengujian, maka evaluasi ketersediaan satu set tes pendahuluan. Tes mengarah pada implementasi kerja.

Saya tidak bisa mengatakan banyak tentang proses ini, kecuali saya ulangi: manual Mal adalah harta nyata. Di setiap langkah, saya tahu persis apa yang harus dilakukan!

Kesulitan

Melihat ke belakang, berikut adalah beberapa kesulitan ketika menulis kompiler Mal, di mana saya harus bermain-main:

1. Macro harus mengkompilasi dengan cepat dan siap untuk dieksekusi pada waktu kompilasi. Ini sedikit membingungkan.
   
2. Penting untuk menyediakan "lingkungan" (pohon hash / array asosiatif / kamus dengan variabel dan nilai-nilai mereka) baik untuk kode kompiler dan untuk kode akhir dari program yang dikompilasi. Ini memungkinkan Anda untuk mendefinisikan makro pada waktu kompilasi.
   
3. Karena lingkungan tersedia pada waktu kompilasi, pada awalnya Malcc menangkap kesalahan yang tidak terdefinisi selama kompilasi (akses ke variabel yang tidak didefinisikan), dan di beberapa tempat ini melanggar harapan suite uji. Pada akhirnya, untuk lulus tes, saya mematikan fitur ini. Akan sangat bagus untuk menambahkannya kembali sebagai flag tambahan dari kompiler, karena dengan cara ini Anda dapat menangkap banyak kesalahan sebelumnya.
4. Saya menyusun kode C dengan menulis dalam tiga baris struktur:
   • top : kode tingkat atas - inilah fungsinya
   • decl : deklarasi dan inisialisasi variabel yang digunakan dalam tubuh
   • body : tubuh di mana pekerjaan utama dilakukan
5. Sepanjang hari saya bertanya-tanya apakah saya bisa menulis pengumpul sampah saya sendiri, tetapi saya memutuskan untuk meninggalkan latihan ini untuk nanti. Perpustakaan pengumpulan sampah Boehm-Demers-Weiser mudah disambungkan dan tersedia di banyak platform.
   
6. Penting untuk melihat kode yang ditulis oleh kompiler Anda. Setiap kali kompiler menemukan variabel lingkungan DEBUG , ia mengembalikan kode C yang dikompilasi di mana kesalahan dapat dilihat.

Apa yang akan saya lakukan sebaliknya

1. Menulis kode C dan berusaha menjaga lekukan itu tidak mudah, maka saya tidak akan menolak otomatisasi. Tampaknya bagi saya bahwa beberapa kompiler menulis kode jelek, dan kemudian perpustakaan khusus "menghiasi" sebelum mengeluarkannya. Itu perlu dipelajari!
   
2. Menambahkan ke baris selama pembuatan kode agak berantakan. Anda dapat mempertimbangkan untuk membuat AST dan kemudian mengubahnya ke baris terakhir dari kode C. Ini harus membawa kode dalam urutan dan memberikan harmoni.

Sekarang saran

Saya suka itu butuh hampir satu dekade untuk kompiler. Tidak benar Setiap langkah di jalan adalah memori yang menyenangkan tentang bagaimana saya secara bertahap menjadi programmer yang lebih baik.

Tetapi ini tidak berarti bahwa saya "selesai". Masih ada ratusan metode dan alat yang perlu Anda pelajari untuk merasa seperti penulis kompiler yang sebenarnya. Tetapi saya dapat dengan yakin mengatakan: "Saya melakukannya."

Inilah keseluruhan proses dalam bentuk ringkas, cara membuat kompilator Lisp Anda sendiri:

1. Pilih bahasa di mana Anda merasa nyaman. Anda tidak ingin secara bersamaan mempelajari bahasa baru dan bagaimana menulis bahasa baru lainnya.
   
2. Dengan mengikuti panduan Mal, tulislah seorang penerjemah.
   
3. Bersukacitalah!
   
4. Ikuti instruksi lagi, tetapi alih-alih mengeksekusi kode, tulis kode yang mengeksekusi kode. (Bukan hanya "refactoring" penerjemah yang ada. Anda harus mulai dari awal, meskipun copy-paste tidak dilarang).

Saya percaya bahwa metode ini dapat digunakan dengan bahasa pemrograman apa pun yang dikompilasi menjadi file yang dapat dieksekusi. Misalnya, Anda dapat:

1. Tuliskan penerjemah Bahasa Mal saat Pergi .
2. Ubah kode Anda menjadi:
   
   • buat baris kode Go dan tulis ke file;
   • kompilasi file yang dihasilkan ini dengan go build .

Idealnya, lebih baik mengontrol kompiler Go sebagai pustaka, tetapi ini juga merupakan cara untuk membuat kompiler!

Dengan bantuan pemandu Mal dan kecerdikan Anda, Anda dapat melakukan semua ini. Jika saya bisa, maka Anda bisa!