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#.
Développé par Alonzo Church dans les années 1930, le lambda-calcul offre un cadre minimaliste mais puissant pour définir et appliquer des fonctions. Sa syntaxe se compose de trois éléments seulement : les variables (par exemple, `x`), les abstractions et les applications. Une abstraction, ou fonction lambda, est une définition de fonction anonyme, notée `lambda xM`, où `x` est le paramètre d'entrée et `M` le corps de la fonction. Une application, notée `MN`, représente l'application de la fonction `M` à l'argument `N`. Les calculs en lambda-calcul s'effectuent par un processus appelé bêta-réduction, où l'application d'une fonction lambda à un argument est résolue en substituant cet argument à la variable liée dans le corps de la fonction. Par exemple, appliquer `(lambda x.x+1)` à `3` se réduit à `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.
Le lambda-calcul a eu une profonde influence sur langage de programmation Le lambda-calcul est l'ancêtre direct du paradigme de la programmation fonctionnelle. Des concepts aujourd'hui courants dans de nombreux langages, tels que les fonctions de première classe (traitement des fonctions comme des données), les fonctions d'ordre supérieur (fonctions prenant d'autres fonctions comme arguments), les fermetures (fonctions capturant leur environnement lexical) et la curryfication, trouvent tous leur origine dans le lambda-calcul. Des langages comme Lisp furent parmi les premiers à implémenter ces idées, et les langages modernes, de Haskell à JavaScript en passant par Python, les ont profondément intégrés à leur conception.
En lien avec : le lambda-calcul, la programmation fonctionnelle, Alonzo Church, la réduction bêta, les fonctions d’ordre supérieur, Lisp, Haskell, les systèmes formels, la calculabilité, la théorie des types.