Pertanyaan apa yang dapat dijawab oleh semantik denotasional yang semantik operasional tidak dapat lakukan?

Saya akrab dengan semantik operasional (baik langkah kecil maupun besar) untuk mendefinisikan bahasa pemrograman. Saya tertarik untuk belajar semantik denotasional juga, tetapi saya tidak yakin apakah itu akan sepadan dengan usahanya. Apakah saya hanya akan mempelajari materi yang sama dari sudut pandang yang berbeda, atau ada wawasan yang hanya dapat saya peroleh dari memahami semantik denotasional?

Tidak ada kesepakatan nyata apa yang mencirikan semantik denotasional (lihat juga artikel ini ), kecuali bahwa itu harus komposisional . Itu berarti bahwa jika adalah fungsi semantik, memetakan program sesuai artinya, kira-kira seperti berikut harus menjadi kasus untuk semua konstruktor program -ary dan semua program , ..., (implisit mengasumsikan baik-typedness):$\newcommand{\SEMB}[1]{\lbrack\!\lbrack #1 \rbrack\!\rbrack} \SEMB{\cdot}$$n$$f$$M_1$$M_n$

$$\SEMB{f(M_1, ..., M_n)} = trans(f) (\SEMB{M_1}, ..., \SEMB{M_n})$$

Di sini adalah konstruktor yang sesuai dengan dalam domain semantik. Komposisionalitas mirip dengan konsep homomorfisme dalam aljabar.$trans(f)$$f$

Semantik operasional bukan komposisional dalam pengertian ini. Secara historis, semantik denotasional dikembangkan sebagian karena semantik operasional tidak komposisional. Mengikuti terobosan D. Scott's semantik orde-theoretik semantik -calculus, semantik paling denotasional dulunya adalah orde-teoretik. Saya membayangkan bahwa - terlepas dari kepentingan intelektual murni - semantik denotasional sebagian besar ditemukan karena pada waktu itu (1960-an):$\lambda$

1. Dulu sulit untuk alasan tentang semantik operasional.
2. Dulu sulit untuk memberikan semantik aksiomatik untuk bahasa non-sepele.

Sebagian dari masalahnya adalah bahwa gagasan tentang kesetaraan program tidak dipahami dengan baik seperti sekarang. Saya berpendapat bahwa kedua masalah telah diperbaiki ke tingkat yang substansial, (1) misalnya dengan teknik berbasis bisimilasi yang berasal dari teori proses (yang dapat dilihat sebagai bentuk spesifik semantik operasional) atau misalnya Pitts bekerja pada semantik operasional dan program kesetaraan, dan (2) oleh pengembangan misalnya logika pemisahan atau logika Hoare yang diturunkan sebagai versi yang diketik dari logika Hennessy-Milner melalui embedded bahasa pemrograman dalam huruf in-calculi yang diketik. Perhatikan bahwa logika program (= semantik aksiomatik) juga komposisional.

Cara lain untuk melihat semantik denotasional adalah bahwa ada banyak bahasa pemrograman dan mereka semua terlihat serupa, jadi mungkin kita dapat menemukan meta-bahasa yang sederhana namun universal, dan memetakan semua bahasa pemrograman dengan cara komposisi terhadap meta- bahasa. Pada 1960-an, ada anggapan bahwa beberapa mengetik -calculus adalah meta-bahasa. Sebuah gambar mungkin mengatakan lebih dari 1000 kata:$\lambda$

Apa keuntungan dari pendekatan ini? Mungkin masuk akal untuk melihatnya dari POV ekonomi. Jika kita ingin membuktikan sesuatu yang menarik tentang kelas program objek, kita memiliki dua opsi.

• Buktikan langsung pada level objek.

• Buktikan bahwa terjemahan ke tingkat-meta (dan kembali) 'mempertahankan' properti, dan kemudian membuktikannya untuk tingkat-meta, dan kemudian mendorong hasilnya kembali ke tingkat objek.

Biaya gabungan dari yang terakhir mungkin lebih tinggi dari biaya yang sebelumnya, tetapi biaya untuk membuktikan terjemahan dapat diamortisasi atas semua penggunaan di masa depan, sementara biaya untuk membuktikan properti untuk tingkat meta jauh lebih kecil daripada biaya pembuktian pada tingkat objek.

Pendekatan orde-teoretik orisinal untuk semantik denotasional sejauh ini tidak memenuhi janji ini, karena fitur bahasa yang rumit seperti orientasi objek, konkurensi dan komputasi terdistribusi belum diberikan semantik orde-teoritik orde yang tepat. Dengan "tepat" yang saya maksudkan semantik yang cocok dengan semantik operasional alami bahasa tersebut.

---

Apakah layak belajar semantik denotasional? Jika maksud Anda pendekatan orde-teoretis terhadap semantik denotasional, maka mungkin tidak, kecuali jika Anda ingin bekerja dalam teori bahasa pemrograman dan perlu memahami makalah yang lebih tua. Alasan lain untuk mempelajari pendekatan orde-teoretis pada semantik denotasional adalah keindahan dari pendekatan ini.

$O(p,\sigma)$$\sigma'$$\langle p, \sigma \rangle \to \sigma'$$\bot$$D(p)$$p$$O(p,\sigma)=D(p)(\sigma)$$S(p)$$\sigma\mapsto O(p,\sigma)$$D(p)$

$C:X \to X'$$S(C(p))=S'(p)$$p$$\sigma$$O(C(p),\sigma)=O'(p,\sigma)$$p$$D(C(p))=D'(p)$$\sigma$

Contoh konyol:

$C(p)=$$(q;q')$$(skip;q;skip;q';skip)$

$p$$C$