Apa peran Kalkulus Konstruksi Bicolored?

Jadi, saya membaca sedikit tentang elaborasi, khususnya, algoritma yang didasarkan pada Kalkulus Konstruksi Bicolored, dan saya agak bingung. Saya tidak mengerti apa sebenarnya tujuan itu. Tampaknya identik dengan kecuali ada perbedaan antara argumen implisit dan eksplisit untuk fungsi. Secara khusus, saya tidak melihat bagaimana ini memungkinkan Anda untuk menulis bukan . Jika kita mengasumsikan sistem untuk definisi global, maka, $CC^{bi}$ $CC$ $(id\; 0)$ $(id\; \mathbb{N}\; 0)$

$id : (\Pi A\; |\; \mathsf{Type}\; . (\Pi x : A\; . A))$

dan

$id = (\lambda A\; |\; \mathsf{Type}\; . (\lambda x : A . x))$ .

Apakah aturan benar-benar mengizinkan ? Tentu saja sintaksinya, tetapi saya tidak melihatnya dalam hubungan pengetikan. Apakah saya melewatkan sesuatu? Apakah saya salah memahami peran ? $(id\; 0)$ $CC^{bi}$

Juga, bukankah properti pertemuan hilang? Saya kira masalah saya adalah bahwa saya membaca tentang penjabaran tanpa membaca banyak tentang sebelum ini. Apa makalah yang bagus yang memperkenalkannya dan itu sendiri? $CC^{bi}$

Sunting: Untuk lebih spesifik, saya bertanya bagaimana diterima sebagai pengganti ketika aturan untuk aplikasi eksplisit dan implisit identik modulo sytnax . Saya tidak melihat perbedaan antara danaturan untuk keduanya tampak sama. $(id\; 0)$ $(id\; \mathbb{N}\; 0)$ $\Pi$ $:$ $|$

Sunting: Saya tidak berbicara tentang Kalkulus Konstruksi Implisit, yang merupakan teori yang berbeda dan memiliki aturan berbeda untuk eksplisit (aplikasi vs generasi.) $\Pi$

Sunting: Oke, saya pikir saya mulai memahami ini, tetapi saya tidak akan menjawab pertanyaan ini sampai saya yakin. Pada dasarnya tidak mengetik cek dan pada kenyataannya itu hanya diuraikan ke tepat sebelum pengecekan tipe atau dilakukan sebagai tanggung jawab sekunder dari algoritma pengecekan tipe. Pada dasarnya, kalkulus implisit ini dimaksudkan untuk menjadi bahasa antarmuka (pengguna-akhir) yang diuraikan ke dalam kalkulus biasa (eksplisit) atau setidaknya fragmen eksplisit kalkulus implisit sebelum istilah tersebut diketikkan. Jika itu masalahnya, maka saya pikir saya melihat gambaran besarnya. Bisakah seseorang tolong konfirmasi ini? $(id\; 0)$ $(id\; \mathbb{N}\; 0)$

type-theory lambda-calculus type-inference dependent-type Anthony
sumber

Seperti yang saya katakan di bawah ini, intuisi Anda benar: kalkulus konstruksi dua warna adalah kalkulus eksplisit, di mana argumen dihilangkan oleh pengguna tetapi diuraikan oleh "ujung depan" secara eksplisit ditandai. Juga, pertemuan hilang untuk reduksi beta + eta, tetapi benar jika dibatasi hanya beta.

cody

Jawaban:

Dalam Kalkulus Implisit Konstruksi yang Memperluas Sistem Jenis Murni dengan Binder dan Subtipe Tipe Persimpangan , Alexandre Miquel memperkenalkan konsep dasar untuk Kalkulus Konstruksi Implisit, yang saya yakini identik dengan Kalkulus Konstruksi Bicolored.

Intinya adalah (antara lain) untuk memiliki kalkulus tanpa kekacauan jenis penjelasan eksplisit di mana-mana. Jenis inferensi (sangat mungkin) tidak dapat diputuskan.

Dalam kalkulus ini, jika kita mengambil , maka Anda dapat memperoleh hanya dengan menggunakan produk eksplisit dan aturan produk implisit secara berurutan. Kemudian aturan instantiasi untuk produk implisit memungkinkan dan begitu $id=\lambda x. x$

⊢ saya d : \forall X : T y hal e . X \to X

$\vdash id\colon \forall X\colon Type. X\rightarrow X$

⊢ saya d : N Sebuah t \to N Sebuah t

$\vdash id\colon Nat\rightarrow Nat$

⊢ saya d 0 : N Sebuah t

$\vdash id\ 0 \colon Nat$ Sistem mengakui reduksi dan pertemuan subjek, bahkan pada istilah yang tidak diketik (yang sebenarnya gagal untuk kalkulus dengan anotasi abstraksi). Semua ini dapat ditemukan dalam tesis Alexandre, yang sayangnya dalam bahasa Prancis. Tidak yakin saya memiliki referensi yang lebih baik untuk hasil ini meskipun saya takut.

cody
sumber

Bagian pertama dari jawaban Anda saya tahu tetapi saya pikir saya seharusnya lebih spesifik dalam pertanyaan awal saya. Yaitu, bagaimana tepatnya (id 0) diizinkan jika id memiliki tipe (\ Pi X | Type. X -> X) karena sepertinya aturan APP identik untuk implisit dan eksplisit \ Pi. Dalam kalkulus konstruksi implisit, yang sebenarnya merupakan teori yang berbeda, ini tidak terjadi karena dipisahkan ke dalam APP dan GEN. Untuk verifikasi bahwa ini berbeda, periksa judul "Kalkulus dengan argumen 'sangat implisit'" di makalah yang Anda referensikan.

Anthony

Tentang decidability. Makalah yang Anda referensi berspekulasi bahwa teorinya tidak dapat diputuskan. Makalah yang direferensikan (saya kira kalkulus bikolored konstruksi kertas "asli") mengklaim dapat dipilih tetapi tidak secara eksplisit membuktikannya. Saya membacanya setelah saya memposting pertanyaan ini dan tampaknya itu pasti harus diperhitungkan dan tergantung pada batasan sintaksis mempertahankan pertemuan. Di sisi lain, saya masih terjebak dengan kebingungan asli saya: \

Anthony

Mungkin Anda harus memberi tahu kami makalah mana yang Anda lihat.

cody

Ok, saya telah melihat Elaboration and Erasure in Type Theory oleh Marko Luther, yang saya duga adalah referensi Anda. Dalam hal itu, tidak ada perbedaan semantik antara produk eksplisit dan implisit, dan memang sistem dua warna adalah perpanjangan konservatif dari kalkulus konstruksi. Yang terjadi adalah Anda menggunakan elaborasi untuk mengambil istilah tanpa argumen eksplisit untuk mengubahnya menjadi istilah yang sepenuhnya beranotasi: id !1 0diuraikan menjadi id Nat 0. Dalam teks ini, elaborasi dibahas di bagian 4.

cody

C C^{b i}

$CC^{bi}$