Qu'est-ce que la prédicativité?

Question

J'ai une intuition assez décente sur les types Haskell interdit comme «impédicatif»: à savoir ceux où un apparaît dans un argument à un constructeur de type autre que . Mais qu'est-ce que la prédicativité? Qu'est-ce qui le rend important? Quel est le lien avec le mot «prédicat»?

Answer 1

La question centrale de ce type de systèmes est la suivante: "Pouvez-vous remplacer un type polymorphe dans une variable de type?". Prédictive des systèmes de type sont les no-nonsense instituteur de répondre, "ABSOLUMENT PAS", tandis que impredicative type de systèmes sont votre insouciance copain qui pense, qui sonne comme une bonne idée et ce qui pourrait aller mal?

Maintenant, Haskell brouille le débat un peu, parce qu'il croit polymorphisme doit être utile, mais invisible. Donc pour le reste de ce post, je vais être écrit dans un dialecte de Haskell où les utilisations de l' forall sont non seulement permis, mais nécessaire. De cette façon, nous pouvons faire la distinction entre le type a, ce qui est un monomorphe type qui tire sa valeur de frappe de l'environnement que nous pouvons définir plus tard, et le type forall a. a, qui est l'un des plus difficile polymorphes types d'habiter. Nous allons également permettre l' forall aller pratiquement n'importe où dans un type -- comme nous allons le voir, GHC restreint son type de syntaxe comme un "fail-fast" mécanisme, plutôt que comme une exigence technique.

Supposons que nous avons dit au compilateur id :: forall a. a -> a. Pouvons-nous plus tard de demander à id comme si elle avait le type (forall b. b) -> (forall b. b)? Impredicative type de systèmes sont d'accord avec cela, parce que nous pouvons instancier le quantificateur en id's type d' forall b. b, et les remplacer par forall b. b pour a partout dans le résultat. Prédictive des systèmes de type sont un peu plus prudents en ce que: seuls les types monomorphes sont admis dans. (Ainsi, si nous avions un particulier b, nous pourrions écrire id :: b -> b.)

Il y a une histoire similaire à propos de [] :: forall a. [a] et (:) :: forall a. a -> [a] -> [a]. Alors que votre insouciance copain peut être d'accord avec [] :: [forall b. b] et (:) :: (forall b. b) -> [forall b. b] -> [forall b. b], les prédictive instituteur n'est-ce pas, tellement. En fait, comme vous pouvez le voir sur les deux seuls constructeurs de listes, il est aucun moyen de produire des listes contenant des valeurs polymorphes sans l'instanciation de la variable de type dans leurs constructeurs pour un polymorphe de la valeur. Ainsi, bien que le type [forall b. b] est autorisé dans notre dialecte de Haskell, il n'est pas vraiment sensible -- il n'y a pas (terminer), les termes de ce type. Ce qui motive GHC la décision de se plaindre si vous vous même de penser à un tel type, c'est le compilateur façon de vous dire "ne pas déranger".*

Eh bien, ce qui fait de l'instituteur si stricte? Comme d'habitude, la réponse est sur la tenue de la vérification de type et de l'inférence de type faisable. L'inférence de Type pour impredicative types est à droite. La vérification du Type semble comme il pourrait être possible, mais c'est sanglant compliqué et personne ne veut conserver que.

D'autre part, certains pourraient objet que GHC est parfaitement à l'aise avec certains types qui semblent avoir besoin de impredicativity:

> :set -Rank2Types
> :t id :: (forall b. b) -> (forall b. b)
{- no complaint, but very chatty -}

Il s'avère que certains légèrement restreint versions de impredicativity ne sont pas trop mauvais: plus précisément, la vérification de type de plus haut rang types (qui permettent de variables de type à être remplacés par des types polymorphes lorsqu'ils ne sont que des arguments au (->)) est relativement simple. Vous faire perdre de l'inférence de type au-dessus de rang 2, et les principaux types ci-dessus de rang 1, mais parfois de rang supérieur types sont juste ce que le médecin a ordonné.

Je ne sais pas à propos de l'étymologie du mot, si!

* Vous pourriez vous demander si vous pouvez faire quelque chose comme ceci:

data FooTy a where
     FooTm :: FooTy (forall a. a)

Ensuite, vous recevez un terme (FooTm) dont le type avait quelque chose polymorphes comme un argument de quelque chose d'autre que (->) (à savoir, FooTy), vous n'avez pas à traverser l'instituteur à le faire, et si la croyance "application de la non-(->) trucs de types polymorphes n'est pas utile parce que vous ne pouvez pas les faire" serait invalidé. GHC ne pas vous laisser écrire FooTy, et je vais avouer que je ne suis pas sûr qu'il y a un principe à raison de la restriction ou pas.

Answer 2

Permettez-moi simplement d'ajouter un point concernant la "étymologie" problème de, depuis l'autre réponse par @DanielWagner couvre la plus grande partie de la technique au sol.

Un prédicat sur quelque chose comme a est a -> Bool. Maintenant un prédicat logique est celui qui peut dans un certain sens, de la raison sur les prédicats -- donc, si nous avons quelques prédicat P , et nous pouvons parler, pour un a, P(a),, maintenant, dans une "logique des prédicats" (comme la logique du premier ordre), nous pouvons également dire ∀a. P(a). On peut donc quantifier plus de variables et de discuter le comportement des prédicats sur de telles choses.

Maintenant, à son tour, nous disons qu'une déclaration est prédictive si toutes les choses qu'un prédicat est appliqué à sont introduites avant le à elle. Si les déclarations sont "fondées sur" des choses qui existent déjà. À son tour, une déclaration est impredicative si l'on peut dans un certain sens, se référer à lui-même par ses "bottes".

Ainsi, dans le cas par exemple de la id exemple ci-dessus, nous constatons que nous pouvons donner à un type d' id tel qu'il prenne quelque chose du type d' id de quelque chose d'autre, le type d' id. Ainsi, nous pouvons maintenant donner une fonction d'un type d'une variable quantifiée (introduite par l' forall a.) peut "étendre" à être le même type que celui de l'ensemble de la fonction elle-même!

Donc impredicativity introduit une possibilité d'une certaine "auto-référence". Mais attendez, vous pourriez dire, ne serait pas une telle chose conduisent à la contradiction? La réponse est: "eh bien, parfois." En particulier, "F", qui est le polymorphe lambda calcul et l'essentiel "de base" de GHC "de base" de la langue permet une forme de impredicativity qui a néanmoins deux niveaux -- le plan de la valeur, et le type de niveau, ce qui est permis de quantifier sur lui-même. Dans ce deux-niveau de stratification, nous pouvons avoir impredicativity et pas de contradiction/paradoxe.

À noter toutefois que cette astuce est très délicat et facile à visser par l'ajout de plus de fonctionnalités, comme cette collection d'articles par Oleg indique: http://okmij.org/ftp/Haskell/impredicativity-bites.html

Answer 3

Je voudrais faire un commentaire sur l'étymologie problème, puisque @sclv la réponse n'est pas tout à fait à droite (étymologiquement, conceptuellement).

Remonter dans le temps, à l'époque de Russell, quand tout est la théorie des ensembles - y compris la logique. Celui de la logique des notions d'importation particulière est le "principe de la compréhension"; que, compte tenu de certaines logique de prédicat φ:A→2 nous aimerions avoir quelques principes pour déterminer l'ensemble de tous les éléments de satisfaction que prédicat, écrit que "{x | φ(x) }" ou une variante à ce sujet. Le point essentiel à garder à l'esprit est que les "jeux" et les "prédicats" sont considérées comme fondamentalement différentes choses: les prédicats sont des mappages d'objets de valeurs de vérité, et les jeux sont des objets. Ainsi, par exemple, nous pouvons permettre la quantification sur les ensembles, mais pas de quantification plus de prédicats.

Maintenant, Russell était plutôt préoccupé par son éponyme paradoxe, et cherché un moyen de se débarrasser d'elle. Il y a de nombreux bugs, mais celui qui nous intéresse ici est de restreindre le principe de la compréhension. Mais tout d'abord, la définition formelle de ce principe: ∃S.∀x.S x ↔︎ φ(x); c'est, pour notre φ il existe un certain objet (c'est à dire, set) S tel que, pour chaque objet (qui est aussi un jeu, mais considéré comme un élément) x, nous avons qu' S x (vous pouvez considérer cela comme signifiant "x∈S", bien que les logiciens de l'époque, a donné "∈" un sens différent de la simple juxtaposition) est vrai, juste au cas φ(x) est vrai. Si nous prenons le principe exactement comme c'est écrit puis nous nous retrouvons avec un impredicative théorie. Cependant, nous pouvons placer des restrictions sur ce qui φ nous sommes autorisés à prendre de la compréhension de l'. (Par exemple, si nous disons que φ ne doit pas contenir de second ordre des quantificateurs.) Ainsi, pour toute restriction R, si un ensemble S est déterminé (à savoir, généré par la compréhension) par certains R-prédicat, alors nous dirons que l' S est "R-prédictive". Si tous ensemble, dans notre langue, est - R-prédictive alors nous disons que notre langue est "R-prédictive". Et puis, comme c'est souvent le cas avec les mots à préfixe choses, le préfixe est perdu et partit implicite, d'où "prédictive" les langues. Et, naturellement, des langues qui ne sont pas prédictive sont "impredicative".

C'est la vieille école étymologie. Depuis ces jours, les conditions sont passés et il est devenu leur propre vie. Les moyens que nous utilisons "prédictive" et "impredicative" d'aujourd'hui sont tout à fait différents, parce que les choses qui nous concernent ont changé. Il peut parfois être un peu difficile de voir comment le diable nos temps modernes, l'utilisation de liens de retour pour ce genre de choses. Honnêtement, je ne pense pas connaître l'étymologie permet vraiment de tout en termes d'essayer de comprendre ce que les mots sont vraiment (de nos jours).