Bisakah lingkungan runtime mendeteksi loop tak terbatas?

Apakah mungkin untuk lingkungan runtime untuk mendeteksi loop tak terbatas dan kemudian menghentikan proses yang terkait, atau akan mengimplementasikan logika seperti itu setara dengan menyelesaikan masalah penghentian?

Untuk keperluan pertanyaan ini, saya mendefinisikan "loop tak terbatas" yang berarti serangkaian instruksi dan terkait mulai tumpukan / tumpukan data yang, ketika dieksekusi, mengembalikan proses ke keadaan yang sama persis (termasuk data) seperti sebelumnya memulai loop tak terbatas. (Dengan kata lain, program yang menghasilkan ekspansi desimal panjang pi yang tidak terbatas tidak "terjebak" dalam "loop tak terbatas," karena pada setiap iterasi, ia memiliki lebih banyak digit pi di suatu tempat dalam memori yang terkait.)

(Porting dari /programming//q/16250472/1858225 )

Secara teori dimungkinkan untuk lingkungan runtime untuk memeriksa loop tersebut menggunakan prosedur berikut:

Setelah instruksi dijalankan, lingkungan runtime akan membuat gambar lengkap dari status proses yang sedang berjalan (yaitu semua memori yang terkait dengannya, termasuk register, PC, stack, heap, dan global), simpan gambar itu di suatu tempat, dan kemudian periksa untuk lihat apakah itu cocok dengan salah satu gambar yang disimpan sebelumnya untuk proses itu. Jika ada kecocokan, maka proses macet dalam infinite loop. Jika tidak, instruksi selanjutnya dijalankan dan prosesnya diulang.

Faktanya, daripada melakukan pemeriksaan ini setelah setiap instruksi tunggal, lingkungan runtime bisa dengan mudah menjeda proses secara berkala dan membuat save-state. Jika proses macet dalam infinite loop yang melibatkan n state, maka setelah paling n memeriksa, keadaan duplikat akan diamati.

Perhatikan, tentu saja, bahwa ini bukan solusi untuk masalah penghentian; perbedaannya dibahas di sini .

Tetapi fitur seperti itu akan menjadi pemborosan sumber daya yang sangat besar ; terus-menerus menghentikan proses untuk menyimpan semua memori yang terkait dengannya akan memperlambatnya dengan sangat cepat dan menghabiskan banyak sekali memori dengan sangat cepat. (Meskipun gambar lama dapat dihapus setelah beberapa saat, akan berisiko untuk membatasi jumlah total gambar yang dapat disimpan karena loop tak terbatas yang besar - yaitu, dengan banyak negara - mungkin tidak tertangkap jika terlalu sedikit status disimpan dalam memori.) Selain itu, fitur ini sebenarnya tidak akan memberikan banyak manfaat, karena kemampuannya untuk menangkap kesalahan akan sangat terbatas dan karena itu relatif mudah untuk menemukan loop tak terbatas dengan metode debug lain (seperti hanya melangkah melalui kode dan mengenali kesalahan logika).

Oleh karena itu, saya ragu bahwa lingkungan runtime seperti itu ada atau akan pernah ada, kecuali seseorang memprogramnya hanya untuk iseng. (Yang saya agak tergoda untuk lakukan sekarang.)

Mari kita asumsikan bahwa program tidak berinteraksi dengan dunia luar, jadi itu sangat mungkin untuk merangkum seluruh keadaan program. (Ini berarti ia tidak melakukan input apa pun, setidaknya.) Selanjutnya, mari kita asumsikan bahwa program ini berjalan di beberapa lingkungan deterministik sehingga setiap negara memiliki penerus yang unik, yang berarti bahwa runtime tidak diulir, atau bahwa threading dapat secara deterministik direduksi menjadi suatu urutan.

Di bawah asumsi yang sangat tidak mungkin tetapi secara teoritis tidak terbatas ini, kita dapat menduplikasi program dan menjalankannya dalam dua runtimes terpisah; masing-masing akan melakukan perhitungan yang persis sama.

Jadi mari kita lakukan itu. Kami akan menjalankannya sekali dalam runtime Tortoise, dan pada saat yang sama kami akan menjalankannya di runtime Hare. Namun, kami akan mengatur agar Hare runtime beroperasi tepat dua kali lebih cepat; setiap kali runtime kura-kura membuat satu langkah, runtime kelinci membuat dua langkah.

$n$$p$$kn$$k$$kn\ge p$

Total biaya tes adalah satu keadaan ekstra dan satu perbandingan keadaan per langkah, dan itu akan berakhir tidak lebih dari tiga kali jumlah langkah yang diperlukan untuk program untuk menyelesaikan loop pertama. (Satu kali di Kura-kura dan dua kali di Kelinci, dengan total tiga kali.)

Seperti istilah yang saya gunakan, ini hanyalah algoritma pendeteksi siklus Tortoise dan Hare yang terkenal Robert Floyd .

Sama seperti saya akan menyarankan algoritma deteksi siklus Floyd, posting rici mengalahkan saya untuk itu. Namun, semuanya dapat dibuat lebih praktis dengan mempercepat perbandingan keadaan penuh.

Hambatan dari algoritma yang diusulkan akan membandingkan kondisi penuh. Perbandingan ini biasanya tidak akan selesai, tetapi berhenti lebih awal --- pada perbedaan pertama. Salah satu optimasi adalah untuk mengingat di mana perbedaan masa lalu terjadi, dan periksa bagian-bagian negara itu terlebih dahulu. Misalnya, pertahankan daftar lokasi, dan periksa daftar ini sebelum membuat perbandingan penuh. Ketika lokasi dari daftar ini memperlihatkan perbedaan, hentikan perbandingan (dengan kegagalan), dan pindahkan lokasi ke depan daftar.

Pendekatan yang berbeda (dan berpotensi lebih skalabel) adalah menggunakan hashing tambahan. Pilih fungsi status penuh sehingga nilai hash mudah disesuaikan di O (1) ketika beberapa bagian dari kondisi berubah. Misalnya, ambil jumlah kata negara tertimbang mod beberapa prime besar dan gabungkan dengan jumlah mod tertimbang beberapa prime besar lainnya (juga bisa melempar dalam jumlah modular tertimbang kotak kuadrat kata-kata, dengan berat dan modulus berbeda). Dengan cara ini, pembaruan hash akan mengambil O (1) waktu pada setiap langkah eksekusi, dan perbandingan akan mengambil O (1) waktu sampai Anda mendapatkan hit. Peluang positif palsu (yaitu, hash cocok ketika negara berbeda) sangat rendah, dan bahkan jika ini pernah terjadi, itu akan diamortisasi atas sejumlah besar negatif sejati (negatif palsu tidak mungkin).

Tentu saja, dalam praktiknya, tampaknya lebih mungkin masuk ke situasi seperti menghasilkan digit angka pi --- hal terus berubah, tetapi tidak pernah berakhir. Kemungkinan lain yang sering terjadi adalah bahwa infinite loop mengalokasikan memori, yang mana hal itu dengan cepat menghabiskan semua memori yang tersedia.

Dalam kursus saya tentang algoritma dan struktur data, autograder kami harus berurusan dengan pengiriman siswa yang kadang-kadang masuk ke loop tak terbatas. Ini ditangani oleh time-out 30 detik dan batas memori tertentu. Keduanya jauh lebih longgar daripada runtime dan anggaran memori yang kami terapkan sebagai bagian dari penilaian. Saya tidak yakin jika menerapkan deteksi infinite-loop benar akan membuat banyak pengertian dalam konteks ini karena program seperti itu akan berjalan sedikit lebih lambat (ini adalah di mana dukungan perangkat keras untuk hashing negara dapat membantu, tapi sekali lagi Anda akan memerlukan kegunaan tambahan untuk benarkan ini). Ketika siswa tahu bahwa waktu program mereka habis, mereka biasanya dapat menemukan infinite loop.

The aprove alat pemutusan melakukan analisis statis pada sistem penulisan ulang (termasuk subclass dari program Haskell) yang dapat membuktikan non-terminasi, memberikan contoh yang sebenarnya dari program non-terminating. Teknik ini cukup kuat dan bekerja menggunakan varian teknik yang disebut penyempitan .

Sejauh yang saya tahu, belum ada banyak pekerjaan dalam mendeteksi non-terminasi aktual untuk bahasa umum.