Apa teknik formal umum untuk membuktikan kode fungsional yang benar?

10

Saya ingin memberikan bukti untuk bagian dari program Haskell yang saya tulis sebagai bagian dari tesis saya. Namun sejauh ini, saya gagal menemukan referensi yang bagus.

Buku pengantar Graham Hutton, Programming in Haskell ( Google Books ) —yang saya baca sambil mempelajari Haskell — menyentuh beberapa teknik untuk alasan tentang program seperti

  • penalaran yang sama
  • menggunakan pola yang tidak tumpang tindih
  • daftar induksi

dalam bab 13 tetapi tidak terlalu mendalam.

Adakah buku atau artikel yang bisa Anda rekomendasikan yang memberikan gambaran yang lebih rinci tentang teknik pembuktian formal untuk Haskell, atau kode fungsional lainnya?

reference-request proof-techniques functional-programming books software-verification FK82
sumber

Jawaban:

5

Salah satu metode de facto untuk membuktikan hasil dalam pemrograman fungsional adalah melalui kelompok Richard Bird.

Secara khusus, Anda meminta pendekatan yang mendalam atau setidaknya lebih komprehensif untuk penalaran persamaan dan induksi daftar dan ini disediakan dalam Kuliah tentang Pemrograman Fungsional Konstruktif .

Lebih umum, teks "Aljabar Pemrograman", oleh Bird dan de Moor, juga membahas tentang kebenaran algoritma fungsional seperti optimisasi dan masalah pemrograman dinamis.

Jika Anda menemukan sumber daya lain yang bermanfaat untuk masalah ini, harap sebutkan dan mungkin kami dapat mengubah posting ini menjadi wiki.

Musa Al-hassy
sumber
Terima kasih! Tentu, jika saya menemukan lebih banyak sumber daya, saya akan memastikan untuk menambahkannya ke posting saya.
FK82
6

Anda bisa mulai dengan

Topik meliputi konsep dasar logika, pembuktian teorema berbantuan komputer, asisten bukti Coq, pemrograman fungsional, semantik operasional, logika Hoare, dan sistem tipe statis. Eksposisi ini ditujukan untuk pembaca yang luas, mulai dari mahasiswa tingkat sarjana hingga mahasiswa dan peneliti PhD. Tidak ada latar belakang khusus dalam logika atau bahasa pemrograman yang diasumsikan, meskipun tingkat kematangan matematika akan membantu.

Anda dapat melewati (atau membaca sekilas) bagian-bagian teori bahasa pemrograman dan hanya belajar bagaimana menangani bukti formal mulai dari Kata Pengantar hingga IndPrinciples. Buku ini ditulis dengan sangat baik dan mencerahkan.

Maka Anda mungkin ingin melanjutkan

Dalam volume ini Anda akan belajar bagaimana menentukan dan memverifikasi (membuktikan kebenaran) algoritma penyortiran, pohon pencarian biner, pohon pencarian biner seimbang, dan antrian prioritas. Sebelum menggunakan buku ini, Anda harus memiliki pemahaman tentang algoritma dan struktur data ini, yang tersedia di buku teks algoritma sarjana standar. Anda harus memahami semua materi dalam Yayasan Perangkat Lunak Volume 1 (Yayasan Logika)

Catatan peringatan: VFA masih dalam rilis beta!

Anton Trunov
sumber
(Tautan kedua Anda mengarahkan ke tempat yang salah.) Juga, ada Pemrograman Fungsional Terverifikasi di Agda ; yang menggunakan Agda, secara formal bahasa pemrograman tetapi menggunakan unicode dan lebih dekat dengan notasi matematika.
Musa Al-hassy
Diperbaiki, terima kasih. Ya, saya sudah membaca VFPiA, tetapi ini tidak sesuai dengan selera saya.
Anton Trunov
Terima kasih atas jawaban Anda! Saya pikir ada kesalahpahaman. Saya tidak mencari teknik fungsional untuk membuktikan algoritma (seperti asisten bukti), tetapi untuk teknik membuktikan kode fungsional (misalnya untuk membuktikan implementasi fungsional dari algoritma yang diberikan benar) @ MusaAl-hassy jawaban sangat dekat dengan saya jawaban yang diinginkan. Jika saya melewatkannya dan buku-buku yang Anda kutip juga mencakup aspek ini, maukah Anda menambahkan bab-bab yang relevan?
FK82
@ FK82 Ini adalah Theorem app_assoc : ∀ l1 l2 l3 : natlist, (l1 ++ l2) ++ l3 = l1 ++ (l2 ++ l3)dari bab Daftar . Apakah contoh ini terlihat seperti hal yang Anda minati? Mereka mulai dengan pemrograman fungsional dalam Coq, tetapi kemudian beralih ke penalaran tentang sifat-sifat program fungsional. Bab-bab dari Pendahuluan hingga IndPrinciples membahas keduanya, dan saya akan mengatakan pemrograman dan penalaran terjalin di sana.
Anton Trunov
1
@ FK82 (1) Saya sangat setuju dengan komentar ini . (2) Anda mungkin ingin melihat buku "Berpikir Berfungsi dengan Haskell" (2015) oleh R. Bird. Buku ini memiliki banyak contoh alasan tentang Haskell. (3) Juga, "Desain Algoritma Fungsional Mutiara" (2010) oleh penulis yang sama mungkin dapat membantu Anda.
Anton Trunov
5

Ternyata sumber yang sangat baik dari teknik bukti dan contoh untuk membuktikan hal-hal tentang bahasa fungsional murni adalah asisten bukti yang biasanya termasuk sebagai bagian dari bahasa spesifikasi mereka bahasa fungsional murni di mana dimungkinkan untuk bernalar secara adil.

Seseorang mungkin ingin membaca buku seperti Programing Bersertifikat dengan Tipe Ketergantungan untuk pengantar mendalam tentang jenis penalaran ini dalam asisten bukti spesifik, yaitu Coq.

cody
sumber
Terima kasih! Saya sebenarnya mencari teknik khusus di Haskell . Posting saya diedit untuk memasukkan semua kode fungsional, tetapi itu jauh di atas maksud saya.
FK82
1
Saya tidak mengetahui sistem yang dirancang untuk memverifikasi Haskell secara khusus, tetapi saya akan mencatat bahwa 1) Inti fungsional Coq (dan Agda) pada dasarnya tidak dapat dibedakan dari Haskell (kecuali untuk pembatasan fungsi total ) dan 2) Program diverifikasi dalam Coq dan Agda dapat diekstraksi ke Haskell (meskipun saya percaya ekstraksi ke Haskell lebih baik didukung di Agda, di mana Coq lebih Ocaml-sentris)
cody
Senang mendengarnya! Namun ini menyiratkan bahwa saya menulis ulang program saya (atau bagian yang relevan) dalam Coq atau Agda. Saya pikir itu tidak masuk akal dalam kasus saya.
FK82
Ada beberapa "ujung depan" yang sangat eksperimental yang mencoba mengubah Haskell menjadi Isabelle atau langsung membuktikan kesetaraan menggunakan Isabelle, tetapi saya tidak akan memiliki terlalu banyak stok dalam jatuh tempo. Saya pikir menulis ulang kode pada akhirnya akan kurang berhasil.
cody
4

Saya menyarankan untuk menggunakan logika program. Mereka menangani efek dengan jauh lebih baik daripada sistem mengetik.

Ada banyak logika program untuk bahasa fungsional. Ini menjadi menarik dengan efek. Lihat misalnya Penalaran Logis untuk Fungsi Tingkat Tinggi dengan Negara Bagian .

Pekerjaan oleh Arthur Charguéraud mengintegrasikan pendekatan logika program dengan asisten bukti, lihat misalnya halaman ikhtisar ini .

Martin Berger
sumber