Kuantifikasi universal / eksistensial?

Saya berjuang untuk memahami tujuan dari kuantifikasi tipe yang universal dan eksistensial. Saya bermain-main dengan menulis bahasa mainan berdasarkan kalkulus konstruksi . Saya telah membaca tentang Morte dan Henk untuk membantu saya mendapatkan pemahaman yang lebih baik.

Saya tidak mengerti mengapa CoC memiliki abstraksi lambda dan forall.

( ∀ x : A . B

Tampaknya bagi saya lambda merangkul semua dalam sistem di mana jenis dilewatkan secara manual. Dengan kata lain, itu yang berikut

Bisa diganti dengan

Jika pertama kali diterapkan pada jenis yang digunakan.

Apa yang saya lewatkan? Apa makalah atau blog atau artikel yang bisa dibaca yang bisa membantu saya?

Terima kasih.

Akan membantu untuk mengingat bahwa (atau seperti yang kadang-kadang Anda lihat) adalah tipe. Ini menggeneralisasi . Jadi walaupun masuk akal untuk mengatakan , tidak masuk akal untuk mengatakan karena hanyalah sebuah tipe. Anda tidak akan mengatakan becaues tidak untuk komputasi per-se, itu ada di sana untuk hal lambda mengklasifikasikan yang dapat diterapkan seperti ini .Π → ( λ x : A . M ) N ( ∀ x : A . M ) N ∀ . . . ( A → B ) N $\forall$$\Pi$$\to$$(\lambda x : A. M)\ N$$(\forall x : A. M)\ N$$\forall ...$$(A \to B)\ N$$\to$

Ini adalah sesuatu yang membuat saya tersandung juga, tapi ini adalah bagaimana kalkulus konstruksi (dan juga sistem mengetik yang dependen lainnya didefinisikan).

Dua program yang Anda tulis memiliki niat yang sangat berbeda dan yang pertama salah ketik. Tidak masuk akal untuk mengatakan karena membutuhkan kedua argumennya dengan tipe yang berarti bahwa jika harus diketik dengan baik, kita harus miliki . Namun, bukan tipe, itu hanya bisa diberikan tipe formulir , tidak pernah . Yang kedua di sisi lain hampir (Saya pikir Anda bermaksud untuk kembali tidak ) adalah fungsi dan diberikan jenis menggunakan dua s.∀ ∀ x : A . B B : ∗ λ x . x ∀ x : A . B ∗ a x $\forall x : A.\ \lambda x.\ x$$\forall$$\forall x : A. B$$B : *$$\lambda x. x$$\forall x : A. B$$*$$a$$x$$\forall$

Perlu diingat bahwa tipe eksistensial dan universal agak berbeda. Ini adalah logika konstruktif, bukan logika klasik dan dalam logika konstruktif dan ∃ tidak berhubungan seperti mereka dalam logika klasik.$\forall$$\exists$

adalah jenis program yang menerima objek tipe A dan mengembalikan objek tipe B ( x ) . Yang penting di sini adalah bahwa tipe B ( x ) tergantungpada x dan tidak sama untuk semua x . Itu dapat bervariasi tergantung pada apa x . Untuk satu input x kita mungkin menghasilkan integer. Untuk yang lain kita bisa menampilkan bilangan real. Untuk yang lainnya kita mungkin menampilkan fungsi lebih dari bilangan real. Jika B ( x $\forall x:A. B(x)$$A$$B(x)$$B(x)$ $x$$x$$x$$x$$B(x)$tidak berbeda dengan maka Anda dapat menggunakan A → B di tempat yang merupakan jenis fungsi dari A ke B .$x$$A\to B$$A$$B$

adalahversidependendari disjungsi (konstruktif). Anda bisa memikirkan disjungsi konstruktif A ∨ B dari dua jenis A dan B sebagai serikat menguraikan dari A dan B . ∃ x : A . B ( x ) adalah gabungan menguraikan dari kumpulan jenis B ( x ) diindeks oleh x : A . Fakta bahwa tipe B $\exists x:A. B(x)$$A \lor B$$A$$B$$A$$B$$\exists x:A.B(x)$$B(x)$$x:A$ van bervariasi tergantung pada nilai x : A membuatnya menjadi tipe dependen. Bandingkan dengan kasus di mana B tidak tergantung pada x : A : ∃ x : A . B . Kami mengambil satu salinan yang sama B untuk setiap x : A . Ini adalah isomorfik ke A × B .$B(x)$$x:A$$B$$x:A$$\exists x:A. B$$B$$x:A$$A \times B$

Sekarang Anda dapat bertanya mengapa kami membutuhkan jenis produk dan jumlah yang tergantung ? Karena mereka memberi kita kekuatan yang lebih ekspresif. Sekarang kita dapat mengabaikan tipe sepenuhnya dan memiliki teori tipe / pemrograman fungsional yang tidak diketik. Tapi itu menghilangkan manfaat memiliki jenis di tempat pertama, misalnya Anda tidak akan tahu apakah semua program akan selalu berakhir (normalisasi kuat). Lihat Lambda Cube dan Jenis Ketergantungan . Saya pikir cara yang baik untuk memahami tipe dependen dengan baik adalah dengan melihat aturan untuk memperkenalkan dan menghilangkan tipe dependen dalam teori tipe Martin-Lof .

Poin utama dari tipe dependen adalah: kami ingin tetap berada di dalam teori yang diketik dengan baik karena berbagai alasan (mis. Menghindari bug, bukti terminasi otomatis, dll.) Kami tidak ingin melihat sesuatu seperti kalkulus lambda yang tidak diketik di mana kami dapat membuat ekspresi seperti yang Anda nyatakan dan cara yang lebih kuat. Kita dapat mengatakan bahwa tipe dependen diciptakan untuk memungkinkan mengekspresikan lebih banyak hal sambil tetap berada di dalam teori tipe yang bagus.