¿No hay modelos teóricos ingenuos del cálculo polimórfico de Lambda?

En el artículo de Philip Wadler sobre Theorems for Free , afirma en la Sección 2 sobre Parametricidad que

no existen modelos ingenuos de teoría de conjuntos de cálculo lambda polimórfico

En el ingenuo modelo teórico de conjuntos, los tipos son conjuntos y las funciones son funciones teóricas de conjuntos, lo que parece razonable. Entonces, ¿por qué dice que no hay modelos ingenuos de teoría de conjuntos de cálculo lambda polimórfico?

functional-programming MK
fuente

OK, me topé con este documento: hal.inria.fr/inria-00076261/document . Voy a tener que atravesarlo.

¡Ese artículo de Reynolds es de hecho el más adecuado para leer! Omitiendo muchos detalles que resume: considere data T = K ((T -> Bool) -> Bool). Entonces, Ty ((T->Bool)->Bool)son isomorfos. Si tienen un modelo de conjunto donde ->denota el espacio de funciones (como un conjunto), este último tiene una cardinalidad más alta, por lo que no puede ser isomorfo T. Entonces, en un modelo, necesitamos interpretar de manera ->diferente, por ejemplo, como el espacio de funciones continuas .

chi

Respondí demasiado rápido y respondí la pregunta equivocada. Lo siento por eso. La razón por la cual el cálculo lambda polimórfico no tiene un modelo en la teoría de conjuntos ingenua es aparentemente diferente de la del cálculo lambda sin tipo.

Respuestas:

La referencia estándar que está buscando es, de hecho, el polimorfismo de Reynold no es teórico de conjuntos . Si bien es bastante obvio que no se puede formar, por ejemplo, el producto $\Pi_{S\in\mathrm{Set}}S$ sobre todos los conjuntos que usan el producto teórico de conjunto habitual, es una pregunta legítima y no trivial si existe alguna noción más débil de producto que funcione, mientras se preserva el producto binario habitual $\times$ y espacio funcional $\rightarrow$ .

Esto tampoco es posible, ya que, por un lado, es bastante fácil construir un tipo $\bf 2$ tal que la interpretación tenga al menos 2 elementos, y demuestre que la interpretación de $T=\Pi_X(X\rightarrow {\bf 2})\rightarrow{\bf 2}$ es isomorfo a $(T\rightarrow {\bf 2})\rightarrow {\bf 2}$ , que no es posible para la interpretación habitual de $\rightarrow$ por la usual paradoja cantor. En este sentido, es algo similar a la prueba del cálculo sin tipo.

Tenga en cuenta que un artículo adicional, de Andrew Pitts, Polymorphism is Set Theoretic, Constructively , anula esta conclusión al mostrar que la contradicción anterior solo es posible construir en la teoría clásica de conjuntos, y que hay varias teorías constructivas de conjuntos en los que el polimorfismo puede ser interpretado con las interpretaciones habituales de espacios de funciones y productos. En particular, estos "productos grandes" existen en Topos efectivos, la introducción más completa de Phoa .

cody
fuente