Mengapa penugasan statis-tunggal lebih disukai daripada gaya kelanjutan kelanjutan dalam banyak kompiler yang digunakan industri?

Menurut halaman Wikipedia tentang static-single assignment (SSA) , SSA digunakan oleh proyek-proyek besar dan terkenal seperti LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey, dan V8 sedangkan halaman tentang proyek menggunakan gaya kelanjutan-lewat (CPS) agak kurang dibandingkan.

Saya berpendapat bahwa CPS lebih disukai oleh kompiler dan interpreter yang menerapkan bahasa fungsional utama - khususnya, Haskell dan Skema tampaknya memiliki kecenderungan kuat terhadap gaya CPS karena pembatasan mutasi atau kebutuhan untuk dukungan kelanjutan kelas satu (saya kira bahwa Smalltalk mungkin akan membutuhkan ini juga). Literatur utama yang saya temui yang menggunakan CPS tampaknya adalah yang terutama bekerja pada Skema atau terkait dengan Skema dalam beberapa hal.

Apakah ada alasan khusus mengapa SSA digunakan dalam industri selain momentum adopsi? SSA dan CPS memiliki hubungan dekat; itu berarti bahwa akan mudah untuk menyatakan dalam hal yang lain, tetapi mungkin representasi informasi akan kurang kompak atau kurang efisien untuk CPS.

Saya membayangkan banyak pelaksana kompiler untuk bahasa imperatif yang khas tidak begitu akrab dengan teknik kompilasi berbasis CPS dan CPS. Dalam komunitas pemrograman fungsional baik kompilasi berbasis CPS dan CPS adalah teknik yang sangat terkenal - yang terakhir dari karya Guy Steele. Namun demikian, bahkan dalam komunitas FP, kebanyakan kompiler tidak menggunakan teknik berbasis CPS untuk kompilasi kecuali bahasa itu sendiri mendukung operator kontrol call/cc. Sesuatu yang lebih seperti Formulir Normal Administratif (ANF) (kadang-kadang juga disebut sebagai Bentuk Normal Monadik yang terkait erat dengan alasan yang akan menjadi jelas) digunakan yang memiliki hubungan yang lebih erat dengan SSA daripada CPS .

Jika saya ingat dengan benar, bentuk normal administratif mendapatkan namanya dari fakta bahwa kompilasi berbasis CPS dapat mengarah ke beta-redexes dalam kode perantara yang tidak sesuai dengan apa pun dalam kode sumber. Ini disebut sebagai "redex administrasi". Ini dapat dikurangi pada saat kompilasi, tetapi ada sejumlah penelitian yang baik dalam melakukan transformasi CPS yang akan menghasilkan kode tanpa ada redex administratif di tempat pertama. Tujuannya kemudian adalah untuk menghasilkan output dalam bentuk normal di mana semua redex "administratif" berkurang, dan ini adalah asal dari Formulir Normal Administratif. Tidak butuh waktu lama untuk menyadari bahwa tidak ada banyak manfaat untuk melihat ini sebagai (n optimasi dari) proses dua langkah: CPS-transform, mengurangi redex administrasi. Khususnya, bentuk normal administratif agak mirip gaya monadik seperti yang dipraktikkan (dengan tangan) terutama di Haskell. Transformasi CPS dapat dipahami sebagai konversi ke gaya monadik di mana Anda kebetulan menggunakan monad CPS (jadi sebenarnya ada banyak cara untuk "mengkonversi" ke gaya monadik sesuai dengan pesanan evaluasi yang berbeda). Namun, secara umum, Anda dapat menggunakan monad yang sangat berbeda, sehingga konversi ke gaya monadik dan dengan demikian bentuk normal administratif tidak benar-benar terkait dengan CPS pada khususnya.

Namun demikian, ada beberapa manfaat untuk CPS dibandingkan ANF. Secara khusus, ada optimasi tertentu yang dapat Anda lakukan di CPS dengan hanya optimasi standar, seperti pengurangan beta, yang diperlukan (tampaknya) aturan ad-hoc untuk ANF. Dari sudut pandang monadik, aturan-aturan ini sesuai dengan konversi komuter. Hasilnya sekarang ada teori yang dapat menjelaskan aturan apa yang harus ditambahkan dan mengapa. Sebuah makalah baru - baru ini memberikan (dan baru) deskripsi yang cukup jelas tentang ini (dari perspektif logis) dan bagian pekerjaan terkait berfungsi sebagai survei singkat dan layak dan referensi ke dalam literatur tentang topik yang saya sebutkan.

Masalah dengan CPS terkait dengan salah satu manfaat utamanya. Transformasi CPS memungkinkan Anda untuk menerapkan operator kontrol seperti call/cc, tetapi ini berarti setiap panggilan fungsi non-lokal dalam kode perantara CPS harus diperlakukan sebagai berpotensi melakukan efek kontrol. Jika bahasa Anda termasuk operator kontrol, maka ini sudah seperti semestinya (meskipun bahkan sebagian besar fungsi mungkin tidak melakukan shenanigans kontrol apa pun). Jika bahasa Anda tidak termasuk operator kontrol, maka ada invarian global tentang penggunaan kelanjutan yang tidak terbukti secara lokal. Ini berarti ada optimasi yang tidak sehat untuk dilakukan pada kode CPS umum yang akan menjadi suara untuk dilakukan pada penggunaan CPS yang sangat baik. Salah satu cara mewujudkan ini adalahperubahan presisi data dan analisis aliran kontrol . (Transformasi CPS membantu dalam beberapa hal, menyakiti orang lain, meskipun cara itu membantu sebagian besar karena duplikasi daripada aspek CPS itu sendiri.) ¹ Anda tentu saja dapat menambahkan aturan dan menyesuaikan analisis untuk mengkompensasi hal ini (yaitu mengeksploitasi invarian global), tetapi kemudian Anda telah mengalahkan sebagian dari salah satu manfaat utama kompilasi berbasis CPS yaitu banyak (tampaknya) optimasi khusus, ad-hoc menjadi kasus-kasus khusus optimasi tujuan umum (khususnya pengurangan beta ).

Pada akhirnya, kecuali bahasa Anda memiliki operator kontrol, biasanya tidak ada banyak alasan untuk menggunakan skema kompilasi berbasis CPS. Setelah Anda mengkompensasi masalah yang saya sebutkan di atas, Anda biasanya menghilangkan manfaat kompilasi berbasis CPS dan menghasilkan sesuatu yang setara dengan tidak menggunakan CPS. Pada saat itu, CPS hanya membuat kode perantara yang berbelit-belit untuk keuntungan yang tidak banyak. Argumen untuk kompilasi berbasis CPS dari 2007 membahas beberapa masalah ini dan menyajikan beberapa manfaat lain menggunakan bentuk konversi CPS yang berbeda. Hal-hal yang diangkat oleh kertas sebagian tercakup oleh makalah (2017) yang saya sebutkan sebelumnya.

¹ Bukankah kesetaraan antara SSA dan CPS membuat ini lebih atau kurang mungkin? Tidak. Salah satu hal pertama yang diperkenalkan makalah ini menyatakan kesetaraan adalah bahwa kesetaraan tidak bekerja untuk kode CPS sewenang - wenang , tetapi itu bekerja untuk output dari transformasi CPS (yang mereka tetapkan) untuk bahasa tanpa operator kontrol.

Saya bukan ahli kompiler, jadi ambillah apa yang saya katakan dengan sebutir garam, saya berharap bahwa ahli kompiler nyata akan berpadu. Saya diberitahu bahwa:

• Kode CPSed cenderung melompat non-lokal banyak, yang merusak lokalitas cache, maka kinerja.
• CPS membutuhkan pengumpulan sampah yang lebih mahal daripada kompilasi konvensional yang biasanya dapat menyimpan banyak barang di tumpukan (yang lebih cepat dialokasikan dan didelokasikan).

Keduanya bersekongkol untuk membuat kode yang dikompilasi oleh CPS-transform relatif lambat.