Cálculo lambda para niños

Términos enlazados con funciones de recursión.

El cálculo lambda es un sistema especial en la lógica matemática que ayuda a entender qué es una función, cómo se usan las funciones y cómo funciona la recursión (cuando algo se define a sí mismo). Fue creado por los matemáticos Alonzo Church y Stephen Kleene en la década de 1930. Church lo usó para resolver un problema importante en matemáticas. También sirve para definir de forma clara qué es una "función computable", es decir, una función que una computadora puede resolver.

Una pregunta interesante es si dos expresiones del cálculo lambda son iguales. No existe un algoritmo (un conjunto de pasos) que pueda resolver siempre esta pregunta. Esta fue una de las primeras veces que se demostró que un problema no podía ser resuelto por un algoritmo general. El cálculo lambda ha influido mucho en los lenguajes de programación funcional, como Lisp, ML y Haskell.

Puedes pensar en el cálculo lambda como uno de los lenguajes de programación más sencillos. Solo tiene una regla simple para cambiar cosas (sustituir variables) y una forma sencilla de crear funciones.

Es un sistema "universal" porque cualquier función que una computadora pueda calcular se puede expresar y resolver con él. Por eso, es tan potente como las máquinas de Turing. Sin embargo, el cálculo lambda se enfoca más en las reglas de transformación y no tanto en cómo una máquina real lo implementaría. Es más como una idea para el software que para el hardware.

Este artículo se centrará en el cálculo lambda sin tipos, que fue la versión original de Church. Más tarde, se crearon otras versiones con "tipos" (categorías para los datos).

Historia del Cálculo Lambda

Originalmente, Church quería crear un sistema matemático completo. Pero en 1934, otros matemáticos encontraron un problema que hizo que el cálculo lambda se usara para estudiar la computabilidad (qué se puede calcular). Esto llevó a la respuesta de que algunos problemas no se pueden resolver con algoritmos. En 1940, Church presentó el Cálculo lambda simplemente tipado, que es menos potente para calcular, pero más consistente lógicamente.

Entendiendo el Cálculo Lambda de Forma Sencilla

Imagina dos funciones. La primera es la función identidad, que toma un número x y devuelve el mismo x. Por ejemplo, si le das 5, te devuelve 5. La segunda es la función suma, que toma dos números, x e y, y devuelve su suma. Por ejemplo, si le das 2 y 3, te devuelve 5.

Con estas funciones, podemos aprender algunas ideas clave del cálculo lambda:

Funciones sin Nombre

Las funciones no necesitan tener un nombre específico. La función suma (x,y → x + y) puede escribirse como "el par de x e y se convierte en x + y". La función identidad (x → x) puede ser "el argumento x se convierte en sí mismo".

Nombres de Argumentos Flexibles

El nombre que le des a los argumentos de una función no importa. Por ejemplo, "x → x" y "y → y" son la misma función identidad. Lo mismo ocurre con la función suma: "x,y → x + y" y "u,v → u + v" son idénticas.

Funciones de un Solo Argumento (Currificación)

Una función que necesita varios argumentos, como la suma, puede reescribirse para que acepte un solo argumento. Luego, esta función devuelve otra función que acepta el siguiente argumento. Esto se llama currificación.

Por ejemplo, la suma x,y → x + y puede ser x → (y → x + y). Si le das el 2 a x → (y → x + y), obtienes la función y → 2 + y. Luego, si le das el 3 a esa nueva función, obtienes 2 + 3, que es 5. El resultado es el mismo. En el cálculo lambda, todas las expresiones representan funciones anónimas que solo toman un argumento a la vez.

Funciones que Aceptan Otras Funciones

Una función puede tomar otra función como argumento, siempre que esa otra función también acepte un solo argumento. Por ejemplo, la función identidad (z → z) puede tomar como argumento la función suma currificada (x → (y → x + y)). El resultado será la misma función suma, porque la identidad siempre devuelve lo que recibe.

En el cálculo lambda, las funciones se definen con expresiones lambda. Por ejemplo, la función "sumar 2" (f(x) = x + 2) se escribe como λ x. x + 2. Para calcular f(3), se escribe (λ x. x + 2) 3. La aplicación de funciones se lee de izquierda a derecha: f x y significa ((f x) y).

Las expresiones (λ f. f 3)(λ x. x + 2), (λ x. x + 2) 3 y 3 + 2 son equivalentes.

No todas las expresiones lambda pueden simplificarse a un "valor" final. Algunas, como (λ x. x x) (λ x. x x), solo se repiten o se vuelven más complejas al intentar simplificarlas.

Reglas Formales del Cálculo Lambda

En el cálculo lambda, una expresión o término se construye siguiendo estas reglas:

• Cualquier variable es un término: x, y, z, ...
• Si t es un término y x es una variable, entonces (λx.t) es un término (llamado abstracción lambda). Esto define una función.
• Si t y s son términos, entonces (ts) es un término (llamado aplicación lambda). Esto aplica una función a un argumento.
• Nada más es un término.

Por ejemplo, x, (xy), (λx.x) son términos válidos. Para simplificar, a menudo se quitan los paréntesis externos. También, la aplicación de funciones se asocia de izquierda a derecha, así xyzz significa (((xy)z)z).

Una abstracción lambda λx.t representa una función anónima que toma un argumento. El símbolo λ "une" la variable x en el término t. Una aplicación lambda ts significa que la función t se aplica al argumento s. Por ejemplo, λx.x es la función identidad, y (λx.x)y es la función identidad aplicada a y.

Las expresiones lambda se vuelven interesantes por las formas en que se pueden considerar equivalentes o simplificar.

Variables Libres y Ligadas

Las variables en una expresión pueden ser de tres tipos:

• Variables de ligadura: Son las que están entre el λ y el punto, como x, y, z en (λ x y z. E).
• Ocurrencias ligadas: Son las variables dentro de una función que están "atadas" por un λ. Por ejemplo, en λx.x, la x después del punto está ligada.
• Ocurrencias libres: Son las variables que no están atadas por ningún λ. Por ejemplo, en λ x. (x y), la y es libre.

Si una expresión no tiene variables libres, se dice que es "cerrada".

α-conversión (Cambio de Nombre)

Esta regla dice que el nombre de las variables ligadas no importa. Por ejemplo, λx.x y λy.y representan la misma función. Sin embargo, hay que tener cuidado de no "capturar" variables. Por ejemplo, cambiar x por y en λx.λy.x a λy.λy.y no es correcto, porque cambia el significado.

La regla establece que puedes cambiar una variable V por W en λ V. E para obtener λ W. E[V:= W], siempre que W no sea una variable libre en E y no se "ligue" a otro λ donde se haya reemplazado V.

β-reducción (Aplicación de Funciones)

Esta regla explica cómo se aplica una función. Dice que ((λ V. E) E′) se convierte en E[V:= E′]. Esto significa que si tienes una función λ V. E y le aplicas un argumento E′, simplemente reemplazas todas las apariciones de V en E por E′.

Una expresión como ((λ V. E) E′) se llama "beta redex". Si una expresión lambda no se puede simplificar más con beta reducción, se dice que está en su "forma normal". No todas las expresiones tienen una forma normal, pero si la tienen, es única.

η-conversión (Extensionalidad)

Esta regla adicional dice que dos funciones son iguales si siempre dan el mismo resultado para el mismo argumento. La eta conversión permite cambiar entre λ x. f x y f, siempre que x no aparezca sola en f. Esto significa que si una función f simplemente aplica otra función f a su argumento x, entonces es lo mismo que la función f original.

Cálculos Aritméticos con Lambda

Podemos representar los números naturales (0, 1, 2, 3...) en el cálculo lambda usando los "números de Church":

• 0:= λ f x. x
• 1:= λ f x. f x
• 2:= λ f x. f (f x)
• 3:= λ f x. f (f (f x))

Un número n de Church es una función que toma otra función f y la aplica n veces.

Con esto, podemos definir operaciones:

• Siguiente número (SUCC): SUCC:= λ n f x. f ((n f) x) (da n + 1)
• Suma (PLUS): PLUS:= λ m n f x. n f (m f x)
• Multiplicación (MULT): MULT:= λ m n. m (PLUS n) 0 (multiplicar m por n es como sumar n a sí mismo m veces).

Lógica y Predicados

También podemos representar los valores lógicos (verdadero y falso) y operaciones lógicas:

• VERDADERO (TRUE): TRUE:= λ x y. x (si es verdadero, elige el primer argumento)
• FALSO (FALSE): FALSE:= λ x y. y (si es falso, elige el segundo argumento)

Con esto, podemos definir:

• Y (AND): AND:= λ p q. p q FALSE
• O (OR): OR:= λ p q. p TRUE q
• NO (NOT): NOT:= λ p. p FALSE TRUE
• SI-ENTONCES-SINO (IFTHENELSE): IFTHENELSE:= λp.λa.λb.p a b (si p es verdadero, devuelve a; si es falso, devuelve b).

Un "predicado" es una función que devuelve un valor booleano. Por ejemplo, ISZERO (¿Es Cero?) devuelve TRUE si el número de Church es 0, y FALSE en otro caso:

• ¿Es Cero? (ISZERO): ISZERO:= λ n. n (λ x. FALSE) TRUE

Pares de Datos

Podemos definir un par de elementos (como una tupla de dos) usando TRUE y FALSE:

• CONSTRUIR PAR (CONS): CONS:= λf.λs. λb. b f s (crea un par con el primer elemento f y el segundo s)
• PRIMER ELEMENTO (CAR): CAR:= λp. p TRUE (obtiene el primer elemento de un par p)
• SEGUNDO ELEMENTO (CDR): CDR:= λp. p FALSE (obtiene el segundo elemento de un par p)

Recursión en el Cálculo Lambda

La Recursión es cuando una función se define a sí misma. El cálculo lambda no permite esto directamente. Sin embargo, hay una forma de lograrlo usando un truco llamado "operador de punto fijo" o "combinador Y".

Imagina que quieres calcular el factorial de un número (por ejemplo, 5! = 5 * 4 * 3 * 2 * 1). La función factorial se define así:

• factorial(n) = 1, si n = 0
• factorial(n) = n * factorial(n-1), si n > 0

En el cálculo lambda, no puedes simplemente decir que una función se llama a sí misma. En su lugar, defines una función g que toma otra función f como argumento y devuelve la lógica del factorial. Para que g actúe como el factorial, la función f que le pasas debe ser la misma función g aplicada a sí misma.

Aquí es donde entra el combinador Y:

• Y = λ g. (λ x. g (x x)) (λ x. g (x x))

Cuando aplicas Y a una función g, el resultado Y g se comporta como un "punto fijo" de g, lo que significa que Y g es equivalente a g (Y g). Esto permite que la función se "llame a sí misma" de forma indirecta, logrando la recursión.

Así, para calcular el factorial de n, llamarías a g (Y g) n. Esto permite que cualquier función recursiva se exprese en el cálculo lambda.

Funciones Computables y el Cálculo Lambda

Una función que toma números naturales y devuelve números naturales es "computable" si existe una expresión lambda que la represente. Esto significa que el cálculo lambda es tan potente como cualquier otra forma de definir lo que una computadora puede calcular, como las máquinas de Turing.

La Indecisión de la Equivalencia

No existe un algoritmo que pueda decir siempre si dos expresiones lambda son equivalentes. Este fue el primer problema para el que se demostró que no se podía resolver con un algoritmo general. Esto es importante porque muestra los límites de lo que las computadoras pueden hacer.

Cálculo Lambda y Lenguajes de Programación

Muchos lenguajes de programación modernos tienen sus raíces en el cálculo lambda. Provee las ideas básicas para crear "procedimientos" (bloques de código) y "aplicar" esos procedimientos.

Implementar el cálculo lambda en una computadora significa tratar las "funciones" como "objetos de primera clase". Esto significa que puedes pasar funciones como argumentos, devolverlas de otras funciones o guardarlas en variables, igual que harías con un número o un texto.

Los lenguajes de programación funcional, como Haskell, son los que más se parecen al cálculo lambda, ya que se basan en sus principios. Pero muchos otros lenguajes, incluso los que no son puramente funcionales, han adoptado ideas del cálculo lambda, permitiendo trabajar con funciones de formas muy flexibles.

Estrategias de Reducción

La forma en que se simplifica una expresión lambda puede afectar si llega a una forma normal y cuánto trabajo se necesita. Esto es similar a cómo los lenguajes de programación deciden cuándo calcular los valores.

• Evaluación estricta (o "llamada por valor"): La mayoría de los lenguajes de programación (como Lisp, ML, C, Java) usan esto. Significa que los argumentos de una función se calculan completamente antes de que la función se aplique. Si un argumento no se puede simplificar, la función tampoco.
• Evaluación perezosa (o "llamada por necesidad"): Algunos lenguajes funcionales puros (como Haskell) usan esto. Los argumentos no se calculan hasta que realmente se necesitan. Esto puede ahorrar trabajo si un argumento no se usa o si se usa varias veces, ya que se calcula solo una vez.

Concurrencia y Paralelismo

La propiedad Church-Rosser del cálculo lambda significa que las simplificaciones (reducciones) se pueden hacer en "cualquier orden", incluso al mismo tiempo. Esto es útil para entender cómo se pueden evaluar las cosas, pero el cálculo lambda no fue diseñado para describir la computación paralela (cuando varias cosas se hacen a la vez) o los lenguajes de programación concurrentes (que manejan múltiples tareas al mismo tiempo). Para eso, se han creado otros sistemas.

Reducción Óptima

La "reducción óptima" busca simplificar las expresiones lambda sin repetir trabajo. A veces, al simplificar una expresión, se duplican partes de ella, lo que significa que el mismo cálculo se hace varias veces. La reducción óptima intenta evitar esto.

Aunque se ha definido la idea de compartir óptimamente para no duplicar el trabajo, encontrar un algoritmo que lo haga siempre es muy complejo. Sin embargo, se han desarrollado métodos que transforman las expresiones lambda en "redes de interacción" para lograr una reducción más eficiente.

Significado (Semántica)

El hecho de que los términos del cálculo lambda puedan actuar como funciones sobre otros términos, o incluso sobre sí mismos, llevó a preguntarse: ¿Podemos darle un significado real a estas expresiones? En 1970, el matemático Dana Scott demostró que sí, que se podía encontrar un modelo matemático para el cálculo lambda, lo que ayudó a entender cómo funcionan los lenguajes de programación.

Galería de imágenes

• 

  Términos enlazados con funciones de recursión.

Véase también

En inglés: Lambda calculus Facts for Kids