Calcul lambda

Le calcul lambda (également écrit λ -calcul ) est un système formel en logique mathématique pour exprimer le calcul basé sur l’ abstraction et l’ application de fonctions utilisant la liaison et la substitution de variables . C’est un modèle de calcul universel qui peut être utilisé pour simuler n’importe quelle machine de Turing . Il a été introduit par le mathématicien Alonzo Church dans les années 1930 dans le cadre de ses recherches sur les fondements des mathématiques .

Le calcul lambda consiste à construire des termes lambda et à effectuer des opérations de réduction sur ceux-ci. Dans la forme la plus simple du calcul lambda, les termes sont construits en utilisant uniquement les règles suivantes :

Syntaxe	Nom	La description
X	Variable	Caractère ou chaîne représentant un paramètre ou une valeur mathématique/logique.
(λ x . M )	Abstraction	Définition de la fonction ( M est un terme lambda). La variable x devient liée dans l’expression.
( M N )	Application	Application d’une fonction à un argument. M et N sont des termes lambda.

produisant des expressions telles que : (λ x .λ y .(λ z .(λ x . zx ) (λ y . zy )) ( xy )). Les parenthèses peuvent être supprimées si l’expression n’est pas ambiguë. Pour certaines applications, des termes pour les constantes et les opérations logiques et mathématiques peuvent être inclus.

Les opérations de réduction comprennent :

Opération	Nom	La description
(λ x . M [ x ]) → (λ y . M [ y ])	conversion α	Renommer les variables liées dans l’expression. Utilisé pour éviter les collisions de noms .
((λ x . M ) E ) → ( M [ x := E ])	β-réduction	Remplacement des variables liées par l’expression d’argument dans le corps de l’abstraction.

Si l’indexation De Bruijn est utilisée, la conversion α n’est plus nécessaire car il n’y aura pas de collisions de noms. Si l’application répétée des étapes de réduction se termine finalement, alors par le théorème de Church-Rosser, cela produira une forme β-normale .

Les noms de variables ne sont pas nécessaires si vous utilisez une fonction lambda universelle, telle que Iota et Jot , qui peut créer n’importe quel comportement de fonction en l’appelant sur elle-même dans diverses combinaisons.

Explication et applications

Le calcul lambda est Turing complet , c’est-à-dire qu’il s’agit d’un modèle de calcul universel qui peut être utilisé pour simuler n’importe quelle machine de Turing . ^[1] 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 .

Le calcul lambda peut être non typé ou typé . Dans le calcul lambda typé, les fonctions ne peuvent être appliquées que si elles sont capables d’accepter le “type” de données de l’entrée donnée. Les calculs lambda typés sont plus faibles que les calculs lambda non typés, qui sont le sujet principal de cet article, dans le sens où les calculs lambda typés peuvent exprimer moins que les calculs non typés, mais d’un autre côté les calculs lambda typés permettent de prouver plus de choses. ; dans le calcul lambda simplement typéc’est, par exemple, un théorème selon lequel chaque stratégie d’évaluation se termine pour chaque terme lambda simplement typé, alors que l’évaluation des termes lambda non typés n’a pas besoin de se terminer. L’une des raisons pour lesquelles il existe de nombreux calculs lambda typés différents est le désir de faire plus (de ce que le calcul non typé peut faire) sans renoncer à pouvoir prouver des théorèmes solides sur le calcul.

Le calcul lambda a des applications dans de nombreux domaines différents en mathématiques , philosophie , ^[2] linguistique , ^{[3] [4]} et informatique . ^[5] Le calcul lambda a joué un rôle important dans le développement de la théorie des langages de programmation . Les langages de programmation fonctionnelle implémentent le calcul lambda. Le calcul lambda est également un sujet de recherche actuel en théorie des catégories . ^[6]

Histoire

Le calcul lambda a été introduit par le mathématicien Alonzo Church dans les années 1930 dans le cadre d’une enquête sur les fondements des mathématiques . ^{[7] [a]} Le système original s’est avéré logiquement incohérent en 1935 lorsque Stephen Kleene et JB Rosser ont développé le paradoxe Kleene-Rosser . ^{[8] [9]}

Par la suite, en 1936, Church a isolé et publié uniquement la partie relative au calcul, ce que l’on appelle maintenant le calcul lambda non typé. ^[10] En 1940, il a également introduit un système informatiquement plus faible, mais logiquement cohérent, connu sous le nom de calcul lambda simplement typé . ^[11]

Jusqu’aux années 1960, lorsque sa relation avec les langages de programmation a été clarifiée, le calcul lambda n’était qu’un formalisme. Grâce aux applications de Richard Montague et d’autres linguistes dans la sémantique du langage naturel, le calcul lambda a commencé à jouir d’une place respectable à la fois en linguistique ^[12] et en informatique. ^[13]

Origine du symbole lambda

Il existe une certaine incertitude quant à la raison de l’utilisation par Church de la lettre grecque lambda (λ) comme notation pour l’abstraction de fonction dans le calcul lambda, peut-être en partie en raison d’explications contradictoires de Church lui-même. Selon Cardone et Hindley (2006) :

Au fait, pourquoi Church a-t-il choisi la notation « λ » ? Dans [une lettre non publiée de 1964 à Harald Dickson], il a clairement déclaré que cela venait de la notation « x ^ {displaystyle {hat {x}}} ” utilisé pour l’abstraction de classe par Whitehead et Russell , en modifiant d’abord “ x ^ {displaystyle {hat {x}}} ” pour ” ∧ x {displaystyle terre x} ” pour distinguer l’abstraction de fonction de l’abstraction de classe, puis en changeant ” ∧ {displaystyle terre} ” à “λ” pour faciliter l’impression.

Cette origine a également été rapportée dans [Rosser, 1984, p.338]. D’un autre côté, dans ses dernières années, Church a dit à deux enquêteurs que le choix était plus accidentel : un symbole était nécessaire et λ s’est avéré être choisi.

Dana Scott a également abordé cette question dans diverses conférences publiques. ^[14] Scott raconte qu’il a posé une fois une question sur l’origine du symbole lambda à l’ancien élève et gendre de Church, John W. Addison Jr., qui a ensuite écrit une carte postale à son beau-père :

Cher professeur Church,

Russell avait l’ Opérateur Iota , Hilbert avait l’ Opérateur Epsilon . Pourquoi avez-vous choisi lambda comme opérateur ?

Selon Scott, toute la réponse de Church consistait à renvoyer la carte postale avec l’annotation suivante : « eeny, meeny, miny, moe ».

Description informelle

Apprendre encore plus Cette section comprend une liste de références , de lectures connexes ou de liens externes , mais ses sources restent floues car elle manque de citations en ligne . ( septembre 2013 ) Please help to improve this section by introducing more precise citations. (Learn how and when to remove this template message)

Motivation

Les fonctions calculables sont un concept fondamental en informatique et en mathématiques. Le calcul lambda fournit une sémantique simple pour le calcul, permettant d’étudier formellement les propriétés du calcul. Le calcul lambda incorpore deux simplifications qui rendent cette sémantique simple. La première simplification est que le calcul lambda traite les fonctions “de manière anonyme”, sans leur donner de noms explicites. Par exemple, la fonction

s q u a r e _ s u m ⁡ ( x , y ) = x 2 + y 2 {displaystyle operatorname {carré_sum} (x,y)=x^{2}+y^{2}} ${displaystyle operatorname {square_sum} (x,y)=x^{2}+y^{2}}$ ${displaystyle operatorname {carré_sum} (x,y)=x^{2}+y^{2}}$

peut être réécrit sous forme anonyme comme

( x , y ) ↦ x 2 + y 2 {displaystyle (x,y)mapsto x^{2}+y^{2}} ${displaystyle (x,y)mapsto x^{2}+y^{2}}$

(qui se lit comme “un tuple de x et y est mappé sur x 2 + y 2 {textstyle x^{2}+y^{2}} ${textstyle x^{2}+y^{2}}$ “). De même, la fonction

id ⁡ ( x ) = x {displaystyle operatorname {id} (x)=x}

peut être réécrit sous forme anonyme comme

x ↦ x {displaystyle xmapsto x} x mapsto x

où l’entrée est simplement mappée sur elle-même.

La deuxième simplification est que le calcul lambda n’utilise que des fonctions d’une seule entrée. Une fonction ordinaire qui nécessite deux entrées, par exemple le s q u a r e _ s u m {textstyle operatorname {carré_sum} } ${textstyle operatorname {square_sum} }$ ${textstyle operatorname {carré_sum} }$ fonction, peut être retravaillée en une fonction équivalente qui accepte une seule entrée, et en tant que sortie renvoie une autre fonction, qui à son tour accepte une seule entrée. Par example,

( x , y ) ↦ x 2 + y 2 {displaystyle (x,y)mapsto x^{2}+y^{2}} ${displaystyle (x,y)mapsto x^{2}+y^{2}}$ ${displaystyle (x,y)mapsto x^{2}+y^{2}}$

peut être retravaillé en

x ↦ ( y ↦ x 2 + y 2 ) {displaystyle xmapsto (ymapsto x^{2}+y^{2})} ${displaystyle xmapsto (ymapsto x^{2}+y^{2})}$ ${displaystyle xmapsto (ymapsto x^{2}+y^{2})}$

Cette méthode, connue sous le nom de currying , transforme une fonction qui prend plusieurs arguments en une chaîne de fonctions chacune avec un seul argument.

Application de la fonction de la s q u a r e _ s u m {textstyle operatorname {carré_sum} } ${textstyle operatorname {square_sum} }$ ${textstyle operatorname {carré_sum} }$ fonction aux arguments (5, 2), donne immédiatement

( ( x , y ) ↦ x 2 + y 2 ) ( 5 , 2 ) {textstyle ((x,y)mapsto x^{2}+y^{2})(5,2)} ${textstyle ((x,y)mapsto x^{2}+y^{2})(5,2)}$ ${textstyle ((x,y)mapsto x^{2}+y^{2})(5,2)}$ = 5 2 + 2 2 {textstyle =5^{2}+2^{2}} ${textstyle =5^{2}+2^{2}}$ ${textstyle =5^{2}+2^{2}}$ = 29 {textstyle =29} ,

alors que l’évaluation de la version au curry nécessite une étape de plus

( ( x ↦ ( y ↦ x 2 + y 2 ) ) ( 5 ) ) ( 2 ) {textstyle {Bigl (}{bigl (}xmapsto (ymapsto x^{2}+y^{2}){bigr )}(5){Bigr )}(2)} ${textstyle {Bigl (}{bigl (}xmapsto (ymapsto x^{2}+y^{2}){bigr )}(5){Bigr )}(2)}$ ${textstyle {Bigl (}{bigl (}xmapsto (ymapsto x^{2}+y^{2}){bigr )}(5){Bigr )}(2)}$ = ( y ↦ 5 2 + y 2 ) ( 2 ) {textstyle =(ymapsto 5^{2}+y^{2})(2)} ${textstyle =(ymapsto 5^{2}+y^{2})(2)}$ ${textstyle =(ymapsto 5^{2}+y^{2})(2)}$ // la définition de x {style d’affichage x} a été utilisé avec 5 {displaystyle 5} dans l’expression intérieure. C’est comme la β-réduction. = 5 2 + 2 2 {textstyle =5^{2}+2^{2}} ${textstyle =5^{2}+2^{2}}$ ${textstyle =5^{2}+2^{2}}$ // la définition de y {displaystyle y} a été utilisé avec 2 {displaystyle 2} . Encore une fois, similaire à la β-réduction. = 29 {textstyle =29}

pour arriver au même résultat.

Le calcul lambda

Le calcul lambda consiste en un langage de termes lambda , qui sont définis par une certaine syntaxe formelle, et un ensemble de règles de transformation, qui permettent la manipulation des termes lambda. Ces règles de transformation peuvent être considérées comme une Théorie équationnelle ou comme une définition opérationnelle .

Comme décrit ci-dessus, toutes les fonctions du calcul lambda sont des fonctions anonymes, sans nom. Ils n’acceptent qu’une seule variable d’entrée, le curry étant utilisé pour implémenter des fonctions à plusieurs variables.

Termes lambda

La syntaxe du calcul lambda définit certaines expressions comme des expressions de calcul lambda valides et d’autres comme invalides, tout comme certaines chaînes de caractères sont des programmes C valides et d’autres non. Une expression de calcul lambda valide est appelée un “terme lambda”.

Les trois règles suivantes donnent une Définition inductive qui peut être appliquée pour construire tous les termes lambda syntaxiquement valides :

une variable, x , est elle-même un terme lambda valide
si t est un terme lambda et x est une variable, alors ( λ x . t ) {displaystyle (lambda xt)} (parfois écrit en ASCII comme L x . t {displaystyle Lx.t} ) est un terme lambda (appelé une abstraction );
si t et s sont des termes lambda, alors ( t s ) {displaystyle (ts)} est un terme lambda (appelé une application ).

Rien d’autre n’est un terme lambda. Ainsi un terme lambda est valide si et seulement s’il peut être obtenu par application répétée de ces trois règles. Cependant, certaines parenthèses peuvent être omises selon certaines règles. Par exemple, les parenthèses les plus externes ne sont généralement pas écrites. Voir Notation , ci-dessous.

Une abstraction λ x . t { style d’affichage lambda xt} lambda x.t est une définition d’une fonction anonyme capable de prendre une seule entrée x et de la substituer dans l’expression t . Il définit ainsi une fonction anonyme qui prend x et retourne t . Par example, λ x . x 2 + 2 {displaystylelambda xx^{2}+2} $lambda x.x^{2}+2$ $lambda xx^{2}+2$ est une abstraction de la fonction f ( x ) = x 2 + 2 {displaystyle f(x)=x^{2}+2} $f(x)=x^{2}+2$ $f(x)=x^{2}+2$ en utilisant le terme x 2 + 2 {displaystyle x^{2}+2} $x^{2}+2$ $x^{2}+2$ pour t . La définition d’une fonction avec une abstraction “établit” simplement la fonction mais ne l’invoque pas. L’abstraction lie la variable x dans le terme t .

Une application ts représente l’application d’une fonction t à une entrée s , c’est-à-dire qu’elle représente l’acte d’appeler la fonction t sur l’entrée s pour produire t ( s ) {displaystyle t(s)} t(s) .

Il n’y a pas de concept dans le calcul lambda de déclaration de variable. Dans une définition telle que λ x . x + y {displaystylelambda x.x+y} (c’est à dire f ( x ) = x + y {displaystyle f(x)=x+y} ), le calcul lambda traite y comme une variable qui n’est pas encore définie. L’abstraction λ x . x + y {displaystylelambda x.x+y} est syntaxiquement valide et représente une fonction qui ajoute son entrée au y encore inconnu .

Les crochets peuvent être utilisés et peuvent être nécessaires pour lever l’ambiguïté des termes. Par example, λ x . ( ( λ x . x ) x ) { displaystyle lambda x. (( lambda xx) x)} lambda x.((lambda x.x)x) et ( λ x . ( λ x . x ) ) x {displaystyle (lambda x.(lambda xx))x} (lambda x.(lambda x.x))x désignent des termes différents (bien qu’ils se réduisent par coïncidence à la même valeur). Ici, le premier exemple définit une fonction dont le terme lambda est le résultat de l’application de x à la fonction enfant, tandis que le deuxième exemple est l’application de la fonction la plus externe à l’entrée x, qui renvoie la fonction enfant. Par conséquent, les deux exemples évaluent la fonction d’identité λ x . x { style d’affichage lambda xx} lambda x.x .

Fonctions qui opèrent sur des fonctions

Dans le calcul lambda, les fonctions sont considérées comme des ” valeurs de première classe “, de sorte que les fonctions peuvent être utilisées comme entrées ou renvoyées comme sorties d’autres fonctions.

Par example, λ x . x { style d’affichage lambda xx} lambda x.x représente la fonction identité , x ↦ x {displaystyle xmapsto x} x mapsto x , et ( λ x . x ) y {displaystyle (lambda xx)y} (lambda x.x)y représente la fonction identité appliquée à y {displaystyle y} . Plus loin, ( λ x . y ) {displaystyle (lambda xy)} (lambda x.y) représente la fonction constante x ↦ y {displaystyle xmapsto y} , la fonction qui retourne toujours y {displaystyle y} , peu importe l’entrée. Dans le calcul lambda, l’application de la fonction est considérée comme associative à gauche , de sorte que s t x {displaystyle stx} stx moyens ( s t ) x {displaystyle (st)x} (st)x .

Il existe plusieurs notions d'”équivalence” et de “réduction” qui permettent de “réduire” les termes lambda en termes lambda “équivalents”.

Équivalence alpha

Une forme de base d’équivalence, définissable en termes lambda, est l’équivalence alpha. Il capture l’intuition que le choix particulier d’une variable liée, dans une abstraction, n’a (généralement) pas d’importance. Par exemple, λ x . x { style d’affichage lambda xx} lambda x.x et λ y . y {displaystyle lambda aa} lambda y.y sont des termes lambda équivalents en alpha, et ils représentent tous les deux la même fonction (la fonction d’identité). Les termes x {style d’affichage x} et y {displaystyle y} ne sont pas alpha-équivalents, car ils ne sont pas liés dans une abstraction. Dans de nombreuses présentations, il est courant d’identifier les termes lambda équivalents alpha.

Les définitions suivantes sont nécessaires pour pouvoir définir la β-réduction :

Variables libres

(les variables libres dans la notation lambda et son calcul sont comparables à l’algèbre linéaire et aux concepts mathématiques du même nom )

Les variables libres d’un terme sont les variables non liées par une abstraction. L’ensemble des variables libres d’une expression est défini de manière inductive :

Les variables libres de x {style d’affichage x} sont justes x {style d’affichage x}
L’ ensemble des variables libres de λ x . t { style d’affichage lambda xt} est l’ensemble des variables libres de t {displaystyle t} , mais avec x {style d’affichage x} supprimé
L’ ensemble des variables libres de t s {displaystyle ts} est la réunion de l’ensemble des variables libres de t {displaystyle t} et l’ensemble des variables libres de s {displaystyle s} .

Par exemple, le terme lambda représentant l’identité λ x . x { style d’affichage lambda xx} lambda x.x n’a pas de variables libres, mais la fonction λ x . y x {displaystylelambda x.yx} {displaystyle lambda x.yx} a une seule variable libre, y {displaystyle y} .

Remplacements évitant la capture

Un changement systématique de variables pour éviter la capture d’une variable libre peut introduire une erreur , dans un Langage de programmation fonctionnel où les fonctions sont des citoyens de première classe. ^[15]

Supposer t {displaystyle t} , s {displaystyle s} et r {displaystyle r} sont des termes lambda et x {style d’affichage x} et y {displaystyle y} sont variables. La notation t [ x := r ] {displaystyle t[x:=r]} t[x:=r] indique la substitution de r {displaystyle r} pour x {style d’affichage x} dans t {displaystyle t} d’une manière évitant la capture . Celui-ci est défini de sorte que :

x [ x := r ] = r {displaystyle x[x:=r]=r} ; x {style d’affichage x} remplacé par r {displaystyle r} est juste r {displaystyle r}
y [ x := r ] = y {displaystyle y[x:=r]=y} si x ≠ y {displaystyle xneq y} ; x {style d’affichage x} remplacé par r {displaystyle r} lorsqu’il s’agit de y {displaystyle y} est juste y {displaystyle y}
( t s ) [ x := r ] = ( t [ x := r ] ) ( s [ x := r ] ) {displaystyle (ts)[x:=r]=(t[x:=r])(s[x:=r])} ; substitution distribue à une application ultérieure de la variable
( λ x . t ) [ x := r ] = λ x . t {displaystyle (lambda xt)[x:=r]=lambda xt} ; même si x {style d’affichage x} a été mappé sur r {displaystyle r} , cartographiant ensuite tous x {style d’affichage x} pour t {displaystyle t} ne changera pas la fonction lambda ( λ x . t ) {displaystyle (lambda xt)}
( λ y . t ) [ x := r ] = λ y . ( t [ x := r ] ) {displaystyle (lambda yt)[x:=r]=lambda y.(t[x:=r])} si x ≠ y {displaystyle xneq y} et y {displaystyle y} n’est pas dans les variables libres de r {displaystyle r} . La variable y {displaystyle y} est dit « frais » pour r {displaystyle r} .

Par example, ( λ x . x ) [ y := y ] = λ x . ( x [ y := y ] ) = λ x . x {displaystyle (lambda xx)[y:=y]=lambda x.(x[y:=y])=lambda xx} (lambda x.x)[y:=y]=lambda x.(x[y:=y])=lambda x.x , et ( ( λ x . y ) x ) [ x := y ] = ( ( λ x . y ) [ x := y ] ) ( x [ x := y ] ) = ( λ x . y ) y {displaystyle ((lambda xy)x)[x:=y]=((lambda xy)[x:=y])(x[x:=y])=(lambda xy)y} ((lambda x.y)x)[x:=y]=((lambda x.y)[x:=y])(x[x:=y])=(lambda x.y)y .

La condition de fraîcheur (nécessitant que y {displaystyle y} n’est pas dans les variables libres de r {displaystyle r} ) est cruciale pour garantir que la substitution ne modifie pas la signification des fonctions. Par exemple, une substitution effectuée qui ignore la condition de fraîcheur peut entraîner des erreurs : ( λ x . y ) [ y := x ] = λ x . ( y [ y := x ] ) = λ x . x {displaystyle (lambda xy)[y:=x]=lambda x.(y[y:=x])=lambda xx} (lambda x.y)[y:=x]=lambda x.(y[y:=x])=lambda x.x . Cette substitution transforme la fonction constante λ x . y { style d’affichage lambda xy} dans l’identité λ x . x { style d’affichage lambda xx} par substitution.

En général, le non-respect de la condition de fraîcheur peut être résolu par un changement de nom alpha avec une variable de fraîcheur appropriée. Par exemple, en revenant à notre notion correcte de substitution, dans ( λ x . y ) [ y := x ] {displaystyle (lambda xy)[y:=x]} (lambda x.y)[y:=x] l’abstraction peut être renommée avec une nouvelle variable z {displaystyle z} , obtenir ( λ z . y ) [ y := x ] = λ z . ( y [ y := x ] ) = λ z . x {displaystyle (lambda zy)[y:=x]=lambda z.(y[y:=x])=lambda zx} (lambda z.y)[y:=x]=lambda z.(y[y:=x])=lambda z.x , et la signification de la fonction est conservée par substitution.

β-réduction

La règle de β-réduction stipule qu’une application de la forme ( λ x . t ) s {displaystyle (lambda xt)s} (lambda x.t)s réduit au terme t [ x := s ] {displaystyle t[x:=s]} t[x:=s] . La notation ( λ x . t ) s → t [ x := s ] {displaystyle (lambda xt)sto t[x:=s]} (lambda x.t)sto t[x:=s] est utilisé pour indiquer que ( λ x . t ) s {displaystyle (lambda xt)s} β-réduit à t [ x := s ] {displaystyle t[x:=s]} t[x:=s] . Par exemple, pour chaque s {displaystyle s} , ( λ x . x ) s → x [ x := s ] = s {displaystyle (lambda xx)sto x[x:=s]=s} (lambda x.x)sto x[x:=s]=s . Cela démontre que λ x . x { style d’affichage lambda xx} est vraiment l’identité. De la même manière, ( λ x . y ) s → y [ x := s ] = y {displaystyle (lambda xy)sto y[x:=s]=y} (lambda x.y)sto y[x:=s]=y , ce qui démontre que λ x . y { style d’affichage lambda xy} est une fonction constante.

Le calcul lambda peut être vu comme une version idéalisée d’un Langage de programmation fonctionnel, comme Haskell ou Standard ML . Selon ce point de vue, la β-réduction correspond à une étape de calcul. Cette étape peut être répétée par des β-réductions supplémentaires jusqu’à ce qu’il ne reste plus d’applications à réduire. Dans le calcul lambda non typé, tel que présenté ici, ce processus de réduction peut ne pas se terminer. Par exemple, considérons le terme Ω = ( λ x . x x ) ( λ x . x x ) {displaystyle Omega =(lambda x.xx)(lambda x.xx)} . Ici ( λ x . x x ) ( λ x . x x ) → ( x x ) [ x := λ x . x x ] = ( x [ x := λ x . x x ] ) ( x [ x := λ x . x x ] ) = ( λ x . x x ) ( λ x . x x ) {displaystyle (lambda x.xx)(lambda x.xx)to (xx)[x:=lambda x.xx]=(x[x:=lambda x.xx])(x[x :=lambda x.xx])=(lambda x.xx)(lambda x.xx)} . Autrement dit, le terme se réduit à lui-même en une seule β-réduction et, par conséquent, le processus de réduction ne se terminera jamais.

Un autre aspect du calcul lambda non typé est qu’il ne fait pas de distinction entre les différents types de données. Par exemple, il peut être souhaitable d’écrire une fonction qui n’opère que sur des nombres. Cependant, dans le calcul lambda non typé, il n’y a aucun moyen d’empêcher l’application d’une fonction à des valeurs de vérité , des chaînes ou d’autres objets non numériques.

Définition formelle

Définition

Les expressions lambda sont composées de :

variables v ₁ , v ₂ , …;
les symboles d’abstraction λ (lambda) et . (point);
parenthèses ().

L’ensemble des expressions lambda, Λ , peut être défini de manière inductive :

Si x est une variable, alors x ∈ Λ.
Si x est une variable et M ∈ Λ, alors (λ x . M ) ∈ Λ.
Si M , N ∈ Λ, alors ( MN ) ∈ Λ.

Les instances de la règle 2 sont appelées abstractions et les instances de la règle 3 sont appelées applications . ^{[16] [17]}

Notation

Pour garder la notation des expressions lambda épurée, les conventions suivantes sont généralement appliquées :

Les parenthèses les plus à l’extérieur sont supprimées : M N au lieu de ( M N ).
Les applications sont supposées être associatives à gauche : M N P peut être écrit à la place de (( M N ) P ). ^[18]
Le corps d’une abstraction s’étend le plus à droite possible : λ x . MN signifie λ x .( MN ) et non (λ x . M ) N .
Une suite d’abstractions est contractée : λ x .λ y .λ z . N est abrégé en λ xyz . N. _ ^{[19] [18]}

Variables libres et liées

On dit que l’opérateur d’abstraction, λ, lie sa variable partout où elle se produit dans le corps de l’abstraction. Les variables qui entrent dans le cadre d’une abstraction sont dites liées . Dans une expression λ x . M , la partie λ x est souvent appelée liant , comme un indice que la variable x est liée en ajoutant λ x à M . Toutes les autres variables sont appelées free . Par exemple, dans l’expression λ y . xxy , y est une variable liée et xest une variable libre. De plus, une variable est liée par son abstraction la plus proche. Dans l’exemple suivant, la seule occurrence de x dans l’expression est liée par le deuxième lambda : λ x . y (λ x . zx ).

L’ensemble des variables libres d’une expression lambda, M , est noté FV( M ) et est défini par récursivité sur la structure des termes, comme suit :

FV( x ) = { x }, où x est une variable.
FV(λ x . M ) = FV( M ) { X }.
FV( MN ) = FV( M ) ∪ FV( N ). ^[20]

Une expression qui ne contient aucune variable libre est dite fermée . Les expressions lambda fermées sont également appelées combinateurs et sont équivalentes aux termes de la logique combinatoire .

Réduction

La signification des expressions lambda est définie par la manière dont les expressions peuvent être réduites. ^[21]

Il existe trois types de réduction :

α-conversion : modification des variables liées ;
β-réduction : application de fonctions à leurs arguments ;
η-réduction : qui capture une notion d’extensionnalité.

On parle aussi des équivalences résultantes : deux expressions sont α-équivalentes , si elles peuvent être α-converties en la même expression. L’équivalence β et l’équivalence η sont définies de manière similaire.

Le terme redex , abréviation de expression réductible , fait référence à des sous-termes qui peuvent être réduits par l’une des règles de réduction. Par exemple, (λ x . M ) N est un β-redex dans l’expression de la substitution de N pour x dans M . L’expression à laquelle se réduit un redex s’appelle son reduct ; le réduit de (λ x . M ) N est M [ x := N ].

Si x n’est pas libre dans M , λ x . M x est aussi un η-redex, avec un réduit de M .

conversion α

L’α-conversion, parfois connue sous le nom d’α-renommage, ^[22] permet de changer les noms des variables liées. Par exemple, la conversion α de λ x . x pourrait donner λ y . y . Les termes qui ne diffèrent que par α-conversion sont appelés α-équivalent . Fréquemment, dans les utilisations du calcul lambda, les termes α-équivalents sont considérés comme équivalents.

Les règles précises pour la conversion α ne sont pas complètement triviales. Premièrement, lors de la conversion α d’une abstraction, les seules occurrences de variables qui sont renommées sont celles qui sont liées à la même abstraction. Par exemple, une α-conversion de λ x .λ x . x pourrait résulter en λ y .λ x . x , mais cela ne pouvait pas donner λ y .λ x . y . Ce dernier a une signification différente de l’original. Ceci est analogue à la notion de programmation de variable shadowing .

Deuxièmement, la conversion α n’est pas possible si elle entraînait la capture d’une variable par une abstraction différente. Par exemple, si nous remplaçons x par y dans λ x .λ y . x , on obtient λ y .λ y . y , ce qui n’est pas du tout pareil.

Dans les langages de programmation à portée statique, la conversion α peut être utilisée pour simplifier la résolution de nom en s’assurant qu’aucun nom de variable ne masque un nom dans une portée contenante (voir α-renommer pour rendre la résolution de nom triviale ).

Dans la notation d’ index De Bruijn , deux termes équivalents α sont syntaxiquement identiques.

Substitution

La substitution, notée M [ V := N ], est le processus de remplacement de toutes les occurrences libres de la variable V dans l’expression M par l’expression N . La substitution sur les termes du calcul lambda est définie par récursivité sur la structure des termes, comme suit (remarque : x et y ne sont que des variables alors que M et N sont n’importe quelle expression lambda) :

x [ x := N ] = N y [ x := N ] = y , si x ≠ y ( M ₁ M ₂ )[ X := N ] = M ₁ [ X := N ] M ₂ [ X := N ] (λ x . M )[ x := N ] = λ x . M (λ y . M )[ x := N ] = λ y .( M [ x := N ]), si x ≠ y et y ∉ FV( N )

Pour substituer dans une abstraction, il est parfois nécessaire de α-convertir l’expression. Par exemple, il n’est pas correct que (λ x . y )[ y := x ] donne λ x . x , car le x substitué était censé être libre mais a fini par être lié. La substitution correcte dans ce cas est λ z . x , jusqu’à l’α-équivalence. La substitution est définie uniquement à α-équivalence près.

β-réduction

La β-réduction capture l’idée d’application de fonction. La β-réduction est définie en termes de substitution : la β-réduction de (λ V . M ) N est M [ V := N ].

Par exemple, en supposant un codage de 2, 7, ×, nous avons la β-réduction suivante : (λ n . n × 2) 7 → 7 × 2.

La β-réduction peut être considérée comme identique au concept de réductibilité locale dans la déduction naturelle , via l ‘ isomorphisme de Curry-Howard .

η-réduction

η-réduction exprime l’idée d’ extensionnalité , qui dans ce contexte est que deux fonctions sont identiques si et seulement si elles donnent le même résultat pour tous les arguments. η-réduction convertit entre λ x . f x et f chaque fois que x n’apparaît pas libre dans f .

La réduction η peut être considérée comme identique au concept de complétude locale dans la déduction naturelle , via l ‘ isomorphisme de Curry-Howard .

Formes normales et confluence

Pour le calcul lambda non typé, la β-réduction en tant que règle de réécriture n’est ni fortement normalisante ni faiblement normalisante .

Cependant, on peut montrer que la β-réduction est confluente lorsqu’on travaille jusqu’à la α-conversion (c’est-à-dire que l’on considère que deux formes normales sont égales s’il est possible de α-convertir l’une dans l’autre).

Par conséquent, les termes fortement normalisants et les termes faiblement normalisants ont une forme normale unique. Pour les termes fortement normalisants, toute stratégie de réduction est garantie de produire la forme normale, alors que pour les termes faiblement normalisants, certaines stratégies de réduction peuvent ne pas la trouver.

Encodage des types de données

Le calcul lambda de base peut être utilisé pour modéliser les booléens, l’arithmétique , les structures de données et la récursivité, comme illustré dans les sous-sections suivantes.

Arithmétique dans le calcul lambda

Il existe plusieurs manières de définir les nombres naturels dans le calcul lambda, mais les plus courantes sont de loin les chiffres d’Église , qui peuvent être définis comme suit :

0 := λ f .λ x . X 1 := λ f .λ x . f x 2 := λ f .λ x . f ( fx ) _ 3 := λ f .λ x . f ( f ( f X ))

etc. Ou en utilisant la syntaxe alternative présentée ci-dessus dans Notation :

0 := λ fx . X 1 := λ fx . f x 2 := λ fx . f ( fx ) _ 3 := λ fx . f ( f ( f X ))

Un chiffre de Church est une fonction d’ordre supérieur – il prend une fonction à argument unique f et renvoie une autre fonction à argument unique. Le nombre d’Église 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 avec elle-même n fois. Celle-ci est notée f ⁽ⁿ⁾ et est en fait la n -ième puissance de f (considéré comme un opérateur) ; F⁽⁰⁾ est défini comme étant la fonction identité. De telles compositions répétées (d’une seule fonction f ) obéissent aux Lois des exposants , c’est pourquoi ces chiffres peuvent être utilisés pour l’arithmétique. (Dans le calcul lambda 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 ci-dessus de 0. )

Une façon de penser au Chiffre d’église n , qui est souvent utile lors de l’analyse de programmes, est comme une instruction «répéter n fois». Par exemple, en utilisant les fonctions PAIR et NIL définies ci-dessous, on peut définir une fonction qui construit une liste (liée) de n éléments tous égaux à x en répétant ‘prepend another x element’ n fois, à partir d’une liste vide. Le terme lambda est

λ n .λ x . n (PAIRE x ) NUL

En faisant varier ce qui est répété et en faisant varier l’argument auquel la fonction répétée est appliquée, un grand nombre d’effets différents peuvent être obtenus.

Nous pouvons définir une fonction successeur, qui prend un chiffre de Church n et renvoie n + 1 en ajoutant une autre application de f , où ‘(mf)x’ signifie que la fonction ‘f’ est appliquée ‘m’ fois sur ‘x’ :

SUCC := λ n .λ f .λ x . f ( n f x )

Learn more.

Décroissance exponentielle

Jun 30, 2022

Schéma (langage de programmation)

Jun 26, 2022

Calcul

Jun 26, 2022

Algèbre informatique

Jun 22, 2022

Parce que 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 , l’addition peut être définie comme suit :

PLUS := λ m .λ n .λ f .λ x . m f ( n f X )

PLUS peut être considéré comme une fonction prenant deux nombres naturels comme arguments et renvoyant un nombre naturel ; on peut vérifier que

PLUS 2 3

sont des expressions lambda β-équivalentes. Étant donné que l’ajout de m à un nombre n peut être accompli en ajoutant 1 m fois, une définition alternative est :

PLUS := λ m .λ n . m SUCC n ^[23]

De même, la multiplication peut être définie comme

MULT := λ m .λ n .λ f . m ( n f ) ^[19]

Alternativement

MULT := λ m .λ n . m (PLUS n ) 0

puisque multiplier m et n équivaut à répéter m fois la fonction d’addition n puis à l’appliquer à zéro. L’exponentiation a un rendu assez simple dans les chiffres de l’Église, à savoir

POW := λ b .λ e . e b ^[20]

La fonction prédécesseur définie par PRED n = n − 1 pour un entier positif n et PRED 0 = 0 est considérablement plus difficile. La formule

PRED := λ n .λ f .λ x . n (λ g .λ h . h ( g f )) (λ u . x ) (λ u . u )

peut être validé en montrant inductivement que si T désigne (λ g .λ h . h ( g f )) , alors T ⁽ⁿ⁾ (λ u . x ) = (λ h . h ( f ⁽ⁿ⁻¹⁾ ( x ))) pour n > 0 . Deux autres définitions de PRED sont données ci-dessous, l’une utilisant des conditionnels et l’autre utilisant des paires . Avec la fonction prédécesseur, la soustraction est simple. Définir

SOUS := λ m .λ n . n PRED m ,

SUB m n donne m − n quand m > n et 0 sinon.

Logique et prédicats

Par convention, les deux définitions suivantes (appelées booléens de Church) sont utilisées pour les valeurs booléennes TRUE et FALSE :

VRAI := λ x .λ y . X FAUX := λ x .λ y . y (Notez que FALSE équivaut au chiffre zéro de l’Église défini ci-dessus)

Ensuite, avec ces deux termes lambda, nous pouvons définir des opérateurs logiques (ce ne sont que des formulations possibles ; d’autres expressions sont également 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 maintenant capables de calculer certaines fonctions logiques, par exemple :

ET VRAI FAUX ≡ (λ p .λ q . p q p ) VRAI FAUX → _β VRAI FAUX VRAI ≡ (λ x .λ y . x ) FAUX VRAI → _β FAUX

et on voit que AND TRUE FALSE est équivalent à FALSE .

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 Church 0 , et FALSE si son argument est un autre chiffre Church :

ESTZERO := λ 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” dans le calcul lambda. Par exemple, la fonction prédécesseur peut être définie comme :

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 addition n − 1 pour n > 0.

Paires

Une paire (2-tuple) peut être définie en termes de TRUE et FALSE , en utilisant l’ encodage Church pour les paires . Par exemple, PAIR encapsule la paire ( x , y ), FIRST renvoie le premier élément de la paire et SECOND renvoie le second.

COUPLE := λ x .λ y .λ f . f x y PREMIER := λ p . p VRAI SECONDE := λ p . p FAUX NUL := λ x .VRAI NULL := λ p . p (λ x .λ y .FAUX)

Une liste chaînée peut être définie comme NIL pour la liste vide, ou la PAIRE d’un élément et d’une liste plus petite. Le prédicat NULL teste la valeur NIL . (Alternativement, avec NIL := FALSE , la construction l (λ h .λ t .λ z .deal_with_head_ h _and_tail_ t ) (deal_with_nil) évite le besoin d’un test NULL explicite).

Comme exemple d’utilisation de paires, la fonction de décalage et d’incrémentation qui mappe ( m , n ) à ( n , n + 1) peut être définie comme

Φ := λ x .PAIR (DEUXIÈME x ) (SUCC (DEUXIÈME x ))

ce qui nous permet de donner peut-être la version la plus transparente de la fonction prédécesseur :

PRED := λ n .PREMIER ( n Φ (PAIRE 0 0)).

Techniques de programmation supplémentaires

Il existe un nombre considérable d’ idiomes de programmation pour le calcul lambda. Beaucoup d’entre eux ont été développés à l’origine dans le contexte de l’utilisation du calcul lambda comme base de la sémantique des langages de programmation , utilisant efficacement le calcul lambda comme langage de programmation de bas niveau . Étant donné que plusieurs langages de programmation incluent le calcul lambda (ou quelque chose de très similaire) en tant que fragment, ces techniques sont également utilisées dans la programmation pratique, mais peuvent alors être perçues comme obscures ou étrangères.

Constantes nommées

Dans le calcul lambda, une bibliothèque prendrait la forme d’une collection de fonctions préalablement définies, qui, en tant que termes lambda, ne sont que des constantes particulières. Le calcul lambda pur n’a pas de concept de constantes nommées puisque tous les termes lambda atomiques sont des variables, mais on peut imiter le fait d’avoir des constantes nommées en mettant de côté une variable comme nom de la constante, en utilisant l’abstraction pour lier cette variable dans le corps principal , et appliquez cette abstraction à la définition voulue. Ainsi, pour utiliser f pour signifier M (un terme lambda explicite) dans N (un autre terme lambda, le “programme principal”), on peut dire

(λ f . N ) M

Les auteurs introduisent souvent du sucre syntaxique , tel que let , pour permettre d’écrire ce qui précède dans l’ordre le plus intuitif

soit f = M dans N

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 terme lambda utilisant ces fonctions qui constituent le corps principal du programme.

Une restriction notable de cette let est que le nom f n’est pas défini dans M , puisque M est en dehors de la portée de la liaison d’abstraction f ; cela signifie qu’une définition de fonction récursive ne peut pas être utilisée comme M avec let . La construction de sucre syntaxique letrec plus avancée qui permet d’écrire des définitions de fonctions récursives dans ce style naïf utilise à la place des combinateurs à virgule fixe.

Récursivité et points fixes

La récursivité est la définition d’une fonction utilisant la fonction elle-même. Le calcul lambda ne peut pas exprimer cela aussi directement que certaines autres notations : toutes les fonctions sont anonymes dans le calcul lambda, nous ne pouvons donc pas faire référence à une valeur qui reste à définir, à l’intérieur du terme lambda définissant cette même valeur. Cependant, la récursivité peut toujours être obtenue en faisant en sorte qu’une expression lambda se reçoive elle-même comme sa valeur d’argument, par exemple dans (λ x . x x ) E .

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 qui doit représenter cette fonction, un paramètre (généralement le premier) sera supposé recevoir l’expression lambda elle-même comme sa valeur, de sorte que l’appeler – l’appliquer à un argument – équivaudra à une récursivité. Ainsi, pour réaliser la récursivité, l’argument prévu comme auto-référençant (appelé r ici) doit toujours être passé à lui-même dans le corps de la fonction, à un point d’appel :

G := λ r . λ n .(1, si n = 0 ; sinon n × ( r r ( n −1))) avec r r x = F x = G r x pour tenir, donc r = G et F := GG = (λ x . x x ) G

L’auto-application réalise ici la réplication, en transmettant l’expression lambda de la fonction à l’invocation suivante en tant que valeur d’argument, la rendant disponible pour être référencée et appelée ici.

Cela le résout mais nécessite de réécrire chaque appel récursif en tant qu’auto-application. Nous aimerions avoir une solution générique, sans avoir besoin de réécriture :

G := λ r . λ n .(1, si n = 0 ; sinon n × ( r ( n −1))) avec r x = F x = G r x pour 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é un terme lambda avec le premier argument représentant un appel récursif (par exemple G ici), le combinateur à virgule fixe FIX renverra une expression lambda auto-réplicative représentant la fonction récursive (ici, F ). La fonction n’a pas besoin d’être explicitement transmise à elle-même à aucun moment, car l’auto-réplication est organisée à l’avance, lors de sa création, pour être effectuée à chaque fois qu’elle est appelée. Ainsi, l’expression lambda originale (FIX G) est recréée à l’intérieur d’elle-même, au point d’appel, réalisant l’auto-référence .

En fait, il existe de nombreuses définitions possibles pour cet opérateur FIX , la plus simple d’entre elles étant :

Y := λ g .(λ x . g ( x x )) (λ x . g ( x x ))

Dans le lambda calcul, Y g est un point fixe de g , tel qu’il se développe en :

Oui g (λ h .(λ x . h ( x x )) (λ x . h ( x x ))) g (λ x . g ( x x )) (λ x . g ( x x )) g ((λ x . g ( x x )) (λ x . g ( x x ))) g ( Oui g )

Maintenant, pour effectuer notre appel récursif à la fonction factorielle, nous appellerions simplement ( Y G) n , où n est le nombre dont nous calculons la factorielle. Soit n = 4, par exemple, cela donne :

( O G) 4 G ( O G) 4 (λ r .λ n .(1, si n = 0 ; sinon n × ( r ( n −1)))) ( Y G) 4 (λ n .(1, si n = 0 ; sinon n × (( Y G) ( n −1)))) 4 1, si 4 = 0 ; sinon 4 × (( Y G) (4−1)) 4 × (G ( O G) (4−1)) 4 × ((λ n .(1, si n = 0; sinon n × (( Y G) ( n −1)))) (4−1)) 4 × (1, si 3 = 0 ; sinon 3 × (( Y G) (3−1))) 4 × (3 × (G ( Y G) (3−1))) 4 × (3 × ((λ n .(1, si n = 0; sinon n × (( Y G) ( n −1)))) (3−1))) 4 × (3 × (1, si 2 = 0; sinon 2 × (( Y G) (2−1)))) 4 × (3 × (2 × (G ( O G) (2−1)))) 4 × (3 × (2 × ((λ n .(1, si n = 0; sinon n × (( Y G) ( n −1)))) (2−1)))) 4 × (3 × (2 × (1, si 1 = 0; sinon 1 × (( Y G) (1−1))))) 4 × (3 × (2 × (1 × (G ( Y G) (1−1))))) 4 × (3 × (2 × (1 × ((λ n .(1, si n = 0; sinon n × (( Y G) ( n −1)))) (1−1)))))) 4 × (3 × (2 × (1 × (1, si 0 = 0; sinon 0 × (( Y G) (0−1))))))) 4 × (3 × (2 × (1 × (1)))) 24

Chaque fonction définie de manière récursive peut être considérée comme un point fixe d’une fonction correctement définie se refermant sur l’appel récursif avec un argument supplémentaire, et par conséquent, en utilisant Y , chaque fonction définie de manière récursive peut être exprimée sous la forme d’une expression lambda. En particulier, nous pouvons maintenant définir proprement le prédicat de soustraction, de multiplication et de comparaison des nombres naturels de manière récursive.

Conditions générales

Certains termes ont des noms communément acceptés : ^{[24] [25] [26]}

Je := λ x . X S := λ x .λ y .λ z . x z ( y z ) K := λ x .λ y . X B := λ x .λ y .λ z . x ( y z ) C := λ x .λ y .λ z . x z y W := λ x .λ y . x y y ω ou Δ := λ x . x x Ω := ω ω

I est la fonction identité. SK et BCKW forment des systèmes complets de Calcul combinatoire qui peuvent exprimer n’importe quel terme lambda – voir la section suivante . Ω est Y I , le plus petit terme qui n’a pas de forme normale. Y est standard et défini ci- dessus . VRAI et FAUX définis ci- dessus sont généralement abrégés en T et F .

Élimination de l’abstraction

Si N est un lambda-terme sans abstraction, mais contenant éventuellement des constantes nommées ( combinateurs ), alors il existe un lambda-terme T ( x , N ) qui est équivalent à λ x . N mais manque d’abstraction (sauf dans le cadre des constantes nommées, si celles-ci sont considérées comme non atomiques). Cela peut également être considéré comme des variables d’anonymisation, car T ( x , N ) supprime toutes les occurrences de x de N , tout en permettant toujours aux valeurs d’argument d’être substituées dans les positions où Ncontient un x . La fonction de conversion T peut être définie par :

T ( x , x ) := je 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 peut réduire en ayant le combinateur initial I , K ou S saisir l’argument P , tout comme le ferait la β-réduction de (λ x . N ) P . Je renvoie cet argument. K rejette l’argument, tout comme (λ x . N ) le ferait si x n’a pas d’occurrence libre dans N . S passe l’argument aux deux sous-termes de l’application, puis applique le résultat du premier au résultat du second.

Les combinateurs B et C sont similaires à S , mais transmettent l’argument à un seul sous-terme d’une application ( B au sous-terme “argument” et C au sous-terme “fonction”), économisant ainsi un K suivant s’il n’y a pas d’occurrence de x dans un sous-terme. Par rapport à B et C , le combinateur S combine en fait deux fonctionnalités : réorganiser les arguments et dupliquer un argument afin qu’il puisse être utilisé à deux endroits. Le combinateur W ne fait que ce dernier, donnant le système B, C, K, W comme alternative àCalcul du combinateur SKI .

Calcul lambda typé

Un calcul lambda typé est un formalisme typé qui utilise le symbole lambda ( λ {displaystylelambda} lambda ) pour désigner une abstraction de fonction anonyme. Dans ce contexte, les types sont généralement des objets de nature syntaxique qui sont affectés à des termes lambda ; la nature exacte d’un type dépend du calcul considéré (voir Types de calculs lambda typés ). D’un certain point de vue, les calculs lambda typés peuvent être vus comme des raffinements du calcul lambda non typé mais d’un autre point de vue, ils peuvent également être considérés comme la théorie la plus fondamentale et le calcul lambda non typé comme un cas particulier avec un seul type. ^[27]

Les calculs lambda typés sont des langages de programmation fondamentaux et sont à la base des langages de programmation fonctionnels typés tels que ML et Haskell et, plus indirectement, des langages de programmation impératifs typés . Les calculs lambda typés jouent un rôle important dans la conception de systèmes de types pour les langages de programmation ; ici, la typabilité capture généralement les propriétés souhaitables du programme, par exemple le programme ne causera pas de violation d’accès à la mémoire.

Les calculs lambda typés sont étroitement liés à la logique mathématique et à la théorie de la preuve via l’ isomorphisme de Curry-Howard et ils peuvent être considérés comme le langage interne des classes de catégories , par exemple le calcul lambda simplement typé est le langage des catégories fermées cartésiennes (CCC).

Stratégies de réduction

Le fait qu’un terme se normalise ou non, et la quantité de travail nécessaire pour le normaliser s’il l’est, dépend dans une large mesure de la stratégie de réduction utilisée. Les stratégies courantes de réduction du lambda calcul comprennent : ^[28]

Commande normale Le redex le plus à gauche et le plus à l’extérieur est toujours réduit en premier. Autrement dit, dans la mesure du possible, les arguments sont substitués dans le corps d’une abstraction avant que les arguments ne soient réduits. Ordonnance applicative Le redex le plus à gauche et le plus interne est toujours réduit en premier. Intuitivement, cela signifie que les arguments d’une fonction sont toujours réduits avant la fonction elle-même. L’ordre applicatif tente toujours d’appliquer des fonctions aux formes normales, même lorsque cela n’est pas possible. Réductions β complètes Tout redex peut être réduit à tout moment. Cela signifie essentiellement l’absence de stratégie de réduction particulière – en ce qui concerne la réductibilité, « tous les paris sont ouverts ».

Les stratégies de réduction faible ne réduisent pas sous les abstractions lambda :

Appel par valeur Un redex n’est réduit que lorsque son côté droit est réduit à une valeur (variable ou abstraction). Seuls les redex les plus externes sont réduits. Appel par nom Dans l’ordre normal, mais aucune réduction n’est effectuée à l’intérieur des abstractions. Par exemple, λ x .(λ x . x ) x est sous forme normale selon cette stratégie, bien qu’il contienne le redex (λ x . x ) x .

Les stratégies avec partage réduisent les calculs qui sont “les mêmes” en parallèle :

Réduction optimale Comme ordre normal, mais les calculs qui ont la même étiquette sont réduits simultanément. Appel par besoin Comme appel par le nom (donc faible), mais les applications de fonction qui dupliqueraient les termes à la place nomment l’argument, qui n’est alors réduit que “quand c’est nécessaire”.

Calculabilité

Il n’y a pas d’algorithme qui prend en entrée deux expressions lambda et renvoie TRUE ou FALSE selon qu’une expression se réduit à l’autre. ^[10] Plus précisément, aucune fonction calculable ne peut trancher la question. C’était historiquement le premier problème pour lequel l’indécidabilité pouvait être prouvée. Comme d’habitude pour une telle preuve, calculable signifie calculable par tout modèle de calcul complet de Turing . En fait la calculabilité peut elle-même être définie via le lambda calcul : une fonction F : N → Ndes nombres naturels est une fonction calculable si et seulement s’il existe une expression lambda f telle que pour chaque paire de x , y dans N , F ( x )= y si et seulement si f x = _βy , où x et y sont les chiffres d’Église correspondant respectivement à x et y , et = _β signifiant équivalence avec β-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 preuve de l’incalculabilité de Church réduit d’abord le problème à déterminer si une expression lambda donnée a une forme normale . Ensuite, il suppose que ce prédicat est calculable, et peut donc être exprimé en 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 preuve du premier théorème d’incomplétude de Gödel . Si e est appliqué à son propre nombre de Gödel, une contradiction en résulte.

Complexité

La notion de complexité de calcul pour le calcul lambda est un peu délicate, car le coût d’une β-réduction peut varier en fonction de la manière dont elle est mise en œuvre. ^[29] Pour être précis, il faut en quelque sorte trouver l’emplacement de toutes les occurrences de la variable liée V dans l’expression E , ce qui implique un coût en temps, ou on doit garder une trace des emplacements des variables libres d’une manière ou d’une autre, ce qui implique un coût de l’espace. Une recherche naïve des emplacements de V dans E est O ( n ) dans la longueur n de E . Chaînes de directeurétaient une première approche qui échangeait ce coût de temps pour une utilisation de l’espace quadratique. ^[30] Plus généralement, cela a conduit à l’étude de systèmes utilisant la substitution explicite .

En 2014, il a été montré que le nombre d’étapes de β-réduction prises par la réduction d’ordre normal pour réduire un terme est un modèle de coût en temps raisonnable , c’est-à-dire que la réduction peut être simulée sur une machine de Turing en temps polynomialement proportionnel au nombre d’étapes . ^[31] Il s’agissait d’un problème ouvert de longue date, en raison de l’ explosion de la taille , de l’existence de termes lambda dont la taille croît de manière exponentielle pour chaque β-réduction. Le résultat contourne cela en travaillant avec une représentation partagée compacte. Le résultat montre clairement que la quantité d’espace nécessaire pour évaluer un terme lambda n’est pas proportionnelle à la taille du terme lors de la réduction. On ne sait pas actuellement quelle serait une bonne mesure de la complexité de l’espace. ^[32]

Un modèle déraisonnable ne signifie pas nécessairement inefficace. La réduction optimale réduit tous les calculs avec la même étiquette en une seule étape, évitant le travail en double, mais le nombre d’étapes de β-réduction parallèles pour réduire un terme donné à la forme normale est approximativement linéaire dans la taille du terme. C’est beaucoup trop petit pour être une mesure de coût raisonnable, car toute machine de Turing peut être codée dans le calcul lambda en taille linéairement proportionnelle à la taille de la machine de Turing. Le véritable coût de la réduction des termes lambda n’est pas dû à la β-réduction en soi mais plutôt à la gestion de la duplication des redexes lors de la β-réduction. ^[33]On ne sait pas si les implémentations de réduction optimales sont raisonnables lorsqu’elles sont mesurées par rapport à un modèle de coût raisonnable tel que le nombre d’étapes les plus à gauche les plus à l’extérieur vers la forme normale, mais il a été démontré pour des fragments du calcul lambda que l’algorithme de réduction optimale est efficace et a au plus une surcharge quadratique par rapport à la plus à gauche la plus à l’extérieur. ^[32] De plus, la mise en œuvre du prototype BOHM de la réduction optimale a surpassé à la fois Caml Light et Haskell en termes lambda purs. ^[33]

Calcul lambda et langages de programmation

Comme le souligne l’article de Peter Landin de 1965 “A Correspondence between ALGOL 60 and Church’s Lambda-notation”, ^[34] les langages de programmation procédurale séquentielle peuvent être compris en termes de calcul lambda, qui fournit les mécanismes de base de l’abstraction procédurale et de la procédure. (sous-programme) application.

Fonctions anonymes

Par exemple, en Lisp , la fonction “square” peut être exprimée sous la forme d’une expression lambda comme suit :

( lambda ( x ) ( * x x ))

L’exemple ci-dessus est une expression qui évalue une fonction de première classe. Le symbole lambdacrée une fonction anonyme, étant donné une liste de noms de paramètres, (x)- un seul argument dans ce cas, et une expression qui est évaluée comme le corps de la fonction, (* x x). Les fonctions anonymes sont parfois appelées expressions lambda.

Par exemple, Pascal et de nombreux autres langages impératifs prennent depuis longtemps en charge le passage de sous- programmes en tant qu’arguments à d’autres sous-programmes via le mécanisme des pointeurs de fonction . Cependant, les pointeurs de fonction ne sont pas une condition suffisante pour que les fonctions soient des types de données de première classe , car une fonction est un type de données de première classe si et seulement si de nouvelles instances de la fonction peuvent être créées au moment de l’exécution. Et cette création de fonctions à l’exécution est prise en charge dans Smalltalk , JavaScript et Wolfram Language , et plus récemment dans Scala , Eiffel (“agents”), C# (“délégués”) etC++11 , entre autres.

Parallélisme et concurrence

La propriété de Church-Rosser du lambda calcul signifie que l’évaluation (β-réduction) peut être effectuée dans n’importe quel ordre , même en parallèle. Cela signifie que diverses stratégies d’évaluation non déterministes sont pertinentes. Cependant, le calcul lambda n’offre aucune construction explicite pour le parallélisme . On peut ajouter des constructions telles que Futures au calcul lambda. 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, et même sur eux-mêmes, a conduit à des questions sur la sémantique du lambda calcul. Une signification sensée pourrait-elle être attribuée aux termes du lambda calcul ? La sémantique naturelle était de trouver un ensemble D isomorphe à l’espace des fonctions D → D , des fonctions sur lui-même. Cependant, aucun tel D non trivial ne peut exister, par des contraintes de cardinalité car l’ensemble de toutes les fonctions de D à D a une plus grande cardinalité que D , à moins que D ne soit un ensemble singleton .

Dans les années 1970, Dana Scott a montré que si seules les fonctions continues étaient considérées, un ensemble ou un domaine D avec la propriété requise pouvait être trouvé, fournissant ainsi un modèle pour le calcul lambda.

Ce travail a également constitué la base de la sémantique dénotationnelle des langages de programmation.

Variantes et extensions

Ces extensions sont dans le cube lambda :

Calcul lambda typé – Calcul lambda avec variables typées (et fonctions)
Système F – Un calcul lambda typé avec des variables de type
Calcul des constructions – Un calcul lambda typé avec des types comme valeurs de première classe

Ces systèmes formels sont des extensions du calcul lambda qui ne sont pas dans le cube lambda :

Calcul lambda binaire – Une version du calcul lambda avec des E / S binaires, un codage binaire des termes et une machine universelle désignée.
Calcul lambda-mu – Une extension du calcul lambda pour traiter la logique classique

Ces systèmes formels sont des variantes du lambda calcul :

Calcul Kappa – Un analogue de premier ordre du calcul lambda

Ces systèmes formels sont liés au lambda calcul :

Logique combinatoire – Une notation pour la logique mathématique sans variables
Calcul combinateur SKI – Un système de calcul basé sur les combinateurs S , K et I , équivalent au calcul lambda , mais réductible sans substitutions de variables

Voir également

Portail des mathématiques

Systèmes informatiques applicatifs – Traitement des objets à la manière du lambda calcul
Catégorie fermée cartésienne – Un cadre pour le calcul lambda en théorie des catégories
Machine abstraite catégorielle – Un modèle de calcul applicable au calcul lambda
Isomorphisme de Curry-Howard – La correspondance formelle entre les programmes et les preuves
Indice De Bruijn – notation désambiguïsante des conversions alpha
Notation De Bruijn – notation utilisant les fonctions de modification postfixées
Calcul lambda déductif – La prise en compte des problèmes associés à la considération du calcul lambda comme un système déductif .
Théorie des domaines – Étude de certains posets donnant une sémantique dénotationnelle pour le calcul lambda
Stratégie d’évaluation – Règles d’évaluation des expressions dans les langages de programmation
Substitution explicite – La théorie de la substitution, telle qu’utilisée dans la β-réduction
Programmation fonctionnelle
Formule de Harrop – Une sorte de formule logique constructive telle que les preuves sont des termes lambda
Réseaux d’interaction
Paradoxe de Kleene-Rosser – Une démonstration qu’une certaine forme de calcul lambda est incohérente
Knights of the Lambda Calculus – Une organisation semi-fictive de hackers LISP et Scheme
Machine de Krivine – Une machine abstraite pour interpréter l’appel par le nom dans le calcul lambda
Définition du calcul lambda – Définition formelle du calcul lambda.
Let expression – Une expression étroitement liée à une abstraction.
Minimalisme (informatique)
Réécriture – Transformation de formules en systèmes formels
Machine SECD – Une machine virtuelle conçue pour le calcul lambda
Théorème de Scott – Curry – Un théorème sur les ensembles de termes lambda
To Mock a Mockingbird – Une introduction à la logique combinatoire
Machine de Turing universelle – Une machine informatique formelle équivalente au calcul lambda
Unlambda – Un langage de programmation fonctionnelle ésotérique basé sur la logique combinatoire

Remarques

^ Pour un historique complet, voir “History of Lambda-calculus and Combinatory Logic” de Cardone et Hindley (2006).

Références

^ Turing, Alan M. (décembre 1937). “Calculabilité et λ-définissabilité”. Le Journal de la logique symbolique . 2 (4): 153–163. doi : 10.2307/2268280 . JSTOR 2268280 .
^ Coquand, Thierry (8 février 2006). Zalta, Edward N. (éd.). “Théorie des types” . L’Encyclopédie de philosophie de Stanford (éd. Été 2013) . Consulté le 17 novembre 2020 .
^ Moortgat, Michael (1988). Enquêtes catégorielles : aspects logiques et linguistiques du calcul de Lambek . Éditions Foris. ISBN 9789067653879.
^ Carie, Harry; Muskens, Reinhard, éd. (2008). Signification de l’informatique . Springer. ISBN 978-1-4020-5957-5.
^ Mitchell, John C. (2003). Concepts en langages de programmation . La presse de l’Universite de Cambridge. p. 57. ISBN 978-0-521-78098-8..
^ Pierce, Benjamin C. Théorie des catégories de base pour les informaticiens . p. 53.
^ Église, Alonzo (1932). “Un ensemble de postulats pour le fondement de la logique”. Annales de Mathématiques . Série 2. 33 (2): 346–366. doi : 10.2307/1968337 . JSTOR 1968337 .
^ Kleene, Stephen C. ; Rosser, JB (juillet 1935). “L’incohérence de certaines logiques formelles”. Les Annales de Mathématiques . 36 (3): 630. doi : 10.2307/1968646 . JSTOR 1968646 .
^ Église, Alonzo (décembre 1942). « Examen de Haskell B. Curry, L’incohérence de certaines logiques formelles ». Le Journal de la logique symbolique . 7 (4): 170–171. doi : 10.2307/2268117 . JSTOR 2268117 .
^ ^{une église} ^b , Alonzo (1936). “Un problème insoluble de théorie élémentaire des nombres”. Journal américain de mathématiques . 58 (2): 345–363. doi : 10.2307/2371045 . JSTOR 2371045 .
^ Église, Alonzo (1940). “Une Formulation de la Théorie Simple des Types”. Journal de logique symbolique . 5 (2): 56–68. doi : 10.2307/2266170 . JSTOR 2266170 .
^ Partee, BBH; ter Meulen, A. ; Mur, RE (1990). Méthodes mathématiques en linguistique . Springer. ISBN 9789027722454. Récupéré le 29 décembre 2016 .
^ Alma, Jesse. Zalta, Edward N. (éd.). “Le calcul Lambda” . L’Encyclopédie de philosophie de Stanford (éd. Été 2013) . Consulté le 17 novembre 2020 .
^ Dana Scott, ” Looking Backward; Looking Forward “, conférence invitée à l’atelier en l’honneur du 85e anniversaire de Dana Scott et des 50 ans de théorie des domaines, 7-8 juillet, FLoC 2018 (conférence 7 juillet 2018). Le passage pertinent commence à 32:50 . (Voir aussi cet extrait d’une conférence de mai 2016 à l’Université de Birmingham, Royaume-Uni.)
^ “DA Turner “Some History of Functional Programming Languages” dans une conférence invitée TFP12 , St Andrews University, 12 juin 2012. Voir la section sur Algol 60″ (PDF) .
^ Barendregt, Hendrik Pieter (1984). Le calcul lambda : sa syntaxe et sa sémantique . Etudes de Logique et des Fondements des Mathématiques. Vol. 103 (éd. révisée). Hollande du Nord. ISBN 0-444-87508-5.
^ Corrections .
^ ^un ^b “Exemple pour les Règles d’Associativité” . Lambda-bound.com . Récupéré le 18/06/2012 .
^ ^un ^b Selinger, Peter (2008), Notes de cours sur le calcul Lambda (PDF) , vol. 0804, Département de mathématiques et de statistique, Université d’Ottawa, p. 9, arXiv : 0804.3434 , Bibcode : 2008arXiv0804.3434S
^ ^un ^b Barendregt, Henk ; Barendsen, Erik (mars 2000), Introduction au calcul lambda (PDF)
^ de Queiroz, Ruy JGB (1988). “Un compte rendu théorique de la programmation et le rôle des règles de réduction”. Dialectique . 42 (4): 265–282. doi : 10.1111/j.1746-8361.1988.tb00919.x .
^ Turbak, Franklyn; Gifford, David (2008), Concepts de conception dans les langages de programmation , MIT press, p. 251, ISBN 978-0-262-20175-9
^ Felleisen, Matthias; Flatt, Matthew (2006), Langages de programmation et calculs lambda (PDF) , p. 26, archivé de l’original (PDF) le 2009-02-05; Une note (consultée en 2017) à l’emplacement d’origine suggère que les auteurs considèrent que l’ouvrage initialement référencé a été remplacé par un livre.
^ Ker, Andrew D. “Calcul Lambda et Types” (PDF) . p. 6 . Récupéré le 14 janvier 2022 .
^ Dezani-Ciancaglini, Mariangiola; Ghilézan, Silvia (2014). “Précision du sous-typage sur les types d’intersection et d’union” (PDF) . Réécriture et calculs lambda typés . Notes de cours en informatique. 8560 : 196. doi : 10.1007/978-3-319-08918-8_14 . hdl : 2318/149874 . ISBN 978-3-319-08917-1. Récupéré le 14 janvier 2022 .
^ Forster, Yannick; Smolka, Gert (août 2019). “Call-by-Value Lambda Calculus comme modèle de calcul en Coq” (PDF) . Journal de raisonnement automatisé . 63 (2): 393–413. doi : 10.1007/s10817-018-9484-2 . S2CID 53087112 . Récupéré le 14 janvier 2022 .
^ Types et langages de programmation, p. 273, Benjamin C. Pierce
^ Pierce, Benjamin C. (2002). Types et langages de programmation . Presse du MIT . p. 56. ISBN 0-262-16209-1.
^ Frandsen, Gudmund Skovbjerg; Sturtivant, Carl (26 août 1991). “Qu’est-ce qu’une implémentation efficace du lambda-calcul ?” . Actes de la 5e conférence ACM sur les langages de programmation fonctionnels et l’architecture informatique . Notes de cours en informatique. Springer Verlag. 523 : 289–312. CiteSeerX 10.1.1.139.6913 . doi : 10.1007/3540543961_14 . ISBN 9783540543961.
^ Sinot, F.-R. (2005). “Director Strings Revisited: Une approche générique de la représentation efficace des variables libres dans la réécriture d’ordre supérieur” (PDF) . Journal de logique et de calcul . 15 (2): 201–218. doi : 10.1093/logcom/exi010 .
^ Accattoli, Beniamino; Dal Lago, Ugo (14 juillet 2014). “La réduction bêta est invariante, en effet” (PDF) . Actes de la réunion conjointe de la vingt-troisième conférence annuelle de l’EACSL sur la logique informatique (CSL) et du vingt-neuvième symposium annuel ACM / IEEE sur la logique en informatique (LICS) : 1–10. arXiv : 1601.01233 . doi : 10.1145/2603088.2603105 . ISBN 9781450328869. S2CID 11485010 .
^ ^un ^b Accattoli, Beniamino (octobre 2018). “Modèles d'(in)efficacité et de coût raisonnable” . Notes électroniques en informatique théorique . 338 : 23–43. doi : 10.1016/j.entcs.2018.10.003 .
^ ^un ^b Asperti, Andrea (16 janvier 2017). “À propos de la réduction efficace des termes lambda” (PDF) . arXiv : 1701.04240v1 . Récupéré le 19 août 2021 . {{cite journal}}: Cite journal requires |journal= (help)
^ Landin, PJ (1965). “Une correspondance entre ALGOL 60 et la notation Lambda de Church”. Communications de l’ACM . 8 (2): 89–101. doi : 10.1145/363744.363749 . S2CID 6505810 .

Lectures complémentaires

Abelson, Harold et Gérald Jay Sussman. Structure et interprétation des programmes informatiques . La presse du MIT . ISBN 0-262-51087-1 .
Hendrik Pieter Barendregt Introduction au calcul lambda .
Henk Barendregt , L’impact du calcul lambda en logique et en informatique . Le Bulletin de logique symbolique, volume 3, numéro 2, juin 1997.
Barendregt, Hendrik Pieter , The Type Free Lambda Calculus pp1091–1132 du Manuel de logique mathématique , North-Holland (1977) ISBN 0-7204-2285-X
Cardone et Hindley, 2006. Histoire du lambda-calcul et de la logique combinatoire . Dans Gabbay et Woods (eds.), Manuel d’histoire de la logique , vol. 5. Elsevier.
Church, Alonzo, Un problème insoluble de la théorie élémentaire des nombres , American Journal of Mathematics , 58 (1936), pp. 345–363. Cet article contient la preuve que l’équivalence des expressions lambda n’est en général pas décidable.
Alonzo Church, The Calculi of Lambda-Conversion ( ISBN 978-0-691-08394-0 ) ^[1]
Frink Jr., Orrin, Review: The Calculi of Lambda-Conversion ^[2]
Kleene, Stephen, Une théorie des entiers positifs dans la logique formelle , American Journal of Mathematics , 57 (1935), pp. 153-173 et 219-244. Contient les définitions du calcul lambda de plusieurs fonctions familières.
Landin, Peter , Une correspondance entre ALGOL 60 et Church’s Lambda-Notation , Communications de l’ACM , vol. 8, non. 2 (1965), pages 89–101. Disponible sur le site de l’ACM . Un article classique soulignant l’importance du lambda calcul comme base des langages de programmation.
Larson, Jim, Une introduction au calcul lambda et au schéma . Une introduction en douceur pour les programmeurs.
Schalk, A. et Simmons, H. (2005) Une introduction au λ-calcul et à l’arithmétique avec une bonne sélection d’exercices . Notes pour un cours de Mathematical Logic MSc à l’Université de Manchester.
de Queiroz, Ruy JGB (2008). “Sur les règles de réduction, la signification en tant qu’utilisation et la sémantique théorique de la preuve”. Studia Logica . 90 (2): 211-247. doi : 10.1007/s11225-008-9150-5 . S2CID 11321602 .Un article donnant un fondement formel à l’idée de “ le sens est l’utilisation ” qui, même si elle est basée sur des preuves, est différente de la sémantique de la théorie de la preuve comme dans la tradition Dummett-Prawitz car elle prend la réduction comme les règles donnant le sens.
Hankin, Chris, Une introduction aux calculs lambda pour les informaticiens, ISBN 0954300653

Monographies/manuels pour étudiants diplômés :

Morten Heine Sørensen, Paweł Urzyczyn, Lectures on the Curry–Howard isomorphism , Elsevier, 2006, ISBN 0-444-52077-5 est une monographie récente qui couvre les principaux sujets du calcul lambda de la variété sans type à la plupart des lambda typés. calculi , y compris des développements plus récents comme les systèmes de types purs et le cube lambda . Il ne couvre pas les extensions de sous-typage .
Pierce, Benjamin (2002), Types et langages de programmation , MIT Press, ISBN 0-262-16209-1couvre les calculs lambda d’un point de vue pratique du système de type ; certains sujets comme les types dépendants sont seulement mentionnés, mais le sous-typage est un sujet important.

Certaines parties de cet article sont basées sur du matériel de FOLDOC , utilisé avec permission .

Liens externes

Wikimedia Commons a des médias liés au calcul Lambda .

Graham Hutton, calcul lambda , une courte (12 minutes) vidéo informaticienne sur le Lambda Calculus
Helmut Brandl, Introduction étape par étape au calcul lambda
“Lambda-calcul” , Encyclopédie des mathématiques , EMS Press , 2001 [1994]
Achim Jung, Une brève introduction au calcul lambda -( PDF )
Dana Scott, Une chronologie du calcul lambda -( PDF )
David C. Keenan, Pour disséquer un oiseau moqueur : une notation graphique pour le calcul lambda avec réduction animée
Raúl Rojas, Un tutoriel d’introduction au calcul lambda – ( PDF )
Peter Selinger, Notes de cours sur le calcul lambda -( PDF )
L. Allison, Quelques exemples exécutables de λ-calcul
Georg P. Loczewski, Le calcul lambda et A++
Bret Victor, Alligator Eggs: Un jeu de puzzle basé sur le calcul lambda
Lambda Calculus Archivé le 14/10/2012 sur la Wayback Machine sur le site Web de Safalra Archivé le 02/05/2021 sur la Wayback Machine
LCI Lambda Interpreter un interpréteur de calcul pur simple mais puissant
Liens Lambda Calculus sur Lambda-the-Ultimate
Mike Thyer, Lambda Animator , une applet graphique Java démontrant des stratégies de réduction alternatives.
Implémentation du calcul Lambda à l’ aide de modèles C++
Marius Buliga, Calcul lambda graphique
Lambda Calculus comme modèle de flux de travail par Peter Kelly, Paul Coddington et Andrew Wendelborn ; mentionne la réduction de graphe comme un moyen courant d’évaluer les expressions lambda et discute de l’applicabilité du calcul lambda pour le calcul distribué (en raison de la propriété Church-Rosser , qui permet la réduction de graphe parallèle pour les expressions lambda).
Shane Steinert-Threlkeld, “Lambda Calculi” , Encyclopédie Internet de Philosophie
Anton Salikhmetov, Macro-calcul lambda

^ Église, Alonzo (1941). Les calculs de Lambda-Conversion . Princeton : Presse universitaire de Princeton . Récupéré le 14/04/2020 .
^ Frink Jr., Orrin (1944). “Revue: Les calculs de Lambda-Conversion par Alonzo Church” (PDF) . Taureau. Amer. Math. Soc . 50 (3): 169–172. doi : 10.1090/s0002-9904-1944-08090-7 .