J'ai du mal à comprendre le but de la quantification universelle et existentielle des types. Je joue avec l'écriture d'un langage jouet basé sur le calcul des constructions . J'ai lu sur Morte et Henk pour m'aider à mieux comprendre.
Je ne comprends pas pourquoi le CoC a une abstraction lambda et forall.
( ∀ x : A . B )
( Λ x : A . B )
( ∀ x : A . B )
Il me semble que lambda subsume forall dans un système où les types sont passés manuellement. En d'autres termes, que les éléments suivants
( ∀ x : * . Λ a : x . A )
Pourrait être remplacé par
( λ x : ∗ . λ a : x . a )
S'il a d'abord été appliqué au type utilisé.
Qu'est-ce que je rate? Quels sont les articles, blogs ou articles à lire qui pourraient m'aider?
Il est utile de se rappeler que (ou comme vous le voyez parfois) est un type. C'est généraliser . Donc, alors qu'il est parfaitement logique de dire , cela n'a pas de sens de dire parce que n'est qu'un type. Vous ne diriez pas que parce que n'est pas pour le calcul en soi, il est là pour classer les termes lambda qui peuvent être appliqués comme ceci .tc → ( λ x : A . M ) N ( ∀ x : A . M ) N ∀ . . . ( A → B ) N →∀Π→( Λ x : A . M) N( ∀ x : A . M) N∀ . . .( A → B ) N→
C'est quelque chose qui m'a aussi fait trébucher, mais c'est ainsi que le calcul des constructions (ainsi que tout autre système typé de manière dépendante) est défini.
Les deux programmes que vous avez écrits ont des intentions très différentes et le premier est mal typé. Il n'est pas logique de dire parce que requiert ses deux arguments par types, ce qui signifie que si doit être bien typé, nous devons avoir . Cependant, n'est pas un type, on ne peut lui affecter qu'un type de la forme , jamais . Le second, d'autre part, est presque (je pense que vous vouliez renvoyer pas ) est une fonction et est donné un type utilisant deux s.∀ ∀ x : A . B B : ∗ λ x . x ∀ x : A . B ∗ a x ∀∀ x : A . λ x . X∀∀ x : A . BB : ∗λ x . X∀ x : A . B∗uneX∀
Pas exactement. Je suis encore un peu confus. Je vais peut-être devoir y réfléchir davantage. J'ai changé les deux programmes d'exemple pour retourner plutôt que x depuis que j'essayais d'implémenter i d . :)uneXje d
oconnor0
Je pense qu'à un certain niveau, je voulais faire des termes et des types la même chose. Entre votre réponse et cs.stackexchange.com/questions/49531/… Je pense que je vois où je suis allé de travers. Je veux le faire dans un système fortement normalisant.
oconnor0
5
Gardez à l'esprit que les types existentiels et universels sont assez différents. C'est la logique constructive, pas la logique classique et en logique constructive et ∃ ne sont pas aussi liés qu'ils le sont en logique classique.∀∃
est le type de programmes qui reçoivent un objet de type A et renvoient un objet de type B ( x ) . L'important ici est que le type B ( x ) dépendde x et n'est pas le même pour tous les x . Cela peut varier en fonction de ce que x est. Pour une entrée x, nous pouvons produire un entier. Pour un autre, nous pourrions produire un nombre réel. Pour encore un autre, nous pourrions produire une fonction sur des nombres réels. Si B ( x )∀ x : A . B ( x )UNEB ( x )B ( x )XXXXB ( x )ne pas varier en fonction vous pouvez utiliser A → B en place qui est le type de fonctions de A à B .XA → BUNEB
est laversiondépendantede la disjonction (constructive). Vous pouvez penser constructive disjunction A ∨ B de deux types A et B comme l'union disjointe de A et B .
∃ x : A . B ( x ) est l'union disjointe d'une collection de types B ( x )
indexé par x : A . Le fait que le type B (∃ x : A . B ( x )A ∨ BUNEBUNEB∃ x : A . B ( x )B ( x )x : A van varie en fonction de la valeur de x : A en
fait un type dépendant. Comparer avec le cas où B ne dépend pas de x : A : ∃ x : A . B . Nous prenons une copie du même B pour chaque x : A . Ceci est isomorphe à A de B .B ( x )x : ABx:A∃x:A.BBx:AA×B
Vous pouvez maintenant demander pourquoi nous avons besoin de types de produits et de sommes dépendants ? Parce qu'ils nous donnent plus de pouvoir expressif. Nous pouvons maintenant ignorer complètement les types et avoir une théorie des types / programmation fonctionnelle non typée. Mais cela supprime les avantages d'avoir des types en premier lieu, par exemple, vous ne saurez pas si tous les programmes se termineront toujours (forte normalisation). Voir Cube Lambda et
type dépendant . Je pense qu'un bon moyen de bien comprendre les types dépendants est d'examiner les règles d'introduction et d'élimination des types dépendants dans la théorie des types de Martin-Lof .
Le point principal des types dépendants est: nous voulons rester dans une belle théorie typée pour diverses raisons (par exemple en évitant les bogues, la preuve automatique de la terminaison, etc.). Nous ne voulons pas aller à quelque chose comme le calcul lambda non typé où nous pouvons faire exprimer comme ceux que vous avez indiqués et des choses beaucoup plus puissantes. On peut dire que les types dépendants ont été inventés pour permettre d'exprimer plus de choses tout en restant dans une belle théorie des types.
Gardez à l'esprit que les types existentiels et universels sont assez différents. C'est la logique constructive, pas la logique classique et en logique constructive et ∃ ne sont pas aussi liés qu'ils le sont en logique classique.∀ ∃
est le type de programmes qui reçoivent un objet de type A et renvoient un objet de type B ( x ) . L'important ici est que le type B ( x ) dépendde x et n'est pas le même pour tous les x . Cela peut varier en fonction de ce que x est. Pour une entrée x, nous pouvons produire un entier. Pour un autre, nous pourrions produire un nombre réel. Pour encore un autre, nous pourrions produire une fonction sur des nombres réels. Si B ( x )∀ x : A . B ( x ) UNE B ( x ) B ( x ) X X X X B ( x ) ne pas varier en fonction vous pouvez utiliser A → B en place qui est le type de fonctions de A à B .X A → B UNE B
est laversiondépendantede la disjonction (constructive). Vous pouvez penser constructive disjunction A ∨ B de deux types A et B comme l'union disjointe de A et B . ∃ x : A . B ( x ) est l'union disjointe d'une collection de types B ( x ) indexé par x : A . Le fait que le type B (∃ x : A . B ( x ) A ∨ B UNE B UNE B ∃ x : A . B ( x ) B ( x ) x : A van varie en fonction de la valeur de x : A en
fait un type dépendant. Comparer avec le cas où B ne dépend pas de x : A : ∃ x : A . B . Nous prenons une copie du même B pour chaque x : A . Ceci est isomorphe à A de B .B ( x ) x : A B x:A ∃x:A.B B x:A A×B
Vous pouvez maintenant demander pourquoi nous avons besoin de types de produits et de sommes dépendants ? Parce qu'ils nous donnent plus de pouvoir expressif. Nous pouvons maintenant ignorer complètement les types et avoir une théorie des types / programmation fonctionnelle non typée. Mais cela supprime les avantages d'avoir des types en premier lieu, par exemple, vous ne saurez pas si tous les programmes se termineront toujours (forte normalisation). Voir Cube Lambda et type dépendant . Je pense qu'un bon moyen de bien comprendre les types dépendants est d'examiner les règles d'introduction et d'élimination des types dépendants dans la théorie des types de Martin-Lof .
Le point principal des types dépendants est: nous voulons rester dans une belle théorie typée pour diverses raisons (par exemple en évitant les bogues, la preuve automatique de la terminaison, etc.). Nous ne voulons pas aller à quelque chose comme le calcul lambda non typé où nous pouvons faire exprimer comme ceux que vous avez indiqués et des choses beaucoup plus puissantes. On peut dire que les types dépendants ont été inventés pour permettre d'exprimer plus de choses tout en restant dans une belle théorie des types.
la source