Bukti bahwa kode mati tidak dapat dideteksi oleh kompiler

32

Saya berencana untuk mengajar kursus musim dingin tentang berbagai topik, salah satunya akan menjadi penyusun. Sekarang, saya menemukan masalah ini sambil memikirkan tugas untuk diberikan sepanjang kuartal, tapi itu membuat saya bingung sehingga saya dapat menggunakannya sebagai contoh.

public class DeadCode {
  public static void main(String[] args) {
     return;
     System.out.println("This line won't print.");
  }
}

Dalam program di atas, jelas bahwa pernyataan cetak tidak akan pernah dijalankan karena return. Kompiler terkadang memberikan peringatan atau kesalahan tentang kode mati. Misalnya, kode di atas tidak akan dikompilasi di Jawa. Kompiler javac, bagaimanapun, tidak akan mendeteksi semua contoh kode mati di setiap program. Bagaimana saya membuktikan bahwa tidak ada kompiler yang dapat melakukannya?

thomas
sumber
29
Apa latar belakang Anda dan apa konteks yang akan Anda ajarkan? Terus terang, saya agak khawatir bahwa Anda harus bertanya ini, mengingat Anda akan mengajar. Tapi panggilan yang bagus bertanya di sini!
Raphael
9
@ MichaelKjörling Deteksi kode mati tidak mungkin bahkan tanpa pertimbangan itu.
David Richerby
2
BigInteger i = 0; while(isCollatzConjectureTrueFor(i)) i++; printf("Hello world\n");
user253751
2
@immibis Pertanyaan meminta bukti bahwa deteksi kode mati tidak mungkin . Anda telah memberikan contoh di mana deteksi kode mati yang benar membutuhkan pemecahan masalah terbuka dalam matematika. Itu tidak membuktikan bahwa deteksi kode mati tidak mungkin .
David Richerby

Jawaban:

57

Itu semua berasal dari ketidakpastian masalah penghentian. Misalkan kita memiliki fungsi kode mati "sempurna", beberapa Mesin Turing M, dan beberapa string input x, dan prosedur yang terlihat seperti ini:

Run M on input x;
print "Finished running input";

Jika M berjalan selamanya, maka kami menghapus pernyataan cetak, karena kami tidak akan pernah mencapainya. Jika M tidak berjalan selamanya, maka kita perlu menjaga pernyataan cetak. Jadi, jika kita memiliki penghapus kode mati, itu juga memungkinkan kita menyelesaikan Masalah Pemutusan, jadi kita tahu tidak akan ada penghapus kode mati semacam itu.

Cara kita menyiasatinya adalah dengan "perkiraan konservatif." Jadi, dalam contoh Mesin Turing saya di atas, kita dapat mengasumsikan bahwa menjalankan M pada x mungkin selesai, jadi kami memainkannya dengan aman dan tidak menghapus pernyataan cetak. Dalam contoh Anda, kami tahu bahwa apa pun fungsi yang dilakukan atau tidak dihentikan, tidak mungkin kami akan mencapai pernyataan cetak itu.

Biasanya, ini dilakukan dengan membangun "grafik aliran kendali". Kami membuat asumsi yang disederhanakan, seperti "akhir putaran sementara terhubung ke awal dan pernyataan setelah", bahkan jika itu berjalan selamanya atau hanya berjalan sekali dan tidak mengunjungi keduanya. Demikian pula, kami mengasumsikan bahwa pernyataan if dapat mencapai semua cabangnya, bahkan jika pada kenyataannya beberapa tidak pernah digunakan. Jenis penyederhanaan ini memungkinkan kami untuk menghapus "kode mati jelas" seperti contoh yang Anda berikan, namun tetap dapat diperhitungkan.

Untuk mengklarifikasi beberapa kebingungan dari komentar:

  1. Nitpick: untuk fixed M, ini selalu decidable. M harus menjadi input

    Seperti yang dikatakan Raphael, dalam contoh saya, kami menganggap Mesin Turing sebagai input. Idenya adalah bahwa, jika kita memiliki algoritma DCE yang sempurna, kita akan dapat membuat cuplikan kode yang saya berikan untuk Mesin Turing apa pun , dan memiliki DCE akan menyelesaikan masalah penghentian.

  2. tidak meyakinkan. kembali sebagai pernyataan tumpul dalam eksekusi tanpa cabang langsung tidak sulit untuk diputuskan. (dan kompiler saya memberitahu saya ia mampu mencari tahu ini)

    Untuk masalah njzk2 memunculkan: Anda benar sekali, dalam hal ini Anda dapat menentukan bahwa tidak ada cara pernyataan setelah pengembalian dapat dicapai. Ini karena cukup sederhana sehingga kita dapat menggambarkan ketidakterjangkauannya dengan menggunakan batasan grafik aliran-kontrol (yaitu tidak ada tepi keluar dari pernyataan kembali). Tetapi tidak ada eliminator kode mati yang sempurna, yang menghilangkan semua kode yang tidak digunakan.

  3. Saya tidak mengambil bukti yang bergantung pada input untuk bukti. Jika ada semacam input pengguna yang dapat memungkinkan kode menjadi terbatas, benar bagi kompilator untuk menganggap bahwa cabang berikut ini tidak mati. Saya tidak bisa melihat untuk apa semua upvotes ini, itu jelas (mis. Stdin tak berujung) dan salah.

    Untuk TomášZato: ini bukan bukti yang bergantung pada input. Sebaliknya, tafsirkan sebagai "forall". Ini berfungsi sebagai berikut: anggap kita memiliki algoritma DCE yang sempurna. Jika Anda memberi saya Turing Machine M acak dan input x, saya dapat menggunakan algoritma DCE untuk menentukan apakah M berhenti, dengan membuat cuplikan kode di atas dan melihat apakah pernyataan cetak dihapus. Teknik ini, meninggalkan parameter sewenang-wenang untuk membuktikan pernyataan forall, adalah umum dalam matematika dan logika.

    Saya tidak sepenuhnya mengerti poin TomášZato tentang kode menjadi terbatas. Tentunya kode ini terbatas, tetapi algoritma DCE yang sempurna harus berlaku untuk semua kode, yang merupakan kumpulan infinte. Demikian juga, sementara kode itu sendiri terbatas, set input potensial tidak lengkap, seperti potensi waktu berjalan dari kode.

    Mengenai mempertimbangkan cabang terakhir yang tidak mati: aman dalam hal "perkiraan konservatif" yang saya bicarakan, tetapi tidak cukup untuk mendeteksi semua contoh kode mati seperti yang diminta OP.

Pertimbangkan kode seperti ini:

while (true)
  print "Hello"
print "goodbye"

Jelas kami dapat menghapus print "goodbye"tanpa mengubah perilaku program. Jadi, itu adalah kode mati. Tetapi jika ada pemanggilan fungsi yang berbeda alih-alih (true)dalam whilekondisi, maka kita tidak tahu apakah kita dapat menghapusnya atau tidak, yang mengarah pada ketidakpastian.

Perhatikan bahwa saya tidak membuat ini sendirian. Ini adalah hasil yang terkenal dalam teori kompiler. Ini dibahas dalam The Tiger Book . (Anda mungkin dapat melihat di mana mereka berbicara di dalam buku Google .

Ya ampun
sumber
1
@ njzk2: Kami berusaha menunjukkan bahwa tidak mungkin untuk membangun penghilang kode mati yang menghilangkan semua kode mati, bukan bahwa tidak mungkin untuk membangun kode penghapus mati yang menghilangkan beberapa kode mati. Contoh print-after-return dapat dihilangkan dengan mudah menggunakan teknik grafik control-flow, tetapi tidak semua kode mati dapat dihilangkan dengan cara ini.
user2357112 mendukung Monica
4
Jawaban ini merujuk komentar. Ketika saya membaca jawabannya, saya perlu melompat ke bawah ke komentar, lalu kembali ke jawabannya. Ini membingungkan (dua kali lipat jadi ketika Anda menganggap bahwa komentar rapuh dan mungkin hilang). Jawaban yang lengkap akan jauh lebih mudah dibaca.
TRiG
1
nn
3
MxMx
1
jmite, tolong masukkan komentar yang valid ke dalam jawaban sehingga jawabannya berdiri sendiri. Lalu tandai semua komentar yang sudah usang sehingga kami dapat membersihkan. Terima kasih!
Raphael
14

Ini adalah twist pada jawaban jmite yang menghindari potensi kebingungan tentang non-terminasi. Saya akan memberikan program yang selalu berhenti sendiri, mungkin memiliki kode mati tetapi kita tidak dapat (selalu) secara algoritmik memutuskan apakah ada.

Pertimbangkan kelas input berikut untuk pengidentifikasi kode mati:

simulateMx(n) {
  simulate TM M on input x for n steps
  if M did halt
    return 0
  else
    return 1
}

Sejak Mdan xdiperbaiki, simulateMsmemiliki kode mati dengan return 0jika dan hanya jika Mtidak berhenti x.

MxMM

Karenanya, pemeriksaan kode mati tidak dapat dihitung.

Jika Anda tidak terbiasa dengan reduksi sebagai teknik bukti dalam konteks ini, saya merekomendasikan bahan referensi kami .

Raphael
sumber
5

Cara sederhana untuk mendemonstrasikan properti semacam ini tanpa terperangkap dalam rincian adalah dengan menggunakan lemma berikut:

Lemma: Untuk setiap kompiler C untuk bahasa Turing-complete, ada fungsi undecidable_but_true()yang tidak mengambil argumen dan mengembalikan boolean true, sehingga C tidak dapat memprediksi apakah undecidable_but_true()mengembalikan benar atau salah.

Perhatikan bahwa fungsinya tergantung pada kompiler. Diberikan fungsi undecidable_but_true1(), kompiler selalu dapat ditambah dengan pengetahuan apakah fungsi ini mengembalikan benar atau salah; tetapi selalu ada beberapa fungsi lain undecidable_but_true2()yang tidak akan dibahas.

Bukti: menurut teorema Rice , properti "fungsi ini mengembalikan nilai sebenarnya" tidak dapat diputuskan. Karenanya setiap algoritma analisis statis tidak dapat memutuskan properti ini untuk semua fungsi yang mungkin.

Konsekuensi: Diberikan kompiler C, program berikut berisi kode mati yang tidak dapat dideteksi:

if (!undecidable_but_true()) {
    do_stuff();
}

Catatan tentang Java: mandat bahasa Jawa bahwa kompiler menolak program tertentu yang berisi kode yang tidak dapat dijangkau, sementara mandat yang masuk akal bahwa kode disediakan di semua titik yang dapat dijangkau (misalnya aliran kontrol dalam fungsi non-void harus diakhiri dengan returnpernyataan). Bahasa tersebut menentukan dengan tepat bagaimana analisis kode yang tidak terjangkau dilakukan; jika tidak maka tidak mungkin untuk menulis program portabel. Diberikan program formulir

some_method () {
    <code whose continuation is unreachable>
    // is throw InternalError() needed here?
}

perlu untuk menentukan dalam kasus apa kode yang tidak dapat dijangkau harus diikuti oleh beberapa kode lain dan dalam kasus apa itu tidak boleh diikuti oleh kode apa pun. Contoh program Java yang berisi kode yang tidak dapat dijangkau, tetapi tidak dengan cara yang diizinkan oleh penyusun Java, muncul di Java 101:

String day_of_week(int n) {
    switch (n % 7) {
    case 0: return "Sunday";
    case 1: case -6: return "Monday";
    …
    case 6: case -1: return "Saturday";
    }
    // return or throw is required here, even though this point is unreachable
}
Gilles 'SANGAT berhenti menjadi jahat'
sumber
Perhatikan bahwa beberapa kompiler untuk beberapa bahasa mungkin dapat mendeteksi bahwa akhir day_of_weektidak terjangkau.
user253751
@immibis Ya, misalnya siswa CS101 dapat melakukannya dalam pengalaman saya (meskipun siswa CS101 memang bukan penganalisa statis yang baik, mereka biasanya melupakan kasus negatif). Itu bagian dari poin saya: ini adalah contoh program dengan kode yang tidak dapat dijangkau yang tidak akan terdeteksi oleh kompiler Java (setidaknya, mungkin memperingatkan, tetapi mungkin tidak menolak).
Gilles 'SO- stop being evil'
1
Saya khawatir ungkapan Lemma menyesatkan, dengan sedikit kesalahan. Ketidakpastian hanya masuk akal jika Anda menggunakan istilah instance (tak terbatas). (Kompiler memang menghasilkan jawaban untuk setiap fungsi, dan kami tahu bahwa itu tidak selalu benar, tetapi mengatakan bahwa ada satu contoh yang tidak dapat dipastikan tidak aktif.) Paragraf Anda antara Lemma dan Bukti (yang tidak cocok dengan Lemma sebagaimana dinyatakan) mencoba untuk memperbaikinya, tetapi saya pikir akan lebih baik untuk merumuskan lemma yang benar-benar benar.
Raphael
@Raphael Uh? Tidak, kompiler tidak perlu menghasilkan jawaban untuk pertanyaan “apakah fungsi ini konstan?”. Tidak perlu membedakan "Saya tidak tahu" dari "tidak" untuk menghasilkan kode kerja, tetapi itu tidak relevan di sini karena kami hanya tertarik pada bagian analisis statis dari kompiler, bukan di bagian terjemahan kode. Saya tidak mengerti apa yang Anda temukan menyesatkan atau tidak benar tentang pernyataan lemma - kecuali maksud Anda adalah saya harus menulis "penganalisa statis" bukan "kompiler"?
Gilles 'SANGAT berhenti menjadi jahat'
Pernyataan itu terdengar seperti "ketidakpastian" berarti ada contoh yang tidak dapat diselesaikan, yang salah. (Saya tahu Anda tidak bermaksud mengatakan itu, tetapi begitulah ia dapat membaca kepada yang tidak waspada / novis, imho.)
Raphael
3

Jawaban jmite berlaku untuk apakah program akan pernah keluar dari perhitungan - hanya karena tidak terbatas saya tidak akan memanggil kode setelah mati.

Namun, ada pendekatan lain: Masalah yang ada jawabannya tetapi tidak diketahui:

public void Demo()
{
  if (Chess.Evaluate(new Chessboard(), int.MaxValue) != 0)
    MessageBox.Show("Chess is unfair!");
  else
    MessageBox.Show("Chess is fair!");
}

public class chess
{
  public Int64 Evaluate(Chessboard Board, int SearchDepth)
  {
  ...
  }
}

Rutin ini tanpa diragukan lagi memang mengandung kode mati - fungsi akan mengembalikan jawaban yang mengeksekusi satu jalur tetapi tidak yang lain. Semoga berhasil menemukannya! Ingatan saya, tidak ada komputer teoretis yang dapat memecahkan masalah ini dalam umur semesta.

Lebih detail:

The Evaluate()Toedjoe menghitung fungsi sisi mana memenangkan permainan catur jika kedua belah pihak bermain sempurna (dengan kedalaman pencarian maksimum).

Evaluator catur biasanya melihat ke depan pada setiap gerakan yang mungkin dilakukan dengan kedalaman tertentu dan kemudian mencoba untuk menilai papan pada titik itu (kadang-kadang memperluas cabang tertentu lebih jauh dengan melihat setengah melalui pertukaran atau sejenisnya dapat menghasilkan persepsi yang sangat miring.) Karena kedalaman maksimum sebenarnya adalah 17695 setengah-bergerak pencarian sudah lengkap, itu akan melintasi setiap permainan catur yang mungkin. Karena semua permainan berakhir, tidak ada masalah mencoba memutuskan seberapa baik posisi masing-masing papan (dan dengan demikian tidak ada alasan untuk melihat logika evaluasi papan - itu tidak akan pernah disebut), hasilnya adalah menang, kalah atau Gambaran. Jika hasilnya seri, permainan itu adil, jika hasilnya bukan seri, itu adalah permainan yang tidak adil. Untuk sedikit mengembangkannya kita dapatkan:

public Int64 Evaluate(Chessboard Board, int SearchDepth)
{
  foreach (ChessMove Move in Board.GetPossibleMoves())
    {
      Chessboard NewBoard = Board.MakeMove(Move);
      if (NewBoard.Checkmate()) return int.MaxValue;
      if (NewBoard.Draw()) return 0;
      if (SearchDepth == 0) return NewBoard.Score();
      return -Evaluate(NewBoard, SearchDepth - 1);
    }
}

Perhatikan, juga, bahwa hampir tidak mungkin bagi kompiler untuk menyadari bahwa Chessboard.Score () adalah kode mati. Pengetahuan tentang aturan catur memungkinkan kita manusia untuk mengetahui hal ini, tetapi untuk mengetahui hal ini, Anda harus tahu bahwa MakeMove tidak pernah dapat meningkatkan jumlah keping dan bahwa Papan Catur. Gambar () akan kembali benar jika jumlah keping tetap statis terlalu lama .

Perhatikan bahwa kedalaman pencarian berada dalam setengah gerakan, bukan keseluruhan gerakan. Ini normal untuk rutin AI semacam ini karena ini merupakan rutin O (x ^ n) - menambahkan satu lapis pencarian memiliki efek besar pada berapa lama waktu yang dibutuhkan untuk menjalankan.

Loren Pechtel
sumber
8
Anda berasumsi bahwa algoritma pengecekan harus melakukan perhitungan. Kesalahan umum! Tidak, Anda tidak bisa menganggap apa-apa tentang bagaimana checker akan bekerja, jika tidak, anda tidak bisa membantah keberadaannya.
Raphael
6
Pertanyaan itu meminta bukti bahwa tidak mungkin mendeteksi kode mati. Posting Anda berisi contoh kasus di mana Anda mencurigai akan sulit untuk mendeteksi kode mati. Itu bukan jawaban untuk pertanyaan yang ada.
David Richerby
2
@ LorenPechtel Saya tidak tahu, tapi itu bukan bukti. Lihat juga di sini ; contoh bersih dari kesalahpahaman Anda.
Raphael
3
Jika itu membantu, pertimbangkan bahwa tidak ada yang secara teoritis menghentikan seseorang dari menjalankan kompiler mereka selama lebih dari umur alam semesta; satu-satunya batasan adalah kepraktisan. Masalah yang dapat diputuskan adalah masalah yang dapat diputuskan, bahkan jika itu dalam kelas kompleksitas NONELEMENTARY.
Nama samaran
4
Dengan kata lain, jawaban ini paling tidak merupakan heuristik yang dimaksudkan untuk menunjukkan mengapa mungkin tidak mudah untuk membangun kompiler yang mendeteksi semua kode mati - tetapi itu bukan bukti ketidakmungkinan. Contoh semacam ini mungkin berguna sebagai cara untuk membangun intuisi bagi siswa, tetapi itu bukan bukti. Dengan menampilkan dirinya sebagai bukti, itu merugikan. Jawabannya harus diedit untuk menyatakan bahwa itu adalah contoh membangun intuisi tetapi bukan bukti ketidakmungkinan.
DW
-3

Saya pikir dalam kursus komputasi, gagasan kode mati menarik dalam konteks memahami perbedaan antara waktu kompilasi dan waktu berjalan!

Kompiler dapat menentukan kapan Anda memiliki kode yang tidak pernah dalam skenario kompilasi-waktu yang dapat dilalui, tetapi tidak dapat melakukannya untuk runtime. loop sementara sederhana dengan input pengguna untuk tes loop-break menunjukkan hal itu.

Jika kompiler benar-benar dapat menentukan kode mati runtime (yaitu discern Turing complete) maka ada argumen bahwa kode tidak perlu dijalankan, karena pekerjaan sudah selesai!

Jika tidak ada yang lain, keberadaan kode yang lolos dari kompilasi kode waktu mati menggambarkan perlunya memeriksa batas pragmatis pada input dan kebersihan kode umum (di dunia nyata dari proyek nyata.)

dwoz
sumber
1
Pertanyaan itu meminta bukti bahwa tidak mungkin mendeteksi kode mati. Anda belum menjawab pertanyaan itu.
David Richerby
Juga, pernyataan Anda bahwa "Seorang kompiler dapat menentukan kapan Anda mendapatkan kode yang tidak dapat dilacak dalam skenario waktu kompilasi" adalah tidak benar dan secara langsung bertentangan dengan pertanyaan yang diminta Anda buktikan.
David Richerby
@ David Richerby, saya pikir Anda mungkin salah membaca saya. Saya tidak menyarankan bahwa pemeriksaan waktu kompilasi dapat menemukan SEMUA kode mati, jelas tidak. Saya menyarankan bahwa ada himpunan bagian dari semua kode mati yang dapat dilihat pada waktu kompilasi. Jika saya menulis: if (true == false) {print ("something");}, pernyataan cetak itu akan terlihat pada waktu kompilasi menjadi kode mati. Apakah Anda tidak setuju bahwa ini adalah contoh tandingan terhadap pernyataan Anda?
dwoz
Tentu, Anda dapat menentukan beberapa kode mati. Tetapi jika Anda akan mengatakan "menentukan kapan [Anda memiliki kode mati]" tanpa kualifikasi maka itu, bagi saya, berarti menemukan semua kode mati, bukan hanya sebagian saja.
David Richerby