Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.

Le lambda-calcul

Les activités #.dec (dec pour Découverte) consistent à étudier des présentations explicatives et à traiter tous les exercices de découverte proposés. Si vous ne répondez pas correctement à un exercice de découverte, revenez en arrière pour relire les explications et identifier la cause de votre erreur.

Les activités #.ent (ent pour Entrainement) consistent à traiter des exercices d’entraînement. Vous devez d’abord tenter de traiter ces exercices sans dévoiler d’indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de découverte ou d’entraînement précédemment traités.

Activité de découverte A.dec

Un très rapide tour d’horizon

Le \(\lambda\)-calcul est un langage rudimentaire permettant de réaliser une forme de programmation non impérative appelée programmation fonctionnelle.

L’exécution d’un programme en \(\lambda\)-calcul s’effectue en appliquant des règles simples faisant appel à des substitutions syntaxiques.

Les données et les programmes sont représentés par des \(\lambda\)-termes constitué des éléments syntaxiques suivants :

  • Les symboles \(\lambda\) \(.\) \(( )\)
  • des variables \(a,b,c,…\)

Voici un exemple de programme et une donnée à laquelle il peut être appliqué :

\[\underbrace{(\lambda p. \lambda a. \lambda b. pab)}_{\text{programme }} \underbrace{(\lambda a. \lambda b.a)}_{\text{ donnée}}
\]

Les étapes d’exécution de ce programme sont les suivantes :

  1. \(\lambda a. \lambda b. (\lambda a. \lambda b.a)ab\)
  2. \(\lambda a. \lambda b. (\lambda b.a)b\)
  3. \(\lambda a. \lambda b. a\)

Pour l’instant, cette séquence paraît mystérieuse. Nous verrons plus tard que les règles permettant de la réaliser sont des substitutions, c’est à dire des "copier coller" qui remplacent certaines variables par des termes.

Le \(\lambda\)-calcul a la puissance d’expression de la machine de Turing. Il permet de calculer les mêmes fonctions. C’est un modèle de calculateur universel.

A.dec1 : les lambda-termes

En \(\lambda\)-calcul, les programmes et les données sont représentés par des \(\lambda\)-termes. Ces termes sont construits à partir

  • de variables (dans cet enseignement, on les désignera par des lettres minuscules),
  • des symboles \(\lambda\), \(.\) et des parenthèses \(()\).

Un \(\lambda\)-terme complètement parenthésé est :

  • Soit une variable : \(a\), \(b\), \(c\),…
  • Soit une abstraction \((\lambda x.T)\), où \(T\) est une \(\lambda\)-terme et \(x\) une variable.
  • Soit une application \((T U)\), où \(T\) et \(U\) sont des termes.

Voici quelques exemples de \(\lambda\)-termes :

  • une application : \((a b)\)

  • une abstraction : \((\lambda x . y)\)

  • une application composée de 2 abstractions :

    \((\overbrace{\underbrace{(\lambda x.a)}_{\text{abstraction }} \underbrace{(\lambda y.y)}_{\text{ abstraction}}}^{\text{application}})\)

Exercice de découverte A.dec.x1

Parmi les écritures suivantes, lesquelles sont des \(\lambda\)-termes complètement parenthésés ?

  1. \((a \lambda a)\)
  2. \((a(\lambda b.a))\)
  3. \((\lambda x. (x \lambda z))\)
  4. \((\lambda x. (x (\lambda z.a)))\)
"Réponse"

Le 2 et le 4. Un \(\lambda\) doit toujours être suivi par une variable, elle-même suivie d’un point.

A.dec2 : décomposition d’un lambda-terme

Les règles suivantes permettent de supprimer certaines parenthèses (qui deviennes implicites) pour une meilleure lisibilité.

  1. Associativité à gauche des applications : \(((UT)X) \equiv UTX\)
  2. Associativité à droite des abstractions : \((\lambda x . (\lambda y. U)) \equiv \lambda x . \lambda y. U\)
  3. Priorité des application sur les abstractions : \(\lambda x.(UT) \equiv \lambda x.UT\)

Voici, à titre d’exemple, la décomposition du terme \(\lambda x. \lambda y . x y \lambda t.t\)

On commence par encadrer les abstractions (ici en pointillé) en partant de la droite.

image-20220104213522070

Puis on encadre (ici en trait plein) les applications en partant de la gauche.

image-20220104213646931

Exercice de découverte A.dec.x2

Décomposez le terme suivant en applications et abstractions.

\(\lambda t . a \lambda u . a t\)

"Réponse"

image-20220104214613700

Exercice de découverte A.dec.x3

Décomposez le terme suivant en applications et abstractions.

\((\lambda t . \lambda x . x t) u \lambda x . x u\)

"Réponse"

image-20220112070746499

A.dec3 : Variables liées et variables libres

Le symbole \(\lambda\) est appelé lieur. Il introduit une variable liée à toutes les occurrence des variables de même nom dans la portée du lieur.

Cette portée est l’abstraction engendrée par le lieur, sauf les abstractions incluses avec une variable liée de même nom.

image-20220104221013164

Toute variable qui n’est pas liée est dite libre.

Voici un exemple de terme avec ses variables libres et ses occurrences de variables liées entre elles.

image-20220104221812201

Exercice de découverte A.dec.x4

Dans le terme suivant, entourez les variables libres et connectez avec des flèches les occurrences de variables liées entre elles.

\(a\lambda x . \lambda y . x t y\)

"Réponse"

image-20220104222536172

Exercice de découverte A.dec.x5

Dans le terme suivant, entourez les variables libres et connectez avec des flèches les occurrences de variables liées entre elles.

\(a\lambda a . ( b \lambda a . a ) \lambda z . a c\)

"Réponse"

image-20220104223324541

Remarquez que la variable \(z\) est liée, parce qu’elle suit immédiatement un lieur \(\lambda\), bien qu’elle ne soit liée qu’à elle-même.

A.dec4 : Équivalence de termes

Deux termes \(T\) et \(U\) sont dit équivalents (plus précisément \(\alpha\)-équivalents, mais nous ne parlerons que de cette forme d’équivalence) si et seulement si on peut transformet \(T\) et \(U\) en un même terme \(R\) par les opérations suivantes :

  1. Renommer des occurrences de variables liées sans changer les liens entre occurrences de variables liées. Nous appellerons une telle opération renommage autorisé.
  2. Supprimer des parenthèses non significatives, c’est à dire ne modifiant pas la décomposition d’un terme en abstractions et applications.

Par exemple \(a \lambda x . x a\) est équivalent à \(a \lambda y . y a\) car on peut obtenir le deuxième terme en renommant en \(y\) les occurrences liées entre elles de la variable \(x\) du premier terme.

Mais \(a \lambda x . x a\) n’est pas équivalent à \(b \lambda y . y b\) car la variable \(a\) est une variable libre. Renommer des occurrences de variables libres change le sens d’un \(\lambda\)-terme.

image-20220107104125569

Exercice de découverte A.dec.x6

Dans la liste suivante, quels sont les termes équivalents à \(\lambda t. \lambda x. x t\) ?

  1. \(\lambda t. \lambda t. t t\)
  2. \(\lambda w. \lambda t. t w\)
  3. \((\lambda t. \lambda x. x) t\)
  4. \(\lambda t. \lambda y. (y t)\)
"Réponse"

  1. Non. En renommant \(x\) en \(t\), le dernier \(t\) n’est plus lié par le premier, mais par le deuxième lieur. Le renommage n’est pas autorisé car il modifie les liaisons entre les occurrences de variables liées.
  2. Oui. Les occurrences de \(t\) ont été renommés en \(w\) et celle de \(x\) on été renommées en \(t\).
  3. Non. Les décompositions en abstractions et application, c’est à dire les structures des deux termes sont différentes.
  4. Oui. D’une part, le occurrences de \(x\) ont été renommées en \(y\), d’autre part, des parenthèses non significatives (ne changeant pas la structure du terme) ont été ajoutées.

Exercice de découverte A.dec.x7

Dans la liste suivante, quels sont les termes équivalents à \(\lambda x.(a x a) \lambda y. y\) ?

  1. \((\lambda x.(a x a)) \lambda y. y\)
  2. \((\lambda y.(a y a)) \lambda y. y\)
  3. \(\lambda t.(a t a) \lambda y. y\)
  4. \(\lambda x.(b x b) \lambda y. y\)
"Réponse"

Uniquement le 3. L’occurrence (liée seulement à elle-même) de \(x\) a été remplacée par \(t\).

Pas 1 ni 2 parce que les parenthèses changent la structure (décomposition en abstractions et applications du terme). Faites un dessin si vous avez des difficultés à le visualiser mentalement.

Pas 4 car des variables libres changent de nom.

A.dec5 : Redex

Un redex est un terme ayant la forme \((A)T\), où \(A\) est une abstraction et \(T\) est un terme (pouvant être une variable, une abstraction et une application).

Identifier les redex est la clé de l’évaluation des termes, ce qui correspond à l’exécution des "programmes" en \(\lambda\)-calcul.

Voici un exemple de redex qui introduit une terminologie pas spécialement standard, mais qui permettra de simplifier les explications du principe de réduction présenté dans la section suivante, qui correspond à une étape d’évaluation d’un terme.

Soit le terme \(\lambda x . (\lambda z . z x) x y\). Ce terme comporte un redex qui est le terme \((\lambda z . z x) x\).

\(\lambda x . \; \underbrace{(\lambda z . z x) x}_\text{redex} \; y\).

Exercice de découverte A.dec.x8

Pourquoi le redex n’est-il pas \((\lambda z . z x) x y\) ?

"Réponse"

Si on décompose le terme en applications et abstractions, on obtient la structure suivante :

image-20220105191953060

L’abstraction entre parenthèse est appliquée à la variable \(x\) et non à \(xy\) en raison de l’associativité à gauche des applications.

Nous allons donner des noms aux différentes parties d’un redex \((\lambda x.C)T\) :

  • La variable de liaison \(x\).
  • Le corps du redex \(C\).
  • L’argument du redex \(T\)

image-20220107114301858

Le corps et l’argument peuvent être n’importe quels \(\lambda\)-termes. Il peuvent comporter des abstractions et des applications.

Exercice de découverte A.dec.x9

Dans le terme \(\lambda x . (\lambda y. a x) b \lambda t . t\), identifiez (si applicable) le redex en le mettant entre crochets et en soulignant sa variable de liaison.

"Réponse"

Le redex est \(\lambda x . [(\lambda \underline{y}. a x) b] \lambda t . t\)

Exercice de découverte A.dec.x10

Dans le terme \(\lambda x . (x \lambda y . a x) b \lambda t . t\), identifiez (si applicable) le redex en le mettant entre crochets et en soulignant sa variable de liaison.

"Réponse"

Il n’y a pas de redex. C’était un piège. En effet, dans un redex, il y a toujours un symbole \(\lambda\) immédiatement après la première parenthèse ouvrante.

Exercice de découverte A.dec.x11

Dans le terme \((\lambda x . (\lambda y . a x) b ) \lambda t . t\), identifiez (si applicable) le redex en le mettant entre crochets et en soulignant sa variable de liaison.

"Réponse"

Le terme entier est un redex : \([(\lambda \underline{x} . (\lambda y . a \underline{x}) b ) \lambda t . t]\)

Et il y a aussi le redex \((\lambda x . [(\lambda \underline{y} . a x) b )] \lambda t . t\).

Exercice de découverte A.dec.x12

Dans le terme \(\lambda x . x y (\lambda z . z) x\), identifiez (si applicable) le redex en le mettant entre crochets et en soulignant sa variable de liaison.

"Réponse"

Il n’y a pas de redex car le terme se décompose de la manière suivante :

image-20220105202741482

On voit que l’application ayant \(x\) comme deuxième terme (le plus grand rectangle en trait plein) n’a pas une abstraction comme premier terme. Il ne suffit donc pas qu’il y ait un motif \((\lambda x.C)T\) pour que ce soit un redex. Par exemple, dans un terme ayant la forme \(W(\lambda x.C)T\), \((\lambda x.C)T\) n’est pas un redex parce qu’en raison de l’associativité à gauche des applications, le terme se décompose en \((W(\lambda x.C))T\), i.e., (\(W\) appliqué à \((\lambda x.C)\)), le tout appliqué à \(T\).

A.dec6 : Réduction, cas simple

La réduction est une étape d’évaluation d’un \(\lambda\)-terme. Elles s’applique à un redex \(R = (\lambda x.C)T\) et consiste à remplacer ce redex \(R\) par le terme \((C)\) dans lequel toutes les occurrences de variables liées à \(x\) ont été remplacées par \((T)\).

Reformulons pour bien comprendre le principe :

  1. On prend le corps du redex \(C\).
  2. On identifie chaque occurrence de la variable de liaison dans \(C\).
  3. On remplace chacune de ces occurrences par \((T)\), c’est à dire l’argument entre parenthèses.
  4. On met entre parenthèses le terme obtenu.

Le résultat est la réduction du redex. Certaines des parenthèses peuvent être supprimées si cela ne modifie pas la structure du terme.

Voici un exemple de réduction d’un redex dans le terme \((\lambda x . \lambda y . x) z \lambda t . t\). La première chose à faire est de trouver le redex, sa variable de liaison, son corps et son argument.

\([(\;\lambda \underline{x} .\; \lambda y .\; \underline{x}\;)\; z] \;\lambda t .\; t\)

image-20220107114116868

Maintenant, on remplace le redex par son corps \((\lambda y . x)\) dans lequel chaque occurrence de la variable de liaison du redex, \(x\), est remplacée par l’argument entre parenthèses, \((z)\). Tous ce qui est en dehors des limites du redex reste inchangé.

Le redex réduit est \((\lambda y . (z))\). Après réduction, le terme devient \((\lambda y.(z))\lambda t.t\). Ce terme peut être simplifié en virant les parenthèses autour de \(z\). Par contre, les autres parenthèses ne doivent pas être supprimées car cela changerait la structure du terme.

On obtient donc \((\lambda y.z)\lambda t.t\).

Exercice de découverte A.dec.x13

Identifiez le redex du terme \(\lambda a.(\lambda x . x y) y z\) et les occurrences de sa variable de liaison, puis réduisez-le.

"Réponse"

Identification du redex dans le terme (entre crochets) : \(\lambda a. [(\lambda \underline{x} . \underline{x} y) y] z\).

Si vous avez du mal à comprendre cette première étape, prenez le temps de décomposer le terme en applications et abstraction.

Maintenant, il faut réduire le redex, donc le remplacer par son corps \(\underline{x} y\) dans lequel \(\underline{x}\) est remplacé par l’argument \(y\).

Le redex est donc remplacé par \((yy)\).

Le terme complet après réduction est \(\lambda a . (yy) z\), qui se simplifie en \(\lambda a . y y z\).

Exercice de découverte A.dec.x14

Identifiez le redex du terme \((\lambda a. \lambda b . b a) c \lambda x.x\) et les occurrences de sa variable de liaison, puis réduisez-le.

"Réponse"

On isole le redex : \([(\lambda \underline{a}. \lambda b . b \underline{a}) c]\lambda x.x\).

On réduit le redex : \((\lambda b . b c)\lambda x . x\).

A.dec7 : Réduction nécessitant un renommage

Il y a un cas particulier dans lequel un renommage doit être réalisé avant de procéder à une réduction :

Lorsqu’une variable libre située dans l’argument du redex serait capturée par un lieur situé dans le corps du redex, c’est à dire une variable qui ne serait plus libre après la réduction.

Il faut donc une sorte de concours de circonstances :

  • Il faut qu’il y ait un lieur \(\lambda \underline{x}\) dans le corps du redex.
  • Il faut qu’il y ait une variable libre \(\underline{x}\) dans l’argument du redex.

On doit alors renommer toutes les occurrences de \(\underline{x}\) dans le corps du redex de manière éviter toute capture de variable libre.

Voici un exemple de redex nécessitant un tel renommage.

image-20220106161618715

On voit que les occurrences de \(y\) situées dans le corps du redex sont liées. Par ailleurs, il y a une variable \(y\) libre dans l’argument du redex. C’est LE type de situation où un renommage est nécessaire. Or il est interdit de renommer une variables libres (cela change le sens d’un terme), donc ce sont les occurrences de \(y\) dans le corps du redex qu’il faut renommer.

On peut par exemple les remplacer par une variable \(w\). Le redex devient \((\lambda x.\lambda w.w x)\lambda t.y\) qui est équivalent au redex initial mais ne pose pas de problème de capture de variable libre lors de sa réduction.

Le résultat de la réduction est \(\lambda w.w(\lambda t . y)\). (L’ occurrence de la variable de liaison \(\underline x\) a été remplacée par l’argument \(\lambda t.y\)). Les parenthèses peuvent être supprimées sans changer la structure du terme, ce qui nous donne \(\lambda w.w \lambda t . y\).

Mais que ce serait-il passé sans le renommage ? Nous aurions obtenu \(\lambda y.y \lambda t . y\), qui a une structure différente puisque les trois occurrences de \(y\) sont liées.

Attention : Une variable peut être liée dans un terme tout en étant libre dans un des ses sous-termes, notamment dans un redex. Pour déterminer la nécessité d’un renommage, ce sont les variables libres dans le redex qui nous intéressent.

Par exemple, dans le terme \(\lambda y. [(\lambda x.\lambda y.y x)\lambda t.y]\), l’occurrence de la variable \(y\) située à la fin est liée par le lieur situé au début. Mais dans le scope du redex \((\lambda x.\lambda y.y x)\lambda t.y\), cette variable est libre (parce que son lieur n’est pas dans le redex). Il faut faire un renommage pour réduire ce redex.

La question à se poser est donc : Y-a-t-il dans le scope du redex (en masquant tout ce qui est autour), une variable qui est libre dans l’argument du redex et liées dans le corps du redex.

Exercice de découverte A.dec.x15

Le redex \((\lambda x . \lambda y. y x) (y a)\) nécessite-t-il un renommage ? Si oui, soulignez les occurrences de variables devant être renommées.

"Réponse"

Un renommage est nécessaire : \((\lambda x . \lambda \underline{y}. \underline{y} x) (y a)\).

Exercice de découverte A.dec.x16

Le redex \((\lambda t . a t) t\) nécessite-t-il un renommage ? Si oui, soulignez les occurrences de variables devant être renommées.

"Réponse"

Aucun renommage n’est nécessaire car il n’y a pas de lieur dans le corps du redex, qui est \(a t\).

Exercice de découverte A.dec.x17

Le redex \((\lambda w . a \lambda t.t) \lambda x . t x\) nécessite-t-il un renommage ? Si oui, soulignez les occurrences de variables devant être renommées.

"Réponse"

Ce cas est particulier : la variable de liaison du redex n’apparait pas dans le corps du redex, donc le résultat de la réduction sera le corps du redex non modifié. Comme l’argument ne sera pas recopié dans le résultat de l’évaluation, il n’y aura pas de problème de capture de sa variable libre. Un renommage n’est pas nécessaire.

A.dec8 : Évaluation d’un terme

L’évaluation d’un terme consiste à réaliser des réductions successives jusqu’à ce qu’il n’y ait plus aucun redex. Il peut arriver que l’évaluation ne s’arrête jamais, comme c’est le cas pour certains programmes dans tous les langages ayant la puissance d’expression de la machine de Turing.

Si, à certaines étapes de la réduction, il y a plusieurs redex, il faut en choisir un. Le résultat final sera toujours le même quelque soit le redex choisi.

À titre d’exemple, voici l’évaluation du terme \((\lambda x . x x)(\lambda a . a b) c\).

  1. On identifie un redex : \([(\lambda \underline{x} . \underline{x} \underline{x})(\lambda a . a b)] c\).
  2. On réduit ce redex : \((\lambda a . a b) (\lambda a . a b) c\).
  3. On identifie un redex : \([(\lambda \underline{a} . \underline{a} b) (\lambda a . a b)] c\). Attention, il y a un seul redex. Si vous en voyez deux, c’est que vous avez mal décomposé le terme.
  4. On réduit le redex : \(((\lambda a . a b) b)c\).
  5. On identifie un redex : \([(\lambda \underline{a} . \underline{a} b) b] c\).
  6. On réduit le redex : \((b b)c\), , qui peut être simplifié en \(bbc\).
  7. Il n’y a plus de redex, l’évaluation est terminée.

Exercice de découverte A.dec.x18

Détaillez l’évaluation du terme \((\lambda x . x x )(\lambda t . t a) b\).

"Réponse"

  1. redex : \([(\lambda \underline{x} . \underline{x} \underline{x} ) (\lambda t . t a)] b\).
  2. réduction : \(((\lambda t . t a) (\lambda t . t a)) b\).
  3. redex : \([(\lambda \underline{t} . \underline{t} a) (\lambda t . t a)] b\).
  4. réduction : \(((\lambda t . t a) a) b\).
  5. redex : \([(\lambda \underline{t} . \underline{t} a) a] b\).
  6. réduction : \((a a) b\), pouvant être simplifié en \(a a b\).
  7. plus de redex, l’évaluation est terminée.

Exercice de découverte A.dec.x19

Détaillez l’évaluation du terme \((\lambda x . \lambda y . x y ) y (\lambda x . x)\).

"Réponse"

  1. redex : \([(\lambda x . \lambda y . x y ) y] (\lambda x . x)\).
  2. renommage nécessaire : \([(\lambda x . \lambda t . x t ) y] (\lambda x . x)\).
  3. réduction : \((\lambda t . y t ) (\lambda x . x)\).
  4. redex : \([(\lambda t . y t ) (\lambda x . x)]\).
  5. réduction : \(y (\lambda x . x)\).
  6. plus de redex, fin de l’évaluation.

Activité d’entraînement A.ent

Cette activité est essentielle. C’est grâce à elle que vous apprendrez vraiment à comprendre et utiliser les notions vues précédemment. Elle se décompose en deux itérations : ent1, ent2. Vous devez réaliser au moins une itération et évaluer votre niveau de réussite.

Si vous avez eu beaucoup de difficulté à traiter les exercices et fait beaucoup d’erreurs, vous devrez traiter à nouveau l’activité de découverte précédente, en laissant passer au moins une nuit, avant de revenir à cette activité d’entraînement en réalisant à nouveau la première l’itération. Vous devez aussi essayer d’identifier les points de blocage et demander à votre enseignant de vous aider à les surmonter.

Si vous avez réussi certains exercices, mais échoué à d’autres, vous devrez d’abord comprendre ce qui vous a conduit à des erreurs et / ou ce qui vous a bloqué. Si vous avez des doutes, des difficultés, essayez de trouver les réponses dans les présentations et explications de l’activité de découverte précédente et demandez toute l’aide nécessaire à votre enseignant. Ensuite, vous devrez réaliser l’itération suivante après au moins une nuit de sommeil et au plus une semaine.

Si vous avez réussi presque tous les exercices et que vos rares erreurs sont dues à l’inattention, vous devriez revenir traiter l’itération suivante après un délai de plusieurs semaines.

Si besoin, après avoir traité la deuxième itération, vous pouvez revenir à la première. Vous pouvez aussi traiter des annales d’évaluations de l’unité d’enseignement.

Itération A.ent1

Exercice d’entrainement A.ent1.1

Décomposez les termes suivants en abstractions et applications, entourez les variables libres et connectez les variables liées entre elles.

  1. \(y\;\lambda x. \; \lambda y. \; x \; y\)
  2. \(\lambda y.\; x\; y\; \lambda t.\; x\; y\; \lambda x .\; z\).

Attention, toute variable située entre le symbole \(\lambda\) et le point est liée, même si elle n’est pas liée à d’autres occurrences( auquel cas elle n’est liée qu’à elle-même.

"Solution1"

image-20220106181203829

"Solution2"

image-20220106182628430

Exercice d’entrainement A.ent1.2

Pour chacune des paires de termes suivants, déterminez s’il y a équivalence.

  1. \(\lambda x. y x\) et \(\lambda z. y z\).
  2. \(\lambda x. y x\) et \(\lambda x. y y\).
  3. \(\lambda x.y x\) et \(\lambda x. z x\).
  4. \(\lambda x.\lambda y. y x\) et \(\lambda y.\lambda x. x y\).
  5. \(\lambda x. y \lambda z. z x\) et \(\lambda x . y \lambda y.y x\).
"Réponse1"

Oui, la variable \(x\) du premier terme est renommée \(z\) dans le deuxième.

"Réponse2"

Non, une seule des 2 occurrence de la variable liée du premier terme a été renommée dans le deuxième terme.

"Réponse3"

Non, la variable libre \(y\) du premier terme ne peut pas être renommée. Seules les variables liées peuvent être renommées sans changer le sens d’un terme.

"Réponse4"

Oui, un double renommage permet de passer d’un terme à l’autre.

"Réponse5"

Oui, la variable \(z\) du premier terme est renommée en \(y\) dans le deuxième, et la variable libre \(y\) reste libre et garde le même nom dans les deux termes.

Exercice d’entrainement A.ent1.3

Évaluez les termes suivants :

  1. \((\lambda x.\lambda y. xyx)(\lambda x. x)\)
  2. \((\lambda t.tt)\lambda x.x\)
  3. \(\lambda t.tt \lambda x.x\)
  4. \((\lambda t.tt)(\lambda x. \lambda y. x y)\)
"Réponse1"

  1. redex : \([(\lambda x.\lambda y. xyx)(\lambda x. x)]\)
  2. réduction : \(\lambda y. (\lambda x. x)y(\lambda x. x)\)
  3. redex : \(\lambda y. [(\lambda x. x)y](\lambda x. x)\)
  4. réduction : \(\lambda y. y(\lambda x. x)\)
  5. Fin.

"Réponse2"

  1. redex : \([(\lambda t.tt)\lambda x.x]\)
  2. réduction : \((\lambda x.x)(\lambda x.x)\)
  3. redex : \([(\lambda x.x)(\lambda x.x)]\)
  4. réduction : \(\lambda x.x\)
  5. Fin.

"Réponse3"

  1. Il n’y a pas de redex. Fin.

"Réponse4"

  1. redex : \([(\lambda tt)(\lambda x. \lambda y. x y)]\)
  2. réduction : \((\lambda x. \lambda y. x y)(\lambda x. \lambda y. x y)\)
  3. redex : \([(\lambda x. \lambda y. x y)(\lambda x. \lambda y. x y)]\)
  4. réduction : \(\lambda y. (\lambda x. \lambda y. x y) y\)
  5. redex : \(\lambda y. [(\lambda x. \lambda y. x y) y]\)
  6. renommage nécessaire : \(\lambda y. [(\lambda x. \lambda w. x w) y]\)
  7. réduction : \(\lambda y. (\lambda w. y w)\)
  8. Fin.

Itération A.ent2

Exercice d’entrainement A.ent2.1

Décomposez les termes suivants en abstractions et applications, entourez les variables libres et connectez les variables liées entre elles.

  1. \(\lambda t.\; x\; \lambda f .\; t\)
  2. \(\lambda x .\; x\; y\;(\;\lambda y.\;x\; y\;)(\;\lambda x.\;x\;)\).
"Solution1"

image-20220106183153009

"Solution2"

image-2022010618365744

Exercice d’entrainement A.ent2.2

Pour chacune des paires de termes suivants, déterminez s’il y a équivalence.

  1. \(a\lambda b . ab\) et \(a\lambda c . ac\)
  2. \(a\lambda b . ab\) et \(b\lambda c. bc\)
  3. \(\lambda x. \lambda f.f(fx)\) et \(\lambda x. \lambda f.ffx\)
  4. \(\lambda x. \lambda f.f(fx)\) et \(\lambda f. \lambda x.x(xf)\)
  5. \(\lambda x.yx\lambda x.x\) et \(\lambda x.y x\lambda y.y\)
"Réponse1"

Oui, on passe du premier terme au second en renommant \(b\) en \(c\).

"Réponse2"

Non, car la variable libre \(a\) du premier terme change de nom dans le deuxième.

"Réponse3"

Non, car l’applications est associative à gauche, donc \(ffx\) est équivalent à \((ff)x\) et pas à \(f(fx)\).

"Réponse4"

Oui car on peut passer du premier terme au deuxième par un double renommage.

"Réponse5"

Oui, les deux dernières occurrences de \(x\) dans le premier terme ne sont pas liées au deux premières et peuvent être renommées sans changer le sens du terme.

Exercice d’entrainement A.ent2.3

Évaluez le termes suivants :

  1. \((\lambda w.ww) a a\)
  2. \((\lambda x. \lambda y. xy)(\lambda x.x x)\)
  3. \(((\lambda x.x \lambda t.t)\lambda w.w) t\)
  4. \((\lambda w.\lambda y.a w) \lambda x.y b\)
"Réponse1"

  1. redex : \([(\lambda w.ww) a] a\)
  2. réduction : \(aaa\)
  3. Fin.

"Réponse2"

  1. redex : \([(\lambda x. \lambda y. xy)(\lambda x.x x)]\)
  2. réduction : \(\lambda y. (\lambda x.x x)y\)
  3. redex : \(\lambda y. [(\lambda x.x x)y]\)
  4. réduction : \(\lambda y. yy\)
  5. Fin.

"Réponse3"

  1. redex : \(([(\lambda x.x \lambda t.t)\lambda w.w]) t\)
  2. réduction : \(((\lambda w.w) \lambda t.t) t\)
  3. redex : \(([(\lambda w.w) \lambda t.t]) t\)
  4. réduction : \((\lambda t.t) t\)
  5. redex : \([(\lambda t.t) t]\)
  6. réduction : \(t\)
  7. Fin.

"Réponse4"

  1. redex : \([(\lambda w.\lambda y.a w) \lambda x.y b]\)
  2. renommage nécessaire : \([(\lambda w.\lambda t.a w) \lambda x.y b]\)
  3. réduction : \((\lambda t.a (\lambda x.y b))\)
  4. Fin.

Activité A.top

Cette activité propose des exercices de consolidation qui ne doivent être abordés que par les personnes apprenantes maîtrisant bien la partie A et les parties suivantes disponibles.

Par exemple, si les parties actuellement disponibles sont A et B, vous devez d’abord maîtriser la parie B avant de faire cette activité de consolidation de la partie A.

Itération A.top1

Exercice de consolidation A.top1

Dans les activités de découverte et d’entraînement, nous avons évalué des termes qui n’ont qu’un intérêt purement pédagogique, par leur simplicité, pour apprendre les mécanismes d’évaluation des \(\lambda\)-termes. Dans cet exercice, nous allons découvrir comment utiliser le \(\lambda\)-calcul pour évaluer des expressions Booléennes.

On peut représenter les Booléens vrai et faux de la manière suivante :

  • vrai : \((\lambda a. \lambda b. a)\), que nous noterons \(\boxed{T}\).
  • faux : \((\lambda a. \lambda b. b)\), que nous noterons \(\boxed{F}\).

Le \(\lambda\)-terme \((\lambda p.\lambda a.\lambda b.pab)\), noté \(\boxed{ite}\), encode la fonction if then else.

Question 1

Évaluez \(\boxed{ite}\; \boxed{T}\).

"Réponse"

On remplace \(\boxed{ite}\) par le terme correspondant. On a alors :

\(\boxed{ite}\; \boxed{T}\) = \((\lambda p.\lambda a.\lambda b.pab)\; \boxed{T}\)

= \((\lambda a.\lambda b.\boxed{T} \;ab)\)

= \((\lambda a.\lambda b.(\lambda a. \lambda b. a)ab)\)

= \((\lambda a.\lambda b.[(\lambda a. \lambda b. a)a]b)\)

= \((\lambda a.\lambda b.(\lambda b. a)b)\)

= \((\lambda a.\lambda b.[(\lambda b. a)b])\)

= \(\lambda a.\lambda b.a\) = \(\boxed{T}\).

Question 2

Évaluez \(\boxed{ite}\; \boxed{F}\).

"Réponse"

On remplace \(\boxed{ite}\) par le terme correspondant. On a alors :

\(\boxed{ite}\; \boxed{F}\) = \((\lambda p.\lambda a.\lambda b.pab)\; \boxed{F}\)

= \((\lambda a.\lambda b.\boxed{F} \;ab)\)

= \((\lambda a.\lambda b.(\lambda a. \lambda b. b)ab)\)

= \((\lambda a.\lambda b.[(\lambda a. \lambda b. b)a]b)\)

= \((\lambda a.\lambda b.(\lambda b. b)b)\)

= \((\lambda a.\lambda b.[(\lambda b. b)b])\)

= \(\lambda a.\lambda b.b\) = \(\boxed{F}\).

Donc \(\boxed{ite}\; \boxed{T}\) = \(\boxed{T}\) et \(\boxed{ite}\; \boxed{F}\) = \(\boxed{F}\) .

Soient \(A\) et \(B\) deux termes quelconques entouré de parenthèses.

Question 3

Évaluez \(\boxed{ite}\; \boxed{T}\; A\; B\).

"Réponse"

\(\boxed{ite}\; \boxed{T}\; A\; B\) = \((\lambda p.\lambda a.\lambda b.pab)\; \boxed{T}\; A\; B\)

= \([(\lambda p.\lambda a.\lambda b.pab)\; \boxed{T}\;]\; A\; B\)

= \((\lambda a.\lambda b. \;\boxed{T}\;ab)\; A\; B\)

= \([(\lambda a.\lambda b. \;\boxed{T}\;ab)] A\; B\)

= \((\lambda b. \;\boxed{T}\;A b) B\)

= \([(\lambda b. \;\boxed{T}\;A b) B]\)

= \(\boxed{T}\;A \; B\)

= \((\lambda a. \lambda b. a) A B\)

= \([(\lambda a. \lambda b. a) A] B\)

= \((\lambda b. A) B\)

= \(A\).

Concernant la dernière réduction, il faut comprendre que le corps du redex ne comporte pas d’occurrence de variable liée à sa variable de liaison \(b\). Il peut y avoir des occurrences d’une variable \(b\) dan le terme \(A\), mais soit elles sont liées dans le scope de \(A\), soit elles sont libres dans ce scope, mais alors elles auront été renommées à l’étape d’évaluation précédente.

On a la propriété : \(\boxed{ite}\; \boxed{T}\; A\; B\) = \(A\).

On peut aussi monter que \(\boxed{ite}\; \boxed{F}\; A\; B\) = \(B\).

On voit que ce codage de if then else permet de sélectionner un terme \(A\) ou \(B\) selon que la valeur Booléenne d’un terme de contrôle est vrai ou faux. Cette propriété permet de coder n’importe quelle fonction Booléenne.

Par exemple, la négation logique peut être codée par le terme :

\(\boxed{not}\) = \((\lambda x.\boxed{ite} \;x\; \boxed{F}\; \boxed{T}\;)\), qui peut s’écrire, pour une meilleure compréhension :

\((\lambda x.((\;\boxed{ite} \;x)\; \boxed{F}\;)\; \boxed{T}\;)\)

Question 4 : évaluez \(\boxed{not}\; \boxed{T}\) et \(\boxed{not}\; \boxed{F}\;\).

"Réponse"

\(\boxed{not}\; \boxed{T}\) = \((\lambda x.\;\boxed{ite} \;x\; \boxed{F}\; \boxed{T}\;)\; \boxed{T}\)

= \(\boxed{ite} \;\boxed{T}\; \boxed{F}\; \boxed{T}\)

= \(\boxed{F}\)

\(\boxed{not}\; \boxed{F}\) = \((\lambda x.\;\boxed{ite} \;x\; \boxed{F}\; \boxed{T}\;)\; \boxed{F}\)

= \(\boxed{ite} \;\boxed{F}\; \boxed{F}\; \boxed{T}\)

= \(\boxed{T}\)

Si vous êtes arrivé jusqu’ici, vous êtes en mesure de commencer à percevoir comment, en combinant des termes de \(\lambda\)-calcul, on peut concevoir des fonctions réalisant des traitements complexes.

Nous sommes au delà des objectifs pédagogiques de cette introduction au \(\lambda\)-calcul, mais on commence à comprendre qu’une abstraction représente le code permettant de calculer une fonction à un paramètre et qu’une application \(A D\) représente le calcul de l’image de \(D\) par cette fonction.

Par exemple, la définition \(\boxed{not}\) = \((\lambda x.\boxed{ite} \;x\; \boxed{F}\; \boxed{T}\;)\) dit que l’abstraction \(\boxed{not}\) est une fonction qui à tout Booléen \(x\) associe faux si \(x\) s’évalue à vrai et vrai si x s’évalue à faux.

On touche du doigt à la foi la puissance du \(\lambda\)-calcul, mais aussi l’extrême difficulté à spécifier des calculs complexes dans ce langage. On peut monter que toutes fonction calculable peut être implémentée en \(\lambda\)-calcul, mais le faire est trop compliqué pour avoir un intérêt pratique.

Par contre, le principe d’évaluation peut être mais en oeuvre dans des langages beaucoup plus faciles à exploiter, tels que CAML. Dans la suite de cet enseignement, nous utiliserons ce langage pour réaliser des programmes.