Apa yang seharusnya dibuktikan dengan bukti kebenaran pengetikan?

Saya sudah pemrograman selama beberapa tahun, tetapi saya sangat tidak terbiasa dengan CS teoritis. Saya baru-baru ini mencoba mempelajari bahasa pemrograman, dan sebagai bagian dari itu, ketik pengecekan dan inferensi.

Pertanyaan saya adalah, jika saya mencoba menulis inferensi jenis dan memeriksa program untuk bahasa pemrograman, dan saya ingin membuktikan bahwa typechecker saya berfungsi, apa sebenarnya bukti yang saya cari?

Dalam bahasa sederhana, saya ingin pemeriksa tipe saya dapat mengidentifikasi kesalahan dalam sepotong kode yang mungkin terjadi saat runtime. Jika saya menggunakan sesuatu seperti Coq untuk mencoba membuktikan bahwa implementasi saya benar, apa yang sebenarnya akan "ditunjukkan oleh bukti kebenaran" ini?

coq type-inference proof-assistants Vivek Ghaisas
sumber

Mungkin Anda bisa mengklarifikasi jika Anda ingin tahu (1) apakah implementasi Anda menerapkan sistem pengetikan

diberikan , atau (2) apakah sistem pengetikan Anda

mencegah kesalahan yang menurut Anda seharusnya? Mereka adalah pertanyaan yang berbeda.

T

$T$

T

$T$

Martin Berger

@ MartinBerger: Ah, sepertinya saya telah melewatkan perbedaan itu. Pertanyaan saya yang sebenarnya mungkin dimaksudkan untuk menanyakan keduanya. Konteksnya adalah bahwa saya mencoba membangun sebuah bahasa, dan untuk itu saya sedang menulis typechecker. Dan orang-orang meminta saya untuk menggunakan algoritma yang dicoba dan diuji. Saya tertarik melihat betapa sulitnya untuk "membuktikan" algoritma dan typechecker yang saya gunakan "benar". Karena itu ambiguitas dalam pertanyaan saya.

Vivek Ghaisas

(1) benar-benar sebuah pertanyaan dalam verifikasi program dan tidak ada hubungannya dengan pengetikan. Hanya perlu menunjukkan bahwa implementasi Anda memenuhi spesifikasinya. Mengenai (2), pertama-tama tentukan apa artinya menjadi kesalahan tipe langsung (mis. Istilah seperti 2 + "hello"itu 'macet'). Setelah ini diformalkan, Anda kemudian dapat membuktikan teorema jenis kesehatan. Itu berarti bahwa tidak ada program yang dapat diketik yang dapat berkembang menjadi kesalahan ketik langsung. Secara formal, Anda membuktikan bahwa jika suatu program

dapat diketik, dan untuk setiap

: jika

menjalankan

langkah untuk menjadi

, maka

tidak memiliki kesalahan ketik langsung. (1/2)

M

$M$

n \geq

$n \geq$

M

$M$

n

$n$

N

$N$

N

$N$

Martin Berger

Ini biasanya dibuktikan dengan induksi pada

dan pada derivasi dari ketikan mengetik. (2/2)

n

$n$

Martin Berger

Terima kasih! Berdasarkan penjelasan Anda, sepertinya (2) memang yang saya cari. Bisakah Anda menjawabnya? (Dan mungkin tambahkan setiap detail yang menurut Anda mungkin berguna.) Saya akan menerimanya sebagai jawabannya! :)

Vivek Ghaisas

Jawaban:

Pertanyaannya dapat ditafsirkan dalam dua cara:

Apakah implementasi tidak menerapkan sistem pengetikan diberikan ? $T$
Apakah sistem pengetikan memang mencegah kesalahan yang menurut Anda seharusnya? $T$

Yang pertama sebenarnya adalah pertanyaan dalam verifikasi program dan tidak ada hubungannya dengan pengetikan. Hanya perlu menunjukkan bahwa implementasi Anda memenuhi spesifikasinya, lihat jawaban Andrej.

Biarkan saya berbicara tentang pertanyaan selanjutnya. Seperti yang dikatakan Andrej, dari sudut pandang abstrak, sistem pengetikan tampaknya memberlakukan properti pada program. Dalam praktiknya, sistem pengetikan Anda berupaya mencegah terjadinya kesalahan, yang berarti bahwa program yang diketikkan tidak boleh menunjukkan kelas kesalahan yang diminati. Untuk menunjukkan bahwa melakukan apa yang menurut Anda seharusnya, Anda harus melakukan dua hal. $T$ $T$

Pertama, Anda menetapkan secara formal apa artinya bagi program untuk memiliki kesalahan pengetikan segera . Ada banyak cara ini dapat didefinisikan - terserah Anda. Biasanya kami ingin mencegah program seperti 2 + "hello". Dengan kata lain, Anda perlu mendefinisikan subset program, menyebutnya Buruk , yang berisi persis program dengan kesalahan pengetikan langsung.
$\Gamma \vdash M : \alpha.$ $M$ $\alpha$ $\Gamma$

$\Gamma \vdash M : \alpha$ $M \rightarrow \cdots \rightarrow N$ $N \notin$

Cara membuktikan teorema ini bergantung pada perincian bahasa, sistem pengetikan, dan pilihan Anda yang Buruk .

$M$ $M \rightarrow N$ $M$

$\Gamma \vdash M : \alpha$ $M \rightarrow N$ $\Gamma \vdash N : \alpha$
$\Gamma \vdash M : \alpha$ $M$

Perhatikan bahwa tidak semua sistem pengetikan memiliki "pengurangan subjek", misalnya jenis sesi. Dalam hal ini, teknik bukti yang lebih canggih diperlukan.

Martin Berger
sumber

Itu pertanyaan yang bagus! Itu menanyakan apa yang kita harapkan dari mengetik dalam bahasa yang diketik.

Catatan pertama bahwa kita dapat mengetikkan bahasa pemrograman apa pun dengan unitype : cukup pilih satu huruf, ucapkan U, dan katakan bahwa setiap program memiliki tipe U. Ini tidak terlalu berguna, tetapi itu benar.

$e$ $A$ $e$ $A$ $A$ int

Tidak ada akhir dari seberapa ekspresif tipe Anda. Pada prinsipnya mereka bisa berupa pernyataan logis apa saja, mereka bisa menggunakan teori kategori dan yang lainnya, dll. Sebagai contoh, tipe dependen akan membiarkan Anda mengekspresikan hal-hal seperti "fungsi ini memetakan daftar ke daftar sehingga outputnya adalah input yang diurutkan". Anda dapat melangkah lebih jauh, saat ini saya sedang mendengarkan ceramah tentang "logika pemisahan bersamaan" yang memungkinkan Anda untuk berbicara tentang bagaimana program bersamaan bekerja dengan keadaan bersama. Barang mewah.

Seni mengetik dalam desain bahasa pemrograman adalah salah satu penyeimbangan antara ekspresif dan kesederhanaan :

tipe yang lebih ekspresif memungkinkan kita untuk menjelaskan lebih detail (untuk diri kita sendiri dan kepada kompiler) apa yang seharusnya terjadi
tipe yang lebih sederhana lebih mudah dipahami dan dapat diotomatisasi dengan lebih mudah di kompiler. (Orang-orang datang dengan tipe yang pada dasarnya memerlukan asisten bukti dan input pengguna untuk melakukan pengecekan tipe.)

Kesederhanaan tidak dapat diremehkan, karena tidak setiap programmer memiliki gelar PhD dalam teori bahasa pemrograman.

Jadi, mari kita kembali ke pertanyaan Anda: bagaimana Anda tahu bahwa sistem tipe Anda baik ? Nah, buktikan teorema yang menunjukkan tipe Anda menjadi seimbang. Akan ada dua jenis teorema:

Teorema yang mengatakan bahwa tipe Anda berguna . Mengetahui bahwa suatu program memiliki tipe harus menyiratkan beberapa jaminan, misalnya bahwa program tersebut tidak akan macet (itu akan menjadi teorema Keselamatan ). Keluarga teorema lain akan menghubungkan tipe-tipe tersebut ke model semantik sehingga kita dapat mulai menggunakan matematika nyata untuk membuktikan hal-hal tentang program kita (itu akan menjadi teorema Kecukupan , dan banyak lainnya). Unitype di atas buruk karena tidak memiliki teorema yang berguna.
Teorema yang mengatakan bahwa tipe Anda sederhana . Yang mendasar adalah dapat diputuskan apakah ekspresi yang diberikan memiliki tipe tertentu. Fitur kesederhanaan lainnya adalah memberikan algoritma untuk menyimpulkan suatu tipe. Teorema lain tentang kesederhanaan adalah: bahwa suatu ekspresi memiliki paling banyak satu jenis, atau bahwa suatu ekspresi memiliki jenis utama (yaitu, yang "terbaik" di antara semua jenis yang dimilikinya).

Sulit untuk lebih spesifik karena jenis adalah mekanisme yang sangat umum. Tapi saya harap Anda tahu untuk apa Anda menembak. Seperti kebanyakan aspek desain bahasa pemrograman, tidak ada ukuran keberhasilan mutlak. Sebaliknya, ada ruang kemungkinan desain, dan yang penting adalah memahami di mana di ruang Anda berada, atau ingin berada.

Andrej Bauer
sumber

Terima kasih atas jawaban terinci itu! Namun, saya masih tidak yakin tentang jawaban atas pertanyaan saya. Sebagai contoh nyata, mari kita ambil C - bahasa yang diketik secara statis dengan sistem tipe yang cukup sederhana. Jika saya menulis typechecker untuk C, bagaimana saya membuktikan bahwa typechecker saya "benar"? Bagaimana jawaban ini berubah jika saya malah menulis pemeriksa tipe untuk Haskell, katakanlah HM? Bagaimana saya sekarang bisa membuktikan "kebenaran"?

Vivek Ghaisas

T

$T$

e

$e$

A

$A$

T

$T$

e

$e$

A

$A$

Saya akan merekomendasikan melakukan 2. dan 3. sebagai kombinasi. Juga, lihat di CompCert .

Andrej Bauer

T

$T$

e

$e$

A

$A$

e

$e$

A

$A$

e

$e$

A

$A$

A

$A$

e

$e$

Ada beberapa hal berbeda yang bisa Anda maksud dengan "buktikan bahwa typechecker saya berfungsi". Yang, saya kira, adalah bagian dari pertanyaan Anda;)

Separuh dari pertanyaan ini membuktikan bahwa teori tipe Anda cukup baik untuk membuktikan sifat apa pun tentang bahasa tersebut. Jawaban Andrej menangani masalah ini dengan sangat baik. Bagian lain dari pertanyaannya adalah — mengasumsikan bahasa dan sistem tipenya sudah diperbaiki — bagaimana Anda bisa membuktikan bahwa pemeriksa tipe Anda sebenarnya mengimplementasikan sistem tipe dengan benar? Ada dua perspektif utama yang bisa saya lihat di sini.

Salah satunya adalah: bagaimana kita bisa percaya bahwa beberapa implementasi tertentu sesuai dengan spesifikasinya? Tergantung pada tingkat jaminan yang Anda inginkan, Anda mungkin senang dengan rangkaian uji yang besar, atau Anda mungkin menginginkan semacam verifikasi formal, atau lebih mungkin gabungan keduanya . Sisi positif dari perspektif ini adalah bahwa itu benar-benar menyoroti pentingnya menetapkan batasan pada klaim yang Anda buat: apa sebenarnya arti "benar"? bagian mana dari kode yang diperiksa, vs bagian mana yang dianggap benar-benar TCB? dll. Kelemahannya adalah bahwa berpikir terlalu keras tentang hal ini akan menyebabkan lubang kelinci filosofis turun - well, "downside" jika Anda tidak menikmati lubang kelinci itu.

Perspektif kedua adalah pandangan yang lebih matematis tentang kebenaran. Ketika berhadapan dengan bahasa dalam matematika, kita sering membuat "model" untuk "teori" kita (atau sebaliknya) dan kemudian mencoba membuktikan: (a) semua yang dapat kita lakukan dalam teori yang dapat kita lakukan dalam model, dan (b) semua yang dapat kita lakukan dalam model dapat kita lakukan dalam teori. (Ini adalah Kesehatan dan Kelengkapanteorema. Yang mana yang tergantung pada apakah Anda "memulai" dari teori sintaksis atau dari model semantik.) Dengan pola pikir ini kita dapat menganggap implementasi pemeriksaan tipe Anda sebagai model tertentu untuk teori tipe yang dimaksud. Jadi, Anda ingin membuktikan korespondensi dua arah ini antara apa yang bisa dilakukan oleh implementasi Anda dan apa yang menurut teori Anda harus bisa lakukan. Sisi positif dari perspektif ini adalah bahwa itu benar-benar berfokus pada apakah Anda telah membahas semua kasus sudut, apakah implementasi Anda lengkap dalam arti tidak meninggalkan program apa pun yang seharusnya diterima sebagai jenis-aman, dan apakah implementasi Anda masuk akal rasa tidak membiarkan dalam program apa pun ia harus menolak sebagai salah ketik. Kelemahannya adalah bukti korespondensi Anda cenderung terpisah dari implementasinya sendiri,

wren romano
sumber

Saya tidak yakin saya bisa setuju dengan "terbalik dari perspektif ini adalah bahwa itu benar-benar berfokus pada apakah Anda sudah membahas semua kasus sudut", terutama jika modelnya hanya suara, tetapi tidak lengkap. Saya akan mengusulkan perspektif yang berbeda: melalui model adalah teknik bukti kontingen yang Anda gunakan untuk berbagai alasan, misalnya karena modelnya lebih sederhana. Tidak ada yang lebih bermartabat secara filosofis tentang menjalani model - pada akhirnya Anda ingin tahu tentang eksekusi aktual dan perilakunya.

Martin Berger

Saya pikir "model" dan "teori" dimaksudkan dalam arti luas, dan kami hanya menekankan pentingnya mencoba membangun korespondensi dua arah melalui "teorema kelengkapan + kelengkapan". (Saya juga berpikir ini penting, dan membuat komentar untuk posting Andrej.) Memang benar bahwa dalam beberapa situasi kita hanya akan dapat membuktikan teorema kesehatan (atau teorema kelengkapan, tergantung pada perspektif Anda), tetapi memiliki kedua arah dalam pikiran adalah kendala metodologis yang berguna.

Noam Zeilberger

@NoamZeilberger "Pertanyaannya adalah," kata Martin, "apakah Anda dapat membuat kata-kata berarti banyak hal yang berbeda."

Martin Berger

Ketika saya belajar tentang sistem pengetikan dan semantik bahasa pemrograman, saya menemukan kesadaran bahwa model hanyalah teknik pembuktian tentang semantik operasional, alih-alih tujuan itu sendiri, secara bebas membebaskan.

Martin Berger

Menghubungkan berbagai model melalui kesehatan & kelengkapan adalah metodologi ilmiah penting untuk transfer wawasan.

Martin Berger