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#.
Desenvolvido por Alonzo Church na década de 1930, o cálculo lambda fornece uma estrutura minimalista, porém poderosa, para definir e aplicar funções. Sua sintaxe completa consiste em apenas três componentes: variáveis (por exemplo, `x`), abstrações e aplicações. Uma abstração, ou função lambda, é uma definição de função anônima, escrita como [latex]lambda xM[/latex], onde `x` é o parâmetro de entrada e `M` é o corpo da função. Uma aplicação, escrita como `MN`, representa a aplicação da função `M` ao argumento `N`. A computação no cálculo lambda procede por meio de um processo chamado redução beta, onde a aplicação de uma função lambda a um argumento é resolvida pela substituição do argumento pela variável ligada dentro do corpo da função. Por exemplo, aplicar [latex](lambda x.x+1)[/latex] a `3` se reduz 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.
O cálculo lambda teve uma profunda influência em linguagem de programação O cálculo lambda é o ancestral direto do paradigma da programação funcional. Conceitos que hoje são comuns em muitas linguagens, como funções de primeira classe (tratar funções como dados), funções de ordem superior (funções que recebem outras funções como argumentos), closures (funções que capturam seu ambiente léxico) e currying, têm suas raízes no cálculo lambda. Linguagens como Lisp estiveram entre as primeiras a implementar essas ideias, e linguagens modernas como Haskell, JavaScript e Python as integraram profundamente em seu design.
Relacionado a: cálculo lambda, programação funcional, Alonzo Church, redução beta, funções de ordem superior, Lisp, Haskell, sistemas formais, computabilidade, teoria dos tipos.