Mengapa subtyping behavorial tidak dapat ditentukan?

12

Pekerjaan Liskov di bidang ini berfokus pada subtyping perilaku, yang selain jenis keamanan sistem yang dibahas dalam artikel ini juga mensyaratkan bahwa subtipe mempertahankan semua invarian yang dijamin oleh supertipe dalam beberapa kontrak. [3] Definisi subtyping ini umumnya tidak dapat ditentukan, sehingga tidak dapat diverifikasi oleh pemeriksa tipe.

Dari: http://www.wikiwand.com/en/Subtyping#/Function_types

type-systems subtypes q126y
sumber

Jawaban:

24

Biarkan kontrak operasi oTipe Tmenghentikan semua input. Sekarang putuskan apakah operasi osubtipe S <: Tmemenuhi kontrak itu: Anda baru saja menyelesaikan Masalah Pemutusan .

Lebih umum, S::oharus menghitung fungsi yang sama seolah- T::oolah S <: T. Memutuskan apakah dua program menghitung fungsi yang sama disebut Masalah Fungsi dan setara dengan menyelesaikan Masalah Pemutusan.

Secara umum, statis memutuskan setiap properti runtime non-sepele hampir selalu setara dengan Soal yang terputus-putus.

Jörg W Mittag
sumber
3
Baris terakhir itu berhasil. Saat Anda ingin membuktikan sebuah properti tentang apa yang mungkin dilakukan program dalam pengaturan perilaku Anda melangkah ke hal yang mustahil. Jenis sistem alasan dan alat analisis statis bekerja adalah bahwa mereka memperlakukan bahasa yang berbeda (dari jenis program, dari ruang lingkup variabel dalam program dan sebagainya) dan bukan sifat-sifat bagaimana program berjalan secara langsung.
Benjamin Gruenbaum
5
@BenjaminGruenbaum Jorg jawaban dan komentar Anda benar tetapi ada kehalusan untuk itu saya ingin menjelaskan. Seringkali mungkin untuk membuktikan properti tentang program tertentu . Hanya saja, tidak ada algoritma yang dapat Anda ikuti secara membabi buta yang akan bekerja untuk semua program. Pertimbangkan metode ini ditulis dalam Java: BigInteger sum(int[] arr) { BigInteger sum = BigInteger.ZERO; for (int x: arr) sum = sum.add(BigInteger.valueOf(x)); return sum; }Tidak sulit untuk membuktikan bahwa metode tertentu selalu mengembalikan jumlah elemen array integer dan tidak melakukan hal lain (asalkan argumennya bukan nol).
Doval
1
Dan ketika itu tidak setara dengan masalah penghentian, sering kali bahkan lebih buruk . Karena tidak mungkin belum cukup sulit.
user2357112 mendukung Monica
2
Atau dengan kata lain Doval (blunt), inilah mengapa bahasa lengkap non- turunan menarik dan bermanfaat. Anda sering tidak membutuhkan Turing-kelengkapan (tentu saja pada tingkat modul) untuk pekerjaan nyata.
Leushenko
@Doval: Poin yang sangat bagus. Meskipun benar bahwa Anda tidak dapat memiliki algoritma yang membuktikan penghentian dan / atau kebenaran program acak, dimungkinkan untuk menulis program sedemikian rupa sehingga Anda dapat membuktikan kebenarannya.
Giorgio
12

Karena hampir setiap pertanyaan tentang perilaku program tidak dapat diputuskan. Dengan teorema Rice , setiap masalah keputusan berupa:

Beberapa program menghitung fungsi yang memiliki properti ini, program lain menghitung fungsi yang tidak memiliki properti ini. Diberikan P program, apakah fungsi yang dihitung oleh P memiliki properti yang disebutkan di atas atau tidak?

tidak dapat ditentukan. Jadi, misalnya, Anda tidak selalu dapat membedakan kode yang menghitung kuadrat input dari kode yang tidak. Meskipun dalam kasus-kasus sederhana, seringkali dimungkinkan untuk membuktikan bahwa suatu fungsi tidak atau tidak melakukannya, tidak ada prosedur umum yang berfungsi untuk semua program.

Hampir semua invarian perilaku yang menarik berada di bawah teorema Rice, karena pernyataan-pernyataan itu jarang (jika pernah) berbicara tentang seperti apa metode tersebut secara internal, hanya apa yang dikembalikan dan efek samping apa yang diakibatkannya dalam menanggapi input tertentu.


sumber
3
Anda dapat mengklarifikasi sedikit: Ini bukan berarti bahwa satu program tertentu, tidak peduli seberapa patologis, dapat menolak semua analisis, tetapi bahwa, untuk analisis tertentu, ada setidaknya satu program yang tidak dapat dikategorikan dengan benar.
Nathan Tuggy