Le lambda-calcul est un système formel de logique mathématique permettant d'exprimer des calculs basés sur l'abstraction de fonctions et leur application par liaison et substitution de variables. C'est un modèle de calcul universel permettant de simuler n'importe quelle machine de Turing. Il constitue la base théorique de langages de programmation fonctionnelle comme Lisp, Haskell et 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`.
Malgré sa syntaxe parcimonieuse, le lambda-calcul est Turing-complet. Il peut représenter des nombres (chiffres de Church), des booléens, des structures de données et contrôler le flux (comme la récursivité) uniquement par le biais de fonctions. Cela démontre que le concept de fonction est suffisant pour le calcul universel. Cela contraste avec le modèle de la machine de Turing, basé sur l'état et la mutation. Le théorème de Church-Rosser est une propriété clé du lambda-calcul : il stipule que l'ordre d'application des réductions ne modifie pas le résultat final, une propriété appelée confluence. Cela simplifie considérablement le raisonnement sur le comportement des programmes par rapport aux modèles impératifs, où l'ordre des changements d'état est crucial.
Lambda calculus has had a profound influence on langage de programmation 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.