El cálculo lambda es un sistema formal de lógica matemática que expresa la computación basándose en la abstracción y aplicación de funciones mediante la vinculación y sustitución de variables. Es un modelo universal de computación que permite simular cualquier máquina de Turing. Constituye la base teórica de lenguajes de programación funcional como Lisp, Haskell y F#.
Developed by Alonzo Church in the 1930s, lambda calculus provides a minimalist yet powerful framework for defining and applying functions. Its entire syntax consists of just three components: variables (e.g., `x`), abstractions, and applications. An abstraction, or lambda function, is an anonymous function definition, written as [latex]\lambda x.M[/latex], where `x` is the input parameter and `M` is the body of the function. An application, written as `M N`, represents applying function `M` to argument `N`. Computation in lambda calculus proceeds through a process called beta reduction, where an application of a lambda function to an argument is resolved by substituting the argument for the bound variable within the function’s body. For example, applying [latex](\lambda x.x+1)[/latex] to `3` reduces to `3+1`.
A pesar de su sintaxis dispersa, el cálculo lambda es Turing completo. Puede representar números (numerales de Church), booleanos, estructuras de datos y flujo de control (como la recursión) únicamente mediante funciones. Esto demuestra que el concepto de función es suficiente para la computación universal. Esto contrasta con el modelo de la máquina de Turing, que se basa en el estado y la mutación. El teorema de Church-Rosser es una propiedad clave del cálculo lambda, que establece que el orden en que se aplican las reducciones no altera el resultado final, una propiedad conocida como confluencia. Esto simplifica mucho el razonamiento sobre el comportamiento del programa que en los modelos imperativos, donde el orden de los cambios de estado es crucial.
Lambda calculus has had a profound influence on lenguaje de programación design. It is the direct ancestor of the functional programming paradigm. Concepts that are now common in many languages, such as first-class functions (treating functions as data), higher-order functions (functions that take other functions as arguments), closures (functions that capture their lexical environment), and currying, all have their roots in lambda calculus. Languages like Lisp were among the first to implement these ideas, and modern languages from Haskell to JavaScript and Python have integrated them deeply into their design.