Mengapa deteksi kode mati tidak dapat sepenuhnya dipecahkan oleh kompiler?

192

Kompiler yang telah saya gunakan di C atau Java memiliki pencegahan kode mati (peringatan ketika sebuah baris tidak akan pernah dieksekusi). Profesor saya mengatakan bahwa masalah ini tidak akan pernah bisa diselesaikan sepenuhnya oleh kompiler. Saya bertanya-tanya mengapa itu. Saya tidak terlalu terbiasa dengan pengkodean kompiler yang sebenarnya karena ini adalah kelas berbasis teori. Tapi saya bertanya-tanya apa yang mereka periksa (seperti string input yang mungkin vs input yang dapat diterima, dll), dan mengapa itu tidak cukup.

Pelajar
sumber
91
buat loop, masukkan kode setelah itu, lalu terapkan en.wikipedia.org/wiki/Halting_problem
zapl
48
if (isPrime(1234234234332232323423)){callSomething();}apakah kode ini akan memanggil sesuatu atau tidak? Ada banyak contoh lain, di mana memutuskan apakah suatu fungsi pernah dipanggil jauh lebih mahal daripada hanya memasukkannya ke dalam program.
idclev 463035818
33
public static void main(String[] args) {int counterexample = findCollatzConjectureCounterexample(); System.out.println(counterexample);}<- apakah kode deadln panggilan mati? Bahkan manusia pun tidak bisa menyelesaikannya!
user253751
15
@ tobi303 bukan contoh yang bagus, sangat mudah untuk memfaktorkan bilangan prima ... hanya saja tidak memperhitungkannya secara relatif efisien. Masalah penghentian bukan pada NP, ini tidak dapat diselesaikan.
en_Knight
57
@alephzero dan en_Knight - Anda berdua salah. isPrime adalah contoh yang bagus. Anda membuat asumsi bahwa fungsi sedang memeriksa Nomor Perdana. Mungkin nomor itu adalah nomor seri dan itu pencarian database untuk melihat apakah pengguna adalah anggota Amazon Prime? Alasan itu adalah contoh yang bagus adalah karena satu-satunya cara untuk mengetahui apakah kondisinya konstan atau tidak adalah dengan benar-benar menjalankan fungsi isPrime. Jadi sekarang akan membutuhkan Compiler juga menjadi juru bahasa. Tapi itu masih tidak akan menyelesaikan kasus-kasus di mana data volatile.
Dunk

Jawaban:

275

Masalah kode mati terkait dengan masalah Berhenti .

Alan Turing membuktikan bahwa mustahil untuk menulis algoritma umum yang akan diberikan suatu program dan dapat memutuskan apakah program itu berhenti untuk semua input. Anda mungkin dapat menulis algoritma seperti itu untuk jenis program tertentu, tetapi tidak untuk semua program.

Bagaimana ini berhubungan dengan kode mati?

Masalah Henti dapat direduksi menjadi masalah menemukan kode mati. Artinya, jika Anda menemukan algoritma yang dapat mendeteksi kode mati di program apa pun , maka Anda dapat menggunakan algoritma itu untuk menguji apakah suatu program akan berhenti. Karena itu telah terbukti tidak mungkin, maka menulis algoritma untuk kode mati juga tidak mungkin.

Bagaimana Anda mentransfer algoritme untuk kode mati ke algoritme untuk masalah Berhenti?

Sederhana: Anda menambahkan satu baris kode setelah akhir program yang ingin Anda periksa penghentiannya. Jika detektor kode mati Anda mendeteksi bahwa baris ini sudah mati, maka Anda tahu bahwa programnya tidak berhenti. Jika tidak, maka Anda tahu bahwa program Anda berhenti (sampai ke baris terakhir, dan kemudian ke baris kode yang ditambahkan).


Compiler biasanya memeriksa hal-hal yang dapat dibuktikan pada saat kompilasi untuk mati. Misalnya, blok yang bergantung pada kondisi yang dapat dianggap salah pada waktu kompilasi. Atau pernyataan apa pun setelah return(dalam lingkup yang sama).

Ini adalah kasus-kasus khusus, dan oleh karena itu dimungkinkan untuk menulis sebuah algoritma untuk mereka. Dimungkinkan untuk menulis algoritma untuk kasus yang lebih rumit (seperti algoritma yang memeriksa apakah suatu kondisi secara sintaksis merupakan kontradiksi dan karenanya akan selalu kembali salah), tetapi tetap saja, itu tidak akan mencakup semua kasus yang mungkin.

RealSkeptik
sumber
8
Saya berpendapat bahwa masalah penghentian tidak berlaku di sini, karena setiap platform yang merupakan target kompilasi dari setiap kompiler di dunia nyata memiliki jumlah maksimum data yang dapat diakses, karena itu akan memiliki jumlah maksimum negara yang berarti itu adalah sebenarnya mesin negara yang terbatas, bukan mesin turing. Masalah penghentian tidak dapat dipecahkan untuk FSM sehingga kompiler di dunia nyata dapat melakukan deteksi kode mati.
Vality
50
@Vality 64-bit prosesor dapat mengatasi 2 ^ 64 byte. Bersenang-senang mencari semua 256 ^ (2 ^ 64) negara!
Daniel Wagner
82
@DanielWagner Ini seharusnya tidak menjadi masalah. Mencari 256^(2^64)negara ini O(1), sehingga deteksi kode mati dapat dilakukan dalam waktu polinomial.
aebabis
13
@Leliel, itu sarkasme.
Paul Draper
44
@Vality: Sebagian besar komputer modern memiliki disk, perangkat input, komunikasi jaringan, dll. Setiap analisis lengkap harus mempertimbangkan semua perangkat tersebut - termasuk, secara harfiah, internet dan segala sesuatu yang terhubung dengannya. Ini bukan masalah yang bisa ditelusuri.
Nat
77

Baiklah, mari kita ambil bukti klasik dari ketidakpastian masalah penghentian dan ubah detektor penghenti menjadi detektor kode mati!

Program C #

using System;
using YourVendor.Compiler;

class Program
{
    static void Main(string[] args)
    {
        string quine_text = @"using System;
using YourVendor.Compiler;

class Program
{{
    static void Main(string[] args)
    {{
        string quine_text = @{0}{1}{0};
        quine_text = string.Format(quine_text, (char)34, quine_text);

        if (YourVendor.Compiler.HasDeadCode(quine_text))
        {{
            System.Console.WriteLine({0}Dead code!{0});
        }}
    }}
}}";
        quine_text = string.Format(quine_text, (char)34, quine_text);

        if (YourVendor.Compiler.HasDeadCode(quine_text))
        {
            System.Console.WriteLine("Dead code!");
        }
    }
}

Jika YourVendor.Compiler.HasDeadCode(quine_text)kembali false, maka saluran System.Console.WriteLn("Dead code!");tidak akan pernah dieksekusi, jadi program ini sebenarnya melakukannya memiliki kode mati, dan detektor yang salah.

Tetapi jika itu kembali true, maka garisSystem.Console.WriteLn("Dead code!"); akan dieksekusi, dan karena tidak ada lagi kode dalam program, tidak ada kode mati sama sekali, jadi sekali lagi, detektor itu salah.

Jadi begitulah, detektor kode mati yang hanya mengembalikan "Ada kode mati" atau "Tidak ada kode mati" terkadang harus menghasilkan jawaban yang salah.

Joker_vD
sumber
1
Jika saya memahami argumen Anda dengan benar, maka secara teknis opsi lain adalah bahwa tidak mungkin untuk menulis yang merupakan detektor kode mati, tetapi dimungkinkan untuk menulis detektor kode mati dalam kasus umum. :-)
abligh
1
kenaikan untuk jawaban Godelian.
Jared Smith
@abligh Ugh, itu pilihan kata yang buruk. Saya sebenarnya tidak memasukkan kode sumber detektor kode mati ke dirinya sendiri, tetapi kode sumber program yang menggunakannya. Tentunya, pada titik tertentu mungkin harus melihat kode sendiri, tetapi ini adalah bisnisnya.
Joker_vD
65

Jika masalah penghentian terlalu jelas, pikirkan seperti ini.

Ambil masalah matematika yang diyakini benar untuk semua bilangan bulat positif ini n , tapi belum terbukti benar untuk setiap n . Contoh yang baik adalah dugaan Goldbach , bahwa setiap bilangan bulat positif bahkan lebih besar dari dua dapat diwakili oleh jumlah dua bilangan prima. Kemudian (dengan perpustakaan bigint yang sesuai) jalankan program ini (pseudocode berikut):

 for (BigInt n = 4; ; n+=2) {
     if (!isGoldbachsConjectureTrueFor(n)) {
         print("Conjecture is false for at least one value of n\n");
         exit(0);
     }
 }

Implementasi isGoldbachsConjectureTrueFor()dibiarkan sebagai latihan untuk pembaca tetapi untuk tujuan ini bisa menjadi iterasi sederhana atas semua bilangan prima kurang darin

Sekarang, secara logis di atas harus sama dengan:

 for (; ;) {
 }

(yaitu loop tak terbatas) atau

print("Conjecture is false for at least one value of n\n");

sebagai dugaan Goldbach harus benar atau tidak benar. Jika kompiler selalu dapat menghilangkan kode mati, pasti akan ada kode mati untuk dihilangkan di sini dalam kedua kasus. Namun, dalam melakukannya, paling tidak kompiler Anda harus menyelesaikan masalah sulit yang sewenang-wenang. Kami dapat memberikan masalah yang terbukti sulit yang harus diselesaikan (misalnya masalah NP-complete) untuk menentukan bit kode mana yang harus dihilangkan. Misalnya jika kita mengambil program ini:

 String target = "f3c5ac5a63d50099f3b5147cabbbd81e89211513a92e3dcd2565d8c7d302ba9c";
 for (BigInt n = 0; n < 2**2048; n++) {
     String s = n.toString();
     if (sha256(s).equals(target)) {
         print("Found SHA value\n");
         exit(0);
     }
 }
 print("Not found SHA value\n");

kami tahu bahwa program akan mencetak "Nilai SHA yang ditemukan" atau "Nilai tidak ditemukan SHA" (poin bonus jika Anda dapat memberi tahu saya mana yang benar). Namun, bagi seorang kompiler untuk dapat mengoptimalkan secara wajar yang akan mengambil urutan 2 ^ 2048 iterasi. Ini sebenarnya akan menjadi optimisasi yang hebat karena saya memprediksi program di atas akan (atau mungkin) berjalan sampai kematian panas alam semesta daripada mencetak apa pun tanpa optimasi.

abligh
sumber
4
Sejauh ini ini adalah jawaban terbaik +1
jean
2
Apa yang membuat hal-hal menarik adalah ambiguitas tentang apa yang diperbolehkan atau tidak dibolehkan oleh Standar C untuk mengasumsikan bahwa loop akan berakhir. Ada nilai dalam membiarkan kompiler menunda perhitungan lambat yang hasilnya mungkin atau mungkin tidak digunakan sampai titik di mana hasil mereka benar-benar dibutuhkan; optimasi ini dalam beberapa kasus dapat berguna bahkan jika kompiler tidak dapat membuktikan penghentian perhitungan.
supercat
2
2 ^ 2048 iterasi? Bahkan Deep Thought akan menyerah.
Peter Mortensen
Ini akan mencetak "Ditemukan nilai SHA" dengan probabilitas yang sangat tinggi, bahkan jika target itu adalah string acak 64 digit hex. Kecuali jika sha256mengembalikan array byte dan array byte tidak dapat dibandingkan dengan string dalam bahasa Anda.
user253751
4
Implementation of isGoldbachsConjectureTrueFor() is left as an exercise for the readerIni membuat saya tertawa.
biziclop
34

Saya tidak tahu apakah C ++ atau Java memiliki Evalfungsi tipe, tetapi banyak bahasa memungkinkan Anda melakukan metode panggilan dengan nama . Pertimbangkan contoh VBA (dibuat-buat) berikut ini.

Dim methodName As String

If foo Then
    methodName = "Bar"
Else
    methodName = "Qux"
End If

Application.Run(methodName)

Nama metode yang dipanggil tidak mungkin diketahui sampai runtime. Oleh karena itu, menurut definisi, kompiler tidak dapat mengetahui dengan pasti bahwa metode tertentu tidak pernah dipanggil.

Sebenarnya, mengingat contoh memanggil metode dengan nama, logika percabangan bahkan tidak diperlukan. Cukup mengatakan

Application.Run("Bar")

Lebih dari yang dapat ditentukan oleh kompiler. Ketika kode dikompilasi, semua kompiler tahu adalah bahwa nilai string tertentu diteruskan ke metode itu. Itu tidak memeriksa untuk melihat apakah metode itu ada sampai runtime. Jika metode tidak dipanggil di tempat lain, melalui metode yang lebih normal, upaya untuk menemukan metode mati dapat mengembalikan hasil positif palsu. Masalah yang sama ada dalam bahasa apa pun yang memungkinkan kode dipanggil melalui refleksi.

Bebek karet
sumber
2
Di Jawa (atau C #), ini bisa dilakukan dengan refleksi. C ++ Anda mungkin bisa melakukan beberapa nastiness menggunakan macro untuk melakukannya. Tidak akan cantik, tetapi C ++ jarang.
Darrel Hoffman
6
@ DarrelHoffman - Makro diperluas sebelum kode diberikan ke kompiler, jadi makro jelas bukan bagaimana Anda akan melakukan ini. Pointer ke fungsi adalah bagaimana Anda akan melakukan ini. Saya belum pernah menggunakan C ++ selama bertahun-tahun jadi maafkan saya jika nama ketik saya salah, tapi Anda bisa menyimpan peta string ke pointer fungsi. Kemudian memiliki sesuatu yang menerima string dari input pengguna, mencari string itu di peta, dan kemudian menjalankan fungsi yang diarahkan.
ArtOfWarfare
1
@ ArtOfWarfare kita tidak berbicara tentang bagaimana hal itu bisa dilakukan. Jelas, analisis kode semantik dapat dilakukan untuk menemukan situasi ini, intinya adalah bahwa kompiler tidak . Itu bisa, mungkin, mungkin, tetapi tidak.
RubberDuck
3
@ ArtOfWarfare: Jika Anda ingin nitpick, tentu saja. Saya menganggap preprocessor sebagai bagian dari kompiler, meskipun saya tahu secara teknis tidak. Bagaimanapun, pointer fungsi mungkin melanggar aturan bahwa fungsi tidak langsung direferensikan di mana saja - mereka, hanya sebagai penunjuk alih-alih panggilan langsung, seperti halnya delegasi dalam C #. C ++ secara umum jauh lebih sulit untuk diprediksi oleh kompiler karena ia memiliki banyak cara untuk melakukan sesuatu secara tidak langsung. Bahkan tugas sesederhana "menemukan semua referensi" tidak sepele, karena mereka dapat bersembunyi di typedefs, makro, dll. Tidak mengherankan itu tidak dapat menemukan kode mati dengan mudah.
Darrel Hoffman
1
Anda bahkan tidak perlu pemanggilan metode dinamis untuk menghadapi masalah ini. Setiap metode publik dapat dipanggil oleh fungsi yang belum ditulis yang akan bergantung pada kelas yang sudah dikompilasi di Java atau C # atau bahasa kompilasi lainnya dengan beberapa mekanisme untuk menghubungkan dinamis. Jika kompiler menghilangkan ini sebagai "kode mati," maka kami tidak akan dapat mengemas perpustakaan yang telah dikompilasi untuk distribusi (NuGet, guci, roda Python dengan komponen biner).
jpmc26
12

Kode mati tanpa syarat dapat dideteksi dan dihapus oleh kompiler tingkat lanjut.

Tetapi ada juga kode mati bersyarat. Itu adalah kode yang tidak dapat diketahui pada saat kompilasi dan hanya dapat dideteksi selama runtime. Sebagai contoh, sebuah perangkat lunak dapat dikonfigurasi untuk menyertakan atau mengecualikan fitur tertentu tergantung pada preferensi pengguna, membuat bagian-bagian tertentu dari kode tampaknya mati dalam skenario tertentu. Itu bukan kode mati sungguhan.

Ada alat khusus yang dapat melakukan pengujian, menyelesaikan dependensi, menghapus kode mati bersyarat dan menggabungkan kembali kode yang berguna saat runtime untuk efisiensi. Ini disebut penghapusan kode mati dinamis. Tapi seperti yang Anda lihat itu di luar lingkup kompiler.

dspfnder
sumber
5
"Kode mati tanpa syarat dapat dideteksi dan dihapus oleh kompiler tingkat lanjut." Ini sepertinya tidak mungkin. Kematian kode dapat bergantung pada hasil dari fungsi yang diberikan, dan bahwa fungsi yang diberikan dapat memecahkan masalah sewenang-wenang. Jadi pernyataan Anda menegaskan bahwa kompiler tingkat lanjut dapat memecahkan masalah sewenang-wenang.
Taemyr
6
@ Taemyr Maka itu tidak akan diketahui mati tanpa syarat, sekarang bukan?
JAB
1
@ Taemyr Anda sepertinya salah paham dengan kata "tak bersyarat." Jika kematian kode tergantung pada hasil suatu fungsi, maka itu adalah kode mati bersyarat. "Kondisi" menjadi hasil dari fungsi. Untuk menjadi "tanpa syarat" itu harus tidak bergantung pada hasil apa pun.
Kyeotic
12

Contoh sederhana:

int readValueFromPort(const unsigned int portNum);

int x = readValueFromPort(0x100); // just an example, nothing meaningful
if (x < 2)
{
    std::cout << "Hey! X < 2" << std::endl;
}
else
{
    std::cout << "X is too big!" << std::endl;
}

Sekarang asumsikan bahwa port 0x100 dirancang untuk mengembalikan hanya 0 atau 1. Dalam hal ini kompiler tidak dapat mengetahui bahwa elseblok tidak akan pernah dieksekusi.

Namun dalam contoh dasar ini:

bool boolVal = /*anything boolean*/;

if (boolVal)
{
  // Do A
}
else if (!boolVal)
{
  // Do B
}
else
{
  // Do C
}

Di sini kompiler dapat menghitung elseblok adalah kode mati. Jadi kompilator dapat memperingatkan tentang kode mati hanya jika memiliki cukup data untuk mengetahui kode mati dan juga harus tahu bagaimana menerapkan data itu untuk mengetahui apakah blok yang diberikan adalah kode mati.

EDIT

Kadang-kadang data tidak tersedia pada waktu kompilasi:

// File a.cpp
bool boolMethod();

bool boolVal = boolMethod();

if (boolVal)
{
  // Do A
}
else
{
  // Do B
}

//............
// File b.cpp
bool boolMethod()
{
    return true;
}

Saat mengkompilasi a.cpp, kompiler tidak dapat mengetahui bahwa boolMethodselalu kembali true.

Alex Lop.
sumber
1
Meskipun benar-benar benar bahwa kompiler tidak tahu, saya pikir dalam semangat pertanyaan juga bertanya apakah penghubung bisa tahu.
Casey Kuball
1
@Darthfett Ini bukan tanggung jawab penghubung . Linker tidak menganalisis konten kode yang dikompilasi. Linker (secara umum) hanya menautkan metode dan data global, itu tidak peduli dengan kontennya. Namun beberapa kompiler memiliki opsi untuk menggabungkan file sumber (seperti ICC) dan kemudian melakukan optimasi. Dalam kasus seperti itu kasus di bawah EDIT dicakup tetapi opsi ini akan mempengaruhi waktu kompilasi terutama ketika proyek besar.
Alex Lop.
Jawaban ini tampaknya menyesatkan bagi saya; Anda memberikan dua contoh di mana itu tidak mungkin karena tidak semua informasi tersedia, tetapi tidakkah Anda seharusnya mengatakan bahwa itu tidak mungkin walaupun informasi itu ada di sana?
Anton Golov
@AntonGolovIt os tidak selalu benar. Dalam banyak kasus ketika informasi ada di sana, kompiler dapat mendeteksi kode mati dan mengoptimalkannya.
Alex Lop.
@ abforce hanya satu blok kode. Bisa jadi hal lain. :)
Alex Lop.
4

Kompiler akan selalu kekurangan beberapa informasi konteks. Misalnya Anda mungkin tahu, bahwa nilai ganda tidak pernah melebihi 2, karena itu adalah fitur fungsi matematika, yang Anda gunakan dari perpustakaan. Kompiler bahkan tidak melihat kode di perpustakaan, dan ia tidak pernah dapat mengetahui semua fitur dari semua fungsi matematika, dan mendeteksi semua cara yang rumit dan rumit untuk mengimplementasikannya.

cdonat
sumber
4

Kompiler tidak selalu melihat keseluruhan program. Saya bisa memiliki program yang memanggil perpustakaan bersama, yang memanggil kembali ke fungsi dalam program saya yang tidak dipanggil secara langsung.

Jadi fungsi yang mati sehubungan dengan perpustakaan yang dikompilasi dapat menjadi hidup jika perpustakaan itu diubah saat runtime.

Steve Sanbeg
sumber
3

Jika kompiler dapat menghilangkan semua kode mati secara akurat, itu akan disebut interpreter .

Pertimbangkan skenario sederhana ini:

if (my_func()) {
  am_i_dead();
}

my_func() dapat berisi kode arbitrer dan agar kompiler dapat menentukan apakah mengembalikan benar atau salah, ia harus menjalankan kode atau melakukan sesuatu yang secara fungsional setara dengan menjalankan kode.

Gagasan kompiler adalah bahwa ia hanya melakukan analisis sebagian kode, sehingga menyederhanakan pekerjaan dari lingkungan berjalan yang terpisah. Jika Anda melakukan analisis lengkap, itu bukan kompiler lagi.


Jika Anda menganggap kompiler sebagai fungsi c(), di mana c(source)=compiled code, dan lingkungan yang berjalan sebagai r(), di mana r(compiled code)=program output, maka untuk menentukan output untuk kode sumber apa pun Anda harus menghitung nilai r(c(source code)). Jika penghitungan c()membutuhkan pengetahuan tentang nilai r(c())untuk input apa pun, tidak perlu untuk terpisah r()dan c(): Anda hanya dapat memperoleh fungsi i()dari c()itu i(source)=program output.

biziclop
sumber
2

Yang lain mengomentari masalah penghentian dan sebagainya. Ini biasanya berlaku untuk bagian-bagian fungsi. Namun bisa sulit / tidak mungkin untuk mengetahui apakah bahkan seluruh tipe (kelas / dll) digunakan atau tidak.

Di .NET / Java / JavaScript dan lingkungan yang didorong oleh runtime lainnya, tidak ada yang menghentikan tipe yang dimuat melalui refleksi. Ini populer dengan kerangka kerja injeksi ketergantungan, dan bahkan lebih sulit untuk dipertimbangkan dalam menghadapi deserialisasi atau pemuatan modul dinamis.

Kompiler tidak dapat mengetahui apakah tipe seperti itu akan dimuat. Nama mereka dapat berasal dari file konfigurasi eksternal saat runtime.

Anda mungkin ingin mencari di sekitar pohon goyang yang merupakan istilah umum untuk alat yang berusaha untuk menghapus subgraph kode yang tidak digunakan dengan aman.

Drew Noakes
sumber
Saya tidak tahu tentang Java, dan javascript, tetapi. NET sebenarnya memiliki plugin resharper untuk jenis deteksi DI (disebut Agen Mulder). Tentu saja, itu tidak akan dapat mendeteksi file-file konfigurasi, tetapi ia mampu mendeteksi kode confit (yang jauh lebih populer).
Ikatan
2

Ambil fungsi

void DoSomeAction(int actnumber) 
{
    switch(actnumber) 
    {
        case 1: Action1(); break;
        case 2: Action2(); break;
        case 3: Action3(); break;
    }
}

Bisakah Anda membuktikan bahwa actnumbertidak akan pernah 2demikian yang Action2()tidak pernah disebut ...?

CiaPan
sumber
7
Jika Anda dapat menganalisis fungsi penelepon, maka Anda mungkin bisa, ya.
Abligh
2
@abligh Tetapi kompiler biasanya tidak dapat menganalisis semua kode panggilan. Pokoknya bahkan jika itu bisa, analisis penuh mungkin memerlukan hanya simulasi dari semua aliran kontrol yang mungkin, yang hampir selalu hanya mustahil karena sumber daya dan waktu yang dibutuhkan. Jadi bahkan jika secara teoritis ada bukti bahwa ' Action2()tidak akan pernah disebut' tidak mungkin untuk membuktikan klaim dalam praktek - tidak dapat sepenuhnya diselesaikan oleh kompiler . Perbedaannya seperti 'ada angka X' vs. 'kita bisa menulis angka X dalam desimal'. Untuk beberapa X, yang terakhir tidak akan pernah terjadi meskipun yang pertama benar.
CiaPan
Ini jawaban yang buruk. jawaban lain membuktikan bahwa tidak mungkin untuk mengetahui apakah actnumber==2. Jawaban ini hanya mengklaim itu sulit bahkan tanpa menyatakan kompleksitas.
MSalters
1

Saya tidak setuju tentang masalah penghentian. Saya tidak akan menyebut kode tersebut mati meskipun dalam kenyataannya tidak akan pernah tercapai.

Sebagai gantinya, mari pertimbangkan:

for (int N = 3;;N++)
  for (int A = 2; A < int.MaxValue; A++)
    for (int B = 2; B < int.MaxValue; B++)
    {
      int Square = Math.Pow(A, N) + Math.Pow(B, N);
      float Test = Math.Sqrt(Square);
      if (Test == Math.Trunc(Test))
        FermatWasWrong();
    }

private void FermatWasWrong()
{
  Press.Announce("Fermat was wrong!");
  Nobel.Claim();
}

(Abaikan kesalahan jenis dan melimpah) Kode mati?

Loren Pechtel
sumber
2
Teorema terakhir Fermat telah terbukti pada tahun 1994. Jadi implementasi metode Anda yang benar tidak akan pernah menjalankan FermatWasong. Saya menduga implementasi Anda akan menjalankan FermatWasWrong, karena Anda dapat mencapai batas presisi float.
Taemyr
@Taemyr Aha! Program ini tidak menguji Teorema Terakhir Fermat dengan benar; contoh tandingan untuk pengujian yang dilakukan adalah N = 3, A = 65536, B = 65536 (yang menghasilkan Uji = 0)
user253751
@immibis Ya, saya melewatkan itu akan meluap int sebelum presisi pada pelampung menjadi masalah.
Taemyr
@immibis Catat bagian bawah postingan saya: Abaikan jenis dan kesalahan overflow. Saya hanya mengambil apa yang saya pikir merupakan masalah yang belum terpecahkan sebagai dasar keputusan - saya tahu kodenya tidak sempurna. Itu masalah yang tidak bisa dipaksakan dengan kekerasan.
Loren Pechtel
-1

Lihatlah contoh ini:

public boolean isEven(int i){

    if(i % 2 == 0)
        return true;
    if(i % 2 == 1)
        return false;
    return false;
}

Kompiler tidak dapat mengetahui bahwa int hanya bisa genap atau ganjil. Oleh karena itu kompiler harus dapat memahami semantik kode Anda. Bagaimana seharusnya ini diterapkan? Kompiler tidak dapat memastikan bahwa pengembalian terendah tidak akan pernah dieksekusi. Karenanya kompiler tidak dapat mendeteksi kode mati.

pengguna
sumber
1
Umm, benarkah? Jika saya menulis itu di C # + ReSharper saya mendapatkan beberapa petunjuk. Mengikuti mereka akhirnya memberi saya kode return i%2==0;.
Thomas Weller
10
Teladan Anda terlalu sederhana untuk meyakinkan. Kasus spesifik i % 2 == 0dan i % 2 != 0bahkan tidak memerlukan alasan tentang nilai integer modulo konstanta (yang masih mudah dilakukan), itu hanya memerlukan eliminasi subekspresi umum dan prinsip umum (kanonikisasi, bahkan) yang if (cond) foo; if (!cond) bar;dapat disederhanakan if (cond) foo; else bar;. Tentu saja "memahami semantik" adalah masalah yang sangat sulit, tetapi postingan ini tidak menunjukkan bahwa itu benar, juga tidak menunjukkan bahwa menyelesaikan masalah sulit ini diperlukan untuk deteksi kode mati.
5
Dalam contoh Anda, kompiler pengoptimalisasi akan melihat subekspresi umum i % 2dan menariknya keluar menjadi variabel sementara. Ini kemudian akan mengakui bahwa kedua ifpernyataan itu saling eksklusif dan dapat ditulis sebagai if(a==0)...else..., dan kemudian melihat bahwa semua jalur eksekusi yang mungkin melalui dua returnpernyataan pertama dan oleh karena itu returnpernyataan ketiga adalah kode mati. ( Kompiler pengoptimalan yang baik bahkan lebih agresif: GCC mengubah kode pengujian saya menjadi sepasang operasi manipulasi bit).
Markus
1
Contoh ini baik untuk saya. Ini mewakili kasus ketika kompiler tidak tahu tentang beberapa keadaan faktual. Hal yang sama berlaku untuk if (availableMemory()<0) then {dead code}.
Little Santi
1
@LittleSanti: Sebenarnya, GCC akan mendeteksi bahwa semua yang Anda tulis ada kode mati! Bukan hanya {dead code}bagian. GCC menemukan ini dengan membuktikan ada limpahan bilangan bulat bertanda yang tidak dapat dihindari. Karenanya, semua kode pada arc tersebut dalam grafik eksekusi adalah kode mati. GCC bahkan dapat menghapus cabang bersyarat yang mengarah ke busur itu.
MSalters