Saya telah membaca beberapa artikel tentang tipe dependen dan kontrak pemrograman. Dari sebagian besar yang saya baca, tampaknya kontrak diperiksa secara dinamis dan tipe dependen diperiksa secara statis.
Ada beberapa makalah yang membuat saya berpikir bahwa ada kemungkinan untuk memiliki kontrak yang diperiksa sebagian secara statis:
Dengan ini, tampaknya ada sejumlah besar tumpang tindih dan kategorisasi kontrak saya vs tipe dependen mulai menghilang.
Apakah ada sesuatu yang lebih dalam di kedua konsep yang saya lewatkan? Atau apakah ini benar-benar hanya kategori kabur yang mewakili konsep dasar yang sama?
Pada tataran praktis, kontrak adalah asersi. Mereka memungkinkan Anda memeriksa properti (bebas-kuantifikasi) dari eksekusi individual suatu program. Gagasan kunci di jantung pengecekan kontrak adalah gagasan menyalahkan - pada dasarnya, Anda ingin tahu siapa yang bersalah atas pelanggaran kontrak. Ini bisa berupa implementasi (yang tidak menghitung nilai yang dijanjikan) atau pemanggil (yang melewati fungsi semacam nilai yang salah).
Wawasan utama adalah bahwa Anda dapat melacak kesalahan menggunakan mesin yang sama dengan pasangan proyeksi-embedding dalam konstruksi batas terbalik dari teori domain. Pada dasarnya, Anda beralih dari bekerja dengan asersi ke bekerja dengan pasangan asersi, salah satunya menyalahkan konteks program dan yang lain menyalahkan program. Maka ini memungkinkan Anda membungkus fungsi tingkat tinggi dengan kontrak, karena Anda dapat memodelkan contravariance dari ruang fungsi dengan menukar pasangan asersi. (Lihat kertas Nick Benton, "Undoing Dynamic Typing" , misalnya.)
Tipe tergantung adalah tipe. Jenis menentukan aturan untuk menyatakan apakah program tertentu dapat diterima atau tidak. Akibatnya, mereka tidak memasukkan hal-hal seperti gagasan menyalahkan, karena fungsi mereka adalah untuk mencegah program yang berperilaku buruk ada sejak awal. Tidak ada yang perlu disalahkan karena hanya program yang terbentuk dengan baik yang bahkan merupakan ucapan tata bahasa. Secara pragmatis, ini berarti sangat mudah untuk menggunakan tipe dependen untuk berbicara tentang properti istilah dengan quantifiers (mis., Bahwa suatu fungsi bekerja untuk semua input).
Kedua pandangan ini tidak sama, tetapi keduanya saling terkait. Pada dasarnya, intinya adalah bahwa dengan kontrak, kita mulai dengan domain nilai universal, dan menggunakan kontrak untuk memotong segalanya. Tetapi ketika kami menggunakan tipe, kami mencoba menentukan domain nilai yang lebih kecil (dengan properti yang diinginkan) di depan. Jadi kita bisa menghubungkan keduanya melalui keluarga hubungan tipe-diarahkan (yaitu hubungan logis). Misalnya, lihat "Blame for All" karya Ahmed, Findler, Siek, dan Wadler , atau Reynolds "The The Meaning of Type: dari Intrinsik ke Semantik Ekstrinsik" .
Karena umumnya Anda tidak dapat menggunakan tes untuk menetapkan properti fungsi yang dikuantifikasi secara universal, itu saja.
Neel Krishnaswami
3
Kecuali jika quantifiers berkisar pada domain yang terbatas, dalam hal ini mereka dapat dipandang sebagai konjungsi dan disjungsi yang besar. Atau jika Anda ingin mendapatkan kemewahan, Anda dapat memeriksa beberapa jenis pernyataan terkuantifikasi, asalkan rentang quantiers dari jenis yang dapat ditelusuri Martin Escardo (yang dapat tak terbatas)
Andrej Bauer
2
@ Radu: Saya menyebut hal-hal seperti JML & co "program logics". Bahasa pernyataan logika program tidak terbatas pada istilah yang berasal dari bahasa program. Ini memungkinkan Anda mengesampingkan hal-hal seperti pernyataan nonterminating atau efek samping, yang tidak memiliki interpretasi logis yang bagus. (Namun, hal-hal seperti itu penting untuk pengecekan kontrak - lihat karya Pucella dan Tove baru-baru ini di ESOP tentang penggunaan kontrak negara yang penting untuk melacak properti linieritas.)
Neel Krishnaswami
2
Itu karena saya salah mengeja nama belakang Tov. Lihat "Kontrak Laku
Neel Krishnaswami
13
Masalah (cukup abstrak) yang menyerang kedua jenis dan kontrak adalah "Bagaimana memastikan bahwa program memiliki properti tertentu?". Ada ketegangan yang melekat di sini antara mampu mengekspresikan kelas properti yang lebih luas dan mampu memeriksa apakah suatu program memiliki atau tidak properti. Sistem tipe biasanya memastikan properti yang sangat spesifik (program tidak pernah crash dengan cara tertentu) dan memiliki algoritma pengecekan tipe. Di sisi lain, kontrak memungkinkan Anda menentukan berbagai properti yang sangat luas (katakanlah, output dari program ini adalah bilangan prima) tetapi tidak disertai dengan algoritma pemeriksaan.
Namun demikian, fakta bahwa tidak ada algoritma pengecekan kontrak (yang selalu berfungsi) tidak berarti bahwa hampir tidak ada algoritma pengecekan kontrak (yang cenderung bekerja dalam praktik). Saya akan merekomendasikan Anda melihat Spec # dan plugin Jessie dari Frama-C . Mereka berdua bekerja dengan menyatakan "program ini mematuhi kontrak ini" sebagai pernyataan dalam logika tingkat pertama melalui pembuatan kondisi verifikasi , dan kemudian meminta SMTpemecah untuk pergi mencoba untuk menemukan bukti. Jika pemecah gagal menemukan bukti, maka salah satu program salah atau, yah, pemecah gagal menemukan bukti yang ada. (Itulah sebabnya ini adalah "hampir" algoritma memeriksa kontrak.) Ada juga alat yang didasarkan pada eksekusi simbolis, yang secara kasar berarti bahwa "program ini mematuhi kontrak ini" dinyatakan sebagai sekelompok proposisi (dalam beberapa logika). Lihat, misalnya, jStar .
Karya Flanagan mencoba untuk mengambil yang terbaik dari kedua dunia sedemikian rupa sehingga Anda dapat dengan cepat memeriksa properti seperti tipe dan kemudian bekerja untuk sisanya. Saya tidak terlalu mengenal tipe hybrid, tetapi saya ingat penulis mengatakan bahwa motivasinya adalah untuk menghasilkan solusi yang membutuhkan lebih sedikit anotasi (daripada pekerjaan sebelumnya tentang ESC / Java lakukan). Namun, dalam beberapa hal, ada beberapa integrasi longgar antara jenis dan kontrak di ESC / Java (dan Spesifikasi #) juga: ketika memeriksa kontrak, pemecah masalah diberitahu bahwa pengecekan tipe berhasil sehingga dapat mengumpulkan informasi tersebut.
Kontrak dapat diperiksa secara statis. Jika Anda melihat karya lama Dana Xu tentang ESC / Haskell , ia dapat menerapkan pengecekan kontrak penuh pada waktu kompilasi, hanya mengandalkan pembuktian teorema untuk aritmatika. Pengakhiran diselesaikan dengan batas kedalaman sederhana jika saya ingat dengan benar:
Baik kontrak maupun jenisnya memungkinkan Anda untuk mewakili spesifikasi fungsi (gaya pra / pasca) Hoare pada fungsi. Keduanya dapat diperiksa baik secara statis pada waktu kompilasi atau secara dinamis saat runtime.
Tipe dependen memungkinkan Anda untuk menyandikan berbagai properti yang sangat luas dalam sistem tipe, jenis properti yang diharapkan oleh pemrogram kontrak. Ini karena mereka dapat bergantung pada nilai tipe. Tipe dependen memiliki kecenderungan untuk diperiksa secara statis meskipun saya percaya makalah yang Anda kutip melihat pendekatan alternatif.
Pada akhirnya, ada sedikit perbedaan. Saya pikir itu lebih dari tipe dependen adalah logika di mana Anda dapat mengekspresikan spesifikasi sedangkan kontrak adalah metodologi pemrograman di mana Anda mengekspresikan spesifikasi.
Agak menyesatkan untuk mengatakan bahwa anotasi gaya-Hoare dapat diperiksa secara statis. Jika logikanya FO, seperti biasanya, maka masalahnya tentu tidak dapat diputuskan. Tetapi, ya, saya tahu Anda bermaksud bahwa seseorang dapat mencoba dan bahkan berhasil dalam banyak situasi.
Radu GRIGore
1
Saya mendapat kesan bahwa menghasilkan bukti mungkin tidak dapat diputuskan, tetapi memeriksa bukti seharusnya. Banyak bahasa yang diketik secara dependen bergantung pada pengguna untuk memasok nilai-bukti dari penduduk tipe-teorema.
Jason Reich
Kamu benar. Tapi saya hidup di dunia otomatis, di mana pengguna biasanya tidak dimintai bukti.
Masalah (cukup abstrak) yang menyerang kedua jenis dan kontrak adalah "Bagaimana memastikan bahwa program memiliki properti tertentu?". Ada ketegangan yang melekat di sini antara mampu mengekspresikan kelas properti yang lebih luas dan mampu memeriksa apakah suatu program memiliki atau tidak properti. Sistem tipe biasanya memastikan properti yang sangat spesifik (program tidak pernah crash dengan cara tertentu) dan memiliki algoritma pengecekan tipe. Di sisi lain, kontrak memungkinkan Anda menentukan berbagai properti yang sangat luas (katakanlah, output dari program ini adalah bilangan prima) tetapi tidak disertai dengan algoritma pemeriksaan.
Namun demikian, fakta bahwa tidak ada algoritma pengecekan kontrak (yang selalu berfungsi) tidak berarti bahwa hampir tidak ada algoritma pengecekan kontrak (yang cenderung bekerja dalam praktik). Saya akan merekomendasikan Anda melihat Spec # dan plugin Jessie dari Frama-C . Mereka berdua bekerja dengan menyatakan "program ini mematuhi kontrak ini" sebagai pernyataan dalam logika tingkat pertama melalui pembuatan kondisi verifikasi , dan kemudian meminta SMTpemecah untuk pergi mencoba untuk menemukan bukti. Jika pemecah gagal menemukan bukti, maka salah satu program salah atau, yah, pemecah gagal menemukan bukti yang ada. (Itulah sebabnya ini adalah "hampir" algoritma memeriksa kontrak.) Ada juga alat yang didasarkan pada eksekusi simbolis, yang secara kasar berarti bahwa "program ini mematuhi kontrak ini" dinyatakan sebagai sekelompok proposisi (dalam beberapa logika). Lihat, misalnya, jStar .
Karya Flanagan mencoba untuk mengambil yang terbaik dari kedua dunia sedemikian rupa sehingga Anda dapat dengan cepat memeriksa properti seperti tipe dan kemudian bekerja untuk sisanya. Saya tidak terlalu mengenal tipe hybrid, tetapi saya ingat penulis mengatakan bahwa motivasinya adalah untuk menghasilkan solusi yang membutuhkan lebih sedikit anotasi (daripada pekerjaan sebelumnya tentang ESC / Java lakukan). Namun, dalam beberapa hal, ada beberapa integrasi longgar antara jenis dan kontrak di ESC / Java (dan Spesifikasi #) juga: ketika memeriksa kontrak, pemecah masalah diberitahu bahwa pengecekan tipe berhasil sehingga dapat mengumpulkan informasi tersebut.
sumber
Kontrak dapat diperiksa secara statis. Jika Anda melihat karya lama Dana Xu tentang ESC / Haskell , ia dapat menerapkan pengecekan kontrak penuh pada waktu kompilasi, hanya mengandalkan pembuktian teorema untuk aritmatika. Pengakhiran diselesaikan dengan batas kedalaman sederhana jika saya ingat dengan benar:
sumber
Baik kontrak maupun jenisnya memungkinkan Anda untuk mewakili spesifikasi fungsi (gaya pra / pasca) Hoare pada fungsi. Keduanya dapat diperiksa baik secara statis pada waktu kompilasi atau secara dinamis saat runtime.
Tipe dependen memungkinkan Anda untuk menyandikan berbagai properti yang sangat luas dalam sistem tipe, jenis properti yang diharapkan oleh pemrogram kontrak. Ini karena mereka dapat bergantung pada nilai tipe. Tipe dependen memiliki kecenderungan untuk diperiksa secara statis meskipun saya percaya makalah yang Anda kutip melihat pendekatan alternatif.
Pada akhirnya, ada sedikit perbedaan. Saya pikir itu lebih dari tipe dependen adalah logika di mana Anda dapat mengekspresikan spesifikasi sedangkan kontrak adalah metodologi pemrograman di mana Anda mengekspresikan spesifikasi.
sumber