Lambda Calculus

Las sintaxis y gramática del cálculo lambda son muy sencilla. Si cogemos una expresión cualquiera, por ejemplo \(\lambda ab.a\), vemos que:

• el símbolo \(\lambda\) nos indica que tenemos una función
• en el conjunto ab, la a nos implica que la función se aplica con dicho parámetro: toda función es unaria, por lo que ab es una contracción de la expresión completa \(\lambda a . \lambda b . a\). Es decir, toda función está currificada, y lo anterior sería equivalente en JavaScript a const fn = a => b => a.
• el punto nos separa la definición de la función de expresión que se evalúa cuando se ejecuta dicha función.

La función más sencilla, devuelve el valor que se le pase: su salida es igual a su entrada. Así, \(I(4) -> 4\), \(I([1, 2, 3]) -> [1, 2, 3])\), etc. Su definición informal será:

I :: a -> a

(defn I [e] e)

def I(e): return e

fun <T>I(t: T) = t

La Identidad de una función es a su vez una función. Así, \(I(double) -> double\), e \(I(I) -> I\).

La definición en términos de cálculo lambda es:

• Uso: aplicación propia
• Definición: \(M := \lambda f . ff\)

Como se ve automáticamente a partir de su definición, toma una función como entrada y la usa como input para su propia aplicación.

M :: (a -> a) -> (a -> a)

(defn M [f] (f f))

def M(f): return f(f)

fun <T>M(f: (T) -> T): (T) -> T = ???

• Uso: primer parámetro, constante
• Definición: \(K := \lambda ab.a\)
• a -> b -> a$

Extremadamente sencillo. Muy útil como se verá posteriormente para crear otros combinadores.

(defn K [a b] a)

En Haskell se le llama función const en prelude. Para verlo necesitamos que la función esté currificada. De esta forma, al fijar el primer parámetro obtenemos una función que, la llamemos con lo que la llamemos, siempre nos devolverá aquél parámetro fijado.

user=>  (defn K [a] (fn [b] a))
user=> ((K 2) 5)
2

• Uso: obtener segundo parámetro
• Definición: \(\lambda ab.b\)
• a -> b -> b$

Al contrario que el Kestrell nos devuelve el segundo argumento que se le pase. Puede definirse a partir de aquél con su combinación con \(I\):

\(K I x -> I\) \(K I x y -> y\)

Al devolver \(KIx\) la función identidad, al aplicar otro parámetro \(y\), este último es al final el valor devuelto.

(defn KI [a b] b)

Podemos definirlo también a partir de la versión currificada del Kestrell:

user=> (defn KI [] (K I))
user=> (((KI) 5) 8)
8

Si queremos simplificar la llamada en Clojure, podemos definirla de distintas formas:

user=> (defn KI [a] (fn [b] (((K I) a) b)))
user=> ((KI 5) 8)
8

user=> (defn KI [a b] (((K I) a) b))
user=> (KI 5 8)
8

• Uso: flip
• Definición: \(\lambda fab.fba\)
• f -> a -> a -> a$ ²

(defn C [f a b] (f b a))

El Cardinal del Kestrell nos da el segundo valor, por lo que es igual al Kite.

(Minutos 36:29)