Semantik Denotasional

Semantik denotasional menginterpretasikan program sebagai objek matematis, biasanya fungsi di atas domain terstruktur, memberikan penjelasan makna yang komposisional dan tidak bergantung pada mesin.

Definition

Semantik denotasional menetapkan objek matematis (denotasinya) untuk setiap program, yang didefinisikan secara komposisional dari denotasi bagian-bagiannya, dengan rekursi diinterpretasikan melalui titik-titik tetap terkecil dalam domain.

Scope

Topik ini mencakup pendekatan Scott-Strachey, di mana setiap frasa program menunjukkan elemen dari domain matematis. Ini mencakup teori domain, urutan parsial lengkap, fungsi kontinu, dan interpretasi titik-tetap terkecil dari rekursi, serta abstraksi penuh, yang berkaitan dengan seberapa dekat makna denotasional sesuai dengan perilaku yang dapat diamati.

Core questions

• Struktur matematis apa yang dapat memodelkan rekursi arbitrer dan non-terminasi?
• Bagaimana makna dibangun secara komposisional dari makna subprogram?
• Apa itu abstraksi penuh dan mengapa sulit dicapai?
• Bagaimana makna denotasional berhubungan dengan perilaku operasional?

Key theories

Teori domain dan semantik titik-tetap

Teori domain Scott menyediakan struktur terurut dan fungsi kontinu di mana definisi rekursif diinterpretasikan sebagai titik-titik tetap terkecil, memecahkan masalah pemberian makna pada program yang mereferensikan diri sendiri.

Abstraksi penuh

Studi Plotkin tentang LCF membingkai masalah abstraksi penuh tentang apakah kesetaraan denotasional bertepatan persis dengan kesetaraan observasional, mengungkap celah yang memotivasi penelitian lebih lanjut selama beberapa dekade.

Clinical relevance

Model denotasional memberikan referensi yang tepat dan komposisional untuk makna bahasa, mendukung penalaran tentang kesetaraan dan optimisasi program, serta menginformasikan desain fitur seperti rekursi dan fungsi tingkat tinggi. Teori domain juga menghubungkan bahasa pemrograman dengan matematika dan logika yang lebih luas.

History

Karya Strachey tentang deskripsi matematis bahasa dan konstruksi model domain oleh Scott pada tahun 1969 meluncurkan semantik denotasional, yang diformalkan dalam makalah mereka tahun 1971. Teori domain Scott berkembang sepanjang tahun 1970-an, dan analisis Plotkin terhadap LCF mengkristalkan masalah abstraksi penuh, yang mendorong perkembangan selanjutnya seperti semantik permainan.

Debates

Masalah abstraksi penuh

Pertanyaan sentral adalah apakah model denotasional dapat menangkap secara tepat perilaku yang dapat diamati dari suatu bahasa, tidak lebih dan tidak kurang; model domain klasik gagal dalam hal ini untuk bahasa sekuensial tingkat tinggi, mendorong model alternatif.

Key figures

• Dana Scott
• Christopher Strachey
• Gordon Plotkin
• Glynn Winskel

Seminal works

• scott1971
• scott1976
• plotkin1977
• winskel1993

Frequently asked questions

Apa itu domain dalam semantik denotasional?

Domain adalah struktur matematis, biasanya himpunan terurut parsial dengan batas rantai yang meningkat, yang menyediakan pengaturan di mana komputasi rekursif dan parsial dapat dimodelkan sebagai titik-titik tetap terkecil dari fungsi kontinu.

Apa itu abstraksi penuh?

Semantik dikatakan sepenuhnya abstrak ketika dua program memiliki denotasi yang sama persis ketika keduanya setara secara observasional, yang berarti model tersebut tidak membedakan program yang secara perilaku identik maupun menggabungkan program yang dapat dibedakan.