L'abstraction lambda décomposée. λ {\displaystyle \lambda } indique le début d'une fonction. x {\displaystyle x} est le paramètre d'entrée. M {\displaystyle M} est le corps, sép...
où les variables parcourent un ensemble infini de noms. Les termes parcourent tous les lambda-termes. Ceci correspond à la définition inductive suivante :
est un terme lambda valide.
où est la variable de paramètre de l'abstraction ,
où sont des termes lambda.
Un terme lambda est syntaxiquement valide s'il peut être obtenu par application répétée de ces trois règles. Par commodité, les parenthèses peuvent souvent être omises lors de l'écriture d'un terme lambda ; voir
« Notation », pour plus de détails.
Dans le cadre de lambda, toute occurrence d'une variable qui n'est pas un paramètre d'un lambda englobant est dite libre . Toute occurrence libre de
Par exemple, dans le terme
, c'est-à-dire les variables qui apparaissent librement dans
La notation
Explications et applications
Le lambda-calcul est Turing-complet , c'est-à-dire qu'il s'agit d'un modèle universel de calcul qui peut être utilisé pour simuler n'importe quelle machine de Turing . Son homonyme, la lettre grecque lambda (λ), est utilisée dans les expressions lambda et les termes lambda pour désigner la liaison d'une variable dans une fonction .
Origine du symbole λ
" utilisé pour l'abstraction de classe par Whitehead et Russell , en modifiant d'abord "
Cette origine a également été rapportée dans [Rosser, 1984, p. 338]. Par ailleurs, plus tard, Church a confié à deux personnes qui l’interrogeaient que le choix était plus fortuit : il fallait un symbole et λ a été choisi par hasard.
Dana Scott a également abordé cette question dans diverses conférences publiques. Scott raconte qu'il a un jour posé une question sur l'origine du symbole lambda à John W. Addison Jr., ancien élève et gendre de Church, qui a ensuite écrit une carte postale à son beau-père :
Selon Scott, la seule réponse de Church a consisté à renvoyer la carte postale avec l'annotation suivante : « eeny, meeny, miny, moe ».
Motivation
Les fonctions calculables constituent un concept fondamental en informatique et en mathématiques. Le lambda-calcul offre une sémantique simple pour le calcul, utile pour l'étude formelle de ses propriétés. Ce lambda-calcul intègre deux simplifications qui en confèrent la simplicité à sa sémantique.
La seconde simplification est que le lambda-calcul n'utilise que des fonctions à une seule entrée. Une fonction ordinaire qui nécessite deux entrées, par exemple la fonction lambda, n'en utilise pas.
peut être retravaillé en
Cette méthode, appelée curryfication , transforme une fonction qui prend plusieurs arguments en une chaîne de fonctions, chacune avec un seul argument.
tandis que l'évaluation de la version au curry nécessite une étape supplémentaire
pour arriver au même résultat.
En lambda-calcul, les fonctions sont considérées comme des « valeurs de première classe », ce qui signifie qu'elles peuvent être utilisées comme entrées ou renvoyées comme sorties par d'autres fonctions. Par exemple, le terme lambda
Formes normales et confluence
.
Considérons les termes individuels : les termes fortement normalisants et les termes faiblement normalisants possèdent une forme normale unique. Pour les termes fortement normalisants, toute stratégie de réduction garantit l’obtention de la forme normale, tandis que pour les termes faiblement normalisants, certaines stratégies de réduction peuvent ne pas y parvenir.
Encodage des types de données
:= λ f .λ x . x
1 := λ f .λ x . f x
2 := λ f .λ x . f ( f x )
3 := λ f .λ x . f ( f ( f x ))
et ainsi de suite. Ou encore, en utilisant une syntaxe alternative autorisant plusieurs arguments non curryfiés pour une fonction :
0 := λ fx . x
1 := λ fx . f x
2 := λ fx . f ( f x )
3 := λ fx . f ( f ( f x ))
Un nombre de Church est une fonction d'ordre supérieur : il prend une fonction f à un argument et renvoie une autre fonction à un argument. Le nombre de Church n est une fonction qui prend une fonction f comme argument et renvoie la n -ième composition de f , c'est-à-dire la fonction f composée n fois avec elle-même. On note cette composition f ( n ) , qui correspond en fait à la n -ième puissance de f (considérée comme un opérateur) ; f (0) est définie comme la fonction identité. La composition fonctionnelle est associative , et par conséquent, de telles compositions répétées d'une même fonction f obéissent à deux lois des exposants : f ( m ) ∘ f ( n ) = f ( m+n ) et ( f ( n ) ) ( m ) = f ( m*n ) , ce qui explique pourquoi ces nombres peuvent être utilisés en arithmétique. (Dans le lambda-calcul original de Church, le paramètre formel d'une expression lambda devait apparaître au moins une fois dans le corps de la fonction, ce qui rendait impossible la définition de 0 ci-dessus .)(''n'')"}},"i":0}}] (0)"}},"i":0}}] (''m'')∘''f''(''n'') {{=}} ''f''(''m+n'')"}},"i":0}}] (''n''))(''m'') {{=}} ''f''(''m*n'')"}},"i":0}}]
Une façon d'interpréter le nombre de Church n , souvent utile pour l'analyse de programmes, est de le considérer comme une instruction « répéter n fois ». Par exemple, à l'aide des fonctions PAIR et NIL définies ci-dessous, on peut définir une fonction qui construit une liste chaînée de n éléments tous égaux à x en répétant n fois l'instruction « ajouter un élément x au début » , à partir d'une liste vide. Le terme lambda
λ n .λ x . n (PAIR x ) NIL
crée, étant donné un nombre de Church n et un certain x , une séquence de n applications
PAIRE x (PAIRE x ...(PAIRE x NUL)...)
En faisant varier ce qui est répété et les arguments auxquels cette fonction répétée est appliquée, on peut obtenir une grande variété d'effets différents.
Nous pouvons définir une fonction successeur, qui prend un nombre de Church n et renvoie son successeur n + 1 en effectuant une application supplémentaire de la fonction f qui lui est fournie, où ( nfx ) signifie « n applications de f à partir de x » :
SUCC := λ n .λ f .λ x . f ( n f x )
Puisque la m -ième composition de f composée avec la n -ième composition de f donne la m + n -ième composition de f , f ( m ) ∘ f ( n ) = f ( m+n ) , l'addition peut être définie comme(''m'')∘''f''(''n'') {{=}} ''f''(''m+n'')"}},"i":0}}]
PLUS := λ m .λ n .λ f .λ x . m f ( n f x )
On peut considérer PLUS comme une fonction prenant deux nombres naturels comme arguments et renvoyant un nombre naturel ; on peut vérifier que
PLUS 2 3
et
5
sont des expressions lambda bêta-équivalentes. Puisqu'ajouter m à un nombre peut se faire en répétant l'opération suivante m fois, une autre définition est :
PLUS′ := λ m .λ n . m SUCC n
De même, suivant ( f ( n ) ) ( m ) = f ( m*n ) , la multiplication peut être définie comme(''n''))(''m'') {{=}} ''f''(''m*n'')"}},"i":0}}]
MULT := λ m .λ n .λ f . m ( n f )
Ainsi, la multiplication des nombres de Church revient simplement à leur composition en tant que fonctions.
MULT′ := λ m .λ n . m (PLUS n ) 0
car multiplier m et n revient à ajouter n de manière répétée, m fois, en commençant par zéro.
L'exponentiation, qui consiste à multiplier un nombre par lui-même de façon répétée, se traduit, en tant que fonction, par la composition répétée d'un chiffre de Church avec lui-même. Or, les chiffres de Church sont précisément des compositions répétées .
POW := λ b .λ n . n b
Ou bien, ici aussi,
POW′ := λ b .λ n . n (MULT b ) 1
En simplifiant, cela devient
POW′′ := λ b .λ n .λ f . nbf
mais il s'agit simplement d'une version étendue de POW, que nous avons déjà, ci-dessus.
La fonction prédécesseur , définie par les deux équations PRED (SUCC n ) = n et PRED 0 = 0 , est considérablement plus complexe. La formule
PRED := λ n .λ f .λ x . n (λ g .λ h . h ( g F )) (λ u . X ) (λ u . u )
On peut le valider en démontrant par récurrence que si T désigne (λ g .λ h . h ( g f )) , alors T ( n ) (λ u . x ) = (λ h . h ( f ( n −1) ( x ))) pour n > 0. Deux autres définitions de PRED sont données ci-dessous, l'une utilisant des conditionnelles et l'autre des paires . Avec la fonction prédécesseur, la soustraction est simple. Définition(''n'')(λ''u''.''x'') = (λ''h''.''h''(''f''(''n''−1)(''x'')))"}},"i":0}}] 0"}},"i":0}}]
SOUS := λ m .λ n . n PRED m ,
SUB m n donne m − n lorsque m > n et 0 sinon. ''n''"}},"i":0}}]
Logique et prédicats
Par convention, les deux définitions suivantes (connues sous le nom de booléens de Church) sont utilisées pour les valeurs booléennes VRAI et FAUX :
VRAI := λ x .λ y . x
FAUX := λ x .λ y . y
Ensuite, avec ces deux termes lambda, nous pouvons définir certains opérateurs logiques (ce ne sont que des formulations possibles ; d'autres expressions pourraient être tout aussi correctes) :
ET := λ p .λ q . p q p
OU := λ p .λ q . p p q
NON := λ p . p FAUX VRAI
IFTHENELSE := λ p .λ a .λ b . p un b
Nous sommes désormais capables de calculer certaines fonctions logiques, par exemple :
ET VRAI FAUX
β TRUE FALSE TRUE"}},"i":0}}] ≡ (λ p .λ q . p q p ) VRAI FAUX → β VRAI FAUX VRAI
β FALSE"}},"i":0}}] ≡ (λ x .λ y . x ) FAUX VRAI → β FAUX
et nous constatons que ET VRAI FAUX est équivalent à FAUX .
Un prédicat est une fonction qui renvoie une valeur booléenne. Le prédicat le plus fondamental est ISZERO , qui renvoie TRUE si son argument est le chiffre de Church 0 , mais FALSE si son argument est un autre chiffre de Church.
ISZÉRO := λ n . n (λ x .FAUX) VRAI
Le prédicat suivant teste si le premier argument est inférieur ou égal au second :
LEQ := λ m .λ n .ISZERO (SUB m n ) ,
et puisque m = n si LEQ m n et LEQ n m , il est simple de construire un prédicat pour l'égalité numérique.
La disponibilité des prédicats et la définition ci-dessus de VRAI et FAUX facilitent l'écriture d'expressions « si-alors-sinon » en lambda-calcul. Par exemple, la fonction prédécesseur peut être définie comme suit :
PRED := λ n . n (λ g .λ k .ISZERO ( g 1) k (PLUS ( g k ) 1)) (λ v .0) 0
ce qui peut être vérifié en montrant par induction que n (λ g .λ k .ISZERO ( g 1) k (PLUS ( g k ) 1)) (λ v .0) est la fonction add n − 1 pour n > 0.
Paires
Une paire (un tuple de 2 éléments) encapsule deux valeurs et est représentée par une abstraction qui attend un gestionnaire auquel elle transmettra ces deux valeurs. La méthode FIRST renvoie le premier élément de la paire et la méthode SECOND renvoie le second.
PAIRE := λ x .λ y .λ f . f x y
PREMIER := λ p . p (λ x .λ y . x )
DEUXIÈME := λ p . p (λ x .λ y . y )
Une liste chaînée peut être soit NIL (liste vide), soit une paire composée d'un élément (la tête ) et d'une liste plus petite ( la queue ). Le prédicat NULL renvoie TRUE pour la valeur NIL et FALSE pour une liste non vide.
NIL := λ f .TRUE
NULL := λ p . p (λ x .λ y .FALSE)
Alternativement, avec NIL := FALSE , la construction ( l (λ h .λ t .λ z . ... h ... t ...) _on_nil_) évite le besoin d'un test NULL explicite :
NIL := λ x .λ y . y
NULL := λ l . l (λ h .λ t .λ z .FALSE) VRAI
À titre d'exemple d'utilisation de paires, la fonction de décalage et d'incrémentation qui transforme ( m , n ) en ( n , n + 1) peut être définie comme suit :
Φ := λ p .PAIR (SECOND p ) (SUCC (SECOND p ))
Ψ := λ fp .PAIR (SECOND p ) (f (SECOND p ))
ce qui nous permet de donner peut-être la version la plus transparente de la fonction prédécesseur :
PRED := λ n .FIRST ( n (Ψ SUCC) (PAIR 0 0))
= λ nfx .PREMIER ( n (Ψ f ) (PAIRE xx ))
En substituant les définitions et en simplifiant l'expression résultante, on obtient des définitions simplifiées.
= λ nfx . n (λ rab . rb ( fb )) (λ ab . a ) xx
= λ nfx . n (λ rij . j ( rjf )) (λ ij . x ) II
= λ nfx . n (λ rij . i ( rjj )) (λ ij . x ) Je f
= λ nfx . n (λ ri . je ( rf )) (λ je . x ) je
(où I := λ x . x ), ce qui ramène évidemment à l'original.
Techniques de programmation supplémentaires
Il existe un corpus considérable d' idiomes de programmation pour le lambda-calcul. Nombre d'entre eux ont été initialement développés dans le contexte de l'utilisation du lambda-calcul comme fondement de la sémantique des langages de programmation , l'employant ainsi comme un langage de bas niveau . Étant donné que plusieurs langages de programmation intègrent le lambda-calcul (ou une notion très similaire) sous forme de fragment, ces techniques sont également utilisées en programmation pratique, mais peuvent alors être perçues comme obscures ou étrangères.
Constantes nommées
En lambda-calcul, une bibliothèque prendrait la forme d'une collection de fonctions prédéfinies, qui, en tant que lambda-termes, ne sont que des constantes particulières. Le lambda-calcul pur ne possède pas de concept de constantes nommées puisque tous les lambda-termes atomiques sont des variables, mais on peut simuler des constantes nommées en réservant une variable pour nommer la constante, en utilisant l'abstraction pour lier cette variable au corps principal, et en appliquant cette abstraction à la définition souhaitée. Ainsi, pour utiliser f pour désigner N (un lambda-terme explicite) dans M (un autre lambda-terme, le « programme principal »), on peut dire :
(λ f . M ) N
Les auteurs introduisent souvent des raccourcis syntaxiques , tels que let , pour permettre d'écrire ce qui précède dans un ordre plus intuitif
soit f = N dans M
En enchaînant de telles définitions, on peut écrire un « programme » de calcul lambda sous la forme de zéro ou plusieurs définitions de fonctions, suivies d'un lambda-terme utilisant ces fonctions qui constitue le corps principal du programme.
Une restriction notable de cette instruction `let` est que le nom `f` ne peut être référencé dans `N` , car `N` est hors de la portée de l'abstraction `f` , qui est `M` ; cela signifie qu'une définition de fonction récursive ne peut pas être écrite avec `let` . La construction `letrec permettrait d'écrire des définitions de fonctions récursives, où la portée de l'abstraction `f` inclut à la fois `N` et `M` . On pourrait également utiliser une auto-application, à l'instar de celle qui conduit au combinateur `Y` .
Récursivité et points fixes
La récursivité se produit lorsqu'une fonction s'appelle elle-même. Quelle valeur représenterait une telle fonction ? Elle devrait se référencer elle-même d'une manière ou d'une autre, tout comme sa définition se référence elle-même. Si cette valeur se contenait elle-même par valeur, elle serait de taille infinie, ce qui est impossible. D'autres notations, qui prennent en charge la récursivité nativement, contournent ce problème en référençant la fonction par son nom dans sa définition. Le lambda-calcul ne peut pas exprimer cela, car il n'y a pas de noms pour les termes, seulement des noms d'arguments, c'est-à-dire des paramètres dans les abstractions. Ainsi, une expression lambda peut se recevoir elle-même comme argument et se référencer à (une copie de) cette même fonction via le nom du paramètre correspondant. Cela fonctionnera correctement si la fonction est effectivement appelée avec elle-même comme argument. Par exemple, ` (λ x . x x ) E = ( EE )` exprimera la récursivité lorsque `E` est une abstraction qui applique son paramètre à elle-même dans son corps pour exprimer un appel récursif. Puisque ce paramètre reçoit `E` comme valeur, son auto-application sera à nouveau ` ( EE )` .
À titre d'exemple concret, considérons la fonction factorielle F( n ) , définie récursivement par
F( n ) = 1, si n = 0; sinon n × F( n − 1) .
Dans l'expression lambda représentant cette fonction, un paramètre (généralement le premier) est censé recevoir l'expression lambda elle-même comme valeur. Ainsi, l'appeler avec elle-même comme premier argument équivaut à un appel récursif. Par conséquent, pour obtenir la récursivité, l'argument faisant référence à lui-même (appelé ici `s` , rappelant « self » ou « auto-application ») doit toujours être passé à lui-même dans le corps de la fonction lors d'un appel récursif.
E := λ s . λ n .(1, si n = 0; sinon n × ( s s ( n −1)))
avec ssn = F n = EE n à tenir, donc s = E et
F := (λ x . x x ) E = EE
et nous avons
F = EE = λ n .(1, si n = 0; sinon n × (EE ( n −1)))
Ici, ss devient identique (EE) à l'intérieur du résultat de l'application (EE) , et l'utilisation de la même fonction pour un appel est la définition même de la récursivité. L'auto-application réalise ici la réplication, en transmettant l'expression lambda de la fonction à l'invocation suivante comme valeur d'argument, la rendant disponible pour y être référencée par le nom de paramètre s afin d'être appelée via l'auto-application s s , encore et encore autant de fois que nécessaire, recréant à chaque fois le terme lambda F = EE .
L'application constitue une étape supplémentaire, tout comme la recherche de nom. Elle produit le même effet de délai. Au lieu d'avoir F entièrement contenue en elle-même dès le départ , le fait de différer sa recréation jusqu'au prochain appel rend son existence possible grâce à deux lambda-termes finis E qui la recréent à la volée ultérieurement, selon les besoins.
Cette approche auto-applicative résout le problème, mais nécessite de réécrire chaque appel récursif comme une auto-application. Nous souhaiterions une solution générique, sans aucune réécriture.
G := λ r . λ n .(1, si n = 0; sinon n × ( r ( n −1)))
avec r x = F x = G r x à tenir, donc r = G r =: FIX G et
F := FIX G où FIX g = ( r où r = g r ) = g (FIX g )
de sorte que FIX G = G (FIX G) = (λ n .(1, si n = 0; sinon n × ((FIX G) ( n −1))))
Étant donné une expression lambda dont le premier argument représente un appel récursif (ici, G ), le combinateur à point fixe FIX renvoie une expression lambda autoréplicative représentant la fonction récursive (ici, F ). Il n'est jamais nécessaire de passer explicitement la fonction à elle-même, car l'autoréplication est effectuée dès sa création, à chaque appel. Ainsi, l'expression lambda originale (FIX G) est recréée à l'intérieur d'elle-même au point d'appel, réalisant ainsi une autoréférence .
En fait, il existe de nombreuses définitions possibles pour cet opérateur FIX , la plus simple étant :
:= λ g .(λ x . g ( x x )) (λ x . g ( x x ))
Dans le lambda-calcul, Y g est un point fixe de g , car il se développe en :
Y g
(λ''h''.(λ''x''.''h'' (''x'' ''x'')) (λ''x''.''h'' (''x'' ''x''))) ''g''"}},"i":0}}] ~> (λ h .(λ x . h ( x x )) (λ x . h ( x x ))) g
(λ''x''.''g'' (''x'' ''x'')) (λ''x''.''g'' (''x'' ''x''))"}},"i":0}}] ~> (λ x . g ( x x )) (λ x . g ( x x ))
''g'' ((λ''x''.''g'' (''x'' ''x'')) (λ''x''.''g'' (''x'' ''x'')))"}},"i":0}}] ~> g ((λ x . g ( x x )) (λ x . g ( x x )))
<~ g ( Y g )
Pour effectuer l'appel récursif à la fonction factorielle pour un argument n , il suffit d'appeler ( Y G) n . Par exemple, pour n = 4, on obtient :
Toute fonction définie récursivement peut être vue comme un point fixe d'une fonction d'ordre supérieur (également appelée fonctionnelle) convenablement définie, qui effectue l'appel récursif avec un argument supplémentaire. Par conséquent, grâce à Y , toute fonction récursive peut être exprimée comme une expression lambda. En particulier, nous pouvons désormais définir clairement les prédicats de soustraction, de multiplication et de comparaison des nombres naturels, en utilisant la récursivité.
Lorsque le combinateur Y est codé directement dans un langage de programmation strict , l'ordre d'évaluation applicatif utilisé dans ces langages entraînera une tentative d'extension complète de l'auto-application interne.
Termes standard
Certains termes ont des noms communément acceptés :
:= λ x . x
:= λ x .λ y .λ z . x z ( y z )
:= λ x .λ y . x
:= λ x .λ y .λ z . x ( yz )
:= λ x .λ y .λ z . x z y
:= λ x .λ y . x y y
:= λ x . x x
:= ω ω
I est la fonction identité. SK et BCKW forment des systèmes de calcul combinatoire completscapables d'exprimer n'importe quel terme lambda (voir la section suivante) . Ω est UU , le plus petit terme sans forme normale. YI est un autre exemple de ce type de terme. Y est la fonction standard définie précédemment et peut également être définie comme Y = BU(CBU) , de sorte que Y <sub>g</sub> = g( Y<sub> g </sub>) . Les variables VRAI et FAUX définies précédemment sont généralement abrégées en V et F.
Élimination de l'abstraction
) , alors il existe un lambda-terme T ( x , N ) équivalent à λx.N mais dépourvu d'abstraction (sauf dans les constantes nommées, si celles-ci sont considérées comme non atomiques). On peut également voir cela comme une anonymisation des variables, car T ( x , N ) supprime toutes les occurrences de x dans N , tout en autorisant la substitution de valeurs d'arguments aux positions où N contient un x . La fonction de conversion T peut être définie par :
T ( x , x ) := I
T ( x , N ) := K N si x n'est pas libre dans N .
T ( x , M N ) := S T ( x , M ) T ( x , N )
Dans les deux cas, un terme de la forme T ( x , N ) P est réduit en faisant en sorte que le combinateur initial I, K ou S récupère l'argument P, tout comme le ferait la β-réduction de (λx.N) P . I renvoie cet argument . KN ignore l' argument , tout comme le fait ( λx.N ) lorsque x n'a pas d'occurrence libre dans N. S transmet l' argument aux deux sous - termes de l' application , puis applique le résultat du premier au résultat du second, tout comme ( λx.MN ) P est identique à ( ( λx.M ) P ) ( ( λx.N ) P ) .
Les combinateurs B et C sont similaires à S , mais ne transmettent l'argument qu'à un seul sous-terme d'une application ( B au sous-terme « argument » et C au sous-terme « fonction »), évitant ainsi un appel ultérieur à K si x n'apparaît pas dans l'un des sous-termes. Contrairement à B et C , le combinateur S combine deux fonctionnalités : le réarrangement des arguments et la duplication d'un argument pour qu'il puisse être utilisé à deux endroits. Le combinateur W effectue uniquement cette dernière opération, ce qui donne le système B, C, K, W comme alternative au calcul combinatoire SKI .
lambda-calcul typé
) pour désigner l'abstraction de fonctions anonymes. Dans ce contexte, les types sont généralement des objets de nature syntaxique associés à des termes lambda ; la nature exacte d'un type dépend du calcul considéré (voir Types de lambda-calculs typés ). D'un certain point de vue, les lambda-calculs typés peuvent être vus comme des raffinements du lambda-calcul non typé, mais d'un autre point de vue, ils peuvent également être considérés comme la théorie plus fondamentale et le lambda-calcul non typé comme un cas particulier ne possédant qu'un seul type.
Les lambda-calculs typés sont des langages de programmation fondamentaux et constituent la base des langages de programmation fonctionnelle typés tels que ML et Haskell et, plus indirectement, des langages de programmation impératifs typés . Les lambda-calculs typés jouent un rôle important dans la conception des systèmes de types des langages de programmation ; la typabilité y capture généralement les propriétés souhaitables du programme, par exemple, l’absence de violation d’accès mémoire.
est réduit à lui-même par l'ordre applicatif, tandis que l'ordre normal le réduit à sa forme bêta-normale
Les stratégies de partage permettent de réduire les calculs « identiques » effectués en parallèle :
Réduction optimale
Comme d'habitude, mais les calculs qui ont la même étiquette sont réduits simultanément.
Appeler par besoin
L'appel se fait par son nom (donc par une valeur faible), mais les applications de fonction qui dupliqueraient des termes nomment plutôt l'argument. L'argument peut être évalué « au besoin », auquel cas la liaison de nom est mise à jour avec la valeur réduite. Cela permet de gagner du temps par rapport à une évaluation dans l'ordre normal.
calculabilité
Il n'existe aucun algorithme qui prenne en entrée deux expressions lambda quelconques et produise VRAI ou FAUX selon que l'une se réduit ou non à l'autre. Plus précisément, aucune fonction calculable ne peut trancher cette question. Historiquement, il s'agissait du premier problème pour lequel l'indécidabilité a pu être démontrée. Comme d'usage dans ce type de démonstration, « calculable » signifie calculable par tout modèle de calcul Turing -complet . En fait, la calculabilité peut être définie par le lambda-calcul : une fonction F : N → N de nombres naturels est calculable si et seulement s'il existe une expression lambda f telle que, pour toute paire x , y ∈ N , F ( x ) = y si et seulement si f<sub> x </sub> = β<sub> y</sub> , où x et y sont les nombres de Church correspondant respectivement à x et y , et β signifie l'équivalence avec la β-réduction. Voir la thèse de Church-Turing pour d'autres approches de la définition de la calculabilité et de leur équivalence.
La démonstration de l'incalculabilité de Church ramène d'abord le problème à déterminer si une expression lambda donnée possède une forme normale . Il suppose ensuite que ce prédicat est calculable et peut donc être exprimé dans le lambda-calcul. S'appuyant sur des travaux antérieurs de Kleene et construisant une numérotation de Gödel pour les expressions lambda, il construit une expression lambda e qui suit de près la démonstration du premier théorème d'incomplétude de Gödel . Si e est appliquée à son propre numéro de Gödel, on obtient une contradiction.
Complexité
La notion de complexité algorithmique pour le lambda-calcul est complexe, car le coût d'une β-réduction peut varier selon son implémentation. Plus précisément, il faut soit localiser toutes les occurrences de la variable liée V dans l'expression E , ce qui implique un coût temporel, soit conserver une trace des positions des variables libres, ce qui implique un coût spatial. Une recherche naïve des positions de V dans E est de complexité O ( n ) pour la longueur n de E. Les chaînes de directeurs ont constitué une des premières approches, privilégiant une complexité spatiale quadratique au détriment du temps de calcul. Plus généralement , cela a conduit à l'étude de systèmes utilisant la substitution explicite .
En 2014, il a été démontré que le nombre d'étapes de β-réduction nécessaires à la réduction d'un terme par une méthode de réduction d'ordre normal constitue un modèle de coût temporel raisonnable ; autrement dit, la réduction peut être simulée sur une machine de Turing en un temps polynomialement proportionnel au nombre d'étapes. Ce problème, longtemps resté ouvert, était dû à l'explosion de taille , c'est-à-dire à l'existence de termes lambda dont la taille croît exponentiellement à chaque β-réduction. Le résultat contourne ce problème en utilisant une représentation partagée compacte. Il met en évidence que l'espace mémoire nécessaire à l'évaluation d'un terme lambda n'est pas proportionnel à la taille du terme lors de la réduction. On ignore actuellement quelle mesure appropriée de la complexité spatiale serait pertinente.
Un modèle déraisonnable n'implique pas nécessairement une inefficacité. La réduction optimale regroupe tous les calculs portant le même nom en une seule étape, évitant ainsi les doublons. Cependant, le nombre d'étapes de β-réduction parallèles nécessaires pour ramener un terme donné à sa forme normale est approximativement linéaire par rapport à la taille du terme. Cette relation est bien trop faible pour constituer une mesure de coût pertinente, car toute machine de Turing peut être encodée dans le lambda-calcul avec une taille linéairement proportionnelle à celle de la machine de Turing. Le coût réel de la réduction des termes lambda ne provient pas de la β-réduction en elle-même, mais plutôt de la gestion de la duplication des redexes lors de cette réduction. On ignore si les implémentations de réduction optimale sont pertinentes au regard d'un modèle de coût raisonnable, tel que le nombre d'étapes de réduction de la forme normale par la méthode du plus à gauche et du plus externe. Toutefois, il a été démontré, pour des fragments du lambda-calcul, que l'algorithme de réduction optimale est efficace et présente un surcoût au plus quadratique par rapport à la méthode du plus à gauche et du plus externe. De plus, l'implémentation prototype BOHM de la réduction optimale a surpassé Caml Light et Haskell sur les termes lambda purs.
Lambda-calcul et langages de programmation
Comme le souligne l'article de Peter Landin de 1965 intitulé « Une correspondance entre ALGOL 60 et la notation lambda de Church », les langages de programmation procéduraux séquentiels peuvent être compris en termes de lambda-calcul, qui fournit les mécanismes de base pour l'abstraction procédurale et l'application de procédures (sous-programmes).
Fonctions anonymes
( lambda x : x ** 2 )
L'exemple ci-dessus est une expression qui s'évalue en une fonction de première classe. Le symbole `lambda` lambdacrée une fonction anonyme, à partir d'une liste de noms de paramètres ( xici, un seul argument) et d'une expression qui est évaluée comme le corps de la fonction x**2. Les fonctions anonymes sont parfois appelées expressions lambda.
La propriété de Church-Rosser du lambda-calcul implique que l'évaluation (β-réduction) peut être effectuée dans n'importe quel ordre , même en parallèle. De ce fait, diverses stratégies d'évaluation non déterministes sont pertinentes. Cependant, le lambda-calcul ne propose aucune construction explicite pour le parallélisme . On peut y ajouter des constructions telles que les futures . D'autres calculs de processus ont été développés pour décrire la communication et la concurrence.
Sémantique
Le fait que les termes du lambda-calcul agissent comme des fonctions sur d'autres termes du lambda-calcul, voire sur eux-mêmes, a soulevé des questions quant à la sémantique de ce dernier. Peut-on attribuer une signification cohérente aux termes du lambda-calcul ? La sémantique naturelle consiste à trouver un ensemble D isomorphe à l'espace fonctionnel D → D , constitué des fonctions sur lui-même. Cependant, un tel ensemble D non trivial ne peut exister, du fait des contraintes de cardinalité , car l'ensemble de toutes les fonctions de D vers D a une cardinalité supérieure à celle de D , à moins que D ne soit un singleton .
Dans les années 1970, Dana Scott a montré que si l' on ne considérait que les fonctions continues , on pouvait trouver un ensemble ou domaine D possédant la propriété requise, fournissant ainsi un modèle pour le lambda-calcul.
Ce travail a également constitué la base de la sémantique dénotationnelle des langages de programmation.
Système F – Un lambda-calcul typé avec des variables de type
Calcul des constructions – Un lambda-calcul typé avec des types comme valeurs de première classe
Ces systèmes formels sont des extensions du lambda-calcul qui ne font pas partie du lambda-cube :
Lambda-calcul binaire – Une version du lambda-calcul avec des entrées/sorties binaires (E/S), un encodage binaire des termes et une machine universelle désignée.
Calcul combinatoire SKI – Un système de calcul basé sur les combinateurs S , K et I , équivalent au lambda-calcul, mais réductible sans substitution de variables.
Worldlex Wiki 
où les variables parcourent un ensemble infini de noms. Les termes parcourent tous les lambda-termes. Ceci correspond à la 
où est la variable de paramètre de l'abstraction ,
où sont des termes lambda.
" utilisé pour l'abstraction de classe par 
) pour désigner l'abstraction de fonctions anonymes. Dans ce contexte, les types sont généralement des objets de nature syntaxique associés à des termes lambda ; la nature exacte d'un type dépend du calcul considéré (voir 
est réduit à lui-même par l'ordre applicatif, tandis que l'ordre normal le réduit à sa forme bêta-normale