Calcul lambda et modèles fonctionnels

Le calcul lambda est un système formel minimal dans lequel tout est fonction et où le calcul procède par substitution, offrant à la fois un modèle précoce de calcul effectif et le cœur théorique de la programmation fonctionnelle.

Definition

Le calcul lambda est un langage formel construit à partir de variables, d'abstraction de fonctions et d'application, le calcul étant effectué par la bêta-réduction, la règle qui applique une fonction à un argument par substitution ; c'est un modèle universel équivalent en puissance aux machines de Turing.

Scope

Ce sujet couvre la syntaxe des termes lambda, les règles de réduction qui régissent le calcul, la propriété de confluence de Church–Rosser, l'encodage des données et de la récursion via les combinateurs de point fixe, la complétude de Turing du calcul, et les variantes typées qui relient le calcul à la logique.

Core questions

• Comment le calcul peut-il être exprimé en n'utilisant que des fonctions et la substitution ?
• Pourquoi l'ordre des réductions ne modifie-t-il pas le résultat final ?
• Comment les nombres, les données et la récursion sont-ils représentés uniquement par des fonctions ?
• Comment les calculs lambda typés relient-ils le calcul à la preuve logique ?

Key theories

Théorème de Church–Rosser

Si un terme lambda peut être réduit de différentes manières, les résultats peuvent toujours être ramenés à un point commun, de sorte que chaque terme possède au plus une forme normale et que le calcul est confluent et bien défini en tant que modèle de calcul.

Complétude de Turing et points fixes

Les combinateurs de point fixe expriment une récursion arbitraire, rendant le calcul lambda non typé capable de calculer toute fonction calculable par une machine de Turing et en faisant ainsi un modèle de calcul complet.

Correspondance de Curry–Howard

Les calculs lambda typés correspondent à des systèmes de logique, les types étant des propositions et les programmes des preuves, reliant directement le calcul à la logique constructive et sous-tendant les assistants de preuve.

Clinical relevance

Le calcul lambda est le fondement des langages de programmation fonctionnels tels que Lisp, Haskell et ML, des systèmes de types qui détectent les erreurs dans les langages modernes, et des assistants de preuve où la correspondance de Curry–Howard permet de vérifier les programmes et les preuves mathématiques avec le même mécanisme.

History

Church a introduit le calcul lambda dans les années 1930 comme fondement de la logique et du calcul, et avec Rosser, il en a prouvé la confluence. Bien que le système logique original fût incohérent, le cœur computationnel a prospéré, et à partir des années 1960, il a façonné la programmation fonctionnelle et, par le biais de la correspondance de Curry–Howard, le lien entre les preuves et les programmes.

Key figures

• Alonzo Church
• Haskell Curry
• J. Barkley Rosser
• William Alvin Howard

Seminal works

• church1936
• barendregt1984

Frequently asked questions

Comment un système composé uniquement de fonctions peut-il effectuer des calculs avec des nombres ?

Les nombres sont encodés comme des fonctions, par exemple les nombres de Church représentant un nombre par le nombre de fois qu'une opération donnée est appliquée. L'arithmétique, les booléens, les paires et les structures de données ont tous des encodages fonctionnels, de sorte que le calcul n'a pas besoin de types de données intégrés et peut pourtant exprimer n'importe quel calcul.

Quel est le lien entre le calcul lambda et la programmation ?

Les langages fonctionnels sont essentiellement des calculs lambda étendus : leur cœur est constitué de fonctions, d'application et de substitution. Le calcul fournit également la théorie des types que les langages modernes utilisent pour la sécurité, et par le biais de la correspondance de Curry–Howard, il relie les programmes bien typés aux preuves logiques.