Apa tujuan di balik penafsiran abstrak dalam bahasa pemrograman?

Sekarang saya mencoba untuk memahami lebih baik apa "interpretasi abstrak" dalam bahasa pemrograman. Saya menemukan bab buku yang bagus yang menjelaskan gagasan memperluas domain dengan elemen tetap paling sedikit, empat aksioma yang menghasilkan titik tetap untuk fungsi kontinu, dan sebagainya. Saya memahami detail teknis ini (meskipun saya tidak begitu yakin apa yang dimaksud dengan "interpretasi abstrak" persis dalam seluruh skema ini).

Apa yang saya tidak yakin adalah apa yang memotivasi penggunaan interpretasi abstrak? Apakah hanya mengidentifikasi titik tetap untuk fungsi yang dapat dihitung? Apakah motivasi utama berasal dari rekursi di sebagian besar bahasa pemrograman?

Juga akan senang mendapatkan gambaran umum tingkat tinggi yang secara teknis cukup mendalam bagi seseorang yang memiliki gelar dalam ilmu komputer. Saya menemukan halaman Wikipedia agak mengganggu.

Penafsiran abstrak adalah konsep yang sangat umum dan tergantung pada siapa Anda bertanya, Anda akan menerima penjelasan yang berbeda karena konsep yang serba bisa menerima banyak perspektif. Pandangan dalam jawaban ini adalah milik saya dan saya tidak akan menganggapnya umum.

Kekerasan komputasi sebagai motivasi

Mari kita mulai dengan masalah keputusan, yang solusinya memiliki struktur seperti ini:

Seringkali ada NP-hard lower bound pada prosedur. Memeriksa sifat semantik program bahkan tidak dapat dipastikan. Apa yang bisa kita lakukan?

Mari kita lakukan dua pengamatan. Pertama, kita kadang-kadang dapat memecahkan contoh masalah spesifik bahkan jika kita tidak dapat memecahkan masalah umum. Kedua, aplikasi seperti optimisasi kompiler menoleransi aproksimasi bahwa kompiler yang menghilangkan beberapa tetapi tidak semua sumber inefisiensi berguna. Untuk membuat intuisi ini tepat, kita harus menjawab:

1. Apa artinya secara formal untuk menyelesaikan beberapa, tetapi tidak semua contoh masalah?
2. Apa solusi perkiraan untuk masalah keputusan?

Ide Interpretasi Abstrak 1: Ubah Pernyataan Masalah

Bagi saya, wawasan utama interpretasi abstrak adalah mengubah rumusan masalah sehingga alih-alih meminta jawaban Ya / Tidak , kami meminta jawaban Ya / Tidak / Mungkin .

Sebagai konsekuensinya, setiap masalah memiliki solusi waktu yang sepele dan konstan (output Maybe ). Kita sekarang dapat mengalihkan perhatian kita untuk mendapatkan prosedur yang tidak selalu menghasilkan Maybe . Untuk kembali ke pertanyaan di atas, solusi yang berfungsi untuk beberapa contoh masalah adalah solusi yang mengembalikan Mungkin pada masalah yang tidak dapat dipecahkan. Selain itu, Mungkin merupakan perkiraan dari Ya dan Tidak karena kita tidak yakin apa jawabannya.

Gagasan ini tidak terbatas pada masalah keputusan. Pertimbangkan masalah ini terkait program.

1. Baris kode mana dalam program yang mati (tidak akan pernah dieksekusi)?
2. Variabel mana dalam program yang memiliki nilai konstan?
3. Pernyataan mana dalam program ini yang dilanggar?

Dalam semua situasi ini, kita dapat beralih dari solusi yang tepat ke yang mendekati dengan mempertimbangkan solusi yang memiliki ketidakpastian.

1. Apa satu set baris kode yang mati?
2. Apakah seperangkat variabel dalam program yang memiliki nilai konstan?
3. Apa seperangkat asersi dalam program yang tidak dilanggar?

Set yang dihasilkan tidak harus yang terbesar. Ide ini sangat umum dan berlaku untuk masalah yang tidak ada hubungannya dengan analisis program.

1. $m$$n$$[a,b]$
2. $m$$n$$k$
3. Alih-alih meminta penugasan yang memuaskan ke rumus, kita dapat meminta set yang berisi penugasan yang memuaskan.

Perhatikan bahwa kami tidak hanya mengubah masalah tetapi juga menggeneralisasikannya secara ketat karena solusi untuk masalah asli masih merupakan solusi untuk masalah yang dimodifikasi. Pertanyaan besar yang belum terjawab sekarang adalah: Bagaimana kita bisa menemukan solusi perkiraan?

Abstrak Ide Interpretasi 2: Karakterisasi Titik Tetap dari Solusi Asli

$t$$s$$\mathit{Reach}(s)$$s$$t$$\mathit{Reach}(s)$

$X = \{s\} \cup \{ w ~|~ v \text{ is in } X \text{ and } (v,w) \text{ is an edge}\}$

$n$$n$$s$

Karakterisasi titik tetap adalah keputusan desain. Ada banyak penokohan yang berbeda dari serangkaian solusi. Masing-masing dari mereka mungkin memiliki kelebihan yang berbeda. Dalam hal bahasa pemrograman, kami memiliki lebih banyak struktur daripada hanya berurusan dengan grafik. Persamaan titik tetap yang kita pedulikan dapat didefinisikan dengan induksi pada struktur program input. Ide ini tidak spesifik untuk program. Ketika menerapkan interpretasi abstrak ke elemen-elemen bahasa terstruktur seperti tata bahasa, rumus logis, program, ekspresi aritmatika, dll. Kita dapat menentukan titik tetap dengan menginduksi pada struktur beberapa objek sintaksis.

Dengan memberikan karakterisasi titik tetap ini, kami berkomitmen pada cara spesifik solusi komputasi. Kami tidak akan benar-benar menghitung titik tetap ini karena setidaknya sama sulitnya dengan menyelesaikan masalah awal, yang membawa kami ke langkah berikutnya.

Abstrak Ide Interpretasi 3: Pendekatan Titik Tetap

$F$$L$$G$$M$$M$$L$$M$$L$

$L$$M$$F$$G$

Anda mungkin menemukan intuisi di balik transfer titik tetap berwawasan luas. Kita dapat menganggap titik tetap sebagai batas rantai elemen (mungkin tidak terbatas). Menghitung solusi perkiraan sama dengan mendekati batas ini, yang bisa kita lakukan dengan mendekati elemen rantai.

$s$$t$$s$$t$

Abstrak Ide Interpretasi 4: Algoritma Pendekatan Titik Tetap

Segala sesuatu yang dilihat sejauh ini merupakan hasil keberadaan matematika. Langkah terakhir adalah menghitung aproksimasi. Ketika kisi aproksimasi terbatas (atau jika kondisi rantai naik / turun terpenuhi), kita dapat menggunakan prosedur iteratif sederhana. Jika kisi tidak terbatas prosedur iteratif mungkin tidak cukup, meskipun menghitung titik tetap mungkin masih dapat ditentukan. Dalam situasi ini, banyak teknik yang digunakan untuk memperkirakan solusi lebih lanjut, atau untuk melompat ke solusi yang tepat lebih cepat daripada algoritma iterasi naif. Dalam konteks komputasi solusi, Anda mendengar istilah seperti pelebaran , penyempitan , iterasi strategi , akselerasi , dll.

Ringkasan

Menurut pendapat saya, interpretasi abstrak menyediakan dasar matematika untuk gagasan abstraksi dengan cara yang sama bahwa logika matematika menyediakan dasar matematika untuk penalaran. Solusi untuk banyak masalah yang kami pedulikan memiliki penokohan sebagai titik tetap. Pengamatan ini tidak terbatas pada masalah bahasa pemrograman dan bahkan untuk ilmu komputer. Solusi perkiraan dapat dikarakterisasi sebagai perkiraan titik tetap dan dihitung dengan algoritma khusus. Karakterisasi dan algoritma ini akan mengeksploitasi struktur instance masalah. Dalam kasus program, struktur ini diberikan oleh sintaks bahasa.

Menghitung perkiraan untuk masalah yang tidak memiliki metrik alami adalah seni yang terus dikembangkan dan disempurnakan oleh praktisi. Interpretasi abstrak adalah salah satu teori matematika untuk ilmu di balik seni ini.

Referensi Ada beberapa tutorial bagus tentang interpretasi abstrak yang bisa Anda baca.

1. Pengantar kasual untuk Interpretasi Abstrak , Patrick Cousot (Bekerja bersama dengan Radhia Cousot), Workshop tentang Biologi Sistem dan Metode Formal (SBFM'12)
2. Pengantar lembut untuk verifikasi formal sistem komputer dengan interpretasi abstrak , Patrick dan Radhia Cousot, Marktoberdorf Summer School 2010.
3. Kuliah 13: Abstraksi Bagian I , Patrick Cousot, Interpretasi abstrak, Kursus MIT.
4. Pengantar Interpretasi Abstrak , Samson Abramsky dan Chris Hankin, Interpretasi Abstrak Bahasa Deklaratif, 1987.
5. Interpretasi abstrak dan aplikasi untuk program logika , Patrick dan Radhia Cousot, 1992. Dua bagian pertama memiliki gambaran umum tingkat tinggi dengan beberapa contoh.

Saya setuju bahwa seringkali sulit untuk mengekstraksi poin utama dari semua detail itu. (Sebenarnya, masalah besar saya dengan setiap perlakuan interpretasi abstrak yang saya lihat adalah bahwa mereka menghadirkan begitu banyak mesin tanpa memotivasinya.)

Begini cara saya memikirkannya:

Interpretasi abstrak menjalankan program, kira-kira, pada set input besar sekaligus.

Ini tidak mencakup semuanya, tetapi bertahan dengan baik pada umumnya.

Contoh kanonik mengevaluasi ekspresi aritmatika untuk menentukan tanda hasil. Anda dapat membayangkan mesin hipotetis dan cepat yang dapat mengevaluasi ekspresi pada setiap input positif dan mengembalikan set hasil. Jika Anda memiliki salah satunya, pada prinsipnya Anda dapat menentukan hal-hal seperti "program ini mengembalikan angka positif ketika diberi angka positif."

Tetapi tentu saja Anda tidak benar-benar memiliki mesin itu. Anda terjebak dalam kehidupan nyata, jadi Anda harus melakukan hal yang sama secara simbolis , yang kadang-kadang dapat memberikan jawaban yang tepat tetapi sering gagal, atau kira - kira , dengan cara yang selalu mengembalikan jawaban tetapi mungkin tidak tepat. Yang terakhir adalah apa yang dilakukan interpretasi abstrak.

$\{neg,zero,pos\}$$\{\{...,-2,-1\},\{0\},\{1,2,...\}\}$

$add : pos \times pos \to pos$

$add : pos \times pos \to pos$$add(a,b)$$a$$b$$pos \times neg \to (pos \sqcup zero \sqcup neg)$$\sqcup$

$\sqcap$$\sqsubseteq$

Ketika Anda ingin membuktikan bahwa interpretasi abstrak Anda sekencang mungkin, Anda akan menginginkan koneksi Galois untuk meresmikan korespondensi ini. Hanya dengan satu memastikan bahwa, untuk set beton tertentu, set abstrak ketat ada.

$\bot$

TKI, apa yang telah Anda identifikasi sebagai motivasi untuk interpretasi abstrak sebenarnya adalah motivasi untuk mesin yang diperlukan untuk melakukan interpretasi abstrak pada bahasa yang setara dengan Turing. Motivasi yang sebenarnya berguna meringkas perilaku program dengan menjalankannya pada banyak input sekaligus.