Système formel pour exprimer le calcul fondé sur l'abstraction de fonction, l'application, la liaison de variables et la substitution ; il constitue un modèle de programmation minimal et la base du paradigme fonctionnel et de la théorie de la calculabilité.

Principe

Le calcul s'effectue par règles de transformation syntaxique : alpha-conversion (renommer les variables liées), bêta-réduction (substituer un argument à une variable liée dans le corps d'une fonction) et, parfois, êta-conversion (extensionalité) ; les fonctions sont des valeurs de premier ordre et il n'y a pas d'état intégré.

Démonstration

Avec les encodages de Church, les nombres naturels sont représentés comme des fonctions d'ordre supérieur (numéraux de Church) et l'addition se définit comme une composition d'abstractions lambda ; la bêta-réduction de (add 1 2) produit le numéral correspondant à 3.

Mauvaise application

Confondre égalité syntaxique et équivalence opérationnelle, omettre d'éviter la capture de variables lors de la substitution (ne pas effectuer d'alpha-conversion), ou s'attendre à des effets de bord et à un état mutable comme en impératif — cela mène à un raisonnement ou des programmes incorrects.

Conséquence

Un modèle compact et expressif qui caractérise la calculabilité, sous-tend les systèmes de types et les langages fonctionnels, et clarifie l'équivalence et la transformation de programmes via réductions et formes normales.

Inversion

Un modèle impératif (par ex. machine de Turing avec bande mutable ou machine à registres avec état) qui met l'accent sur les mises à jour séquentielles d'état plutôt que sur l'application de fonctions par substitution.

Limite

Le calcul lambda pur et non typé omet types, données primitives et effets ; les langages pratiques ajoutent types, primitives et systèmes d'effets par-dessus la computation de style lambda pour gérer ressources et interactions avec l'environnement.

Tension sémantique

Le calcul lambda comme modèle abstrait du calcul versus son rôle comme syntaxe et sémantique concrètes d'un langage de programmation ; les variantes non typées et typées s'opposent aussi entre expressivité et sécurité.

Synthèse

Une algèbre dépouillée de fonctions où le calcul est conduit par substitution : on définit des fonctions par abstraction, on les applique à des arguments et on calcule en réduisant systématiquement les expressions, formant le noyau conceptuel de la computation fonctionnelle et de la calculabilité théorique.