Cálculo lambda simplemente tipado

El cálculo lambda simplemente tipado (λ→) es una teoría de tipos basada en el cálculo de lambda con un único constructor de tipos, →, que construye tipos función. Es el ejemplo canónico y más sencillo de un cálculo lambda tipado. El cálculo lambda simplemente tipado fue originalmente introducido por Alonzo Church en el 1940 como un intento de evitar la aparición de paradojas en el cálculo lambda sin tipos.

El término simplemente tipado es también utilizado para referirse a extensiones del cálculo lambda simplemente tipado con productos, coproductos, números naturales (Sistema T) o incluso recursión (como en el lenguaje PCF). En contraste, los sistemas que introducen tipos polimórficos (como Sistema F) o tipos dependientes (como el Logical Framework) no se consideran simplemente tipados. Los primeros, excepto aquellos que implementan recursión arbitraria, se consideran todavía simplemente tipados porque la codificación de Church de estas estructuras puede hacerse utilizando solamente → y variables de tipo, mientras que el polimorfismo y la dependencia no pueden expresarse de esta forma.

Sintaxis

Sean σ y τ dos variables representando tipos arbitrarios. Informalmente, el tipo función σ→τ es el tipo de las funciones que, dado un argumento de tipo σ, producen una salida de tipo τ. Por convención, → es asociativo a derecha: leemos σ→τ→ρ como σ→(τ→ρ).

Para definir los tipos, empezamos fijando un conjunto de tipos base, B, en ocasiones llamados tipos atómicos o constantes de tipo. Una vez fijados, la sintaxis de los tipos viene dada por la siguiente BNF:

τ::=τ→τ∣TdondeT∈B.

La sintaxis de los términos del cálculo lambda simplemente tipado es esencialmente la misma que la del cálculo lambda. Escribimos x:τ para denotar que la variable x es de tipo τ. La sintaxis de los términos en BNF es entonces:

e::=x∣λx:τ.e∣ee∣c

donde c es una constante.

Semántica categórica

El cálculo lambda simplemente tipado (asumiendo βη-equivalencia) es el lenguaje interno de las categorías cartesianas cerradas, como fue observado por Joachim Lambek por primera vez. Dada cualquier categoría cartesiana cerrada específica, los tipos base de su correspondiente cálculo lambda son sus objetos, y los términos son los morfismos. En la otra dirección, cada cálculo lambda simplemente tipado genera una categoría cartesiana cerrada cuyos objetos son los tipos, y cuyos morfismos son clases de equivalencia sobre los términos.