Types dépendants par rapport au type codé par Church dans PTS / CoC

J'expérimente des systèmes de type pur dans le cube lambda de Barendregt, en particulier avec le plus puissant, le Calcul des constructions. Ce système a des sortes *et BOX. Pour mémoire, j'utilise ci-dessous la syntaxe concrète de l' Morteoutil https://github.com/Gabriel439/Haskell-Morte-Library qui est proche du calcul lambda classique.

Je vois que nous pouvons émuler des types inductifs par une sorte de codage de type Church (alias isomorphisme Boehm-Berarducci pour les types de données algébriques). Pour un exemple simple, j'utilise type Bool = ∀(t : *) -> t -> t -> tavec les constructeurs True = λ(t : *) -> λ(x : t) -> λ(y : t) -> xet False = λ(t : *) -> λ(x : t) -> λ(y : t) -> y.

Je vois que le type de fonctions au niveau du terme Bool -> Test isomorphe à des paires de type Product T Tavec une Product = λ(A : *) -> λ(B : *) -> ∀(t : *) -> (A -> B -> t) -> tparamétricité modulo classique au moyen d'une fonction if : Bool -> λ(t : *) -> t -> t -> tqui est en fait l'identité.

Toutes les questions ci-dessous porteront sur les représentations des types dépendants Bool -> *.

Je peux diviser D : Bool -> *en paire de D Trueet D False. Existe-t-il la manière canonique de créer à Dnouveau? Je veux reproduire l'isomosphisme Bool -> T = Product T Tpar un analogue de fonction ifau niveau du type mais je ne peux pas écrire cette fonction aussi simple qu'original ifcar nous ne pouvons pas passer des types dans des arguments comme des types.
J'utilise une sorte de type inductif avec deux constucteurs pour résoudre la question (1). La description de haut niveau (style Agda) est le type suivant (utilisé à la place du niveau de type if)
```
data BoolDep (T : *) (F : *) : Bool -> * where
  DepTrue : T -> BoolDep T F True
  DepFalse : F -> BoolDep T F False
```
avec l'encodage suivant dans PTS / CoC:
```
λ(T : *) -> λ(F : *) -> λ(bool : Bool ) ->
∀(P : Bool -> *) ->
∀(DepTrue : T -> P True ) ->
∀(DepFalse : F -> P False ) ->
P bool
```
Mon encodage ci-dessus est-il correct?

Je peux écrire les constructeurs pour BoolDepcomme ce code pour DepTrue : ∀(T : *) -> ∀(F : *) -> T -> BoolDep T F True:

λ(T : *) ->  λ(F : *) ->  λ(arg : T ) ->
λ(P : Bool -> *) ->
λ(DepTrue : T -> P True ) ->
λ(DepFalse : F -> P False ) ->
DepTrue arg

mais je ne peux pas écrire la fonction inverse (ou toute fonction dans le sens inverse). C'est possible? Ou devrais-je utiliser une autre représentation pour BoolDepproduire un isomorphisme BoolDep T F True = T?

type-theory type-systems dependent-type ZeitRaffer
la source

Product T T

$\text{Product T T}$

Bool \to T

$\text{Bool} \to T$

Bool \to T

$\text{Bool} \to T$

(\forall (t : *) \to (t \to t \to t)) \to T

$(\forall (t : *) \to (t \to t \to t)) \to T$

Product T T

$\text{Product} T T$

\forall (t : *) \to ((T \to T \to t) \to t)

$\forall (t : *) \to ((T \to T \to t) \to t)$

@Giorgio Mossa voir cstheory.stackexchange.com/questions/30923/… - si vous avez la paramétricité (pas dans tous les modèles mais dans le modèle initial (syntaxique)) alors vous avez l'isomorphisme.

ZeitRaffer

Réponses:

Vous ne pouvez pas faire cela en utilisant l'encodage traditionnel de l'Église pour Bool:

#Bool = ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool

... car vous ne pouvez pas écrire une fonction (utile) de type:

#Bool → *

La raison pour laquelle, comme vous l'avez noté, est que vous ne pouvez pas passer *comme premier argument à #Bool, ce qui signifie que les arguments Trueet Falsepeuvent ne pas être des types.

Il existe au moins trois façons de résoudre ce problème:

Utilisez le calcul des constructions inductives. Ensuite, vous pouvez généraliser le type de #Bool:
```
#Bool = ∀(n : Nat) → ∀(Bool : *ₙ) → ∀(True : Bool) → ∀(False : Bool) → Bool
```
... et vous instancierez nà 1, qui signifie que vous pouvez passer *₀comme second argument, qui de type vérification parce que:
```
*₀ : *₁
```
... vous pouvez alors utiliser #Boolpour sélectionner entre deux types.
Ajoutez un tri supplémentaire:
```
* : □ : △
```
Ensuite, vous définiriez un #Bool₂type distinct comme celui-ci:
```
#Bool₂ = ∀(Bool : □) → ∀(True : Bool) → ∀(False : Bool) → Bool
```
Il s'agit essentiellement d'un cas particulier du Calcul des constructions inductives, mais produit un code moins réutilisable car maintenant nous devons conserver deux définitions distinctes de #Bool, une pour chaque type que nous souhaitons prendre en charge.
Encode #Bool₂directement dans le calcul des constructions comme:
```
#Bool₂ = ∀(True : *) → ∀(False : *) → *
```

Si le but est de l'utiliser directement dans une version non modifiée, morteseule l'approche # 3 fonctionnera.

Gabriel Gonzalez
la source

Comme je peux le voir, nous ne pouvons pas convertir # Bool₁ -> # Bool₂, n'est-ce pas?

ZeitRaffer

@ZeitRaffer C'est vrai. Vous ne pouvez pas convertir de #Bool₁à#Bool₂

Gabriel Gonzalez

Hmm ... IIUC vous appelez "Calcul des constructions inductives" un calcul avec une hiérarchie infinie de types, mais AFAIK le CIC d'origine n'avait pas une telle chose (il n'a ajouté que des types inductifs au CoC). Vous pensez peut-être à l'ECC de Luo (calcul étendu des constructions)?

Stefan