Bagaimana Anda mendapatkan Kalkulus Konstruksi dari titik lain di Lambda Cube?

CoC yang dikatakan puncak dari semua tiga dimensi dari Lambda Cube. Ini sama sekali tidak terlihat bagi saya. Saya pikir saya memahami dimensi individu, dan kombinasi dari dua tampaknya menghasilkan persatuan yang relatif mudah (mungkin saya kehilangan sesuatu?). Tapi ketika saya melihat CoC itu, bukan melihat seperti kombinasi dari ketiganya, sepertinya hal yang sama sekali berbeda. Dimensi manakah tipe, prop, dan tipe kecil / besar berasal? Ke mana produk-produk ketergantungan menghilang? Dan mengapa ada fokus pada proposisi dan bukti bukan jenis dan program? Adakah sesuatu yang setara yang berfokus pada jenis dan program?

Sunting: Jika tidak jelas, saya meminta penjelasan tentang bagaimana CoC setara dengan penyatuan langsung dimensi Lambda Cube. Dan apakah ada persatuan yang sebenarnya dari ketiganya di luar sana yang bisa saya pelajari (yaitu dalam hal program dan tipe, bukan bukti dan proposisi)? Ini sebagai tanggapan terhadap komentar pada pertanyaan, bukan untuk jawaban saat ini.

lambda-calculus type-systems typed-lambda-calculus calculus-of-constructions indil
sumber

Paling tidak ini harus a soft-question. Saya tidak melihat pertanyaan teknis yang sebenarnya di sini. Mungkin Anda bisa sedikit lebih spesifik dengan apa yang Anda tanyakan?

Andrej Bauer

@AndrejBauer Bukan pertanyaan: Apa hubungan antara presentasi Barendregt-cube / PTS tentang CoC dan presentasi asli oleh Coquand & Huet?

Martin Berger

@AndrejBauer: Pertanyaannya juga tampaknya bertanya tentang perbedaan dalam presentasi CoC (dalam kedok baik) dan penekanan pada fitur-fitur tertentu dalam praktek. Memang benar bahwa versi CoC yang berorientasi PTS menekankan beberapa fitur sebagai hal yang penting, sedangkan praktik Coq menekankan yang lain. Saya setuju bahwa itu harus memiliki tag pertanyaan-lunak.

Jacques Carette

Saya senang melihat seseorang akan dapat menjawab ini.

Andrej Bauer

Jawaban:

Pertama, untuk mengulangi salah satu poin cody, Calculus of Inductive Constructions (yang menjadi dasar kernel Coq) sangat berbeda dari Calculus of Constructions. Paling baik dianggap sebagai mulai dari teori tipe Martin-Löf dengan alam semesta, dan kemudian menambahkan Prop semacam di bagian bawah hirarki jenis. Ini adalah binatang yang sangat berbeda dari CoC asli, yang dianggap terbaik sebagai versi dependen F-omega. (Misalnya, CiC memiliki model teori set dan CoC tidak.)

Yang mengatakan, lambda-cube (di mana CoC adalah anggota) biasanya disajikan sebagai sistem tipe murni karena alasan ekonomi dalam jumlah aturan pengetikan. Dengan memperlakukan jenis, jenis, dan istilah sebagai elemen dari kategori sintaksis yang sama, Anda dapat menuliskan lebih sedikit aturan dan bukti Anda menjadi sedikit lebih redundan juga.

Namun, untuk pemahaman, akan sangat membantu untuk memisahkan berbagai kategori secara eksplisit. Kita dapat memperkenalkan tiga kategori sintaksis, jenis (berkisar oleh metavariabel k), tipe (berkisar oleh metavariabel A), dan istilah (berkisar oleh metavariabel e). Kemudian semua delapan sistem dapat dipahami sebagai variasi pada apa yang diizinkan pada masing-masing dari tiga tingkatan.

λ → (Kalkulus lambda yang diketik sederhana)

 k ::= ∗
 A ::= p | A → B
 e ::= x | λx:A.e | e e

Ini adalah dasar kalkulus lambda yang diketik. Ada satu jenis ∗, yaitu jenis jenis. Tipe-tipe itu sendiri adalah tipe atom pdan tipe fungsi A → B. Istilah adalah variabel, abstraksi atau aplikasi.

λω_ (STLC + operator jenis yang lebih tinggi)

 k ::= ∗ | k → k
 A ::= a | p | A → B | λa:k.A | A B
 e ::= x | λx:A.e | e e

STLC hanya mengizinkan abstraksi pada tingkat persyaratan. Jika kita menambahkannya pada level tipe, maka kita menambahkan tipe baru k → kyang merupakan tipe fungsi level-level, dan abstraksi λa:k.Adan aplikasi A Bpada level tipe juga. Jadi sekarang kami tidak memiliki polimorfisme, tetapi kami memiliki operator tipe.

Jika memori berfungsi, sistem ini tidak memiliki daya komputasi lebih dari STLC; itu hanya memberi Anda kemampuan untuk menyingkat jenis.

λ2 (Sistem F)

 k ::= ∗
 A ::= a | p | A → B  | ∀a:k. A 
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

Alih-alih menambahkan operator tipe, kita bisa menambahkan polimorfisme. Pada level type, kami menambahkan ∀a:k. Ayang merupakan tipe mantan polymorphic, dan pada level term, kami menambahkan abstraksi atas tipe Λa:k. edan tipe aplikasi e [A].

Sistem ini jauh lebih kuat daripada STLC - ia sekuat aritmatika orde kedua.

λω (Sistem F-omega)

 k ::= ∗ | k → k 
 A ::= a | p | A → B  | ∀a:k. A | λa:k.A | A B
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

Jika kita memiliki operator tipe dan polimorfisme, kita mendapatkan F-omega. Sistem ini kurang lebih merupakan teori tipe kernel dari kebanyakan bahasa fungsional modern (seperti ML dan Haskell). Ini juga jauh lebih kuat daripada Sistem F - itu setara dalam kekuatan untuk aritmatika tingkat tinggi.

λP (LF)

 k ::= ∗ | Πx:A. k 
 A ::= a | p | Πx:A. B | Λx:A.B | A [e]
 e ::= x | λx:A.e | e e

Alih-alih polimorfisme, kita bisa pergi ke arah ketergantungan dari kalkulus lambda yang diketik sederhana. Jika Anda mengizinkan tipe fungsi untuk membiarkan argumennya digunakan dalam tipe kembali (yaitu, tulis Πx:A. B(x)bukan A → B), maka Anda mendapatkan λP. Untuk membuat ini benar-benar berguna, kita harus memperluas rangkaian jenis dengan jenis operator jenis yang menggunakan istilah sebagai argumen Πx:A. k, dan karenanya kita harus menambahkan abstraksi Λx:A.Bdan aplikasi yang sesuai A [e]di tingkat jenis juga.

Sistem ini kadang-kadang disebut LF, atau Edinburgh Logical Framework.

Ia memiliki kekuatan komputasi yang sama dengan kalkulus lambda yang diketik sederhana.

λP2 (tidak ada nama khusus)

 k ::= ∗ | Πx:A. k 
 A ::= a | p | Πx:A. B | ∀a:k.A | Λx:A.B | A [e]
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

Kita juga bisa menambahkan polimorfisme ke λP, untuk mendapatkan λP2. Sistem ini tidak sering digunakan, sehingga tidak memiliki nama tertentu. (Satu makalah yang saya baca yang menggunakannya adalah Induksi Herman Geuvers ' Tidak Turun dalam Teori Tipe Ketergantungan Orde Kedua .)

Sistem ini memiliki kekuatan yang sama dengan Sistem F.

λPω_ (tidak ada nama khusus)

 k ::= ∗ | Πx:A. k | Πa:k. k'
 A ::= a | p | Πx:A. B | Λx:A.B | A [e] | λa:k.A | A B 
 e ::= x | λx:A.e | e e

Kita juga bisa menambahkan operator tipe ke λP, untuk mendapatkan λPω_. Ini melibatkan penambahan jenis Πa:k. k'untuk operator tipe, dan abstraksi tingkat Λx:A.Baplikasi dan tipe yang sesuai A [e].

Karena tidak ada lagi lompatan dalam kekuatan komputasi atas STLC, sistem ini juga harus membuat dasar yang bagus untuk kerangka kerja logis, tetapi tidak ada yang melakukannya.

λPω (Kalkulus Konstruksi)

 k ::= ∗ | Πx:A. k | Πa:k. k'
 A ::= a | p | Πx:A. B | ∀a:k.A | Λx:A.B | A [e] | λa:k.A | A B 
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

Akhirnya, kita sampai ke λPω, Kalkulus Konstruksi, dengan mengambil λPω_ dan menambahkan jenis polimorfik sebelumnya ∀a:k.Adan abstraksi level-term Λa:k. edan aplikasi e [A]untuk itu.

Jenis-jenis sistem ini jauh lebih ekspresif daripada di F-omega, tetapi memiliki kekuatan komputasi yang sama.

Neel Krishnaswami
sumber

Tentu saja, secara teknis CoC (tanpa aksioma) memiliki setidaknya set-theoretik model sebanyak CiC, mereka hanya tidak pandai memodelkan situasi yang kita inginkan, yang merupakan CoC dengan aksioma untuk bilangan asli (katakanlah,

0 \neq 1

$0 \neq 1$

cody

Saya juga sangat menghargai referensi konservatif

atas STLC. Ini sepertinya tidak jelas.

λ ω_

$\lambda\omega\_$

cody

@cody: Saya tidak tahu referensi - Kevin Watkins membuat sketsa bukti untuk saya di papan tulis! Idenya adalah bahwa Anda mengambil istilah yang diketik dalam λω_, menempatkan semua jenis ke dalam bentuk beta-normal panjang eta, dan kemudian menanamkannya ke dalam STLC dengan memperkenalkan jenis atom segar untuk setiap bentuk normal yang berbeda dalam program asli. Maka jelas urutan pengurangan harus berbaris satu-ke-satu.

Neel Krishnaswami

@ user833970 fakta bahwa

tidak dapat diturunkan sebenarnya jauh lebih sederhana daripada fakta-fakta lain yang Anda sebutkan, dan tidak ada hubungannya dengan pengkodean

: itu berasal dari fakta bahwa ada bukti model CC yang tidak relevan , di mana tipe memiliki paling banyak satu elemen . Ini adalah properti yang buruk jika Anda ingin logika di mana ada tipe dengan lebih dari satu elemen (katakanlah, nat). Referensi adalah: Model CC yang tidak terlalu sederhana dan tidak terbukti relevan , oleh Miquel dan Werner.

0 \neq 1

$0\neq 1$

n a t

$\mathrm{nat}$

cody

Anda mengatakan bahwa Fw "jauh lebih kuat" daripada Sistem F. Apakah Anda punya referensi untuk ini? Khususnya apakah ada fungsi pada bilangan asli yang dapat dibuktikan total dalam Fw tetapi tidak dalam F?

Thorsten Altenkirch

Saya sering ingin mencoba dan merangkum setiap dimensi dari kubus dan apa yang mereka wakili, jadi saya akan mencoba yang ini. $\lambda$

Tetapi pertama-tama, seseorang mungkin harus mencoba untuk menguraikan berbagai masalah. Prover teorema interaktif Coq didasarkan pada teori tipe yang mendasarinya, kadang-kadang dengan penuh kasih disebut kalkulus konstruksi induktif dengan alam semesta . Anda akan perhatikan bahwa ini lebih dari sekadar “Kalkulus Konstruksi”, dan memang, ada lebih banyak hal di sana daripada hanya CoC. Secara khusus, saya pikir Anda bingung tentang fitur mana yang ada di CoC yang tepat. Secara khusus, pembedaan Set / Prop dan alam semesta tidak muncul dalam CoC.

Saya tidak akan memberikan gambaran lengkap tentang Sistem Jenis Murni di sini, tetapi aturan penting (untuk PTS fungsional seperti CoC) adalah sebagai berikut

\frac{Γ ⊢ A : s Γ, x : A ⊢ B : k}{Γ ⊢ Π x : A . B : k} (s, k) \in R

$\frac{\Gamma\vdash A:s\qquad \Gamma,x:A\vdash B:k}{\Gamma\vdash \Pi x:A.B\ :\ k}\ (s,k)\in R$

di mana adalah elemen dari set tetap dari macam , dan pasangan adalah dalam satu set tetap pasang , yang disebut aturan . $s,k$ $S$ $(s,k)$ $R$ $S$

The wawasan penting adalah bahwa pilihan hati-hati dan membuat perbedaan besar dalam apa jenis produk sebenarnya mewakili! $S$ $R$ $\Pi x:A.B$

Secara khusus, dalam kalkulus konstruksi, himpunan macam adalah Sering disebut Prop dan Tipe (meskipun terminologi ini agak membingungkan bagi pengguna Coq karena alasan saya akan bicarakan nanti), dan lengkap seperangkat aturan: $S$

{*, ◻}

$\{*, \square\}$

R = {(*, *), (◻, ◻), (◻, *), (*, ◻)}

$R=\{(*,*),(\square,\square),(\square,*),(*,\square)\}$

Dan jadi kami memiliki 4 aturan yang sesuai dengan 4 tujuan berbeda:

: Jenis fungsi $(*,*)$
$(\square,\square)$
$(\square,*)$
$(*,\square)$

Saya akan menjelaskan masing-masing lebih terinci.

$A\rightarrow B$ $\Pi x:A.B$ $x$ $B$

$*$ $\mathrm{nat}$ $\mathrm{bool}$ $x=y$ $x$ $y$ $*$

Ketik keluarga : ini memberikan Anda kemampuan untuk berbicara tentang familly sendiri, memang sebagai istilah juga diketik , bukan hanya contoh $\mathrm{list}$ $\mathrm{list}:*\rightarrow *$ $\mathrm{list}_{\mathrm{nat}}, \mathrm{list}_{\mathrm{bool}}$ $*\rightarrow *$ $(\square,\square)$

Π t : * . t \to t

$\Pi t:*.\ t\rightarrow t$

λ (t : *) (x : t) . x

$\lambda (t:*)(x:t).x$

Π t : * ._

$\Pi t:*.\_$

(◻, *)

$(\square, *)$

t \to t

$t\rightarrow t$

(*, *)

$(*,*)$

A \land B := Π t : * . (A \to B \to t) \to t

$A\wedge B := \Pi t:*.\ (A \rightarrow B\rightarrow t)\rightarrow t$

SEBUAH \lor B : = Π t : * . (SEBUAH \to t) \to (B \to t) \to t

$A\vee B := \Pi t:*.\ (A \rightarrow t)\rightarrow(B\rightarrow t)\rightarrow t$

⊥ : = Π t : * . t

$\bot := \Pi t:*.\ t$

⊤ : = Π t : * . t \to t

$\top := \Pi t:*.\ t\rightarrow t$

\exists x : A . P (x) := Π t : * . (Π y : A . P (y) \to t) \to t

$\exists x:A.\ P(x):= \Pi t:*.\ (\Pi y: A.\ P(y)\rightarrow t)\rightarrow t$

(*, ◻)

$(*,\square)$

$*$ $*$ $(\square, *)$

$(\square,\square)$

Π c : * \to * . c n a t \to c n a t

$\Pi c:*\rightarrow *.\ \ c\ \mathrm{nat}\rightarrow c\ \mathrm{nat}$

Jenis dependen : Ini adalah bagaimana Anda mendapatkan proposisi-sebagai-jenis $0=1$

= : n a t \to n a t \to *

$=\ :\ \mathrm{nat}\rightarrow\mathrm{nat}\rightarrow *$

= : Π t : * . t \to t \to *

$=\ :\ \Pi t:*.\ t\rightarrow t\rightarrow *$

n a t \to n a t \to *

$\mathrm{nat}\rightarrow\mathrm{nat}\rightarrow *$

(*, ◻)

$(*,\square)$

$\square \rightarrow \square$ $\square$ $\square$ $\square_i$ $i=1,2,3,\ldots$ $\square_i:\square_{i+1}$

Aturan apa yang kita inginkan untuk ini? Satu aturan alami adalah $(\square_i, \square_i)$

\frac{Γ ⊢ A : ◻_{i}}{Γ ⊢ A : ◻_{j}} i \leq j

$\frac{\Gamma\vdash A:\square_i}{\Gamma\vdash A:\square_j}\ i\leq j$

Dengan jenis dan aturan ekstra ini, Anda mendapatkan sesuatu yang bukan PTS, tetapi sesuatu yang dekat. Ini adalah (hampir) Kalkulus Konstruksi yang Diperluas , yang lebih dekat dengan basis Coq. Bagian besar yang hilang di sini adalah tipe induktif, yang tidak akan saya bahas di sini.

Sunting: Ada referensi yang agak bagus yang menggambarkan berbagai fitur bahasa pemrograman dalam kerangka PTS, dengan menjelaskan PTS yang merupakan kandidat yang baik untuk representasi perantara dari bahasa pemrograman fungsional:

Henk: Bahasa Antara yang Diketik , SP Jones & E. Meijer.

cody
sumber

Topik Lanjutan dalam Jenis dan Bahasa Pemrograman, S2.6 dan S2.7 .

Kaveh

BTW "Keluarga tipe" sering juga disebut tipe yang lebih tinggi.

Martin Berger

PTS adalah ide yang bagus 20 tahun yang lalu tetapi banyak hal telah berubah sejak saat itu.

Thorsten Altenkirch

@ThorstenAltenkirch tidak perlu untuk eksklusiisme, Thorsten! Masih ada beberapa hal menyenangkan yang perlu dipertimbangkan untuk melibatkan PTS, misalnya karya Bernardy tentang parametrisitas yang diinternalisasi muncul dalam pikiran.

cody

@cody Tidak ada eksklusiisme yang dimaksudkan tetapi kita seharusnya tidak terjebak di masa lalu teori tipe sintaksis. Karya Bernardi sangat bagus dan dapat dilakukan dengan lebih baik menggunakan alam semesta.

Thorsten Altenkirch