Mengapa titik tetap (lfp) paling tidak penting dalam analisis program

11

Saya mencoba untuk mendapatkan gambaran besar tentang pentingnya titik tetap (lfp) dalam analisis program. Misalnya interpretasi abstrak tampaknya menggunakan keberadaan lfp. Banyak makalah penelitian tentang analisis program juga sangat berfokus pada menemukan titik paling tidak tetap.

Lebih khusus lagi, artikel ini di wikipedia: Knaster-Tarski Theorem menyebutkan bahwa lfp digunakan untuk mendefinisikan semantik program.

Mengapa ini penting? Contoh sederhana apa pun membantu saya. (Saya mencoba untuk mendapatkan gambaran besar).

EDIT

Saya pikir kata-kata saya salah. Saya tidak menantang pentingnya lfp. Pertanyaan persis saya (pemula) adalah: Bagaimana komputasi lfp membantu dalam analisis program? Misalnya, mengapa / bagaimana interpretasi abstrak menggunakan lfp? apa yang terjadi jika tidak ada lfp di domain abstrak?

Semoga pertanyaan saya lebih konkret sekarang.

Ram
sumber
@ DW Ini adalah pertanyaan pemula dalam analisis program. Saya berdebat sendiri beberapa kali sebelum memposting pertanyaan jika terlihat terlalu kabur. Apa yang saya cari adalah: Peran apa yang dimainkan lfp dalam analisis program (Ini memang penting, tetapi bagaimana?). Saya mencari jawaban yang tidak menyelidiki banyak detail matematika. Saya pikir kata-kata dalam pertanyaan saya juga tidak jelas. Saya akan mengedit pertanyaan.
Ram
@ WD Saya setuju ini mungkin bukan pertanyaan yang diteliti dengan baik. Namun setiap kali saya terus membaca makalah, banyak detail matematika dan saya dengan cepat kehilangan gambaran besarnya. Sebagai contoh, lebih konkretnya, makalah ini [Pelebaran untuk Kontrol-Aliran] ( berkeleychurchill.com/research/papers/vmcai14.pdf ) nampak sangat abstrak bagi saya. Secara langsung menarik untuk menghitung titik perbaikan paling tidak. Sebagian besar makalah dalam analisis program tampaknya peduli dengan pertanyaan ini di baris yang sama. Saya kehilangan gambaran besarnya. Saya akan senang mengetahui mengapa menghitung lfp itu penting.
Ram

Jawaban:

13

Segala bentuk rekursi atau iterasi dalam pemrograman sebenarnya adalah titik tetap. Misalnya, sebuah whileloop ditandai oleh persamaan

while b do c done  ≡  if b then (c ; while b do c done)

yang mengatakan itu while b do c doneadalah solusi Wdari persamaan

W  ≡  Φ(W)

mana Φ(x) ≡ if b then (c ; x). Tetapi bagaimana jika Φmemiliki banyak poin tetap? Yang mana yang berhubungan dengan whileloop? Salah satu wawasan dasar pemrograman semantik adalah bahwa itu adalah titik paling tidak tetap.

Mari kita ambil contoh sederhana, rekursi kali ini. Saya akan menggunakan Haskell. Fungsi rekursif fdidefinisikan oleh

f :: a -> a
f x = f x

adalah fungsi di mana-mana yang tidak terdefinisi, karena hanya berjalan selamanya. Kami dapat menulis ulang definisi ini dengan cara yang lebih tidak biasa (tetapi masih berfungsi di Haskell) sebagai

f :: a -> a
f = f

Jadi fadalah titik tetap dari fungsi identitas:

f ≡ id f

Tetapi setiap fungsi adalah titik tetap id. Di bawah urutan teoretis domain, "undefined" adalah elemen yang paling sedikit. Dan memang, fungsi kita fadalah fungsi di mana-mana yang tidak ditentukan.

whilenx1,,xnVVnVn{}(v1,,vn)VnVnVnVn{}

  • Vn{}VnVnVn{}
  • while true do skip done
  • setiap peningkatan urutan memiliki supremum

Hanya untuk memberi Anda gambaran tentang bagaimana ini bekerja, semantik program

x_1 := e

(v1,,vn)Vnvee(v1,,vn)(ve,v2,,vn)

Andrej Bauer
sumber
1
+1 untuk contoh sementara. Namun, saya agak bingung. But what if Φ has many fixed points?Sementara saya memahami persamaan titik tetap, dalam konteks ini, apakah W \ dalam L? Bagaimana kita mendefinisikan kisi di sini? Saya menghargai elaborasi lebih lanjut Anda tentang itu.
Ram
Dalam komentar di atas, saya menggunakan "L" untuk berdiri untuk kisi (atau poset)
Ram
Saya mengubah jawabannya.
Andrej Bauer
Terima kasih atas pembaruannya. Saya sangat menghargainya karena memberi saya pandangan berbeda tentang melihat program. Saya sekarang membaca "Teori titik tetap" dari "Semantik dengan aplikasi: Pengantar formal" oleh Nielson, yang melengkapi pandangan tentang membangun kisi dari fungsi parsial untuk bahasa IMP.
Ram
6

Inilah intuisi: titik-titik tetap paling tidak membantu Anda menganalisis loop.

Analisis program melibatkan pelaksanaan program - tetapi mengabstraksi beberapa detail data. Ini semua baik. Abstraksi membantu analisis berjalan lebih cepat daripada benar-benar menjalankan program, karena memungkinkan Anda untuk mengabaikan aspek yang tidak Anda pedulikan. Misalnya, itulah cara interpretasi abstrak bekerja: pada dasarnya mensimulasikan pelaksanaan program, tetapi hanya melacak informasi parsial tentang keadaan program.

Yang sulit adalah ketika Anda sampai pada satu lingkaran. Loop dapat menjalankan banyak, berkali-kali. Biasanya, Anda tidak ingin analisis program Anda harus mengeksekusi semua iterasi loop, karena kemudian analisis program akan memakan waktu lama ... atau bahkan mungkin tidak berakhir. Jadi, di situlah Anda menggunakan titik paling tidak tetap. Titik paling tidak tetap pada dasarnya mencirikan apa yang bisa Anda katakan pasti akan benar setelah loop selesai, jika Anda tidak tahu berapa kali loop akan beralih.

Itulah gunanya titik paling tidak tetap digunakan. Karena loop hadir di seluruh program, titik tetap paling tidak digunakan sepanjang analisis program. Poin tetap paling tidak penting karena loop ada di mana-mana, dan penting untuk dapat menganalisis loop.

Kebetulan, rekursi dan rekursi timbal balik hanyalah bentuk lain dari loop - jadi mereka juga cenderung ditangani dengan titik paling tidak tetap.

DW
sumber