Marco Ordoñez

Un primer vistazo al cálculo lambda

En la actualidad existe tan poca información en español sobre el cálculo lambda que he decidido escribir este post para compartir un poco acerca del tema de una forma que espero sea fácil de entender.

El origen del cálculo lambda se da en la década de 1930 por Alonzo Church, inicialmente fue parte de una meta más ambiciosa (definir nuevas bases para la matemática) sin embargo este intento no se concretó ya que sus alumnos demostraron que era inconsistente.

Lo primero que debemos saber es que las funciones no tienen nombres y se utiliza el símbolo λ (lambda) para definirlas. La definición de una función recibe el nombre de abstracción. A continuación veremos un ejemplo de como definir una abstracción.

La función f(x) = x + 1 se convierte en λx.x+1.

Lo segundo que debemos saber es que las abstracciones cuentan con variables que pueden ser de 2 tipos, ligadas y libres. Decimos que una variable es ligada si se encuentra definida en la función y además en el cuerpo de la misma, ejemplo:

En la siguiente abstracción, x es una variable ligada porque es utilizada en el cuerpo de la abstracción mientras que y es una variable libre porque no se utiliza.
λx.xy.

Lo tercero que debemos saber es que todas las abstracciones reciben solo un valor de entrada, por esa razón, si quisiéramos representar una función con dos valores de entrada tendríamos que escribir una abstracción que retorne otra, ejemplo:

La función f(x,y) = x + y se convierte a λx.λy.x+y.

Ahora que ya sabemos como definir abstracciones podemos revisar el siguiente concepto, la aplicación de una abstracción. Llamamos aplicación a la expresión que aplica un valor a una abstracción, ejemplo:

(λx.x)10 ó ((λx.(λy.xy)) 10) 10.

Sabiendo lo que hemos visto hasta ahora podemos decir que una expresión o término lambda es una abstracción, una aplicación o una variable. A continuación varios ejemplos de términos lambda.

  • (λx.(xy))
  • (x (λx.(λx.x)))
  • ((λy.y)(λx.(xy)))
  • (λx.(yz))

En siguientes posts voy a compartir temas más avanzados sobre este tema.

Marco Ordonez