Cálculo lambda

Introducción

El cálculo lambda es un sistema formal introducido por Alonzo Church en la década de 1930. Como la máquina de Turing, el cálculo lambda es un modelo de computación, y fue utilizado por Church para resolver el Entscheidungsproblem (problema de decisión).

Definiciones

El cálculo lambda consiste en la construcción de expresiones y en la aplicación de operaciones de reducción sobre ellas.

Expresiones

Las expresiones se construyen a partir de tres elementos: variables, abstracciones y aplicaciones.

Variables

Una variable es una letra o cadena de texto que representa un valor indeterminado o parámetro, como \(x\), \(y\) o \(nombre\).

Abstracción

Una abstracción es una definición de función que toma como entrada una variable \(x\) y devuelve el cuerpo \(M\).

\[ (\lambda x.M) \]

Aplicación

Una aplicación aplica la función \(M\) al argumento de entrada \(N\). Tanto \(M\) como \(N\) son expresiones lambda.

\[ (M \; N) \]

Operaciones

Las operaciones de reducción son dos: la conversión \(\alpha\) y la reducción \(\beta\).

Conversión \(\alpha\)

La conversión \(\alpha\) consiste en renombrar las variables para evitar colisiones.

\[ (\lambda x.M[x]) \to (\lambda y.M[y]) \]

Reducción \(\beta\)

La reducción \(\beta\) consiste en sustituir en el cuerpo de la abstracción la variable por el argumento.

\[ ((\lambda x.M) \; N) \to (M[x:=N]) \]

Ejemplos

La expresión lambda \(\lambda x.x+3\) es equivalente a la función \(f(x)=x+3\).

• \(\lambda\) indica el inicio de la expresión (como \(f\))
• la letra \(x\) indica la variable (como \((x)\))
• el punto \(.\) indica que lo que sigue es la salida de la expresión (como \(=\))

La aplicación \((\lambda x.x+3) \; 5\) se reduce al valor \(8\), sustituyendo \(x\) por \(5\) en el cuerpo de la función.

1. Escribe en esta notación las siguientes funciones:

   • \(f(x)=9x-5\)
   • \(f(x)=x^2-2x+1\)

2. Evalúa las siguientes expresiones:

   • \((\lambda x.2x+1) \; 4\)
   • \((\lambda x.x^2-2x+1) \; 3\)
   • \((\lambda x.(\lambda y.7y) \; (x+5)) \; 2\)

¡Un momento!

Aunque hemos usado aritmética en las expresiones anteriores, esto no es del todo correcto. La suma o la resta no están definidas en el cálculo lambda. ¡Ni siquiera los números! En cálculo lambda solo tenemos un objeto: funciones. Y la única operación de que disponemos es la composición de funciones.

Definición

Vamos a definir dos funciones:

• \(I = \lambda x.x\), la identidad
• \(M = \lambda x.xx\), aplica una función \(x\) a sí misma

3. Reduce las siguientes expresiones:

   • \(I \; I\)
   • \(M \; I\)
   • \((I \; I) \; I\)
   • \(\left(\lambda a.(a \; (a \; a))\right) \; I\)
   • \(\left((\lambda a.(\lambda b.a)) \; M\right) \; I\)

Asociatividad

En el cálculo lambda las funciones son asociativas por la izquierda, es decir,

\[ f \; g \; h = (f \; g) \; h \]

Si queremos modificar ese orden de aplicación deberemos usar paréntesis.

4. Reescribe estas expresiones usando el menor número posible de paréntesis.

   • \((\lambda x.(\lambda y.\lambda z.((xz)(yz))))\)
   • \(((ab)(cd))((ef)(gh))\)
   • \((\lambda x.((\lambda y.(yx))(\lambda v.v)z)u)(\lambda w.w)\)

Definición

Dos funciones son equivalentes si solo difieren en el nombre de sus variables.

\[ I \equiv \lambda a.a \equiv \lambda b.b \equiv \lambda \spades.\spades \equiv \dots \]

Definición

La expresión \(K = \lambda a.(\lambda b.a)\) se conoce como función función constante.

5. ¿Por qué ese nombre?

   Solución

   \(Kx = \lambda a.x\), que es una función constante que siempre devuelve \(x\). Dado un argumento, \(K\) devuelve una función constante con ese valor.

6. Evalúa \((M \; K) \; I\) y \((M \; (K \; I))\) para comprobar que la asociatividad es importante. ¿A cuál de las dos expresiones equivale \(M \; K \; I\)?

   Solución

   • \((M \; K) \; I = (K \; K) \; I = (\lambda a.K) \; I = K\)
   • \((M \; (K \; I)) = M \; (\lambda a.I) = (\lambda a.I) \; (\lambda a.I) = I\)

Currificación

En el cálcula lambda, las funciones tienen un solo argumento. Si queremos funciones de varias variables debemos simularlas mediante la currificación. La idea es sencilla: escribir funciones que devuelvan funciones. Ya hemos visto un ejemplo: la función \(K\) toma un argumento \(x\) y lo usa para construir una función constante. De algún modo, \(K\) es una fábrica de funciones.

7. Definimos \(C = \lambda f.(\lambda g.(\lambda x.(f \; (g \; x))))\). ¿Qué hace \(C\)? Evalúa \(C \; a \; b \; x\) para tres expresiones arbitrarias \(a\), \(b\), \(x\).

   Solución

   La evaluación de funciones es asociativa por la izquierda. Así,

   \[ \begin{align*} C \; a \; b \; x &= (C \; a) \; b \; x \\ &= (\lambda f.(\lambda g.(\lambda x.(f \; (g \; x)))) \; a) \; b \; x \\ &= (\lambda g.(\lambda x.(a \; (g \; x)))) \; b \; x \\ &= (\lambda x.(a \; (b \; x))) \; x \\ &= a \; (b \; x) \end{align*} \]

   La función \(C\) asocia los argumentos por la derecha.

8. Evalúa \(C \; M \; I \; \star\) (donde \(\star\) representa una expresión cualquiera). Después, evalúa \(C \; I \; M \; I\).

   Solución

   \[ \begin{align*} C \; M \; I \; \star &= M \; (I \; \star) \\ &= M \; \star \\ &= \lambda x.xx \; \star \\ &= \star \; \star \\ \end{align*} \]

   \[ \begin{align*} C \; I \; M \; I &= I \; (M \; I) \\ &= I \; (I \; I) \\ &= I \; I \\ &= I \end{align*} \]

Notación simplificada

Para simplificar las expresiones, expresaremos todas las variables juntas, tal que así

\[ \lambda x.\lambda y.xy \equiv \lambda xy.xy \\ \lambda x.\lambda y.\lambda z.xyz \equiv \lambda xyz.xyz \]

9. Dada \(Q = \lambda abc.b\), reduce \((Q \; a \; c \; b)\).

   Solución

   Las variables \(a\), \(b\) y \(c\) de la definición de \(Q\) no son las mismas que las de la aplicación, por lo que escribiremos \((Q \; x \; y \; z)\) en vez de \((Q \; a \; c \; b)\).

   \[ \begin{align*} \lambda abc.b \; x \; y \; z &= \lambda a.\lambda b.\lambda c.b \; x \; y \; z \\ &= (\lambda a.\lambda b.\lambda c.b \; x) \; y \; z \\ &= (\lambda b.\lambda c.b \; y) \; z \\ &= \lambda c.y \; z \\ &= y \end{align*} \]

10. Reduce las siguientes expresiones:

    • \(((\lambda a.a) \; \lambda bc.b) \; d \; \lambda eg.g\)
    • \((((\lambda a.a) \; \lambda b.\lambda c.b) \; x) \; \lambda e.f\)
    Solución

    \[ \begin{align*} ((\lambda a.a) \; \lambda bc.b) \; d \; \lambda eg.g &= (\lambda bc.b) \; d \; \lambda eg.g \\ &= (\lambda c.d) \; \lambda eg.g \\ &= d \\ (((\lambda a.a) \; \lambda b.\lambda c.b) \; x) \; \lambda e.f &= ((\lambda b.\lambda c.b) \; x) \; \lambda e.f \\ &= (\lambda c.x) \; \lambda e.f \\ &= x \end{align*} \]

Combinadores

Un combinador es una expresión que no contiene variables libres.

Variables libres y ligadas

Una variable libre es aquella que no aparece como variable de entrada de una abstracción. Una variable ligada es aquella que aparece como variable de entrada de una abstracción.

• \(x\) es una variable libre en las expresiones
  • \(x\)
  • \(vx\)
  • \(\lambda v.x\)
  • \((\lambda x.x) \; x\) (¿ves por qué es libre?)
• \(x\) es una variable ligada en las expresiones
  • \(\lambda x.x\)
  • \(\lambda x.v\)

Ornitología

Algunos combinadores importantes llevan el nombre de pájaros (en inglés). Estos nombres salen del libro de Raymond Smullyan To Mock a Mockingbird, que introduce estas ideas a través de retos y acertijos.

• Idiot: \(I = \lambda a.a\)
• Mockingbird: \(M = \lambda a.aa\)
• Cardinal: \(C = \lambda abc.acb\)
• Kestrel: \(K = \lambda ab.a\)

11. Evalúa la expresión \(K \; \hearts \; \star\). ¿Qué hace \(K\)?

    Solución

    \(K\) recibe dos argumentos y se quede con el primero:

    \[ \lambda a.\lambda b.a \; \hearts \; \star = \lambda b.\hearts \; \star = \hearts \]

12. Escribe un combinador que reciba dos argumentos y se queda con el segundo.

    Solución

    Modificando \(K\), construimos la expresión \(\lambda ab.b\).

    \[ \lambda a.\lambda b.b \; \hearts \; \star = \lambda b.b \; \star = \star \]

13. Comprueba que el combinador del problema anterior, conocido como Kite, se puede obtener con \((K \; I)\).

    Solución

    \[ K \; I \; \hearts \; \star = \lambda a.\lambda b.a \; \lambda c.c \; \hearts \; \star = \lambda b.\lambda c.c \; \hearts \; \star = \lambda c.c \; \star = \star \]

Álgebra de Boole

El Kestrel selecciona su primer argumento, mientras que el Kite selecciona el segundo. ¿Qué podemos hacer con esto? Cambiemos los nombres a \(T = K = \lambda ab.a\) y \(F=K \; I = \lambda ab.b\).

14. Escribe una función \(\text{NOT}\) tal que \(\text{NOT} \; T = F\) y \(\text{NOT} \; F = T\).

    Pistas

    • Evalúa \(T \; F \; T\) y \(F \; F \; T\).
    Solución

    \(\text{NOT} = \lambda a.(a \; F \; T)\)

15. Simplifica las expresiones siguientes, en las que \(a\) puede ser \(T\) o \(F\):

    • \(a \; T \; F\)
    • \(a \; F \; T\)
    Solución

    • Si \(a = T\), dará \(T\). Si \(a = F\), dará \(F\). Por lo tanto, la expresión es equivalente a \(a\).
    • Si \(a = T\), dará \(F\). Si \(a = F\), dará \(T\). Por lo tanto, la expresión es equivalente a \(\text{NOT} \; a\).

16. Además de \(\text{NOT}\), en el álgebra booleana se usan operadores como \(\text{AND}\), \(\text{OR}\) y \(\text{XOR}\). Escribe estos operadores como expresiones lambda.

    Pistas

    • Si el primer argumento de \(\text{AND}\) es \(F\), el resultado es \(F\). Si es \(T\) el resultado es el segundo argumento.
    • Si el primer argumento de \(\text{OR}\) es \(T\), el resultado es \(T\). Si es \(F\) el resultado es el segundo argumento.
    • La función \(\text{XOR}\) se parece a \(\text{OR}\).
    Solución

    • \(\text{AND} = \lambda ab.(a \; b \; F) = \lambda ab.(a \; b \; a)\)
    • \(\text{OR} = \lambda ab.(a \; T \; b) = \lambda ab.(a \; a \; b) = \lambda ab.(M \; a \; b)\)
    • \(\text{XOR} = \lambda ab.(a \; (\text{NOT} \; b) \; b)\)

17. Otro operador importante es el de igualdad, \(\text{EQ}\). ¿Qué argumentos recibe? Escríbelo como expresión lambda.

    Solución

    Es la negación de \(\text{XOR}\). Se puede escribir de varias formas:

    • \(\text{EQ} = \lambda ab.[\text{NOT} \; (\text{XOR} \; a \; b)]\)
    • \(\text{EQ} = \lambda ab.[a \; (b \; T \; F) \; (b \; F \; T)] = \lambda ab.[a \; b \; (\text{NOT} \; b)]\)

Números

Dado que los únicos objetos de que disponemos en el cálculo lambda son funciones, pensaremos en las cantidades como adverbios (una vez, dos veces, tres veces, …) en vez de como sustantivos (uno, dos, tres, …). Así, el cero correspondería a ninguna vez o no hacer nada. Definiremos la función cero así: dada una función y una entrada, no aplicar la función a esa entrada.

\[ 0 = \lambda fa.a \]

18. ¿A qué función de las que ya hemos visto se parece la función 0?

    Solución

    Es equivalente a \(F\).

19. Escribe 1, 2 y 3. Estos son los números de Church.

    Pistas

    Recuerda que 1 quiere decir una vez, 2 quiere decir dos veces, 3 quiere decir tres veces, etcétera.

    Solución

    • \(1 = \lambda fa.(f \; a)\)
    • \(2 = \lambda fa.(f \; (f \; a))\)
    • \(3 = \lambda fa.(f \;(f \; (f \; a)))\)

20. Reduce \((3 \; I \; \clubs)\).

    Solución

    Esta expresión aplica tres veces la función identidad sobre el argumento \(\clubs\).

    \[ \begin{align*} 3 \; I \; \clubs &= \lambda fa.(f \; (f \; (f \; a))) \; I \; \clubs \\ &= \lambda a.(I \; (I \; (I \; a))) \; \clubs \\ &= I \; (I \; (I \; \clubs)) \\ &= I \; (I \; \clubs) \\ &= I \; \clubs \\ &= \clubs \end{align*} \]

21. Reduce las siguientes expresiones:

    • \(3 \; \text{NOT} \; T\)
    • \(8 \; \text{NOT} \; F\)
    • \(1000 \; \text{NOT} \; T\)
    Solución

    Solo veremos la primera, ya que la idea es muy sencilla: aplicar \(\text{NOT}\) una cantidad par de veces nos devuelve el argumento, mientras que aplicarla una cantidad impar de veces nos devuelve la negación del argumento.

    \[ \begin{align*} 3 \; \text{NOT} \; T &= \lambda fa.(f \; (f \; (f \; a))) \; \text{NOT} \; T \\ &= \lambda a.(\text{NOT} \; (\text{NOT} \; (\text{NOT} \; a))) \; T \\ &= \text{NOT} \; (\text{NOT} \; (\text{NOT} \; T)) \\ &= \text{NOT} \; (\text{NOT} \; F) \\ &= \text{NOT} \; T \\ &= F \end{align*} \]

22. Los axiomas de Peano construyen los números naturales a partir de dos objetos: el 0 y la función sucesor \(S\). Ya hemos construido el 0. Construye ahora la función sucesor, tal que \({1 = S(0)}\), \({2 = S(1)}\), etc.

    Pista

    La función debe tener los argumentos \(\lambda nfa = \lambda n.\lambda fa\). ¿Por qué?

    Solución

    Aplicamos la función \(f\) \(n\) veces y después una vez más, \(S = \lambda nfa.(f \; (n \; f \; a))\)

23. Comprueba que \(1 = S(0)\) y que \(2 = S(1)\).

24. Define la función \(\text{SUM}\), que suma dos números de Church.

    Pista

    Debemos sumar \(m\) veces 1 a \(n\).

    Solución

    \(\text{SUM} = \lambda mn.(m \; S \; n)\), donde \(S\) es la función sucesor.

    Extra

    ¿Son equivalentes las funciones \(\lambda mn.(m \; S \; n)\) y \(\lambda mn.(n \; S \; m)\)? Si las aplicamos a números de Church, sí, pero pueden dar resultados distintos si las aplicamos sobre otras funciones. Para comprobarlo, aplica ambas versiones a Kestrel y Kite.

25. Define la función \(\text{MULT}\), que multiplica dos números de Church.

    Pista

    La solución más sencilla usa la función \(\text{SUM}\). Otra más elegante no la usa…

    Solución

    Una posibilidad es \(\text{MULT} = \lambda mn.(m \; (\text{SUM} \; n) \; 0)\). Veamos un ejemplo paso a paso:

    \[ \begin{align*} \text{MULT} \; 3 \; 2 &= \lambda mn.(m \; (\text{SUM} \; n) \; 0) \; 3 \; 2 \\ &= \lambda n.(3 \; (\text{SUM} \; n) \; 0) \; 2 \\ &= 3 \; (\text{SUM} \; 2) \; 0 \\ &= (\text{SUM} \; 2 \; (\text{SUM} \; 2 \; (\text{SUM} \; 2 \; 0))) \\ &= (\text{SUM} \; 2 \; (\text{SUM} \; 2 \; 2)) \\ &= (\text{SUM} \; 2 \; 4) \\ &= 6 \end{align*} \]

    Otra opción es \(\text{MULT} = \lambda mnf.(m \; (n \; f))\)

26. Escribe las funciones \(\text{Z}\) y \(\text{NZ}\), que devuelven \(T\) si el argumento es cero o si no es cero, respectivamente, y \(F\) en caso contrario.

    Solución

    • \(\text{Z} = \lambda a.(a \; (\text{AND} \; F) \; T)\)
    • \(\text{NZ} = \lambda a.(a \; (\text{OR} \; T) \; F)\)

27. Diseña una función \(\text{PAR}\) que construya duplas (2-tuplas), es decir, listas ordenadas de dos elementos. Si \(A = \text{PAR} \; 1 \; 2\), entonces \((A \; T)\) debe devolver \(1\) y \((A \; F)\) debe devolver \(2\).

    Solución

    \[ \text{PAR} = \lambda ab.\lambda i.(i \; a \; b) = \lambda abi.iab \]

    Es habitual expresar \((\text{PAR} \; A \; B)\) de forma más compacta como \(\lang A, B \rang\).

28. Escribe una función \(H\) que dada una dupla desplace el segundo argumento a la primera posición y sume uno al segundo. Es decir,

    • \(H \; \lang 0, 1 \rang = \lang 1, 2 \rang\)
    • \(H \; \lang 1, 2 \rang = \lang 2, 3 \rang\)
    • \(H \; \lang 20, 8 \rang = \lang 8, 9 \rang\)
    Solución

    \[ \text{H} = \lambda p.\lang p \; F, S \; (p \; F) \rang = \lambda pi.\left(i \; (p \; F) \; (S \; (p \; F))\right) \]

    Fíjate en que \(H \; \lang 0, 0 \rang = \lang 0, 1 \rang\).

29. Escribe una función \(D\) que invierta \(S\). Es decir, \(D(1) = 0\), \(D(2) = 1\), …, y \(D(0) = 0\).

    Pista

    Puedes usar \(H\).

    Solución

    \[ D = \lambda n.\left((n \; H \; \lang 0, 0 \rang) \; T\right) \]

Recursión

Un ejemplo típico para explicar la recursión es la definición de factorial,

\[ n! = \begin{cases} n \times (n-1)! & \text{si } n > 0 \\ 1 & \text{si } n = 0 \end{cases} \]

Con esta definición, para calcular \(10!\) debemos calcular \(9!\), que requiere calcular \(8!\), que requiere calcular \(7!\), …, que requiere calcular \(0!\), que sale directamente de la definición. Es decir, la función se llama a sí misma siempre que \(n > 0\).

Este comportamiento no se puede reproducir directamente en el cálculo lambda, ya que no hay una forma de que una función se llame a sí misma. Algo como \(A = \lambda a.A\) no serviría, ya que no es una expresión lambda válida. Pero sí hay maneras de conseguir recursión.

30. Escribe una expresión que se convierta en sí misma al reducirla.

    Solución

    \[ \Omega = M \; M = \lambda x.xx \; \lambda x.xx \]

31. ¿Qué dirías que hace el combinador \(Y\)?

    \[ Y = \lambda f.((\lambda x.f \; (x \; x)) \; (\lambda x.f \; (x \; x))) \]

    Observa su parecido con \(\Omega\).

    Pista

    Evalúa \(Y \; f\).

    Solución

    \[ \begin{align*} Y \; f &= (\lambda x.f \; (x \; x)) \; (\lambda x.f \; (x \; x)) \\ &= f \; ((\lambda x.f \; (x \; x)) \; (\lambda x.f \; (x \; x))) \\ &= f \; (Y \; f) \end{align*} \]

32. Escribe una función recursiva para calcular el factorial usando el combinador \(Y\).

33. Escribe una función no recursiva para calcular el factorial.

Retos

34. Escribe \(D\) sin usar \(H\).

35. Usando duplas, diseña una lista. Define una función \(\text{GET}\) tal que \(\text{GET} \; L \; n\) reduce al \(n\)-simo elemento de la lista \(L\), donde el primer elemento corresponde a \(n=0\), el segundo a \(n=1\), etc. Las listas tienen una longitud definida, así que debes saber cuándo estás en el último elemento.

36. Escribe una expresión lambda que represente la función de Fibonacci: \(f(0) = 1\), \(f(1) = 1\) y \(f(n+2) = f(n+1) + f(n)\).

37. Escribe una expresión lambda que reduzca a \(T\) si un número \(n\) es primo y a \(F\) si no lo es.

38. Escribe una función \(\text{MOD}\) tal que \(\text{MOD} \; a \; b\) reduzca al resto de la división entera \(a \div b\).

Referencias

• Lambda Calculus Calculator
• Alligator Eggs! es un juego que modeliza el cálculo lambda con lagartos y sus huevos:
  • Instrucciones
  • Juego
  • Calculadora