Apa yang kita peroleh dengan memiliki “tipe ketergantungan”?

Saya pikir saya mengerti ketergantungan mengetik (DT) dengan benar, tetapi jawaban untuk pertanyaan ini: /cstheory/30651/why-was-there-a-need-for-martin-l%C3% Teori B6f-to-create-intuitionistic-type membuat saya berpikir sebaliknya.

Setelah membaca tentang DT dan mencoba untuk memahami apa itu DT, saya mencoba untuk bertanya-tanya, apa yang kita dapat dari gagasan DT ini? Mereka tampaknya lebih fleksibel dan kuat daripada sekadar mengetik lambda calculus (STLC), meskipun saya tidak bisa mengerti persis "bagaimana / mengapa".

Apa yang bisa kita lakukan dengan DT yang tidak dapat dilakukan dengan STLC? Sepertinya menambahkan DT membuat teorinya lebih rumit, tetapi apa untungnya?

Dari jawaban pertanyaan di atas:

Tipe dependen diusulkan oleh de Bruijn dan Howard yang ingin memperluas korespondensi Curry-Howard dari proposisional ke logika orde pertama.

Ini tampaknya masuk akal pada tingkat tertentu, tetapi saya masih tidak dapat memahami gambaran besar "bagaimana / mengapa"? Mungkin contoh secara eksplisit menunjukkan ekstensi korespondensi CH ini dengan logika FO dapat membantu mencapai titik awal dalam memahami apa masalah besar dengan DT? Saya tidak yakin saya memahami ini juga saya harus.

logic type-theory intuition PhD
sumber

Sudahkah Anda meng-Google-nya? Pernahkah Anda mendengar tentang Coq, sebuah pepatah teorema yang dibangun berdasarkan tipe dependen? Tahukah Anda bahwa teorema 4 warna telah terbukti menggunakan Coq?

Dave Clarke

Sebenarnya saya lakukan. Apa yang sulit bagi Google adalah apa "kekuatan" ekstra itu (karena tidak ada kata yang lebih baik) yang diberikan DT untuk mengetikkan teori, secara intuitif?

PhD

Mengapa? Tipe dependen memungkinkan Anda mengetik lebih banyak program sambil tetap mengetikkan aman. Bagaimana? Dengan parameterisasi tipe dengan program.

Martin Berger

@ MartinBerger - Bisakah Anda menjelaskan lebih lanjut tentang "lebih banyak program"? Apa "lebih" yang bisa saya lakukan atau butuhkan, dari sudut pandang teoretis?

PhD

@DaveClarke That Coq, dengan tipe mewahnya, telah digunakan untuk melakukan hal-hal mewah tidak menyiratkan bahwa hal-hal mewah memerlukan tipe-tipe mewah. Sebagai contoh, Twelf memiliki kesuksesan besar (seperti bukti ketepatan SML), dan itu hanya urutan kedua, bukan urutan yang lebih tinggi. Saya telah melihat beberapa sistem yang cukup besar yang dibuktikan dengan logika tingkat pertama saja.

Gilles 'SANGAT berhenti menjadi jahat'

Jawaban:

$\lambda$ $List_{2*3+4}(\alpha)$ $10$ $\alpha$ $2*3+4$

Aturan utama yang membedakan dependen dari tipe non-dependen adalah aplikasi:

\frac{Γ ⊢ M : A \to B Γ ⊢ N : A}{Γ ⊢ M N : B} \frac{Γ ⊢ M : Π x^{A} . B Γ ⊢ N : A}{Γ ⊢ M N : B {N / x}}

$\newcommand{\TYPES}[3]{#1 \vdash #2 : #3} \newcommand{\SUBST}[2]{\{#1/#2\}} \frac{ \TYPES{\Gamma}{\color{red}{M}}{A \rightarrow B} \qquad \TYPES{\Gamma}{\color{red}{N}}{A} }{ \TYPES{\Gamma}{\color{red}{MN}}{B} } \qquad \frac{ \TYPES{\Gamma}{{\color{red}M}}{\Pi x^A. B} \qquad \TYPES{\Gamma}{\color{red}{N}}{A} }{ \TYPES{\Gamma}{{\color{red}{MN}}}{B\SUBST{{\color{red}N}}{x}} }$

Di sebelah kiri Anda memiliki STLC, di mana program di tempat 'mengalir' hanya ke dalam program kesimpulan. Sebaliknya, dalam aturan aplikasi dependen di sebelah kanan, program dari premis kanan 'mengalir' ke tipe dalam kesimpulan . $N$ $^1$

Agar dapat membuat parameter tipe oleh program, sintaksis tipe dependen harus lebih kaya, dan untuk memastikan bahwa tipe terbentuk dengan baik, kami menggunakan 'sistem pengetikan' kedua yang disebut jenis yang membatasi tipe. Sistem kinding ini pada dasarnya adalah STLC, tetapi "naik satu tingkat".

Ada banyak penjelasan tentang tipe dependen. Beberapa contoh.

Jenis Tergantung di Tempat Kerja , oleh Bove dan Dybjer.
Jenis Dependen, oleh Aspinall dan Hofmann.
Pemrograman Ketik Ketergantungan di Agda , oleh Norell dan Chapman.
Kalkulator Lambda dengan Jenis , oleh Barendregt.

$^1$ ^{Dalam hal warna: dengan jenis yang tidak tergantung, ekspresi hitam dalam kesimpulan dikonstruksikan dari ekspresi hitam di tempat sedangkan ekspresi merah dalam kesimpulan dibangun dari ekspresi merah di tempat. Dengan tipe dependen, warna dapat dicampur dengan bagian hitam kesimpulan dibuat dari bagian merah dan hitam dari premis.}

Martin Berger
sumber

Sekarang, itu masuk akal. Itu mungkin sudah jelas tetapi untuk beberapa alasan saya tidak bisa menyentuh jari itu. Hargai transisi dari komentar ke jawaban. Sayangnya, pertanyaannya telah dipilih untuk ditutup, tetapi saya senang untuk jawabannya :)

PhD

Saya tidak tergila-gila dengan contoh Anda, karena panjang daftar hanyalah sesuatu yang dapat Anda hapus dalam jenis dan dapatkan program berbicara tentang daftar biasa (tidak diindeks). Mungkin berguna untuk mencatat bahwa ada tipe yang tidak tetap diketik dengan baik setelah penghapusan semacam ini, misalnya program tipe , di mana dan .

A r r n

$\mathrm{Arr}\ n$

A r r 0 = n a t

$\mathrm{Arr}\ 0 = \mathrm{nat}$

A r r (n + 1) = n a t \to A r r n

$\mathrm{Arr}\ (n+1) = \mathrm{nat}\rightarrow\mathrm{Arr}\ n$

cody

@cody Saya tidak yakin apa yang Anda maksud. Jenis Dependent telah (atau dapat diatur untuk memiliki) penghapusan jenis dalam arti berikut: untuk semua P typeable: IFF , di mana adalah run-time pengurangan hubungan . (Ini adalah deskripsi yang disederhanakan di mana fungsi menghapus peta program dengan jenis anotasi untuk program 'yang sama' tanpa anotasi.) Mungkin Anda bermaksud sesuatu yang berbeda?

P ⇓ V

$P\Downarrow V$

e r a s e (P) ⇓ e r a s e (V)

$erase(P)\Downarrow erase(V)$

⇓

$\Downarrow$

Martin Berger

@ MartinBerger: ya dalam hal ini saya sedang berbicara tentang menghapus dependensi dalam tipe dependen untuk mendapatkan tipe sederhana. Satu-satunya contoh yang dapat saya tunjukkan saat ini adalah bukti bahwa menormalkan iff menormalkan (misalnya buku Barendregt ).

F_{ω}

$F_\omega$

C o C

$\mathrm{CoC}$

cody

@cody Saya pikir itu tidak biasa untuk memanggil penghapusan jenis ini. Apa nama yang lebih baik? Mungkin tipe penyederhanaan?

Martin Berger

Pikirkan jenis deklarasi sebagai tidak lebih dari pernyataan. Saat ini, yang dapat Anda katakan adalah hal-hal seperti isInt32 (), isCharPtr (), dll. Berbagai pernyataan ini dipilih untuk dapat diperiksa pada waktu kompilasi. Tetapi konsep ini dapat diperluas ke hal-hal seperti: isCharPtr () && isNotNull (). Pointer nullable adalah masalah besar. Pointer tidak boleh nullable sebagai posisi default, dengan pointer nullable adalah tipe yang tidak dereferenceable tanpa mengetahui apakah itu null atau tidak. Masalah serupa adalah hal-hal seperti: isPositiveInteger (), atau isEvenNaturalNumber ().

rampok
sumber