Mengapa negara tetap tidak berubah dalam semantik operasional langkah kecil dari loop sementara?

9

Biasanya saya melihat bahwa dalam representasi semantik operasional struktural untuk loop sementara, status program tidak berubah:

$(while \> B \> do \>S, \sigma) \rightarrow (if \>B \> then \>S; (while \> B \> do \>S) \> else \> SKIP, \sigma)$

Bagi saya, ini tidak intuitif, jika statusnya tidak berubah (yaitu status memori tetap sama) maka akan tetap benar dan program tidak akan pernah berakhir. $B$

Adakah yang bisa menjelaskan mengapa negara tidak berubah dalam aturan ini?

formal-languages programming-languages formal-methods operational-semantics El Marce
sumber

Perhatikan bahwa ini hanya benar jika kita dapat berasumsi bahwa tidak memiliki efek samping. Ini tidak benar di sebagian besar bahasa pemrograman.

B

$B$

Raphael

10

Dalam semantik bahasa pemrograman, gagasan tentang keadaan program bukanlah gagasan filosofis yang samar, tetapi konsep matematika yang sangat tepat. Sebuah negara dalam kecil-langkah semantik operasional adalah fungsi parsial $s$

s : V Sebuah r ↪ Z

$s : \mathbf{Var} \hookrightarrow \mathbb{Z}$

yang mencatat nilai-nilai variabel. Jadi, jika , maka variabel memiliki nilai . Negara tentu saja merupakan fungsi parsial, karena hanya masuk akal untuk mencatat nilai-nilai variabel yang benar-benar terjadi. $s\, x = v$ $x$ $v$

Aksioma yang berlangsung

⟨ sementara b melakukan S, s ⟩ \Rightarrow ⟨ jika b kemudian S; sementara b melakukan S lain lewati, s ⟩

$\langle \texttt{while}\; b\; \texttt{do}\; S,s \rangle \Rightarrow \langle \texttt{if}\; b\; \texttt{then}\; S; \texttt{while}\; b\; \texttt{do}\; S \; \texttt{else skip},s \rangle$

hanya memberitahu kita bahwa kita membuka loop sementara ke dalam pernyataan kondisional, salah satu cabangnya berisi loop. Tidak ada variabel yang akan mengubah nilainya karena ini, dan karena alasan ini keadaan tidak berubah.

Hans Hüttel
sumber

10

Negara dapat berubah dalam langkah pengurangan berikutnya karena di sisi kanan

⟨ w h saya l e B d Hai S, σ ⟩ \to ⟨ saya f B t h e n (S; w h saya l e B d Hai S) e l s e s k saya hal, σ ⟩

$\langle while\ B\ do\ S, \sigma \rangle \quad\rightarrow\quad \langle if\ B\ then\ ( {\color{red}{S}};\ while\ B\ do\ S )\ else\ skip, \sigma\rangle$

yang -loop dijaga (diawali) oleh . Perhitungan dapat mengubah keadaan sehingga kondisi dapat dievaluasi menjadi . $while$ $S$ $S$ $B$ $\mathsf{false}$

Martin Berger
sumber

Jadi, ini berarti bahwa perubahan negara harus dinyatakan dalam aturan lain yang berpotensi mengurangi S dalam program konkret?

El Marce

@ Elce Ya. Saya sarankan untuk melihat contoh sederhana misalnya

dan lihat bagaimana ini bekerja.

x := 2; w h i l e x > 0 d o x := x - 1

$x := 2;\ while\ x > 0\ do\ x := x - 1$

Martin Berger

9

Negara tidak berubah ketika kita mempertimbangkan untuk memutuskan apakah untuk melakukan satu iterasi dari loop, tetapi dapat berubah nanti ketika kita menjalankan tubuh . Jadi, pada saat kita mempertimbangkan , bisa ada perubahan . $\sigma$ $B$ $S$ $B$ $\sigma$

Andrej Bauer
sumber

Penjelasan ini, walaupun pada dasarnya benar, tidak merujuk pada status apa (yaitu fungsi yang memberi tahu kita nilai-nilai varialbes) dan apa yang ditandakan oleh perubahan kondisi (yaitu bahwa nilai setidaknya satu perubahan variabel).

Hans Hüttel

Memang, tidak relevan apa negara atau bagaimana mereka diterapkan untuk tujuan jawaban saya. Penjelasannya tetap berlaku. Dan lagi pula, sebenarnya salah untuk mengatakan bahwa "keadaan benar-benar berfungsi" karena theat hanya satu cara untuk memodelkannya secara matematis. Ada beberapa model lain yang mungkin. Dan jangan sampai kita membingungkan model matematika dengan cara kerja perangkat keras.

Andrej Bauer

Tetapi pertanyaannya berkaitan dengan semantik operasional langkah-kecil tertentu, yang pengertian negara didefinisikan dengan baik.

Hans Hüttel

Saya tidak pernah mengatakan itu tidak benar. Saya hanya mengatakan bahwa komentar Anda tidak perlu, karena penjelasan saya berlaku tanpa menyebutkan secara eksplisit bagaimana model dimodelkan. Mungkin Anda mendeteksi bahwa OP tidak tahu bahwa keadaan adalah peta dari variabel ke nilai. Baik untuk Anda, jawaban Anda diterima, dan saya tidak. Selamat. Mengapa Anda sekarang memaksakan cara jawaban Anda pada saya adalah di luar pemahaman saya. Mengapa Anda merasa perlu untuk membuat jawaban saya seperti jawaban Anda? Jawaban saya masuk akal tanpa pernyataan yang menurut Anda perlu. Mungkin seseorang akan datang dengan mencari jawaban saya suatu hari nanti.

Andrej Bauer

Mengapa negara tetap tidak berubah dalam semantik operasional langkah kecil dari loop sementara?

Jawaban: