Mengapa Coq memiliki Prop?

Coq memiliki Prop jenis bukti proposisi tidak relevan yang dibuang selama ekstraksi. Apa alasan untuk memiliki ini jika kita menggunakan Coq hanya untuk bukti. Prop adalah impredikatif, ~~jadi Prop: Prop,~~ bagaimanapun, Coq secara otomatis menyimpulkan indeks alam semesta dan kita dapat menggunakan Tipe (i) sebagai gantinya di mana-mana. Sepertinya Prop menyulitkan semuanya.

Saya membaca bahwa ada alasan filosofis untuk memisahkan Set dan Prop dalam buku Luo, namun, saya tidak menemukannya dalam buku itu. Apakah mereka?

coq dependent-type Konstantin Solomatov
sumber

"Jika kita menggunakan Coq hanya untuk bukti": Saya pikir Anda telah mengidentifikasi titik kunci di sini. Coq tidak hanya digunakan untuk bukti.

Gilles 'SANGAT berhenti menjadi jahat'

Jawaban:

$\mathtt{Prop}$ sangat berguna untuk ekstraksi program karena memungkinkan kita untuk menghapus bagian-bagian kode yang tidak berguna. Sebagai contoh, untuk mengekstrak algoritma penyortiran kami akan membuktikan pernyataan "untuk setiap daftar $\ell$ ada daftar $k$ sedemikian sehingga $k$ dipesan dan $k$ adalah permutatiom dari $\ell$ ". Jika kita menuliskan ini dalam Coq dan ekstrak tanpa menggunakan $\mathtt{Prop}$ , kita akan mendapatkan:

"untuk semua $\ell$ ada $k$ " akan memberi kita peta sortyang membawa daftar ke daftar,
"sedemikian rupa sehingga dipesan" akan memberikan fungsi yang berjalan melalui dan memeriksa apakah itu diurutkan, dan $k$ verify $k$
" adalah permutasi dari " akan memberikan permutasi yang membawa ke . Perhatikan bahwa ini bukan hanya pemetaan, tetapi juga pemetaan terbalik bersama dengan program yang memverifikasi bahwa kedua peta tersebut benar-benar terbalik. $k$ $\ell$ pi $\ell$ $k$ pi

Sementara hal-hal tambahan tidak sepenuhnya tidak berguna, dalam banyak aplikasi kami ingin menyingkirkannya dan tetap adil sort. Hal ini dapat dicapai jika kita menggunakan ke negara " memerintahkan" dan " adalah permutasi dari ", tapi tidak "untuk semua ada ". $\mathtt{Prop}$ $k$ $k$ $\ell$ $\ell$ $k$

Secara umum, cara umum untuk mengekstrak kode adalah dengan mempertimbangkan pernyataan bentuk mana adalah input, adalah output, dan menjelaskan apa artinya bagi menjadi output yang benar. (Dalam contoh di atas dan adalah jenis daftar dan adalah " dipesan dan adalah permutasi dari .") Jika ada di maka ekstraksi memberikan peta $\forall x : A \,.\, \exists y : B \,.\, \phi(x, y)$ $x$ $y$ $\phi(x,y)$ $y$ $A$ $B$ $\phi(\ell, k)$ $k$ $k$ $\ell$ $\phi$ $\mathtt{Prop}$ sehingga berlaku untuk semua . Jika ada di maka kita juga mendapatkan fungsi sedemikian sehingga adalah bukti bahwa berlaku, untuk semua $f : A \to B$ $\phi(x, f(x))$ $x \in A$ $\phi$ $\mathtt{Set}$ $g$ $g(x)$ $\phi(x, f(x))$ $x \in A$ . Seringkali buktinya tidak berguna secara komputasional dan kami lebih suka membuangnya, terutama ketika itu bersarang jauh di dalam beberapa pernyataan lainnya. memberi kita kemungkinan untuk melakukannya. $\mathtt{Prop}$

Ditambahkan 2015-07-29: Ada pertanyaan apakah kita bisa menghindari sama sekali dengan secara otomatis mengoptimalkan "kode tidak berguna diekstraksi". Hingga taraf tertentu kita dapat melakukan itu, misalnya semua kode yang diekstraksi dari fragmen negatif dari logika (barang-barang yang dibangun dari tipe kosong, tipe unit, produk) tidak berguna karena hanya bergerak di sekitar unit. Tapi ada desain keputusan asli seseorang harus membuat ketika menggunakan . Berikut ini adalah contoh simpe, di mana berarti bahwa kita berada dalam dan berarti kita berada dalam . Jika kita ekstrak dari $\mathsf{Prop}$ $\mathsf{Prop}$ $\Sigma$ $\mathsf{Type}$ $\exists$ $\mathsf{Prop}$ kita akan mendapatkan program yang menguraikan menjadi bit terendah dan bit yang tersisa , yaitu, ia menghitung semuanya. Jika kita mengekstrak dari

Π_{n : N} Σ_{b : {0, 1}} Σ_{k : N} n = 2 \cdot k + b

$\Pi_{n : \mathbb{N}} \Sigma_{b : \{0,1\}} \Sigma_{k : \mathbb{N}} \; n = 2 \cdot k + b$

n

$n$

b

$b$

k

$k$

maka program hanya akan menghitung bit terendah

. Mesin tidak dapat menentukan mana yang benar, pengguna harus mengatakan apa yang diinginkannya.

Π_{n : N} Σ_{b : {0, 1}} \exists_{k : N} n = 2 \cdot k + b

$\Pi_{n : \mathbb{N}} \Sigma_{b : \{0,1\}} \exists_{k : \mathbb{N}} \; n = 2 \cdot k + b$

b

$b$

Andrej Bauer
sumber

Saya sedikit bingung. Apakah Anda mengatakan bahwa tanpa

tidak mungkin untuk mengenali dalam program yang diekstrak bahwa

tidak berkontribusi pada output (yaitu hanya memverifikasi saja)? Apakah ada skenario di mana seseorang tidak akan dapat mengeluarkan kode tidak berguna seperti itu melalui cara biasa yang tersedia untuk pengoptimal kode?

P r o p

$\mathtt{Prop}$

g (x)

$g(x)$

pengguna

Dari program yang diekstraksi, orang bisa mengatakan, "Saya ingin

," dan mundur dari sana. Saya belum dapat menemukan skenario yang terjerat sehingga kita tidak dapat mengoptimalkan apa pun yang tidak secara langsung berkontribusi untuk menentukan permutasi tanpa itu sebenarnya diperlukan untuk menghitung permutasi tersebut (dari sudut pandang optimasi global, toh ).

k

$k$

pengguna

Anda tidak memiliki informasi "Saya ingin

". Itu adalah asumsi tambahan, dan jelas sekali mereka memberi tahu Anda hasil tertentu yang mereka inginkan, Anda hanya dapat mengoptimalkan kode mati. Sebenarnya, saya pikir dari jawaban yang lebih baik: itu adalah desain pertanyaan yang hal untuk dimasukkan ke dalam

. Anda perlu tahu apa yang diinginkan pengguna, dan ia memberitahu Anda apa yang dia inginkan dengan menggunakan

. Mudah untuk memberikan contoh di mana ada beberapa opsi. Saya akan menambahkan satu ke jawaban saya.

k

$k$

P r o p

$\mathsf{Prop}$

P r o p

$\mathsf{Prop}$

Andrej Bauer

Sejauh yang saya tahu tidak ada yang bisa benar-benar tahu cara mengekstrak apa pun dari

-jenis. Jelas bahwa mereka mengandung beberapa konten komputasi, tetapi tidak seperti ini.

(- 1)

$(-1)$

Andrej Bauer

Ah, baiklah. Menggunakan

sebagai cara menentukan keputusan desain jauh lebih masuk akal bagi saya daripada sebagai cara menghapus kode yang tidak berguna.

P r o p

$\mathtt{Prop}$

pengguna

adalahimpredikatif, yang menciptakan sistem bukti yang sangat ekspresif. Namun "terlalu" ekspresif dalam arti berikut: $\mathrm{Prop}$

i m p r e d i c a t i v e P r o p + l a r g e e l i m i n a t i o n + e x c l u d e d m i d d l e

$\mathrm{impredicative\ Prop} + \mathrm{large\ elimination} + \mathrm{excluded\ middle}$

tidak konsisten. Biasanya Anda ingin menjaga kemungkinan untuk menambahkan tengah yang dikecualikan, jadi salah satu solusinya adalah menjaga eliminasi besar dan membuat Prop predikatif. Yang lainnya adalah untuk menekan eliminasi besar.

Coq melakukan keduanya! Mereka mengganti nama Prop menjadi Prop untuk Set, dan menonaktifkan eliminasi besar di Prop.

Ekspresi yang diperoleh oleh impredicativity adalah "meyakinkan" dalam arti 99% dari matematika "masuk akal" dapat diformalkan dengannya, dan itu diketahui relatif konsisten dengan teori yang ditetapkan. Ini memungkinkan mereka tidak akan melemahkannya menjadi sesuatu seperti Agda, yang hanya memiliki alam semesta predikatif.

cody
sumber

Oh dan saya lupa menyebutkan: bukan itu masalahnya Prop : Prop, itu tidak konsisten. Sebaliknya kuantifikasi atas semua proposisi lagi-lagi merupakan proposisi.

cody

Bisakah Anda mengarahkan saya ke sumber daya lain tentang ini? Semua yang saya dapat temukan tampaknya sangat tersebar.

user833970

@ user833970 hal-hal spesifik yang Anda inginkan untuk petunjuk? Saya khawatir sebenarnya tidak ada referensi yang mencakup semua untuk meta teori tipe dependen. Diskusi ini (yang menunjuk ke sini!) Mungkin berguna: github.com/FStarLang/FStar/issues/360

cody

terima kasih, saya sedang mengerjakan makalah paradoks Berardi sekarang, saya pikir itu akan menjernihkan kebingungan saya.

user833970

Bahkan jika Anda tidak tertarik untuk mengekstraksi program, fakta bahwa Propimpredikatif memungkinkan Anda membangun beberapa model yang tidak dapat Anda bangun menggunakan menara predikatif alam semesta. IIRC Thorsten Altenkirch memiliki model Sistem F menggunakan impredicativity Coq.

gallais
sumber