Kenapa kompiler begitu bisa diandalkan?

Kami menggunakan kompiler setiap hari seolah-olah kebenarannya diberikan, tetapi kompiler juga merupakan program, dan berpotensi mengandung bug. Saya selalu bertanya-tanya tentang ketahanan sempurna ini. Pernahkah Anda menemukan bug di kompiler itu sendiri? Apa itu dan bagaimana Anda menyadari masalahnya ada di kompiler itu sendiri?

... dan bagaimana cara mereka membuat kompiler sangat handal?

Mereka diuji secara menyeluruh melalui penggunaan oleh ribuan atau bahkan jutaan pengembang dari waktu ke waktu.

Juga, masalah yang harus dipecahkan didefinisikan dengan baik (dengan spesifikasi teknis yang sangat rinci). Dan sifat tugas cocok dengan mudah untuk tes unit / sistem. Yaitu pada dasarnya menerjemahkan input tekstual dalam format yang sangat spesifik untuk output dalam jenis lain dari format yang terdefinisi dengan baik (semacam bytecode atau kode mesin). Sehingga mudah untuk membuat dan memverifikasi kasus uji.

Selain itu, biasanya bug juga mudah direproduksi: terlepas dari platform yang tepat dan info versi kompiler, biasanya yang Anda butuhkan hanyalah sepotong kode input. Belum lagi bahwa pengguna kompiler (menjadi pengembang sendiri) cenderung memberikan laporan bug yang jauh lebih tepat dan terperinci daripada pengguna komputer rata-rata :-)

Selain semua jawaban bagus sejauh ini:

Anda memiliki "bias pengamat". Anda tidak mengamati bug, dan karena itu Anda menganggap tidak ada bug.

Dulu saya berpikir seperti Anda. Kemudian saya mulai menulis kompiler secara profesional, dan biarkan saya memberitahu Anda, ada banyak bug di sana!

Anda tidak melihat bug karena Anda menulis kode yang hanya seperti 99,999% dari semua kode yang ditulis orang. Anda mungkin menulis kode yang benar-benar normal, langsung, dan benar, yang memanggil metode dan menjalankan loop dan tidak melakukan sesuatu yang mewah atau aneh, karena Anda adalah pengembang normal yang menyelesaikan masalah bisnis normal.

Anda tidak melihat bug penyusun karena bug penyusun tidak ada dalam skenario kode normal yang mudah dianalisa; bug ada dalam analisis kode aneh yang tidak Anda tulis.

Saya di sisi lain memiliki bias pengamat yang berlawanan. Saya melihat kode gila sepanjang hari setiap hari, dan bagi saya para kompiler sepertinya penuh dengan bug.

Jika Anda duduk dengan spesifikasi bahasa dari bahasa apa pun, dan mengambil implementasi kompiler apa pun untuk bahasa itu, dan benar-benar berusaha keras untuk menentukan apakah kompiler benar-benar mengimplementasikan spesifikasi atau tidak, berkonsentrasi pada kasus sudut yang tidak jelas, segera Anda akan menemukan bug kompiler cukup sering. Biarkan saya memberi Anda sebuah contoh, inilah bug kompiler C # yang saya temukan secara harfiah lima menit yang lalu.

static void N(ref int x){}
...
N(ref 123);

Kompiler memberikan tiga kesalahan.

• Argumen ref atau out harus merupakan variabel yang dapat ditugaskan.
• Kecocokan terbaik untuk N (ref int x) memiliki argumen yang tidak valid.
• Tidak ada "ref" pada argumen 1.

Jelas pesan kesalahan pertama sudah benar dan yang ketiga adalah bug. Algoritma generasi kesalahan sedang mencoba mencari tahu mengapa argumen pertama tidak valid, terlihat pada argumen itu, melihat bahwa argumen tersebut adalah konstanta, dan tidak kembali ke kode sumber untuk memeriksa apakah argumen itu ditandai sebagai "ref"; melainkan mengasumsikan bahwa tidak ada orang yang cukup bodoh untuk menandai sebuah konstanta sebagai referensi, dan memutuskan bahwa referensi tersebut harus hilang.

Tidak jelas apa pesan kesalahan ketiga yang benar, tetapi ini bukan. Bahkan, tidak jelas apakah pesan kesalahan kedua juga benar. Haruskah resolusi kelebihan gagal, atau haruskah "ref 123" diperlakukan sebagai argumen ref dari jenis yang benar? Sekarang saya harus memikirkannya dan membicarakannya dengan tim triase sehingga kita dapat menentukan apa perilaku yang benar.

Anda belum pernah melihat bug ini karena Anda mungkin tidak akan pernah melakukan sesuatu yang konyol untuk mencoba melewati 123 oleh ref. Dan jika Anda melakukannya, Anda mungkin bahkan tidak akan melihat bahwa pesan kesalahan ketiga adalah tidak masuk akal, karena yang pertama sudah benar dan cukup untuk mendiagnosis masalah. Tetapi saya mencoba melakukan hal-hal seperti itu, karena saya mencoba untuk memecahkan kompiler. Jika Anda mencoba, Anda akan melihat bug juga.

Apakah kamu bercanda? Kompiler juga memiliki bug, benar-benar memuat.

GCC mungkin adalah kompiler open source paling terkenal di planet ini dan lihat database bug-nya: http://gcc.gnu.org/bugzilla/buglist.cgi?product=gcc&component=c%2B%2B&resolution=-- -

Antara GCC 3.2 dan GCC 3.2.3 lihat berapa banyak bug diperbaiki: http://gcc.gnu.org/gcc-3.2/changes.html

Adapun orang lain seperti Visual C ++, saya bahkan tidak ingin memulai.

Bagaimana Anda membuat kompiler dapat diandalkan? Sebagai permulaan, mereka memiliki banyak dan banyak unit test. Dan seluruh planet menggunakannya sehingga tidak ada kekurangan penguji.

Serius meskipun, pengembang kompiler saya suka percaya adalah programmer unggul dan sementara mereka tidak sempurna mereka dikemas dalam pukulan yang cukup.

Saya telah menemukan dua atau tiga di hari saya. Satu-satunya cara nyata untuk mendeteksi seseorang adalah dengan melihat kode perakitan.

Meskipun kompiler sangat dapat diandalkan karena alasan yang ditunjukkan poster lain, saya pikir keandalan kompiler seringkali merupakan penilaian yang memuaskan sendiri. Programmer cenderung melihat compiler sebagai standar. Ketika terjadi kesalahan, Anda menganggap itu salah Anda (karena 99,999% dari waktu itu), dan mengubah kode Anda untuk mengatasi masalah kompiler daripada sebaliknya. Misalnya, kode mogok di bawah pengaturan optimasi tinggi jelas merupakan bug penyusun, tetapi kebanyakan orang hanya mengaturnya sedikit lebih rendah dan melanjutkan tanpa melaporkan bug.

Kompiler memiliki beberapa properti yang mengarah pada kebenarannya:

• Domain ini sangat terkenal, dan diteliti. Masalahnya didefinisikan dengan baik, dan solusi yang ditawarkan didefinisikan dengan baik.
• Pengujian otomatis cukup untuk membuktikan kompiler bekerja dengan benar
• Compiler memiliki tes unit yang sangat luas, biasanya publik, otomatis dan, yang telah terakumulasi dari waktu ke waktu untuk mencakup lebih banyak ruang kesalahan daripada untuk sebagian besar program lain
• Compiler memiliki jumlah bola mata yang sangat besar menyaksikan hasilnya

Kami menggunakan kompiler setiap hari

... dan bagaimana mereka membuat kompiler sangat dapat diandalkan?

Mereka tidak melakukannya. Kami lakukan. Karena setiap orang menggunakannya setiap saat, bug ditemukan dengan cepat.

Ini adalah permainan angka. Karena kompiler terbiasa dengan pervasif, kemungkinan besar bug apa pun akan dipicu oleh seseorang, tetapi karena ada sejumlah besar pengguna, sangat kecil kemungkinannya bahwa seseorang akan menjadi Anda secara khusus.

Jadi, itu tergantung pada sudut pandang Anda: di semua pengguna, kompiler buggy. Tetapi sangat mungkin bahwa orang lain akan telah mengkompilasi kode yang serupa sebelum Anda melakukannya, jadi jika mereka adalah bug, itu akan mengenai mereka, bukan Anda, jadi dari sudut pandang pribadi Anda , sepertinya bug itu adalah tidak pernah ada.

Tentu saja, di atas itu, Anda dapat menambahkan semua jawaban lain di sini: kompiler diteliti dengan baik, dipahami dengan baik. Ada mitos bahwa mereka sulit untuk menulis, yang berarti bahwa hanya programmer yang sangat pintar, sangat baik yang benar-benar mencoba untuk menulisnya, dan ekstra hati-hati ketika melakukannya. Mereka umumnya mudah untuk diuji, dan mudah untuk stress test atau fuzz test. Pengguna kompiler cenderung menjadi programmer ahli sendiri, yang mengarah ke laporan bug berkualitas tinggi. Dan sebaliknya: penulis kompiler cenderung menjadi pengguna kompiler mereka sendiri.

Selain semua jawaban yang sudah, saya ingin menambahkan:

Saya percaya banyak kali, para penjual makan makanan anjing mereka sendiri. Artinya, mereka menulis kompiler dalam diri mereka sendiri.

Saya sering mengalami bug kompiler.

Anda dapat menemukannya di sudut yang lebih gelap di mana ada lebih sedikit penguji. Misalnya, untuk menemukan bug di GCC Anda harus mencoba:

• Bangun kompiler silang. Anda akan menemukan lusinan bug di skrip configure dan build GCC. Beberapa menghasilkan kegagalan build selama kompilasi GCC dan yang lainnya akan mengakibatkan kegagalan cross-compiler untuk membangun executable yang berfungsi.
• Buat versi Itanium dari GCC menggunakan profil-bootstrap. Beberapa kali terakhir saya mencoba ini pada GCC 4.4 dan 4.5 gagal untuk menghasilkan pengendali pengecualian C ++ yang berfungsi. Bangunan yang tidak dioptimalkan berfungsi dengan baik. Sepertinya tidak ada yang tertarik untuk memperbaiki bug yang saya laporkan dan saya berhenti memperbaikinya sendiri setelah mencoba menggali apa yang melanggar spesifikasi memori asm GCC.
• Cobalah membangun GCJ Anda sendiri dari hal-hal terbaru tanpa mengikuti skrip distro build. Saya menantang Anda.

Beberapa alasan:

• Penulis kompiler " makan makanan anjing mereka sendiri ".
• Kompiler didasarkan pada prinsip - prinsip CS yang dipahami dengan baik .
• Kompiler dibuat dengan spesifikasi yang sangat jelas .
• Kompiler diuji .
• Kompiler tidak selalu sangat andal .

Mereka biasanya sangat bagus di -O0. Bahkan jika kami mencurigai bug kompiler, kami membandingkan -O0 versus level apa pun yang kami coba gunakan. Level optimisasi yang lebih tinggi cocok dengan risiko yang lebih besar. Beberapa bahkan sengaja melakukannya, dan diberi label seperti itu dalam dokumentasi. Saya telah menemukan banyak sekali (setidaknya seratus selama waktu saya), tetapi mereka menjadi jauh lebih jarang baru-baru ini. Namun demikian dalam mengejar angka-angka specmark yang baik (atau tolok ukur lain yang penting untuk pemasaran), godaan untuk mendorong batasan itu besar. Kami memiliki masalah beberapa tahun yang lalu di mana vendor (untuk tidak disebutkan namanya) memutuskan untuk melakukan pelanggaran terhadap tanda kurung default-lebih daripada beberapa opsi kompilasi yang diberi label dengan jelas.

Mungkin sulit untuk mendiagnosis kesalahan kompiler versus mengatakan referensi memori yang tersesat, kompilasi ulang dengan opsi yang berbeda mungkin hanya memperebutkan posisi relatif dari objek data dalam memori, sehingga Anda tidak tahu apakah itu Heisenbug kode sumber Anda, atau buggy penyusun. Juga banyak optimasi membuat perubahan yang sah dalam urutan operasi, atau bahkan penyederhanaan aljabar untuk aljabar Anda, dan ini akan memiliki sifat yang berbeda sehubungan dengan pembulatan titik mengambang dan under / overflow. Sulit untuk memisahkan efek ini dari bug NYATA. Komputasi floating point hard core sulit karena alasan ini, karena bug dan kepekaan numerik seringkali tidak mudah diurai.

Bug kompiler tidak terlalu langka. Kasus yang paling umum adalah bagi kompilator untuk melaporkan kesalahan pada kode yang harus diterima, atau bagi kompiler untuk menerima kode yang seharusnya ditolak.

Yap, saya menemukan bug di kompiler ASP.NET baru kemarin:

Saat Anda menggunakan model yang sangat diketik dalam tampilan, ada batasan berapa banyak parameter yang dapat berisi template. Jelas tidak dapat mengambil lebih dari 4 parameter templat, sehingga kedua contoh di bawah ini membuatnya terlalu banyak untuk ditangani oleh kompiler:

ViewUserControl<System.Tuple<type1, type2, type3, type4, type5>>

Tidak akan mengkompilasi apa adanya tetapi akan jika type5dihapus.

ViewUserControl<System.Tuple<MyModel, System.Func<type1, type2, type3, type4>>>

Akan dikompilasi jika type4dihapus.

Catatan yang System.Tuplememiliki banyak kelebihan dan bisa memakan hingga 16 parameter (ini gila, saya tahu).

Pernahkah Anda menemukan bug di kompiler itu sendiri? Apa itu dan bagaimana Anda menyadari masalahnya ada di kompiler itu sendiri?

Ya!

Dua yang paling berkesan adalah dua yang pertama saya temui. Mereka berdua di kompiler Lightspeed C untuk 680x0 Mac sekitar 1985-7.

Yang pertama adalah di mana, dalam beberapa keadaan, operator postincrement integer tidak melakukan apa pun - dengan kata lain, dalam potongan kode tertentu, "i ++" sama sekali tidak melakukan apa pun untuk "i". Saya mencabut rambut saya sampai saya melihat pembongkaran. Lalu saya hanya melakukan peningkatan dengan cara yang berbeda, dan mengirimkan laporan bug.

Yang kedua sedikit lebih rumit, dan benar-benar sebuah "fitur" yang dianggap salah. Mac awal memiliki sistem yang rumit untuk melakukan operasi disk tingkat rendah. Untuk beberapa alasan saya tidak pernah mengerti - mungkin ada hubungannya dengan membuat executable yang lebih kecil - daripada kompiler hanya menghasilkan instruksi operasi disk di tempat dalam kode objek, kompiler Lightspeed akan memanggil fungsi internal, yang pada saat runtime menghasilkan operasi disk instruksi di tumpukan dan melompat ke sana.

Itu bekerja sangat baik pada 68000 CPU, tetapi ketika Anda menjalankan kode yang sama pada CPU 68020, itu sering melakukan hal-hal aneh. Ternyata fitur baru dari 68020 adalah instruksi primitif 256-byte cache instruksi. Ini adalah hari-hari awal dengan cache CPU, itu tidak berpendapat bahwa cache "kotor" dan perlu diisi ulang; Saya kira para perancang CPU di Motorola tidak memikirkan kode modifikasi diri. Jadi, jika Anda melakukan dua operasi disk yang cukup berdekatan dalam urutan eksekusi Anda, dan runtime Lightspeed membuat instruksi aktual di lokasi yang sama pada stack, CPU akan keliru mengira itu memiliki cache instruksi yang hit dan menjalankan operasi disk pertama dua kali.

Sekali lagi, mencari tahu mengambil beberapa penggalian dengan disassembler, dan banyak langkah dalam debugger tingkat rendah. Solusi saya adalah untuk mengawali setiap operasi disk dengan panggilan ke fungsi yang melakukan 256 "NOP" instruksi, yang membanjiri (dan dengan demikian membersihkan) cache instruksi.

Lebih dari 25 tahun sejak itu, saya melihat semakin sedikit bug penyusun dari waktu ke waktu. Saya pikir ada beberapa alasan untuk itu:

• Ada satu set tes validasi yang terus meningkat untuk kompiler.
• Kompiler modern biasanya dibagi menjadi dua bagian atau lebih, yang salah satunya menghasilkan kode bebas platform (mis. LLVM menargetkan apa yang Anda anggap sebagai CPU imajiner), dan yang lain menerjemahkannya menjadi instruksi untuk perangkat keras target Anda yang sebenarnya. Dalam kompiler multi-platform, bagian pertama digunakan di mana-mana, sehingga mendapat banyak pengujian di dunia nyata.

Ditemukan kesalahan mencolok di Turbo Pascal 5,5 tahun yang lalu. Galat hadir dalam versi kompiler sebelumnya (5.0) maupun versi (6.0) berikutnya. Dan yang seharusnya mudah untuk diuji, karena itu bukan cornercase sama sekali (hanya panggilan yang tidak biasa digunakan).

Secara umum, tentu pembangun kompiler komersial (daripada proyek hobi) akan memiliki QA yang sangat luas dan prosedur pengujian di tempat. Mereka tahu kompiler mereka adalah proyek andalan mereka dan bahwa kelemahan akan terlihat sangat buruk pada mereka, lebih buruk daripada yang mereka lihat pada perusahaan lain yang membuat sebagian besar produk lainnya. Pengembang perangkat lunak adalah kelompok yang tidak termaafkan, pemasok alat kami mengecewakan kami, kami cenderung mencari alternatif daripada menunggu perbaikan dari pemasok, dan kami sangat mungkin untuk mengomunikasikan fakta itu kepada rekan-rekan kami yang mungkin mengikuti kami contoh. Di banyak industri lain yang tidak demikian, sehingga potensi kerugian bagi pembuat kompiler sebagai akibat dari bug serius jauh lebih besar daripada yang dikatakan pembuat perangkat lunak video editing.

Ketika perilaku perangkat lunak Anda berbeda ketika dikompilasi dengan -O0 dan dengan -O2, maka Anda telah menemukan bug kompilator.

Ketika perilaku perangkat lunak Anda hanya berbeda dari yang Anda harapkan, maka kemungkinan bug tersebut ada dalam kode Anda.

Bug penyusun terjadi, tetapi Anda cenderung menemukannya di sudut aneh ...

Ada bug aneh di kompiler Digital Equipment Corporation VAX VMS C pada 1990-an

(Saya mengenakan bawang di ikat pinggang saya, seperti halnya fashion pada saat itu)

Titik koma asing di mana saja sebelum loop for akan dikompilasi sebagai tubuh loop for.

f(){...}
;
g(){...}

void test(){
  int i;
  for ( i=0; i < 10; i++){
     puts("hello");
  }
}

Pada kompiler yang dimaksud, loop dijalankan hanya sekali.

ia melihat

f(){...}
g(){...}

void test(){
  int i;
  for ( i=0; i < 10; i++) ;  /* empty statement for fun */

  {
     puts("hello");
  }
}

Itu menghabiskan banyak waktu.

Versi lama dari kompiler PIC C yang kami (gunakan) pada pengalaman kerja siswa tidak dapat menghasilkan kode yang menggunakan interupsi prioritas tinggi dengan benar. Anda harus menunggu 2-3 tahun dan memutakhirkan.

Kompiler MSVC 6 memiliki bug yang bagus di tautan, itu akan segmentasi kesalahan dan mati dari waktu ke waktu tanpa alasan. Bangunan bersih umumnya diperbaiki (tapi tidak selalu mendesah ).

Di beberapa domain, seperti perangkat lunak avionik, ada persyaratan sertifikasi yang sangat tinggi, pada kode dan perangkat keras, serta pada kompiler. Tentang bagian terakhir ini, ada proyek yang bertujuan untuk membuat kompiler C yang terverifikasi secara formal, yang disebut Compcert . Secara teori, kompiler semacam ini dapat diandalkan karena mereka datang.

Saya telah melihat beberapa bug penyusun, melaporkan sendiri beberapa (khususnya, dalam F #).

Yang mengatakan, saya pikir bug kompiler jarang terjadi karena orang yang menulis kompiler pada umumnya sangat nyaman dengan konsep ketat ilmu komputer yang membuat mereka benar-benar sadar tentang implikasi matematis dari kode.

Sebagian besar dari mereka mungkin sangat akrab dengan hal-hal seperti kalkulus lambda, verifikasi formal, semantik denotasi, dll. - hal-hal yang hanya bisa dipahami oleh programmer biasa.

Juga, biasanya ada pemetaan yang cukup mudah dari input ke output dalam kompiler, jadi debugging bahasa pemrograman mungkin jauh lebih mudah daripada debugging, katakanlah, mesin blog.

Saya menemukan bug di compiler C # belum lama ini, Anda dapat melihat bagaimana Eric Lippert (yang ada di tim desain C #) menemukan apa bug itu di sini .

Selain jawaban yang sudah diberikan, saya ingin menambahkan beberapa hal lagi. Desainer kompiler seringkali merupakan programmer yang sangat baik. Compiler sangat penting: kebanyakan pemrograman dilakukan dengan menggunakan kompiler, jadi sangat penting kompiler berkualitas tinggi. Oleh karena itu, demi kepentingan terbaik perusahaan membuat kompiler untuk menempatkan orang-orang terbaik mereka di atasnya (atau setidaknya, yang sangat bagus: yang terbaik mungkin tidak suka desain kompiler). Microsoft sangat ingin kompiler C dan C ++ mereka bekerja dengan baik, atau perusahaan lain tidak dapat melakukan pekerjaan mereka.

Juga, jika Anda sedang membangun kompiler yang sangat kompleks, Anda tidak bisa hanya meretasnya bersama. Logika di balik kompiler sangat kompleks dan mudah diformalkan. Oleh karena itu, program-program ini akan sering dibangun dengan cara yang sangat 'kuat' dan generik, yang cenderung menghasilkan lebih sedikit bug.