Lambda calculus is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It forms the theoretical basis for functional programming languages like Lisp, Haskell, and F#.
Desarrollado por Alonzo Church en la década de 1930, el cálculo lambda proporciona un marco minimalista pero potente para definir y aplicar funciones. Su sintaxis completa consta de solo tres componentes: variables (por ejemplo, `x`), abstracciones y aplicaciones. Una abstracción, o función lambda, es una definición de función anónima, escrita como [latex]lambda xM[/latex], donde `x` es el parámetro de entrada y `M` es el cuerpo de la función. Una aplicación, escrita como `MN`, representa la aplicación de la función `M` al argumento `N`. El cálculo en el cálculo lambda se realiza mediante un proceso llamado reducción beta, donde la aplicación de una función lambda a un argumento se resuelve sustituyendo el argumento por la variable ligada dentro del cuerpo de la función. Por ejemplo, aplicar [latex](lambda x.x+1)[/latex] a `3` se reduce a `3+1`.
Despite its sparse syntax, lambda calculus is Turing complete. It can represent numbers (Church numerals), booleans, data structures, and control flow (like recursion) purely through functions. This demonstrates that the concept of a function is sufficient for universal computation. This contrasts with the Turing machine model, which is based on state and mutation. The Church-Rosser theorem is a key property of lambda calculus, stating that the order in which reductions are applied does not change the final result, a property known as confluence. This makes reasoning about program behavior much simpler than in imperative models where the order of state changes is critical.
El cálculo lambda ha tenido una profunda influencia en lenguaje de programación El diseño es el antecesor directo del paradigma de programación funcional. Conceptos que ahora son comunes en muchos lenguajes, como las funciones de primera clase (que tratan las funciones como datos), las funciones de orden superior (que toman otras funciones como argumentos), los cierres (que capturan su entorno léxico) y el currying, tienen sus raíces en el cálculo lambda. Lenguajes como Lisp fueron de los primeros en implementar estas ideas, y lenguajes modernos como Haskell, JavaScript y Python las han integrado profundamente en su diseño.
Relacionado con: cálculo lambda, programación funcional, Alonzo Church, reducción beta, funciones de orden superior, Lisp, Haskell, sistema formal, computabilidad, teoría de tipos.