Penalaran tentang pengakhiran non-deterministically loop

10

Inilah pertanyaan "trek B" jika ada. Ringkasan: hal pertama yang saya pikirkan ketika saya mencoba memberikan semantik untuk program-program non-deterministik menghasilkan semantik di mana saya tidak dapat membuktikan hal-hal tentang loop yang hanya mengakhiri non-deterministik. Tentunya seseorang telah mengetahui apa yang harus dilakukan dalam situasi ini, atau setidaknya menunjukkan bahwa itu sulit, tetapi saya tidak tahu bagaimana cara mencarinya (karena itu tag "permintaan referensi").

Latar Belakang

Saya ingin memodelkan bahasa sementara dengan non-determinisme. Saya pikir ini adalah cara yang jelas (atau paling tidak naif) untuk memodelkan bahasa seperti itu dengan domain kekuasaan Smyth, tetapi koreksi saya jika saya salah. Kami akan memodelkan arti perintah dalam bahasa ini adalah sebagai fungsi yang domainnya adalah himpunan S negara dan yang kodomainnya adalah himpunan P(S)⊥={⊥}∪P(S) , di mana ⊥ adalah elemen paling tidak mewakili non-terminasi dan P(S) adalah set negara.

Kami menginterpretasikan perintah sebagai peta dari status σ ke peristiwa non-penghentian ⊥ atau untuk menetapkan status {σ1,σ2,…} yang mewakili kemungkinan hasil. P⊛Q adalah pilihan non-deterministik.

  • ⟦skip⟧σ={σ}
  • ⟦x:=E⟧σ={σ[(⟦E⟧σ)/x]}
  • ⟦abort⟧σ=⊥
  • ⟦if E then P else Q⟧σ=⟦P⟧σ jika ⟦E⟧σ=true , jika tidak ⟦Q⟧σ
  • ⟦P⊛Q⟧σ=⊥ jika ⟦P⟧σ=⊥ atau ⟦Q⟧σ=⊥ , jika tidak ⟦P⟧σ∪⟦Q⟧σ
  • ⟦ P ⟧ σ = ⊥ ⟦ Q ⟧ τ = ⊥ τ ∈ ⟦ P ⟧ σ ⋃ τ ∈ ⟦ P ⟧ σ ⟦ Q ⟧ τ⟦P;Q⟧σ=⊥ jika atau untuk beberapa , jika tidak⟦P⟧σ=⊥⟦Q⟧τ=⊥τ∈⟦P⟧σ⋃τ∈⟦P⟧σ⟦Q⟧τ

Ada perintah parsial lengkap yang diarahkan , di mana untuk dan jika dan adalah set yang tepat dan , dan kami dapat memperluas ini ke fungsi dari ke menunjuk: jika untuk setiap , dan adalah fungsi yang memetakan setiap negara bagian ke .⊥ ⊑ S ′ S ′ ∈ P ( S ) ⊥ S 1 ⊑ S 2 S 1 S 2 S 1 ⊇ S 2 f S P ( S ) ⊥ f 1 ⊑ f 2 f 1 ( σ ) ⊑ f 2 ( σ ) σ f ⊥ ⊥,⊑⊥⊑S′S′∈P(S)⊥S1⊑S2S1S2S1⊇S2fSP(S)⊥f1⊑f2f1(σ)⊑f2(σ)σf⊥⊥

Arti dari sebuah loop adalah adalah batas paling atas dari rantai , di mana jika , selain itu jika atau untuk beberapa , jika tidak . (Definisi ini mengasumsikan bahwa baru saja saya definisikan adalah Scott berkelanjutan, tetapi saya pikir aman untuk mengabaikannya.)f ⊥ ⊑ f ( f ⊥ ) ⊑ f ( f ( f ⊥ ) ) ⊑ ... f ( g ) ( σ ) = { σ } ⟦ E ⟧ ( σ ) = f a l s e ⊥ ⟦ P ⟧ σ = ⊥⟦while E do P⟧σf⊥⊑f(f⊥)⊑f(f(f⊥))⊑…f(g)(σ)={σ}⟦E⟧(σ)=false⊥⟦P⟧σ=⊥τ ∈ ⟦ P ⟧ σ ⋃ τ ∈ ⟦ P ⟧ σ g ( τ ) fg(τ)=⊥τ∈⟦P⟧σ⋃τ∈⟦P⟧σg(τ)f

Pertanyaan

Pertimbangkan program ini:

b : = t r u e ; w h i l e b d ox:=0;
b:=true;
while b do
x:=x+2;
b:=false⊛b:=true

Secara intuitif, ini adalah loop yang dapat mengembalikan bilangan positif positif atau tidak berakhir, dan yang sesuai dengan apa yang dapat kita buktikan tentang loop ini menggunakan prasyarat liberal terlemah (dimungkinkan untuk menunjukkan bahwa adalah sebuah loop invarian). Namun, karena loop memiliki kemampuan untuk tidak mengakhiri (kita dapat memperbaiki pilihan non-deterministik oleh program yang selalu mengambil cabang kanan), arti dari program ini diberikan setiap keadaan awal adalah . (Kurang informal: fungsi yang memetakan keadaan mana saja di mana salah untuk dirinya sendiri dan setiap keadaan di mana adalah benar untuk adalah titik tetap dari digunakan untuk mendefinisikan loop.)⊥ b b ⊥ f∃n.x=2n⊥bb⊥f

Ini berarti bahwa semantik naif yang saya usulkan tidak sesuai dengan cara yang saya harapkan dapat beralasan tentang program. Saya menyalahkan semantik saya, tetapi tidak bisa memperbaikinya.

reference-request denotational-semantics Rob Simmons
sumber
4
Saya berpikir bahwa dengan menggunakan sebagai kode domain dari arti suatu program, Anda telah secara efektif menyerahkan alasan apa pun tentang suatu program yang dapat berbeda. Pikiran naif adalah menggunakan , tapi saya tidak tahu apakah itu akan menimbulkan masalah lain. P ( S ∪ { ⊥ } ){⊥}∪P(S)P(S∪{⊥})
Tsuyoshi Ito
Ya, Anda benar bahwa melihat set sudah jelas bahwa harapan hilang bahkan sebelum kita sampai pada contoh. Saran Anda terjadi pada saya juga, tapi saya pikir Anda berakhir dengan masalah yang sama dalam contoh ini selama potensi non-terminasi dimodelkan oleh bukan , dan jika kami memilih yang terakhir itu akan mengganggu kemampuan kami untuk memberi makna pada loop sebagai titik paling tidak tetap dengan cara biasa. S ∪ { ⊥ } { ⊥ }{⊥}∪P(S)S∪{⊥}{⊥}
Rob Simmons
Sudahkah Anda melihat Dynamic Logic? Semantik diberikan dalam bentuk hubungan dari negara bagian ke negara bagian, dan Anda dapat menggunakan logika untuk alasan tentang kebenaran parsial dan total, yang artinya, sifat-sifat perhitungan yang berakhir dan bahwa semua perhitungan berakhir dengan properti yang diberikan.
Dave Clarke
Saya belum memikirkan logika dinamis dalam pengaturan ini, tetapi saya melihat bagaimana ini mungkin relevan - saya akan melihat apa yang dipikirkan Platzer dan murid-muridnya ketika saya kembali ke Pittsburgh.
Rob Simmons

Jawaban:

10

Dalam [dB80] analisis Hitchcock dan Park tentang sifat terminasi rekursi terbukti sesuai dengan analisis semantik berdasarkan apa yang disebut interpretasi hubungan Egli-Milner [Egl75, Plo76], yang mengekspresikan nondeterminisme yang tidak menentu . Gagasan ini menangkap bahwa persatuan hubungan nondeterministik benar jika menghasilkan setidaknya satu perhitungan yang mengarah ke hasil yang diinginkan (bahkan di hadapan perhitungan nonterminating). Ini tampaknya sesuai dengan apa yang Anda coba lakukan.

Selanjutnya, makna pernyataan sebagai fungsi memetakan setiap status awal ke beberapa set status , mungkin mengandung , sehingga ketat dalam arti bahwa . Pilihan nondeterministik antara pernyataan dan dijelaskan oleh fungsi memetakan setiap keadaan awal ke penyatuan hasil individu . Jadi, kapan pun atauf S σ ⊥ f S f S ( ⊥ ) = { ⊥ } S 1 S 2 σ f S 1 ( σ ) ∪ f S 2 ( σ ) S 1 S 2SfSσ⊥fSfS(⊥)={⊥}S1S2σfS1(σ)∪fS2(σ)S1S2memiliki kemungkinan nondeterministik untuk menghasilkan hasil yang tidak diinginkan, maka demikian juga pilihan nondeterministik mereka. Sebagai set hasil negara final yang diperoleh dalam analisis ini, yang disebut Egli-Milner powerset of States:

⊥}PE--M(S)={ s⊆S⊥ | s adalah terbatas dan tidak kosong, atau mengandung⊥}

Mengapa himpunan bagian tak terbatas tidak dianggap sebagai set keadaan akhir dalam model ini? Di bawah asumsi bahwa semua blok bangunan dasar dari istilah relasional hanya menghasilkan set terbatas, nonempty dari keadaan akhir yang mungkin, set tak terbatas dari keadaan akhir yang mungkin hanya dapat dihasilkan ketika perhitungan tak terbatas dimungkinkan. Ini bisa dilihat sebagai berikut. Struktur himpunan semua perhitungan yang mungkin dimulai dengan status yang diberikan sebagai pohon dengan root dan menyatakan sebagai node. Set daun kemudian set persis keadaan akhir yang mungkin dicapai dari , kecuali untukσ 0 σ 0 σ 0 ⊥Sσ0σ0σ0⊥, yang mungkin hilang di antara daun tetapi diwakili dalam set keadaan akhir oleh fakta bahwa ada jalan yang tak terbatas di pohon. Dengan asumsi di atas, dan karena hanya pilihan terbatas nondeterministik yang tersedia, pohon ini bercabang dengan baik. Dengan demikian, hanya ada sejumlah daun hingga pada kedalaman tertentu. Akibatnya jumlah tak terbatas dari keadaan akhir yang mungkin hanya dapat dihasilkan dengan adanya perhitungan tak terbatas (aplikasi lemma König [Kön32]).

⊑ E - M s , t ∈ P E - M ( S )(PE--M(S),⊑E--M) adalah poset untuk didefinisikan oleh: untuk ,⊑E--Ms,t∈PE--M(S)

s⊑E--Mt=(⊥∈s∧s∖{⊥}⊆t)∨(⊥∉s∧s=t) .

Di sini, dapat dilihat sebagai placeholder di mana -greater set dapat dihasilkan dengan memasukkan lebih banyak status sebagai pengganti . Karena itu, adalah elemen terkecil dari . Selanjutnya, poset memiliki lub's untuk chain. Demikian pula, fungsi ketat dari hingga sebagian dipesan oleh ekstensi . Selain itu, fungsi yang paling sedikit adalah⊑ E - M ⊥ { ⊥ } ( P E - M ( S ) , ⊑ E - M ) ( P E - M ( S ) , ⊑ E - M ) ω S ∪ { ⊥ } P E --M ( S ) ⊑ E - M λ σ . { ⊥ } ω⊥⊑E--M⊥{⊥}(PE--M(S),⊑E--M)(PE--M(S),⊑E--M)ωS∪{⊥}PE--M(S)⊑E--Mλσ.{⊥} dan lub's of -chains dari fungsi tersebut juga ada.ω

[dB80] JW de Bakker. Teori Matematika tentang Ketepatan Program . Prentice Hall, 1980.

[Egl75] H Egli. Model matematika untuk perhitungan nondeterministik. Laporan teknis, ETH Zürich, 1975.

[Kön32] D König. Theorie der endlichen dan tak berujung Graphen. Laporan teknis, Leipzig, 1932.

[Plo76] GD Plotkin. Konstruksi domain kekuasaan. Jurnal SIAM tentang Perhitungan , 5 (3): 452-487, 1976.

Penafian: ini diambil hampir kata demi kata dari sebuah buku yang pernah saya tulis bersama:

WP de Roever dan K Engelhardt. Penyempitan Data: Metode Bukti yang Berorientasi Model dan Perbandingannya . Cambridge University Press, 1998.

Kai
sumber
4
Frasa "ini diambil hampir kata demi kata dari sebuah buku yang pernah saya tulis bersama" mungkin harus diawali dengan "Extra Awesomeness:" not "Disclaimer:" :-D. Terima kasih, ini sangat membantu.
Rob Simmons
Salah satu cara memandang nondeterminisme (dan cara saya ingin melihatnya) adalah bahwa itu adalah bentuk kurang spesifikasi - program dengan pilihan nondeterministik disempurnakan oleh program yang selalu mengambil pilihan pertama, selalu mengambil pilihan kedua, atau (lihat kerja ekstensif McIver dan Morgan di bidang khusus ini) program yang mengambil satu pilihan atau yang lain dengan probabilitas .5 . Jadi loop yang non-deterministically tidak berakhir disempurnakan oleh loop yang tidak pernah berakhir, dan juga oleh loop flip-koin Anda yang berakhir (dengan probabilitas 1)
Rob Simmons