Existe-t-il un calcul lambda typé où la logique correspondante sous la correspondance de Curry-Howard est cohérente et où il existe des expressions lambda typables pour chaque fonction calculable? Il s'agit certes d'une question imprécise, dépourvue d'une définition précise du «calcul lambda typé»....
Pierce (2002) introduit la relation de frappe à la page 92 en écrivant: La relation de typage pour les expressions arithmétiques, écrite "t: T", est définie par un ensemble de règles d'inférence affectant des types aux termes et la note de bas de page indique que le symbole est souvent utilisé au...
Quelqu'un peut-il expliquer brièvement (si c'est possible!) Ou me renvoyer à une référence, résumant les différences entre le calcul lambda non typé et les calculs lambda typés plus courants? Je recherche en particulier des énoncés de leur puissance expressive, des équivalences avec des systèmes...
Dans un récent fil de discussion sur la liste de diffusion d'Agda, la question des lois ηη\eta est apparue, dans laquelle Peter Hancock a fait une remarque stimulante . Ma compréhension est que les lois ηη\eta viennent avec des types négatifs, c'est-à-dire. connecteurs dont les règles...
Existe-t-il un moyen de prouver le théorème suivant dans Coq? Theorem bool_pirrel : forall (b : bool) (p1 p2 : b = true), p1 = p2. EDIT : Une tentative de donner une brève explication de "ce qu'est la pertinence non pertinente" (corrigez-moi quelqu'un si je me trompe ou je me trompe) L'idée de base...
Cette page affirme que de nombreux langages n'utilisent pas de sous-typage implicite (équivalence structurelle), préférant le sous-typage explicite / déclaré (équivalence de déclaration) J'ai surtout utilisé des langages de programmation qui utilisent un sous-typage explicite . Quels sont les...
Imaginez, nous avons défini les nombres naturels dans le calcul lambda typé de manière dépendante comme des chiffres de l'Église. Ils peuvent être définis de la manière suivante: SimpleNat = (R : Set) → R → (R → R) → R zero : SimpleNat zero = λ R z _ → z suc : SimpleNat → SimpleNat suc sn = λ R z s...
À partir de Curry-Howard-Lambek, il y a eu une belle trinité de théories de types, de logiques et de catégories. Je suis curieux de savoir quelle sémantique catégorique vous obtenez lorsque vous ajoutez un sous-typage (coercitif) à une théorie des types - il semble que cela n'ait pas été beaucoup...
En regardant le blog sur la théorie des types d'homotopie, on peut facilement trouver beaucoup de bibliothèque formalisant la plupart de la théorie des types d'homotopie dans Agda et Coq. Quelqu'un sait-il s'il existe une tentative similaire de formaliser HoTT dans Idris
Nous voulons souvent définir un objet selon certaines règles d'inférence. Ces règles désignent une fonction génératrice qui, lorsqu'elle est monotone, donne un point moins fixe . Nous prenons pour être la "définition inductive" de . De plus, la monotonie de nous permet de raisonner avec le...
Une faible normalisation pour le calcul lambda typé simple peut être prouvée (Turing) par induction sur . Un calcul lambda étendu avec des récurseurs sur les nombres naturels (Gentzen) a une stratégie de normalisation faible par induction sur .ϵ 0ω2ω2\omega^2ϵ0ϵ0\epsilon_0 Qu'en est-il du système F...
Le manuscrit suivant est-il accessible au public? Dana Scott, 1969, Une théorie des fonctions calculables de type supérieur . Notes de séminaire non publiées, 7 pages, Université d'Oxford. Il y a une discussion de cet article dans la section 8.1.2, Types as sets , dans Cardone & Hindley, 2006...
Existe-t-il un moyen naturel de comprendre l'essence de la sémantique relationnelle pour le polymorphisme paramétrique? Je viens de commencer à lire sur la notion de paramétrie relationnelle, à la "Types, abstraction et polymorphisme paramétrique" de John Reynolds, et j'ai du mal à comprendre...
Supposons que nous ayons affaire à un langage de programmation prenant en charge les types linéaires (les termes de type linéaire peuvent être utilisés au maximum une fois, pour ainsi dire). Cela permet de traiter certains effets de calcul (comme la mutation, voire de changer le type de l'opérande)...
L'algèbre booléenne peut être exprimée dans le calcul lambda non typé de cette manière (par exemple). true = \t. \f. t; false = \t. \f. t; not = \x. x false true; and = \x. \y. x y false; or = \x. \y. x true y; L'algèbre booléenne peut également être encodée dans le système F de cette manière :...
Donc, il y a quelque temps, quelqu'un m'a d'abord dit que call / cc pouvait autoriser des objets de preuve pour des preuves classiques en implémentant la loi de Peirce. J'ai réfléchi au sujet récemment et je n'arrive pas à trouver un défaut. Cependant, je n'arrive pas vraiment à voir quelqu'un...
Dans la perspective du langage de programmation, que signifie le sous-typage? J'ai entendu dire que "l'héritage n'est pas un sous-typage". Quelles sont alors les différences entre l'héritage et le
Une catégorie a des sous - produits lorsque les mêmes objets sont à la fois les produits et coproduits. Quelqu'un a-t-il étudié la théorie de la preuve des catégories avec des biproduits? L'exemple le plus connu est peut-être la catégorie des espaces vectoriels, dans laquelle la somme directe et...
Pour une théorie des types, par cohérence, je veux dire qu'elle a un type qui n'est pas habité. De la forte normalisation du cube lambda, il s'ensuit que le système FFF et le système FωFωF_\omega sont cohérents. Les types inductifs MLTT + ont également une preuve de normalisation. Cependant,...
Les relations logiques pour les langages imprédicatifs comme le système F semblent s'appuyer de manière critique sur l'imprédicativité de la logique ambiante. Plus précisément, l'interprétation du forall-type sera définie en termes de toutes les relations typées. Dans un système imprédicatif (comme...