Transformations naturelles et paramétricité

11

Dans les théorèmes gratuitement! , Wadler dit que la caractérisation de la paramétricité peut être ré-exprimée en termes de transformations naturelles laxistes et cela fera l'objet d'un autre article. De quel document parle-t-il?

L'approche catégorique de la paramétricité que je connais utilise des transformations dinaturelles comme dans le polymorphisme funéraire de Bainbridge, Freyd, Scedrov et PJ Scott. Quel est le lien entre la transformation naturelle laxiste et les formulations de transformation dinaturelle de la paramétricité?

reference-request ct.category-theory parametricity sonat
la source
2
J'ai presque peur de faire ce commentaire, mais j'avoue que je ne comprends aucun mot technique dans cette question. Serait-il possible d'ajouter des liens vers les définitions de cet expert (horriblement) non?
Suresh Venkat
1
On dirait un travail pour @UdayReddy.
Dave Clarke
5
Autant que je sache, le document mentionné dans Theorems for Free! n'a (malheureusement) jamais été écrit. Je suis presque sûr que la compréhension actuelle de la paramétricité en termes de théorie des catégories est mieux saisie par les scones et les catégories de virgules . Voir par exemple Mitchell & Scedrov et ce poste de café de catégorie n.
cody
Suresh, désolé de ne pas avoir fourni les liens pertinents. Cody, merci d'avoir édité le post et de mentionner les scones et les catégories de virgules.
sonat

Réponses:

8

Malheureusement, la remarque de Wadler est trop cryptique pour que je puisse dire à quoi il voulait faire des "transformations naturelles laxistes". Voici une supposition. Les carrés de conservation des relations peuvent souvent être refondus en carrés commutatifs laxistes. C'est ainsi qu'ils étaient écrits dans de vieux documents / livres de théorie des automates. Voir le paragraphe 1.2 dans mes notes sur les semi-groupes . Pour faire ce genre de chose, vous devez mélanger les relations et les morphismes et prétendre qu'ils sont les mêmes. Je ne suis pas sûr non plus qu'il vous achète quelque chose de nouveau. C'est juste une notation plus laide pour dire la même chose que la conservation des relations.

N'hésitez pas à explorer la connexion, mais je ne suis pas convaincu que vous trouverez quelque chose de nouveau en le faisant.

Uday Reddy
la source
Merci beaucoup pour le lien. La formulation du paragraphe 1.2 est toujours théorique pour moi. Comment parlez-vous de l'inclusion? Supposez-vous que la catégorie est une allégorie ou possède des propriétés de type topos? S'il s'agit d'une reformualtion de transformations naturelles laxistes, quelle est la 2-catégorie sous-jacente? J'ai également lu la partie "Catégorisation" mais je n'ai rien trouvé sur les transformations naturelles laxistes.
sonat
@ SonatSüer: La catégorie 2 sous-jacente est Rel . Rappelons que chaque poset peut être considéré comme une catégorie (dégénérée) avec des morphismes uniques chaque fois que . De même, chaque catégorie enrichie en posets peut être considérée comme une catégorie 2 (dégénérée), avec 2 cellules uniques chaque fois que . Puisque Rel est une catégorie enrichie en posets avec l'ordre d'inclusion , il s'agit d'une catégorie 2. x ≤ y f → g f ≤ g R ⊆ S : Rel ( A , B )x→yx≤yf→gf≤gR⊆S:Rel(A,B)
Uday Reddy
Oh, donc la catégorie est fixe! Je pensais que Wadler faisait référence à une formulation plus générale et abstraite qui avait du sens dans une certaine classe de catégories contenant Rel comme un cas spécial (et quelque peu trivial). Si nous travaillons uniquement dans Rel, il est inutile d'introduire une structure plus élevée mais dégénérée. Maintenant, je comprends votre réponse originale.
sonat
@ SonatSüer: Si vous êtes intéressé par les généralisations, la manière standard de généraliser les relations à des catégories autres que Set est de les traiter comme des "plages moniques conjointes". Vous pouvez obtenir une catégorie enrichie en précommande au lieu d'enrichir en posets, mais la structure à 2 catégories est toujours la même.
Uday Reddy
@ SonatSüer: Et, si vous êtes vraiment intéressé par une théorie axiomatique appropriée qui couvre tout ce que nous savons, je peux vous référer à notre récent article Logical relations and Parametricity - A Reynolds Program .
Uday Reddy