Un système formel pour représenter la computation par abstraction de fonction (λx. M), application (M N), liaison de variables et substitution, avec des règles opérationnelles telles que l'alpha-équivalence et la beta-réduction ; il sert de modèle fondamental de calcul.

Principe

La computation comme substitution : évaluer une expression revient à remplacer des variables liées par des termes d'argument (beta-réduction) selon des règles évitant la capture (alpha-conversion).

Démonstration

Représenter les nombres naturels par les numéraux de Church et définir l'addition par un terme lambda : add = λm.λn.λf.λx. m f (n f x) ; réduire add 2 3 donne le numéral de Church pour 5 via des beta-réductions successives.

Mauvaise application

Confondre un terme lambda avec une fermeture mutable dans un langage impératif ou traiter des variables libres comme globales par défaut, ce qui déforme la sémantique de portée et de substitution et mène à un raisonnement incorrect sur les programmes.

Conséquence

Fournit un compte rendu simple et compositionnel de la computation qui sous-tend les langages fonctionnels, les transformations de compilateur (inlining, lambda lifting) et des résultats théoriques sur la calculabilité et l'équivalence de programmes.

Inversion

Une vue opérationnelle par transitions d'état (machines impératives) qui met l'accent sur l'état mutable, les commandes et les étapes explicites plutôt que sur la réduction par substitution.

Limite

Concerne les expressions syntaxiques, la liaison et la réduction ; le lambda-calcul non typé est Turing-complet mais omet des garanties statiques, tandis que les variantes typées ajoutent des règles de typage — les aspects opérationnels comme l'I/O ou les effets nécessitent des extensions.

Tension sémantique

Tension entre la réduction syntaxique intensionnelle (comment les termes se réduisent) et l'égalité extensionnelle des fonctions (comportement sur tous les arguments), et entre l'expressivité non typée et les contraintes de sécurité des systèmes typés (simply typed, polymorphique, dépendant).

Synthèse

Le calcul lambda est un formalisme minimal centré sur la substitution qui modélise la computation en traitant les fonctions comme des termes de première classe et l'évaluation comme remplacement de variables selon une discipline de liaison ; il constitue le noyau théorique de la programmation fonctionnelle et des résultats de normalisation et d'équivalence.