Lambda Calculus
Le lambda-calcul est le fondement mathématique de la programmation fonctionnelle : seulement définition de fonction (λx.M) et application (MN), et pourtant Turing-complet.
Objectif
Comprendre le fondement théorique et le modèle de calcul de la programmation fonctionnelle.
Mécanisme
Trois règles : variable x, abstraction λx.M (définir une fonction), application MN (appeler une fonction). La β-réduction ((λx.M)N → M[x:=N]) est le calcul. L'α-conversion renomme les variables liées. L'encodage de Church représente les données par des lambdas.
Cas d’usage
- Programmation fonctionnelle
- Théorie du calcul
- Fondements des langages