Semantik formal OCaml dalam Coq

14

Semantik dari sebagian besar OCaml, yang disebut OCamllight , diformalkan dalam HOL oleh Owens beberapa tahun yang lalu. Baru-baru ini, jenis semantik teoritis dari subset yang lebih kecil dari OCaml diimplementasikan di Nuprl oleh Kreitz, Hayden dan Hickey .

Apakah ada perkembangan serupa di Coq?

coq program-verification ocaml Andrea Asperti
sumber
Anda mungkin tertarik dengan CakeML: cakeml.org . Tapi aku bukan OCaml yang spesifik.
jmite

Jawaban:

12

Pernahkah Anda melihat tesis PhD Arthur Charguéraud, Formula Karakteristik untuk Verifikasi Program Mekanis ?

Daripada membangun sistem tipe dan semantik langkah kecil sebagai hubungan induktif, ia memberikan teknik untuk mengubah program Caml menjadi formula karakteristik. Ini pada dasarnya adalah generalisasi semantik transformator predikat untuk mendukung subset Ocaml yang sangat besar - terutama, termasuk gips yang tidak aman seperti Obj.magic. Mengutip dari tesisnya:

Saya telah fokus pada subset dari bahasa pemrograman OCaml, yang merupakan bahasa pemrograman tingkat tinggi berurutan, panggilan-menurut-nilai. Implementasi CFML saat ini mendukung inti λ-kalkulus, termasuk fungsi tingkat tinggi, rekursi, rekursi timbal balik, dan rekursi polimorfik. Ini mendukung tupel, konstruktor data, pencocokan pola, sel referensi, catatan dan array. Saya menyediakan perpustakaan Caml tambahan yang menambahkan dukungan untuk pointer nol dan pembaruan yang kuat.

Ini adalah pendekatan yang sangat menarik jika Anda ingin membuktikan program Caml tertentu yang benar (kurang begitu jika Anda tertarik dengan metatheory-nya).

Neel Krishnaswami
sumber
Jadi, jika saya mengerti benar, spesifikasi semantik Ocaml tertanam dalam sistem. Apakah mungkin untuk menginterpretasikan formula karakteristik dari (beberapa fungsi utama dari) sistem sebagai spesifikasi? Juga, saya kira sistem ini ditulis dalam OCaml. Apakah mungkin untuk menentukan dan membuktikan kebenarannya dalam sistem itu sendiri?
Andrea Asperti
Untuk program OCaml yang diberikan, rumus karakteristiknya dapat dianggap semantik denotasional, spesifikasi "paling tidak umum" yang dapat digunakan untuk membuktikan sifat-sifat yang diinginkan dari program. Jika Anda berbicara tentang "kebenaran" CFML itu sendiri, pertanyaannya adalah: berkenaan dengan alternatif semantik formal mana?
gasche
Aneh memiliki program yang seharusnya mengesahkan perangkat lunak dan yang perilakunya tidak dapat ditentukan :)
Andrea Asperti
@AndreaAsperti Apa yang Anda maksud dengan "tertanam dalam sistem"? Gagasan di balik formula karakteristik (CF) cukup mudah: memetakan program ke formula logis (biasanya pra dan pascakondisi) seperti formula yang secara tepat menggambarkan semantik program. Dengan kata lain dua program memenuhi CFs yang sama jika mereka tidak dapat dibedakan secara kontekstual. Peta dari program ke CF dilakukan dengan menginduksi struktur program, dan dapat menargetkan logika yang cukup ekspresif. A. Logika target Charguéraud target, tapi itu pilihan kontingen.
Martin Berger
1
@MartinBerger: makalah Guéneau et al hanya membuktikan kesehatan karena pra / posting turunan tidak mencirikan program yang mereka berasal. CF mereka berasal dari semantik tak tertulis dari CakeML, tetapi bahasa yang diketik memiliki kesetaraan pengamatan yang berbeda. (Untuk verifikasi praktis, ini tidak terlalu penting, dan lebih mudah.)
Neel Krishnaswami
8

Anda bisa tertarik dengan Implementasi Tersertifikasi ML Jacques Garrigue dengan Polimorfisme Struktural dan Tipe Rekursif , yang menetapkan kesehatan semantik statis dan dinamis serta properti inferensi tipe untuk bahasa ML dengan (rekursi dan) polimorfisme struktural, dengan demikian memformalkan salah satu sudut OCaml yang lebih maju (varian polimorfik dan tipe objek).

Yang mengatakan, pekerjaan ini lebih ditujukan untuk memverifikasi kesehatan bagian yang lebih maju dari sistem tipe daripada menutupi fitur set program OCaml yang ada. Saya pikir dalam hal mencoba membuktikan kebenaran dari program OCaml yang ada, CFML akan menjadi pilihan yang lebih baik.

gasche
sumber