El cálculo lambda consiste de tres sencillos términos y todas las combinaciones que podemos hacer de ellos recursivamente. Esto es, en la notación de Backus-Naur:
term ::=
var (Una variable) |
term term (Una aplicación) |
λ var . term (Una abstracción lambda)
La primera operación básica del cálculo lambda es la aplicación: Sean (dos elementos de todo el conjunto de términos λ) notemos que, en la expresión:
representa un algoritmo y representa la entrada que toma ese algoritmo, por lo tanto, la expresión puede ser vista de dos formas: como el proceso en si de calcular , o bien como el resultado final de ese proceso.
La segunda operación básica es la abstracción lambda: Recordemos que una función se define como una correspondencia que asigna exactamente un elemento de un conjunto a cada elemento de otro, por lo que si , la función evaluada en siempre tendrá el valor , ahora, si utilizamos esta nueva notación, decimos que un término λ liga su variable, es decir, si es una expresión que contiene o depende de , entonces, denota a la función que toma una variable y devuelve (, o bien ).
¿Por qué esta necesidad de usar funciones en programación? ¿Por qué no usar lenguajes imperativos? Con los ciclos for y while que ya conocemos. Bueno… porque un aspecto fundamental en todas las Matemáticas es el razonamiento ecuacional, según el cual si
, entonces la expresión es igual a , en otras palabras, siempre podemos sustituir a las funciones por los valores que calculan. La idea central de la programación funcional es estructurar nuestros programas de tal manera que podamos razonar sobre ellos como un sistema de ecuaciones, tal y como hacemos en Matemáticas.