Mengapa tidak mungkin untuk membangun sebuah compiler yang dapat menentukan apakah sebuah C++ fungsi akan mengubah nilai dari variabel tertentu?

Mengapa tidak mungkin untuk membangun sebuah compiler?

Untuk alasan yang sama bahwa anda dapat't menulis sebuah program yang akan menentukan apakah suatu program akan dihentikan. Hal ini dikenal sebagai menghentikan masalah, dan itu's salah satu dari hal-hal yang's tidak dapat dihitung.

Untuk menjadi jelas, anda dapat menulis sebuah compiler yang dapat menentukan bahwa fungsi tidak mengubah variabel dalam beberapa kasus, tapi anda dapat't menulis satu yang andal memberitahu anda bahwa fungsi akan atau tidak't perubahan variabel (atau berhenti) untuk setiap fungsi.

Berikut ini's contoh mudah:

void foo() {
    if (bar() == 0) this->a = 1;
}

Bagaimana bisa sebuah compiler menentukan, hanya dari melihat kode itu, apakah foo akan pernah berubah a? Apakah itu doesn't tergantung pada kondisi eksternal untuk fungsi, yaitu pelaksanaan bar. Ada's lebih dari itu untuk bukti bahwa menghentikan masalah isn't dihitung, tapi itu's sudah baik menjelaskan terkait artikel Wikipedia (dan dalam setiap perhitungan teori buku teks), jadi saya'll tidak mencoba untuk menjelaskan dengan benar di sini.

Bayangkan seperti compiler ada. Let's juga menganggap bahwa untuk kenyamanan anda, hotel ini menyediakan perpustakaan fungsi yang mengembalikan 1 jika melewati fungsi memodifikasi suatu variabel dan 0 bila fungsi doesn't. Lalu apa yang harus ini program cetak?

int variable = 0;

void f() {
    if (modifies_variable(f, variable)) {
        /* do nothing */
    } else {
        /* modify variable */
        variable = 1;
    }
}

int main(int argc, char **argv) {
    if (modifies_variable(f, variable)) {
        printf("Modifies variable\n");
    } else {
        printf("Does not modify variable\n");
    }

    return 0;
}

Don't membingungkan "yang akan atau tidak akan mengubah variabel diberikan masukan ini" untuk "telah eksekusi jalan yang memodifikasi variabel."

Mantan disebut buram predikat tekad, dan sepele mustahil untuk memutuskan - selain dari pengurangan dari menghentikan masalah, anda hanya bisa menunjukkan input yang mungkin datang dari sumber yang tidak diketahui (misalnya. pengguna). Ini benar semua bahasa, bukan hanya C++.

Pernyataan yang terakhir, bagaimanapun, bisa dapat ditentukan dengan melihat parse tree, yang merupakan sesuatu yang semua mengoptimalkan penyusun lakukan. Alasan mereka adalah bahwa pure fungsi (dan referentially transparan fungsi, untuk beberapa definisi referentially transparan) memiliki segala macam bagus optimasi yang dapat diterapkan, seperti yang dengan mudah dapat inline atau memiliki mereka nilai yang ditentukan pada saat kompilasi, tetapi untuk mengetahui apakah fungsi murni, kita perlu tahu apakah itu dapat ** pernah memodifikasi variabel.

Jadi, apa yang tampaknya menjadi sebuah pernyataan mengejutkan tentang C++ adalah benar-benar sepele pernyataan tentang semua bahasa.

Saya pikir kata kunci dalam "apakah atau tidak C++ fungsi akan mengubah nilai dari variabel tertentu" adalah "akan". Hal ini tentu saja mungkin untuk membangun sebuah compiler yang memeriksa apakah atau tidak C++ fungsi diperbolehkan untuk mengubah nilai dari suatu variabel tertentu, anda tidak dapat mengatakan dengan pasti bahwa perubahan yang akan terjadi:

void maybe(int& val) {
    cout << "Should I change value? [Y/N] >";
    string reply;
    cin >> reply;
    if (reply == "Y") {
        val = 42;
    }
}

Saya don't pikir itu's yang diperlukan untuk memohon menghentikan masalah untuk menjelaskan bahwa anda dapat't algorithmically tahu pada waktu kompilasi apakah fungsi yang diberikan akan mengubah variabel tertentu atau tidak.

Sebaliknya, it's cukup untuk menunjukkan bahwa fungsi's perilaku sering tergantung pada run-time kondisi, yang kompilator dapat't tahu di muka. E. g.

int y;

int main(int argc, char *argv[]) {
   if (argc > 2) y++;
}

Bagaimana bisa compiler memprediksi dengan pasti apakah y akan dimodifikasi?

Hal ini dapat dilakukan dan compiler melakukan itu semua waktu untuk beberapa fungsi, ini adalah misalnya sepele optimasi untuk simple inline accesor atau banyak murni fungsi.

Apa yang mungkin adalah untuk mengetahui itu dalam kasus umum.

Setiap kali ada panggilan sistem atau fungsi panggilan yang datang dari modul lain, atau panggilan yang berpotensi override metode, apa pun bisa terjadi, termasuk pengambilalihan bermusuhan dari beberapa hacker's penggunaan stack overflow untuk mengubah sebuah variabel yang tidak berhubungan.

Namun anda harus menggunakan const, menghindari globals, lebih memilih referensi untuk pointer, hindari menggunakan variabel untuk tugas yang tidak berhubungan, dll. yang akan membuat compiler's hidup lebih mudah ketika tampil agresif optimisations.

Ada beberapa jalan untuk menjelaskan hal ini, salah satunya adalah Menghentikan Masalah:

Dalam teori komputabilitas, menghentikan masalah yang dapat dikemukakan adalah sebagai berikut: "Diberi keterangan yang sewenang-wenang program komputer, memutuskan apakah program selesai dijalankan atau terus berjalan selamanya". Ini setara dengan masalah memutuskan, mengingat program dan masukan, apakah program ini pada akhirnya akan berhenti ketika berjalan dengan masukan itu, atau akan berjalan selamanya.

Alan Turing terbukti pada tahun 1936 yang umum algoritma untuk memecahkan menghentikan masalah untuk semua kemungkinan program-input pasang tidak ada.

Jika saya menulis sebuah program yang terlihat seperti ini:

do tons of complex stuff
if (condition on result of complex stuff)
{
    change value of x
}
else
{
    do not change value of x
}

Apakah nilai x berubah? Untuk menentukan ini, anda pertama-tama harus menentukan apakah apakah ton dari hal-hal yang kompleks bagian menyebabkan kondisi api - atau bahkan lebih mendasar, apakah itu menghentikan. Yang's sesuatu compiler dapat't lakukan.

Benar-benar terkejut bahwa ada isn't jawaban yang menggunakan menghentikan masalah secara langsung! Ada's sangat mudah pengurangan dari masalah ini untuk menghentikan masalah.

Bayangkan bahwa compiler bisa mengatakan apakah atau tidak suatu fungsi mengubah nilai dari sebuah variabel. Maka itu tentu akan dapat mengetahui apakah fungsi berikut perubahan nilai y atau tidak, dengan asumsi bahwa nilai x dapat dilacak dalam semua panggilan sepanjang sisa dari program ini:

foo(int x){
   if(x)
       y=1;
}

Sekarang, untuk setiap program yang kita suka, let's menulis ulang sebagai:

int y;
main(){
    int x;
    ...
    run the program normally
    ...
    foo(x);
}

Perhatikan bahwa, jika, dan hanya jika, kita program perubahan nilai y, apakah itu kemudian menghentikan - foo() adalah hal terakhir yang dilakukannya sebelum keluar. Ini berarti kita've memecahkan menghentikan masalah!

Apa pengurangan atas menunjukkan kepada kita bahwa masalah penentuan apakah suatu variabel's nilai perubahan adalah at least sekeras menghentikan masalah. Menghentikan masalah ini diketahui incomputable, jadi yang satu ini harus juga.

Segera setelah panggilan fungsi fungsi lain yang kompilator doesn't "seperti" sumber, itu baik untuk mengasumsikan bahwa variabel berubah, atau hal-hal yang mungkin pergi salah lebih lanjut di bawah ini. Sebagai contoh, katakanlah kita memiliki ini di "foo.cpp":

 void foo(int& x)
 {
    ifstream f("f.dat", ifstream::binary);
    f.read((char *)&x, sizeof(x));
 }

dan kami memiliki ini di "bar.cpp":

void bar(int& x)
{
  foo(x);
}

Bagaimana bisa compiler "" bahwa x tidak berubah (atau berubah, lebih tepat) dalam bar?

I'm yakin kita bisa datang dengan sesuatu yang lebih kompleks, jika ini isn't cukup kompleks.

Hal ini tidak mungkin secara umum untuk compiler untuk menentukan apakah variabel akan dapat berubah, seperti yang telah ditunjukkan.

Ketika memeriksa const-ness, pertanyaan tentang bunga tampaknya jika variabel ** bisa diubah oleh fungsi. Bahkan ini lebih keras dalam bahasa yang mendukung pointer. Anda dapat't control apa kode lain halnya dengan pointer, bahkan bisa dibaca dari sumber eksternal (meskipun tidak mungkin). Dalam bahasa yang membatasi akses ke memori, jenis-jenis jaminan yang dapat menjadi mungkin dan memungkinkan untuk lebih agresif optimasi dari C++ tidak.

Untuk membuat pertanyaan yang lebih spesifik saya sarankan set berikut kendala-kendala yang mungkin telah apa yang penulis dari buku ini mungkin memiliki dalam pikiran:

1. Misalnya compiler adalah memeriksa perilaku suatu fungsi tertentu sehubungan dengan const-an dari sebuah variabel. Untuk kebenaran kompiler akan menganggap (karena aliasing seperti yang dijelaskan di bawah ini) jika fungsi yang disebut fungsi lain variabel berubah, jadi asumsi #1 hanya berlaku untuk kode fragmen yang don't membuat panggilan fungsi.
2. Asumsikan variabel isn't dimodifikasi oleh asynchronous atau aktivitas bersamaan.
3. Misalnya compiler adalah hanya untuk menentukan apakah variabel dapat diubah, bukan apakah itu akan diubah. Dengan kata lain compiler hanya melakukan analisis statis.
4. Misalnya compiler hanya mempertimbangkan dengan benar fungsi kode (tidak mempertimbangkan array overruns/underruns, buruk pointer, dll.)

Dalam konteks desain compiler, saya pikir asumsi 1,3,4 masuk akal dalam pandangan compiler penulis dalam konteks kode gen kebenaran dan/atau optimasi kode. Asumsi 2 akal tanpa adanya volatile kata kunci. Dan asumsi ini juga fokus pertanyaan cukup untuk membuat penjurian yang diusulkan jawaban yang jauh lebih definitif :-)

Mengingat asumsi-asumsi tersebut, alasan utama mengapa const-an dapat't diasumsikan adalah karena variabel aliasing. Compiler dapat't tahu apakah variabel lain menunjuk ke const variabel. Aliasing bisa disebabkan fungsi lain di kawasan yang sama kompilasi unit, di mana kasus compiler bisa melihat seluruh fungsi dan penggunaan panggilan pohon statis menentukan bahwa aliasing bisa terjadi. Tapi jika aliasing adalah karena perpustakaan atau lainnya kode asing, maka compiler tidak memiliki cara untuk mengetahui pada fungsi entri apakah variabel alias.

Anda bisa berpendapat bahwa jika variabel/argumen ditandai const maka seharusnya't dapat berubah melalui aliasing, tapi untuk compiler penulis yang's cukup berisiko. Bahkan bisa berisiko bagi manusia programmer untuk mendeklarasikan variabel const sebagai bagian dari, katakanlah sebuah proyek besar di mana dia doesn't mengetahui perilaku dari seluruh sistem, atau OS, atau perpustakaan, untuk benar-benar mengetahui variabel won't perubahan.

Bahkan jika sebuah variabel dinyatakan const, doesn't berarti beberapa kode yang ditulis dengan buruk dapat menimpa.

//   g++ -o foo foo.cc

#include <iostream>
void const_func(const int&a, int* b)
{
   b[0] = 2;
   b[1] = 2;
}

int main() {
   int a = 1;
   int b = 3;

   std::cout << a << std::endl;
   const_func(a,&b);
   std::cout << a << std::endl;
}

output:

1
2

Untuk memperluas pada komentar saya, buku itu's teks jelas yang mengaburkan masalah.

Seperti yang saya berkomentar, bahwa buku ini mencoba untuk mengatakan, "let's mendapatkan jumlah tak terbatas monyet untuk menulis setiap dibayangkan C++ fungsi yang bisa ditulis. Akan ada kasus di mana jika kita memilih variabel yang (beberapa fungsi tertentu monyet menulis) menggunakan, kita bisa't bekerja keluar apakah fungsi akan mengubah variabel tersebut."

Tentu saja untuk beberapa (bahkan banyak) fungsi di setiap aplikasi yang diberikan, hal ini dapat ditentukan oleh compiler, dan sangat mudah. Tapi tidak untuk semua (atau selalu paling).

Fungsi ini dapat dengan mudah dianalisis:

static int global;

void foo()
{
}

"anu" jelas tidak mengubah "global". Itu doesn't mengubah apa-apa sama sekali, dan kompilator dapat bekerja keluar ini sangat mudah.

Fungsi ini tidak dapat dianalisis:

static int global;

int foo()
{
    if ((rand() % 100) > 50)
    {
        global = 1;
    }
    return 1;

Sejak "anu",'s tindakan tergantung pada nilai yang dapat berubah pada saat runtime, itu terang-terangan tidak dapat ditentukan pada waktu kompilasi apakah itu akan mengubah "global".

Seluruh konsep ini adalah jauh lebih mudah untuk memahami dari ilmuwan komputer bisa keluar untuk menjadi. Jika fungsi tersebut dapat melakukan sesuatu yang berbeda berdasarkan hal-hal dapat berubah pada saat runtime, maka anda dapat't tahu apa itu'll jangan sampai berjalan, dan setiap waktu yang berjalan itu dapat melakukan sesuatu yang berbeda. Apakah itu's provably mustahil atau tidak, itu's jelas tidak mungkin.