
Cálculo lambda
Sistema formal de la lógica matemática que describe la computación mediante funciones anónimas, la aplicación de funciones a argumentos y la sustitución de variables.
- Año
- 1936
- Protagonistas
- Alonzo Church
- Sección
- Matemáticas
Historia
El cálculo lambda es un sistema formal con el que se puede representar cualquier cálculo que realizaría una máquina, basado en tres ideas sencillas: nombrar variables, crear funciones anónimas y aplicarlas a un argumento. Su importancia reside en que ofrece una definición precisa de qué significa que una función sea computable, algo que los matemáticos necesitaban para estudiar los límites de lo que se puede calcular.
A comienzos de la década de 1930, Alonzo Church buscaba construir un sistema formal completo para fundamentar las matemáticas. En 1934, Stephen Kleene y J. Barkley Rosser publicaron una paradoja que mostraba que aquel primer sistema era lógicamente inconsistente, lo que obligó a Church a replantearse el proyecto. Desde entonces aisló la parte del sistema relacionada con el cálculo y la publicó en 1936 como cálculo lambda sin tipos. Esa versión permitía expresar funciones sin darles nombre, y cada función recibe un único argumento; cuando una función necesita dos datos, se transforma en una cadena de funciones de un solo argumento, procedimiento que se conoce como currificación. Así, una suma de dos números puede expresarse como una función que toma uno y devuelve otra función que toma el segundo.
El sistema se basa en dos operaciones: la abstracción, que crea una función a partir de una expresión con una variable libre (por ejemplo, λx. x + 2 es la función «sumar 2»), y la aplicación, que sustituye el argumento en el cuerpo de la función. Esta sustitución, la llamada β-reducción, permite simplificar expresiones paso a paso, y aunque no todas las expresiones llegan a un valor final, el sistema permite estudiar de forma rigurosa qué puede calcularse y qué no.
Con este instrumento, Church empleó en 1936 el cálculo lambda para dar una respuesta negativa al Entscheidungsproblem, el problema de decisión planteado por David Hilbert, que preguntaba si existe un procedimiento general que determine la verdad de cualquier enunciado matemático. Poco después, Alan Turing llegó a resultados equivalentes con las máquinas que hoy llevan su nombre, y se demostró que ambos modelos describen exactamente las mismas funciones computables. Esa equivalencia reforzó la tesis de Church-Turing, según la cual cualquier procedimiento calculable puede expresarse de una de estas formas.
En 1940, Church presentó además el cálculo lambda simplemente tipado, una variante más débil en su poder de expresión, pero lógicamente consistente, en la que cada dato tiene un tipo y solo se aplican funciones a datos compatibles. Durante décadas el cálculo lambda fue sobre todo una herramienta teórica, hasta que en los años sesenta se aclaró su relación con los lenguajes de programación. Desde entonces ha influido en lenguajes funcionales como Lisp, ML y Haskell, en los que las funciones se tratan como valores que pueden pasarse a otras funciones. También se usa en lingüística, para describir el significado de las frases, y en la teoría de categorías.
Hoy el cálculo lambda sigue siendo la base conceptual de buena parte del diseño de lenguajes de programación, de los sistemas de verificación de programas y de la teoría de tipos, de modo que una idea surgida para fundamentar las matemáticas acabó siendo una referencia central en la informática.
Cronología
- 1934Kleene y Rosser publican una paradoja que muestra la inconsistencia del primer sistema de Church.
- 1936Church publica el cálculo lambda sin tipos y lo usa para responder negativamente al Entscheidungsproblem.
- 1940Church introduce el cálculo lambda simplemente tipado, menos potente pero lógicamente consistente.
- 1960Se aclara la relación del cálculo lambda con los lenguajes de programación.
Curiosidades y anécdotas
El origen de la letra λ
Church dio explicaciones distintas sobre por qué eligió la letra lambda. En una carta de 1964 dijo que procedía de la notación de Whitehead y Russell, pero años después habló de una elección casi accidental.
Una respuesta de una sola línea
Según relató Dana Scott, cuando un antiguo alumno de Church le preguntó por el símbolo, Church devolvió la postal con la frase «eeny, meeny, miny, moe».