Memprogram alat prototipe semantik bahasa

11

Apakah ada alat untuk membuat prototipe semantik bahasa pemrograman dan sistem tipe dan itu juga memungkinkan untuk semacam pengecekan model properti standar, seperti tipe kesehatan?

Saya menanyakan hal ini, karena saya membaca buku tentang Paduan dan menyediakan fungsionalitas tepat yang saya inginkan, tetapi untuk model yang diungkapkan menggunakan logika relasional.

Saya mengetahui Ott , tetapi tidak memiliki kemampuan "pengecekan model" semacam ini, karena berfokus pada menghasilkan kode untuk sistem asisten bukti.

Referensi apa pun tentang keberadaan alat tersebut akan menyenangkan.

reference-request programming-languages semantics model-checking Rodrigo Ribeiro
sumber
1
Ott adalah langkah pertama, maka Anda melakukan pengecekan model di asisten bukti favorit Anda.
Gilles 'SANGAT berhenti menjadi jahat'
@Gilles: Oke, tetapi poin dari alat pengecekan model adalah bahwa ia menghasilkan seluruh rangkaian elemen dengan ukuran tertentu untuk memeriksa apakah properti tersebut memang berlaku untuk mereka. Dengan cara ini, saya harus membuat kode bagian generasi ini untuk setiap bahasa yang ditentukan. Tahukah Anda jika ada cara untuk mengotomatiskan langkah generasi ini?
Rodrigo Ribeiro
Secara teknis, Anda bisa melakukan ini di asisten bukti (setidaknya di satu seperti Coq) tetapi mungkin akan sangat lambat. Asisten bukti diarahkan pada bukti yang dibantu manusia daripada secara otomatis mencoba jutaan cara untuk memecahkan masalah. Jika Anda ingin menggunakan kembali Ott, Anda bisa menambahkan backend untuk pemeriksa model favorit Anda.
Gilles 'SANGAT berhenti menjadi jahat'

Jawaban:

8

Meskipun ada kerangka kerja yang dibuat khusus untuk keperluan prototyping bahasa pemrograman (termasuk semantik, tipe sistem, evaluasi, serta memeriksa properti mereka), pilihan terbaik tergantung pada kasus khusus Anda dan kebutuhan spesifik.

Karena itu, ada beberapa alternatif (mungkin tidak begitu berbeda) yang mungkin Anda ambil (termasuk yang sudah Anda sebutkan):

  • menggunakan bahasa / kerangka kerja khusus yang dirancang untuk membuat dan membuat prototipe bahasa baru: sebagai contoh, Redex [1], bahasa khusus domain yang disematkan dalam Racket untuk menentukan dan memeriksa semantik (operasional) semantik bahasa pemrograman, yang, diberikan definisi tentang bahasa, memudahkan penanganan tugas seperti pengaturan huruf (dalam Lateks), memeriksa jejak pengurangan, tes unit dan pengujian acak (misalnya untuk memeriksa pengetikan)
  • menggunakan bahasa pemodelan umum yang menawarkan mendefinisikan dan melakukan analisis tertentu dengan mudah, asalkan mereka dapat menangkap bahasa tertentu pada tingkat yang dibutuhkan; Paduan [2] adalah contoh dari pendekatan semacam itu: meskipun cukup umum dan fleksibel, bahasa dapat dimodelkan sebagai hubungan antar negara, sedangkan dukungan untuk pengecekan model (misalnya evaluasi dalam bahasa tersebut) datang secara gratis setelah semantik diekspresikan dengan model relasi (misalnya beberapa ide untuk pemodelan semantik bahasa dapat ditemukan di [3])
  • menanamkan bahasa untuk memeriksa propertinya menggunakan teorema teorema; contoh akan mendefinisikan bahasa serta semantiknya dengan menanamkannya dalam sistem bukti seperti Coq [4] (rincian lebih lanjut tentang pendekatan ini, serta diskusi dan demonstrasi perbedaan antara embedding mendalam dan dangkal dalam Coq diberikan dalam [ 5])
  • menggunakan Ott (seperti yang telah disebutkan, dengan semangat yang sama dengan Redex, tetapi memberikan bahasa definisi baru daripada tertanam); Ott memungkinkan Anda untuk mendefinisikan bahasa pemrograman dalam notasi yang mudah digunakan, dan menghasilkan pengaturan huruf dan definisi dalam sistem bukti (biasanya dengan penyisipan dalam), di mana sebagian besar pemeriksaan (yaitu bukti) perlu dilakukan secara manual
  • mengembangkan bahasa dan semantiknya, serta pemeriksaan yang sesuai (misalnya sebagai tes) "dari awal" dalam bahasa pemrograman tujuan umum dan terjemahan ke dalam sistem lain jika perlu, untuk keperluan pemeriksaan (beberapa bahasa, seperti Leon [6], termasuk built-in verifier, yang memungkinkan secara otomatis membuktikan properti tertentu dan membuat pendekatan ini mirip dengan menanamkan dalam sistem bukti)

Perhatikan bahwa ada pertukaran antara seberapa mudah menggunakan kerangka / alat (misalnya semudah meletakkan definisi di atas kertas atau dalam Lateks) dan seberapa kuat mekanisme untuk memeriksa properti tentang bahasa tersebut (misalnya menyematkan bahasa dalam pepatah teorema dapat memungkinkan memeriksa properti yang sangat rumit).

[1] Casey Klein, John Clements, Christos Dimoulas, Carl Eastlund, Matthias Felleisen, Matthew Flatt, Jay A. McCarthy, Jon Rafkind, Sam Tobin-Hochstadt, dan Robert Bruce Findler. Jalankan Penelitian Anda: Tentang Efektivitas Mekanisasi Ringan. POPL, 2012.

[2] Daniel Jackson. Paduan: notasi pemodelan objek ringan. TOSEM, 2002.

[3] Greg Dennis, Felix Chang, Daniel Jackson. Verifikasi Modular Kode dengan SAT. ISSTA, 2006

[4] Coq sistem manajemen bukti formal

[5] Penalaran Formal Tentang Program. Adam Chlipala, 2016

[6] Leon sistem otomatis untuk memverifikasi, memperbaiki, dan mensintesis program Scala fungsional

ivcha
sumber