Apakah kompiler optimalisasi penuh untuk mengakhiri program ada?

Dalam buku Andrew W. Appel, Implementasi Kompiler Modern dalam ML , ia mengatakan di bawah bab 17 bahwa teori Komputasi menunjukkan bahwa akan selalu mungkin untuk menciptakan transformasi optimisasi baru dan hasil untuk membuktikan bahwa kompiler yang mengoptimalkan sepenuhnya akan menyelesaikan masalah yang terhenti: Sebuah program Q yang tidak menghasilkan output dan tidak pernah berhenti dapat dengan mudah digantikan oleh representasi optimalnya, Opt (Q) , menjadi "L: goto L". Jadi kompiler yang sepenuhnya mengoptimalkan dapat memecahkan masalah penghentian.

Jadi pertanyaan saya adalah ini: Apakah ada kompiler yang mengoptimalkan sepenuhnya ada untuk mengakhiri program? Pikiran saya satu-satunya adalah sebagai berikut: Meskipun sebuah program dijamin akan berakhir, ia masih bisa rumit, dan untuk setiap kompiler pengoptimal yang konkret, C, orang mungkin dapat membangun sebuah program yang mengambil C sebagai input dan entah bagaimana menghasilkan program yang lebih buruk seperti semacam kasus sudut.

Juga, Apa implikasi dari membatasi diri kita sendiri untuk menghentikan program?

computability compilers program-optimization Simon 'Reinstate Monica' Shine
sumber

Sulit bahkan untuk menemukan urutan instruksi optimal untuk satu blok kode tanpa aliran kontrol sama sekali. The superoptimization artikel di Wikipedia memberikan intro yang baik (dengan kutipan.)

Berkelana Logika

Artikel Wikipedia menyebutkan bahwa superoptimisasi melihat urutan instruksi tanpa loop. Tidak memiliki loop, saya kira, adalah cara lain untuk mengatakan bahwa itu berakhir. Dari melihat sekilas referensi yang tersedia, tampaknya mungkin tetapi sangat mahal.

Simon 'Reinstate Monica' Shine

Apa arti dari "mengoptimalkan" di sini? Runtime yang lebih kecil? Jika demikian, yang: kasus terburuk, kasus rata-rata, setiap kasus, beberapa kasus, ...?

Raphael

Jawaban:

Saya menganggap Anda tertarik pada optimasi runtime. Seperti yang saya sudah menulis dalam komentar saya, yang tidak cukup menentukan tujuan: apakah optimasi mengurangi runtime pada setiap masukan, setiap masukan, semua kasus terburuk input atau bahkan rata-rata ?

Saya akan menunjukkan bahwa mereka semua tidak mungkin. Buktinya meluas hingga mengoptimalkan panjang program.

Ingatlah bahwa masalah berikut ini tidak dapat dihitung:

Dengan tata bahasa bebas konteks dengan alfabet terminal , putuskan apakah . $G$ $\Sigma$ $\mathcal{L}(G) = \Sigma^*$

Perhatikan lebih lanjut bahwa dengan diberikan tata bahasa bebas konteks , kita dapat melakukan hardcode, katakanlah, algoritma CYK untuk tata bahasa yang satu itu; menunjukkan algoritma ini dengan . Kita mengamati bahwa berakhir untuk semua masukan (dari ). $G$ $\mathrm{CYK}_G$ $\mathrm{CYK}_G$ $\Sigma^*$

Sekarang asumsikan bahwa ada optimiser yang, mengingat algoritma selalu terminating , menghasilkan algoritma yang setara dengan hasil yang optimal sehubungan dengan runtime. Jelas, $\operatorname{Opt}$ $A$

$\qquad \operatorname{Opt}(\mathrm{CYK}_G) = \text{'}\mathtt{return\ true;}\text{'} \iff \mathcal{L}(G) = \Sigma^*$

dan dengan demikian kami telah membangun penentu untuk masalah yang tidak dapat dihitung, bertentangan dengan asumsi.

Raphael
sumber

Terima kasih atas argumen ini. Beberapa pertanyaan klarifikasi: Apa itu

? Saya menganggap

adalah bahasa yang dihasilkan oleh tata bahasa

Σ *

$\Sigma*$

L (G)

$\mathcal{L}(G)$

G

$G$

Simon 'Reinstate Monica' Shine

Σ^{*}

$\Sigma^{\ast}$

M

$M$

P_{M} (i)

$\mathrm{P}_M(i)$

M

$M$

i

$i$

OPT (P_{M})

$\operatorname{OPT}(\mathrm{P}_M)$

' r e t u r n f a l s e;'

$\text{'}\mathtt{return\ false;}\text{'}$

M

$M$