Dlaczego typy rekurencyjne są potrzebne jako prymitywy dla prób w systemach typu zależnego?

Jestem stosunkowo nowy w teorii typów i programowaniu zależnym. Studiowałem rachunek różniczkowy konstrukcji (CoC) i inne systemy czystego typu. Szczególnie interesuje mnie wykorzystanie go jako pośredniej reprezentacji zabezpieczającej system kompilatora.

Rozumiem, że typy (ko) rekurencyjne są reprezentatywne , obliczeniowo , przy użyciu jako jedynego konstruktora typów. Przeczytałem jednak, że nie można ich używać do budowania dowodów przez indukcję (wybacz mi, nie mogę teraz znaleźć gdzie!), Np. Że nie mogłem udowodnić, że w zwykłym CoC (chociaż można wpisać jako ). $\Pi$ $0\neq 1$ $\texttt{Nat}$ $\Pi(\mathbb{N}:*).\Pi(S:\mathbb{N}\rightarrow\mathbb{N}).\Pi(Z:\mathbb{N}).\mathbb{N}$

Zakładam, że właśnie dlatego zbudowali rachunek konstrukcji indukcyjnych (CIC). Czy to jest poprawne? Ale dlaczego? Nie mogłem znaleźć żadnego materiału wyjaśniającego, dlaczego takich dowodów nie można przedstawić bez użycia typów (ko) indukcyjnych jako prymitywów. Jeśli nie jest to prawdą, to po co dodawać je jako prymitywy w CIC?

type-theory dependent-types coq paulotorrens
źródło

Nie jestem ekspertem, ale podam przykład z tego, co do tej pory rozumiałem.

Rozważmy typ boolowski w CoC, używając jego standardowego kodowania: Możemy się spodziewać, że będziemy w stanie udowodnić

\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}$

Rzeczywiście, szybko wynika to z zasady eliminacji / indukcji zależnej, którą mamy np. W CiC

Π_{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)$

Jednak tak naprawdę nie możemy oczekiwać (*) utrzymania we wszystkich modelach CoC! Intuicyjnie wartość w powinna z grubsza być rodziną funkcji przypisującą każdemu typowi wartość w interpretacji . Ale to nie zmusza do bycia jednym z wartości . Możemy mieć np. (Nieformalnie) $\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$

Aby mieć pewność, że wartości są jedynymi możliwymi wartościami, musimy ograniczyć się do modeli parametrycznych . Rzeczywiście (tak sądzę) właściwość można udowodnić na podstawie dowolnego twierdzenia związanego z wielopisem . $\sf tt,ff$ $(*)$ $\mathbb{B}$

Jednak, o ile rozumiem, CoC nie wyklucza modeli ad-hoc, w których parametryczność nie obowiązuje. W niektórych z nich jest po prostu fałszem. Dzięki solidności w obecności kontrmodelu dochodzimy do wniosku, że nie jest zamieszkały w CoC. W związku z tym w CoC nie ma też wyrażenia . $(*)$ $(*)$ $\mathbb{B}_{ind}$

chi
źródło

(λ (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

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$

Π_{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$

Dlaczego typy rekurencyjne są potrzebne jako prymitywy dla prób w systemach typu zależnego?

Odpowiedzi: