Warum reflexive Graphen für Parametrizität?

11

Wenn ich Modelle des parametrischen Polymorphismus betrachte, bin ich neugierig, warum reflexive Graphkategorien verwendet werden.

Warum enthalten sie insbesondere keine relationale Komposition? Bei der Betrachtung der Modelle scheinen sie alle einen natürlichen Begriff der relationalen Zusammensetzung zu unterstützen:

x(R;S)zy.xRyySz

Die jüngsten Veröffentlichungen, die reflexive Graphen verwenden, scheinen dies als selbstverständlich zu betrachten, und die einzige ältere Veröffentlichung, die ich finden konnte, war "Relationale Parametrizität und lokale Variablen" von O'Hearn und Tennent, die sagen:

Ein Grund dafür, dass keine Kompositionsfähigkeit erforderlich ist, besteht darin, dass die Komposition bekanntlich nicht durch logische Beziehungen bei höheren Typen erhalten bleibt.

Und ich bin mir nicht ganz sicher, was dies bedeutet. Meine erste Frage ist, was damit gemeint ist, und hoffentlich eine bessere Referenz zu dieser Frage.

Ich denke, dies bedeutet, dass zum Beispiel das Exponential nicht unbedingt die relationale Zusammensetzung auf der Nase bewahrt. Insbesondere können wir nicht zeigen . Dies bedeutet, dass sich das Exponential nicht auf einen Funktor in einer Kategorie von Beziehungen erstreckt.(R;R)(S;S)((RS);(RS))

((RS);(RS))((R;R)(S;S))

f((RS);(RS))hgf(RS)g(RS)hxRyRzf(x)Sg(y)Sh(z)

Max Neu
quelle

Antworten:

1

In den Monaten, seit ich diese Frage gestellt habe, habe ich eine vernünftige Antwort gefunden.

R:DEωω|D|×|E|R:ω+1Nω+1NR(n,n)RR;RT:ω+1ω+1nR;RTnωR;RTω

Max Neu
quelle