¿Por qué los gráficos reflexivos para la parametricidad?

11

En cuanto a los modelos de polimorfismo paramétrico, tengo curiosidad por qué se utilizan las categorías de gráficos reflexivos .

En particular, ¿por qué no incluyen la composición relacional? Al observar los modelos, todos parecen apoyar una noción natural de composición relacional:

x(R;S)zy.xRyySz

Los artículos más recientes que usan gráficos reflexivos parecen dar esto por sentado, y el único artículo más antiguo que pude encontrar que discutió que era "Parametricidad relacional y variables locales" de O'Hearn y Tennent que dicen:

Una razón para no requerir componibilidad es que, como es bien sabido, la composición no está preservada por relaciones lógicas en tipos superiores.

Y no estoy muy seguro de lo que esto significa, así que mi primera pregunta es qué se entiende por esto y espero una mejor referencia sobre esta cuestión.

Lo que creo que esto significa es que, por ejemplo, lo exponencial no necesariamente conserva la composición relacional en la nariz. En particular, no podemos mostrar . Esto significa que lo exponencial no se extiende a un functor en una categoría de relaciones.(R;R)(S;S)((RS);(RS))

Sin embargo, aunque no puedo mostrar la equivalencia entre las relaciones anteriores, ciertamente puedo probar una inclusión , ¿verdad?((RS);(RS))((R;R)(S;S))

Dado , entonces existe una de tipo apropiado con , así dado un , puedo mostrar . ¿No significa esto que el exponencial me da un functor laxo , que parece una mala propiedad para tirar? Entonces, mi segunda pregunta es ¿hay ejemplos donde la inclusión en esta dirección tampoco es demostrable?f((RS);(RS))hgf(RS)g(RS)hxRyRzf(x)Sg(y)Sh(z)

Max nuevo
fuente

Respuestas:

1

En los meses transcurridos desde que hice esta pregunta, creo que he encontrado una respuesta sensata.

A menudo, el tipo de relaciones consideradas no se componen. Por ejemplo, si su noción de una relación entre CPOs es un subconjunto completo chain de, entonces la relación entre los naturales ordenados más infinito y el CPO plano de los naturales dado por mantiene y nada más , entonces es admisible, como es su inverso, pero el compuesto no está completo en cadena, ya que para cada natural, pero nosotros no tengoR:DEωω|D|×|E|R:ω+1Nω+1NR(n,n)RR;RT:ω+1ω+1nR;RTnωR;RTω .

Max nuevo
fuente