Correspondencia de curry-Howard

Question

He leído que el de Curry-Howard correspondencia introduce un isomorfismo entre escribió funciones y expresiones lógicas. Por ejemplo, se supone que la función de

$$\begin{array}{l} I : \forall a. a \to a\\ I = \lambda x. x \end{array}$$

puede ser interpretado como:

$$p \implies p \text{ for any proposition } p$$

Es eso correcto? Cómo puedo interpretar una función de $K : \forall ab. a \to (b \to a)$? ¿Qué acerca de la $\text{succ} : \mathbb{N} \to \mathbb{N}$ donde $\text{succ} = \lambda x. x + 1$?

Si el alcance de esta pregunta es demasiado grande, ¿alguien puede recomendar un libro introductorio que cubre esto? Una prueba de la isomorfismo probablemente sería esclarecedor, demasiado: ¿alguien me apunte a uno?

Answer 1

Eche un vistazo a Girard, Lafont y Taylor, Pruebas y Tipos. Está disponible en línea en su totalidad.

---

Podemos afirmar que el Curry–Howard correspondencia en términos generales, como una correspondencia entre los sistemas de prueba y tipo de teorías. Dos maneras de afirmar que a medida que las pruebas de los programas y las propuestas son tipos. Tu pregunta parece que se centra en la conexión que Howard señaló entre deducción natural y simplemente el tipado $\lambda$-cálculo.

Te preguntas cómo interpretar una función de $K : \forall{a, b} . a \rightarrow (b \rightarrow a)$, que no es precisamente la pregunta correcta, porque se pierde el intensional aspecto de la correspondencia. Deje $t$ ser un término de tipo de $\forall{a, b} . a \rightarrow (b \rightarrow a)$ cuya extensión es la función de $K$. (En general, habrá muchos de esos $t$ cualquier $K$.) ¿Qué $t$ corresponden a, entonces? Una prueba de la proposición de que su tipo corresponde a: la proposición de que para arbitrario proposiciones $a$ y $b$, $a \rightarrow (b \rightarrow a)$.

Lo que podría $t$? Podemos entender esto en cierta medida debido a su tipo. Empezar con $r : b \rightarrow a$. Deje $v : a$$x : b$. A continuación, vamos a $r := \lambda x. v$. A continuación,$t := \lambda y. (\lambda x. v)$.

Por supuesto, esto no es muy informativo: para averiguar algo sustancial necesitaríamos saber lo $v$ es. Hay un montón de cosas que podrían ser: he aquí uno que se adapte. Deje $v := y$. A continuación,$t := \lambda y. (\lambda x. y)$. En otras palabras, proporcionar términos de $u : a$ $s: b$ (que, recordemos, son las pruebas de $a$ $b$ respectivamente), por lo que, a continuación, $(t[u / y])[s / x]$ se reduce a $u$, que es una prueba de $b$.

Answer 2

La versión corta de la de Curry-Howard correspondencia es: interpretar un tipo como una proposición, interpretar el tipo de función $a\to b$ " $a$ implica $b$". Interpretar el tipo de producto $a\times b$ como"$a$$b$". Interpretar los distintos tipos de unión $a \sqcup b$ " $a$ o $b$ (o ambos)".

Entonces, por ejemplo, el tipo de la $K$ combinator, $a\to(b\to a)$, se interpreta como la proposición de que si conocemos $a$, entonces si sabemos $b$ podemos concluir $a$. O el tipo de programa que recibe un par $(a,b)$ y vuelve $b$$a\times b\to b$, y este es el teorema que dice que si usted puede probar $a$$b$, entonces usted tiene una prueba de $b$, generalmente por escrito $a\land b\to b$.

(En el lenguaje Haskell, $a\times b$ es anotada (a,b) y $a\sqcup b$ es anotada Either a b.)

La función sucesor es un poco tonto, porque el tipo es un trivial teorema. El tipo de $\Bbb N$ es conocido para ser habitada, porque contiene constantes como 0. Estos tipos corresponden a las proposiciones que son conocidos para ser verdad. Por ejemplo, hay un programa, escrito 0, con el tipo de $\Bbb N$, y esto es de hecho un teorema. Por lo que el sucesor función del tipo, ${\Bbb N}\to{\Bbb N}$, sólo dice que $\Bbb N$ implica $\Bbb N$, que no es muy interesante. Quizás un poco más interesante es el teorema $a\to \Bbb N$, lo que corresponde al programa de $\lambda a. 13$.

Hay más a la correspondencia de que tipos son los teoremas de la lógica. Lo más importante es que un programa con un cierto tipo corresponde a una prueba de la correspondiente teorema. Evaluación del programa corresponde a la eliminación de la "corte" de la regla de la prueba. Puramente funcional de los programas corresponden a los teoremas de intuitionistic lógica, sino imprescindible programas corresponden a los teoremas de la lógica clásica, que es más fuerte. Doble negación corresponde a excepción de la manipulación. El teorema de Glivenko, que dice que cualquier teorema de la lógica clásica tiene un intuitionistic analógica, corresponde a la implementación de un imperativo programa en un lenguaje funcional en consonancia con el estilo de pases.

Le recomiendo que lea Morten Heine Sørensen y Paweł Urzyczyn de Conferencias sobre el Curry-Howard Isomorfismo para los detalles completos.

También potencialmente interesante: esta respuesta se construye un programa con el tipo de $\lnot\lnot(P\lor\lnot P)$.