Intuisi Di Balik Positif Ketat?

Saya bertanya-tanya apakah seseorang dapat memberi saya intuisi di balik mengapa kepastian positif tipe data induktif menjamin normalisasi yang kuat.

Untuk menjadi jelas, saya melihat bagaimana memiliki kejadian negatif mengarah pada perbedaan, yaitu dengan mendefinisikan:

data X where Intro : (X->X) -> X

kita dapat menulis fungsi yang berbeda.

Tetapi saya bertanya-tanya, bagaimana kita dapat membuktikan bahwa tipe induktif yang benar-benar positif tidak memungkinkan terjadinya divergensi? yaitu apakah ada beberapa langkah induksi yang memungkinkan kita membangun bukti normalisasi yang kuat (menggunakan hubungan logis atau serupa)? Dan di mana bukti seperti itu memecah untuk kejadian negatif? Apakah ada referensi bagus yang menunjukkan normalisasi kuat untuk bahasa dengan tipe induktif?

reference-request pl.programming-languages type-theory type-systems dependent-type Ya ampun
sumber

Saya pikir ide ini adalah tipe positif yang dapat dikonversi ke tipe W, secara konsep. Juga tipe non-ketat-positif tidak konsisten dengan Coq vilhelms.github.io/posts/… . Dikomentari bahwa tipe positif konsisten dengan Agda, tetapi saya juga ingin melihat penjelasan konseptual ...

molikto

@molikto Terima kasih, itu membantu. Tapi saya pikir tipe-W tidak memberikan prinsip induksi yang diinginkan dalam teori intensional? Bagaimana kita dapat membuktikan normalisasi kuat untuk induktif positif ketat dalam teori intensional?

jmite

Jawaban:

Sepertinya Anda ingin gambaran umum argumen normalisasi untuk sistem tipe dengan tipe data positif. Saya akan merekomendasikan disertasi PhD Nax Mendler: http://www.nuprl.org/documents/Mendler/InductiveDefinition.html .

Seperti yang disarankan oleh tanggal, ini adalah karya yang cukup klasik. Intuisi dasarnya adalah bahwa $\lambda$ ordinal dapat dikaitkan dengan elemen apa pun dari tipe induktif positif, misalnya untuk tipe data

Inductive Ord = Zero : Ord | Suc : Ord -> Ord | Lim : (Nat -> Ord) -> Ord

Kami akan mendapatkan:

λ (t) = 0

$\lambda(t) = 0$ jika

t

$t$ adalah bentuk normal yang bukan merupakan konstruktor

λ (Z e r o) = 0

$\lambda(\mathrm{Zero}) = 0$

λ (S kamu c (Hai)) = λ (Hai) + 1

$\lambda(\mathrm{Suc}(o)) = \lambda(o)+1$ dan

λ (L. saya m (f)) = sup_{n} λ (f n)

$\lambda(\mathrm{Lim}(f)) = \sup_n \lambda(f\ n)$

$n$ $f\ n$

Satu kemudian dapat mendefinisikan fungsi rekursif dengan induksi atas ordinal ini.

Perhatikan bahwa tipe data ini sudah dapat didefinisikan dalam teori himpunan klasik, seperti yang ditunjukkan dalam makalah Keluarga Induktif yang sangat baik oleh Dybjer ( http://www.cse.chalmers.se/~peterd/papers/Inductive_Families.pdf ). Namun, karena fungsi ruang yang begitu besar, jenis seperti Ordmembutuhkan benar-benar ordinals besar untuk menafsirkan.

cody
sumber

Terima kasih, ini sangat membantu! Apakah Anda tahu jika tata cara seperti itu dapat didefinisikan dalam teori jenis itu sendiri? yaitu jika saya mencoba menggunakan Agda untuk dengan induksi-rekursi untuk memodelkan teori tipe dengan induktif (tapi tanpa induksi-rekursi), dapatkah saya menggunakan sesuatu seperti Orduntuk memodelkan ordinansi yang diperlukan untuk menunjukkan landasan yang kuat?

jmite

@iteite, Anda bisa, tetapi tata cara dalam teori-teori konstruktif agak aneh, dan Anda mungkin juga bekerja dengan perintah atau pohon yang beralasan ( ala -W seperti yang disarankan molikto). Mungkin sulit untuk memiliki satu jenis seragam yang menangkap dasar-dasar setiap induktif dalam bahasa objek meskipun ...

cody

@cody Bukankah contoh Ord yang Anda berikan tipe yang benar-benar positif?

Henning Basold

@HenningBasold ya itu (itu sebabnya saya menggunakannya sebagai ilustrasi!). Tapi itu tidak berperilaku persis seperti tata cara dalam teori himpunan (klasik), dan tentu saja tidak seperti himpunan semua tata cara. Secara khusus, agak sulit untuk menentukan urutannya.

cody

@HenningBasold juga saya harus perhatikan bahwa pertanyaan jmite adalah tentang tipe yang benar-benar positif secara spesifik, meskipun informasi tentang pengaturan yang lebih umum juga menarik!

cody

Sumber bagus lain untuk melampaui tipe yang benar-benar positif adalah tesis PhD dari Ralph Matthes: http://d-nb.info/956895891

Dia membahas ekstensi Sistem F dengan (ketat) tipe positif di bab 3 dan membuktikan banyak hasil normalisasi yang kuat di bab 9. Ada beberapa ide menarik yang dibahas dalam bab 3.

$\rho$ $\alpha$ $\forall \alpha \forall \beta.\, (\alpha \to \beta) \to \rho \to \rho[\beta/\alpha]$
Ketika kita beralih dari tipe positif ke tipe positif, maka tipe induktif tidak lagi dipandang sebagai pohon (pengkodean tipe-W). Sebaliknya ini memperkenalkan beberapa bentuk impredicativity karena konstruksi dari tipe induktif positif sudah dikuantifikasi atas tipe itu sendiri. Perhatikan bahwa ini adalah bentuk impredicativitas yang agak ringan, karena semantik dari jenis-jenis tersebut masih dapat dijelaskan dalam hal iterasi ordinal fungsi monoton.
Matthes juga memberikan beberapa contoh tipe induktif positif. Sangat menarik
- $\mu.\, 1 + ((\alpha \to \rho) \to \rho)$ $\alpha$ $\rho$
- $\mu \alpha \forall \beta.\, (\alpha \to \beta) \to \rho[\beta/\alpha]$ $\rho$

$\lambda\mu$

Saya harap ini membantu pertanyaan Anda.

Henning Basold
sumber