Mengapa tipe rekursif diperlukan sebagai primitif untuk bukti dalam sistem tipe dependen?

Saya relatif baru mengetik teori dan pemrograman dependen. Saya telah mempelajari kalkulus konstruksi (CoC) dan sistem tipe murni lainnya. Saya sangat tertarik menggunakannya sebagai representasi perantara untuk sistem kompiler.

Saya mengerti bahwa (co-) tipe rekursif dapat diwakili , secara komputasi , menggunakan sebagai satu-satunya tipe konstruktor. Saya telah membaca, bahwa mereka tidak dapat digunakan untuk membangun bukti dengan induksi (maafkan saya, saya tidak dapat menemukan di mana sekarang!), Misalnya, bahwa saya tidak dapat membuktikan bahwa di CoC biasa (walaupun dapat diketik dengan ). $\Pi$ $0\neq 1$ $\texttt{Nat}$ $\Pi(\mathbb{N}:*).\Pi(S:\mathbb{N}\rightarrow\mathbb{N}).\Pi(Z:\mathbb{N}).\mathbb{N}$

Saya berasumsi inilah sebabnya mereka membangun kalkulus konstruksi induktif (CIC). Apakah ini benar? Tapi kenapa? Saya tidak dapat menemukan bahan yang menjelaskan mengapa bukti tersebut tidak dapat diwakili tanpa menggunakan (co) tipe induktif sebagai primitif. Jika ini tidak benar, lalu mengapa menambahkannya sebagai primitif di CIC?

type-theory dependent-types coq paulotorrens
sumber

Saya bukan ahli, tetapi saya akan membagikan apa yang saya pahami sejauh ini dengan sebuah contoh.

Mari kita pertimbangkan tipe boolean dalam CoC, menggunakan pengkodean standarnya: Kita mungkin bisa membuktikan Memang, ini dengan cepat mengikuti dari prinsip eliminasi / induksi tergantung kita miliki misalnya dalam CiC

\begin{array}{l} B = Π_{τ : *} τ \to τ \to τ \\ t t = λ τ : *, x : τ, y : τ . x \\ f f = λ τ : *, x : τ, y : τ . y \end{array}

$\begin{array}{l} \mathbb{B} = \Pi_{\tau:*} \tau \to \tau \to \tau \\ \mathsf{tt} = \lambda \tau:*,x:\tau,y:\tau.\ x \\ \mathsf{ff} = \lambda \tau:*,x:\tau,y:\tau.\ y \end{array}$

Π_{b : B} b = t t \lor b = f f (*)

$\Pi_{b : \mathbb{B}} b={\sf tt} \lor b = {\sf ff} \qquad(*)$

B_{i n d} : Π_{P : B \to *} P (t t) \to P (f f) \to Π_{b : B} P (b)

$\mathbb{B}_{ind} : \Pi_{P:\mathbb{B}\to*} P({\sf tt}) \rightarrow P({\sf ff}) \rightarrow \Pi_{b:\mathbb{B}} P(b)$

Namun, kita tidak bisa benar-benar berharap (*) bertahan di semua model CoC! Secara intuitif, nilai dalam seharusnya kira-kira merupakan kumpulan fungsi ditetapkan untuk setiap jenis nilai dalam interpretasi dari . Tapi ini tidak memaksa menjadi salah satu di antara nilai . Kita dapat memiliki mis (informal) $\mathbb{B}$ $\{f_\tau\}_{\tau}$ $\tau$ $\tau\to\tau\to\tau$ $f_\tau$ $\sf tt,ff$

f_{N} (n) (m) = n + m

$f_{\mathbb{N}}(n)(m) = n+m$

Untuk memastikan bahwa nilai adalah satu-satunya nilai yang mungkin, kita perlu membatasi diri kita pada model parametrik . Memang (saya pikir) properti dapat dibuktikan dari teorema bebas yang terkait dengan polytype . $\sf tt,ff$ $(*)$ $\mathbb{B}$

Namun, sejauh yang saya mengerti, CoC tidak mengesampingkan model ad-hoc, di mana parametricity tidak berlaku. Dalam beberapa di antaranya, benar-benar salah. Dengan kesehatan, di hadapan countermodel, kami menyimpulkan bahwa tidak dihuni di CoC. Akibatnya, tidak ada istilah dalam CoC. $(*)$ $(*)$ $\mathbb{B}_{ind}$

chi
sumber

Saya tidak yakin saya mengikuti. Misalnya, diberi ekspresi sebagai , ada banyak cara saya bisa membuat konstruktor untuk Nat, tetapi, pada akhirnya, tidakkah semuanya dibangun dari atau ?

(λ (N a t : *) . (. . .)) (Π (N : *) . Π (S : N \to N) . Π (Z : N) . N)

$(\lambda(Nat:*).(...)) (\Pi(\mathbb{N}:*).\Pi(S:\mathbb{N}\rightarrow\mathbb{N}).\Pi(Z:\mathbb{N}).\mathbb{N})$

S

$S$

Z

$Z$

paulotorrens

@ paulotorrens Di dalam logika, ya, saya percaya bahwa ini adalah satu-satunya pilihan. Namun dalam model CoC (model ad-hoc), mungkin ada nilai-nilai dari yang tidak dapat didefinisikan melalui . Pikirkan nilai alami sehingga untuk semua jenis kecuali untuk mana sebaliknya . Nilai berperilaku sebagai "nol" pada sebagian besar tipe, dan sebagai "satu" untuk boolean. Kami tidak dapat menulis dalam CoC untuk menentukan nilai itu , tetapi dalam model ad-hoc nilai itu mungkin tetap ada.

N a t

$Nat$

S, Z

$S,Z$

n

$n$

n (T) (S_{T}) (Z_{T}) = Z_{T}

$n(T)(S_T)(Z_T) = Z_T$

T

$T$

T = B

$T=\mathbb{B}$

n (B) (S) (Z) = S (Z)

$n(\mathbb{B})(S)(Z) = S(Z)$

n

$n$

λ T : * . i f T = B t h e n \dots

$\lambda T:*. {\sf if}\ T=\mathbb{B}\ {\sf then}\ \ldots$

n

$n$

chi

@paulotorrens Mungkin Anda bisa memahami masalah ini lebih mudah jika Anda berpikir tentang . Tipe ini hanya dihuni oleh identitas (polimorfik), dan dalam model parametrik itu memang satu-satunya nilai yang mungkin untuk istilah tipe itu. Tetapi, dalam model ad-hoc, kita mungkin mendefinisikan nilai untuk semua jenis tetapi untuk mana .

Π_{T : *} T \to T

$\Pi_{T:*} T\to T$

v (T) (x) = x

$v(T)(x) = x$

T

$T$

T = N

$T=\mathbb{N}$

v (N) (x) = x + 1

$v(\mathbb{N})(x) = x+1$

chi

Mengapa tipe rekursif diperlukan sebagai primitif untuk bukti dalam sistem tipe dependen?

Jawaban: