Intuition derrière une positivité stricte?

10

Je me demande si quelqu'un peut me donner l'intuition derrière pourquoi la positivité stricte des types de données inductifs garantit une forte normalisation.

Pour être clair, je vois comment avoir des occurrences négatives conduit à la divergence, c'est-à-dire en définissant:

data X where Intro : (X->X) -> X

nous pouvons écrire une fonction divergente.

Mais je me demande, comment pouvons-nous prouver que les types inductifs strictement positifs ne permettent pas la divergence? Existe-t-il une mesure d'induction qui nous permet de construire une preuve de forte normalisation (en utilisant des relations logiques ou similaires)? Et où une telle preuve se décompose-t-elle pour les événements négatifs? Y a-t-il de bonnes références qui montrent une forte normalisation pour une langue avec des types inductifs?

jmite
la source
Je pense que l'idée est que les types strictement positifs peuvent se convertir en types W, conceptuellement. Le type positif non strict est également incompatible avec Coq vilhelms.github.io/posts/… . On dit que le type positif est compatible avec Agda, mais j'aimerais aussi voir une explication conceptuelle ...
molikto
@molikto Merci, c'est utile. Mais je pensais que les types W ne donnaient pas les principes d'induction souhaités dans une théorie intensionnelle? Comment prouver une forte normalisation des inductifs strictement positifs dans une théorie intensionnelle?
jmite

Réponses:

8

Il semble que vous souhaitiez un aperçu des arguments de normalisation pour les systèmes de types avec des types de données positifs. Je recommanderais la thèse de doctorat de Nax Mendler: http://www.nuprl.org/documents/Mendler/InductiveDefinition.html .

λ

Inductive Ord = Zero : Ord | Suc : Ord -> Ord | Lim : (Nat -> Ord) -> Ord

Nous obtiendrions:

λ(t)=0
t
λ(Zero)=0
λ(Suc(o))=λ(o)+1
λ(Lim(f))=supnλ(f n)

où s'étend sur des termes aux formes normales. La mise en garde est que cette interprétation n'est définie que dans le 3ème cas lorsque a également une forme normale, ce qui nécessite un certain soin dans les définitions.nf n

On peut alors définir des fonctions récursives par induction sur cet ordinal.

Notez que ces types de données peuvent déjà être définis dans la théorie des ensembles classiques, comme indiqué dans l'excellent article sur les familles inductives de Dybjer ( http://www.cse.chalmers.se/~peterd/papers/Inductive_Families.pdf ). Cependant, comme les espaces de fonction sont si énormes, des types comme Ordnécessitent des ordinaux vraiment grands pour interpréter.

cody
la source
Merci, ceci est très utile! Savez-vous si de tels ordinaux peuvent être définis dans la théorie des types elle-même? c'est-à-dire que si j'essayais d'utiliser Agda to avec induction-récursion pour modéliser une théorie des types avec inductifs (mais pas d'induction-récursivité), pourrais-je utiliser quelque chose comme Ordpour modéliser les ordinaux nécessaires pour montrer le bien-fondé?
jmite
@jmite, vous pouvez, mais les ordinaux dans les théories constructives sont un peu étranges, et vous pourriez aussi bien travailler avec des ordres ou des arbres bien fondés ( un type la W comme le suggère molikto). Il pourrait être difficile d'avoir un seul type uniforme qui capture le bien-fondé de chaque inductif dans le langage objet ...
cody
1
@cody N'est-ce pas l'exemple Ord que vous donnez d'un type strictement positif?
Henning Basold
1
@HenningBasold oui c'est (c'est pourquoi je l'ai utilisé comme illustration!). Mais il ne se comporte pas exactement comme les ordinaux dans une théorie des ensembles (classique), et certainement pas comme l'ensemble de tous les ordinaux. En particulier, il est un peu difficile de définir un ordre sur ces derniers.
cody
1
@HenningBasold Je dois également noter que la question de jmite concernait spécifiquement les types strictement positifs, bien que les informations sur le cadre plus général soient également intéressantes!
cody
6

Une autre bonne source pour aller au-delà des types strictement positifs est la thèse de doctorat de Ralph Matthes: http://d-nb.info/956895891

Il discute des extensions du système F avec des types (strictement) positifs dans le chapitre 3 et prouve de nombreux résultats de normalisation solides dans le chapitre 9. Il y a quelques idées intéressantes discutées dans le chapitre 3.

  1. Nous pouvons ajouter des points les moins fixes pour tout type avec variable libre , tant que nous pouvons fournir un témoin de monotonie . Cette idée est déjà présente dans le travail de Mendler que cody a mentionné. De tels témoins existent canoniquement pour tout type positif car ils sont syntaxiquement monotones.ρααβ.(αβ)ρρ[β/α]

  2. Lorsque nous passons de types strictement positifs à des types positifs, les types inductifs ne peuvent plus être considérés comme des arbres (l'encodage de type W). Au lieu de cela, ils introduisent une certaine forme d'imprédicativité parce que la construction d'un type inductif positif quantifie déjà sur le type lui-même. Notez qu'il s'agit d'une forme d'imprédicativité quelque peu légère, car la sémantique de ces types peut encore être expliquée en termes d'itération ordinale des fonctions monotones.

  3. Matthes fournit également quelques exemples de types inductifs positifs. Particulièrement intéressants sont

    • le type de continuations , où ne se produit pas dans .μ.1+((αρ)ρ)αρ
    • le type qui fonctionne pour tout type en le transformant en un type positif. Notez que cela utilise très fortement l'imprédicativité du système F.μαβ.(αβ)ρ[β/α]ρ

Matthes utilise également des types inductifs positifs pour analyser la double négation, par exemple, dans cet article: https://www.irit.fr/~Ralph.Matthes/papers/MatthesStabilization.pdf . Il introduit une extension du de Parigot et prouve une forte normalisation.λμ

J'espère que cela répond à votre question.

Henning Basold
la source