Cálculo Lambda

Cálculo Lambda (Cálculo-λ), originalmente creado por Alonzo Church, es el lenguaje de programación más pequeño del mundo. A pesar de no tener números, cadenas, valores booleanos o cualquier tipo de datos no funcional, el cálculo lambda se puede utilizar para representar cualquier máquina de Turing.

El cálculo lambda se compone de 3 elementos: variables, funciones y aplicaciones.

La función más básica es la función de identidad: λx.x que es equivalente a f(x) = x. La primera “x” es el argumento de la función y la segunda es el cuerpo de la función.

Variables Libres vs. Enlazadas:

• En la función λx.x, “x” se llama una variable enlazada porque está tanto en el cuerpo de la función como en el parámetro.
• En λx.y, “y” se llama variable libre porque nunca se declara de antemano.

Evaluación:

Evaluación se realiza a través de β-Reduction, que es, esencialmente, sustitución de ámbito léxico.

Al evaluar la expresión (λx.x)a, reemplazamos todas las ocurrencias de “x” en el cuerpo de la función con “a”.

• (λx.x)a evalúa a: a
• (λx.y)a evalúa a: y

Incluso puedes crear funciones de orden superior:

• (λx.(λy.x))a evalúa a: λy.a

Aunque el cálculo lambda tradicionalmente solo admite funciones de un solo parámetro, podemos crear funciones multiparamétricas usando una técnica llamada Currificación.

• (λx.λy.λz.xyz) es equivalente a f(x, y, z) = ((x y) z)

Algunas veces λxy.<cuerpo> es usado indistintamente con: λx.λy.<cuerpo>

Es importante reconocer que el cálculo lambda tradicional no tiene números, caracteres ni ningún tipo de datos que no sea de función.

Lógica Booleana:

No hay “Verdadero” o “Falso” en el cálculo lambda. Ni siquiera hay un 1 o un 0.

En vez:

T es representado por: λx.λy.x

F es representado por: λx.λy.y

Primero, podemos definir una función “if” λbtf que devuelve t si b es Verdadero y f si b es Falso

IF es equivalente a: λb.λt.λf.b t f

Usando IF podemos definir los operadores lógicos booleanos básicos:

a AND b es equivalente a: λab.IF a b F

a OR b es equivalente a: λab.IF a T b

a NOT b es equivalente a: λa.IF a F T

Note: IF a b c es esencialmente diciendo: IF((a b) c)

Números:

Aunque no hay números en el cálculo lambda, podemos codificar números usando Númeral de Church.

Para cualquier número n: n = λf.f n así:

0 = λf.λx.x

1 = λf.λx.f x

2 = λf.λx.f(f x)

3 = λf.λx.f(f(f x))

Para incrementar un númeral de Church, usamos la función sucesora S(n) = n + 1 que es:

S = λn.λf.λx.f((n f) x)

Usando el sucesor, podemos definir AGREGAR:

AGREGAR = λab.(a S)n

Desafío: intenta definir tu propia función de multiplicación!

Vamos más pequeño: SKI, SK y Iota

Combinador de SKI

Sean S, K, I las siguientes funciones:

I x = x

K x y = x

S x y z = x z (y z)

Podemos convertir una expresión en el cálculo lambda en una expresión en el cálculo del combinador de SKI:

1. λx.x = I
2. λx.c = Kc
3. λx.(y z) = S (λx.y) (λx.z)

Tome el número 2 de Church por ejemplo:

2 = λf.λx.f(f x)

Para la parte interior λx.f(f x):

  λx.f(f x)
= S (λx.f) (λx.(f x))          (case 3)
= S (K f)  (S (λx.f) (λx.x))   (case 2, 3)
= S (K f)  (S (K f) I)         (case 2, 1)

Así que:

  2
= λf.λx.f(f x)
= λf.(S (K f) (S (K f) I))
= λf.((S (K f)) (S (K f) I))
= S (λf.(S (K f))) (λf.(S (K f) I)) (case 3)

Para el primer argumento λf.(S (K f)):

  λf.(S (K f))
= S (λf.S) (λf.(K f))       (case 3)
= S (K S) (S (λf.K) (λf.f)) (case 2, 3)
= S (K S) (S (K K) I)       (case 2, 3)

Para el segundo argumento λf.(S (K f) I):

  λf.(S (K f) I)
= λf.((S (K f)) I)
= S (λf.(S (K f))) (λf.I)             (case 3)
= S (S (λf.S) (λf.(K f))) (K I)       (case 2, 3)
= S (S (K S) (S (λf.K) (λf.f))) (K I) (case 1, 3)
= S (S (K S) (S (K K) I)) (K I)       (case 1, 2)

Uniéndolos:

  2
= S (λf.(S (K f))) (λf.(S (K f) I))
= S (S (K S) (S (K K) I)) (S (S (K S) (S (K K) I)) (K I))

Al expandir esto, terminaríamos con la misma expresión para el número 2 de Church nuevamente.

Cálculo del combinador SKI

El cálculo del combinador SKI puede reducirse aún más. Podemos eliminar el combinador I observando que I = SKK. Podemos sustituir todos los ‘I’ con SKK.

Combinador Iota

El cálculo del combinador SK todavía no se encuentra en su expresión mínima. Definiendo:

ι = λf.((f S) K)

Tenemos que:

I = ιι
K = ι(ιI) = ι(ι(ιι))
S = ι(K) = ι(ι(ι(ιι)))

Para una lectura más avanzada:

1. A Tutorial Introduction to the Lambda Calculus
2. Cornell CS 312 Recitation 26: The Lambda Calculus
3. Wikipedia - Lambda Calculus
4. Wikipedia - SKI combinator calculus
5. Wikipedia - Iota and Jot

¿Tienes una sugerencia o rectificación? Abre un issue en el repositorio de GitHub, o haz un pull request tu mismo

Originalmente contribuido por Max Sun, y actualizado por 3 colaborador(es).