|
Édition du: 18/04/2026 |
|
INDEX |
LOGIQUE et IA |
|||||
|
Jeux |
||||||
|
|
|
|||||
|
Avril 2026 – pdf – 234 pages |
|
|||||
Faites un double-clic pour un retour
en haut de page
|
LAMBDA
- CALCUL Base de tous les raisonnements:
|
||
|
|
Sommaire de
cette page >>> Approche
du peintre >>> Tour
d'horizon >>>
Rudiments de langage >>>
Calcul >>>
Quelques formulations >>>
Propriétés |
Débutants Glossaire |
Anglais : Lambda-calculus
|
Avertissement N'étant
pas un spécialiste de ce domaine, ce
qui suit permet de toucher du doigt ce sujet. Sans
prétention ! |
|
§ Imaginons une
méthode pour donner des consignes précises aux peintres § Un peu
compliquée, mais efficace |
||
|
Appliquer la consigne
"PEINDRE EN COULEUR" en utilisant le ROUGE |
||
|
Voici l'illustration |
||
|
|
||
|
Traduction en lambda-langage |
||
|
|
||
|
Écriture en lambda-calcul |
||
|
(l x . peindre en x ) rouge |
qui
veut dire ® |
peindre en rouge |
Mise en cascade
|
Un seul niveau |
|
|
(l couleur |
|
peindre en couleur l'objet |
|
) rouge |
|
|
|
Application |
|
|
(l couleur |
|
peindre en couleur l'objet |
|
)
rouge |
|
|
|
Réduction |
|
|
|
|
peindre en rouge l'objet |
|
|
|
|
|
Deux niveaux |
((l objet . |
|
l couleur |
|
peindre en couleur l'objet |
|
) rouge |
|
) mur |
|
Application 1 |
((l objet . |
|
l couleur |
|
peindre en couleur l'objet |
|
)
rouge |
|
) mur |
|
Réduction1 |
|
|
( l couleur |
|
peindre en couleur le mur |
|
)
rouge |
|
|
|
Application 2 |
|
|
( l couleur |
|
peindre en couleur le mur |
|
)
rouge |
|
|
|
Réduction 2 |
|
|
|
|
peindre en rouge le mur |
|
|
|
|
|
§ Avec ces seules
instructions: o
applications et réductions o
sur des variables § Il est possible
de reformuler tous les fonctions mathématiques § et même, le
raisonnement dans tous les domaines o
linguistique o
mathématique o
informatique |
|
§ De même qu'en
informatique, o
écrire des programmes en binaire est fastidieux § En
lambda-calcul aussi, on a imaginé o
des langages de plus haut niveau, plus faciles à
manipuler |
|
§ Le
lambda-calcul est une sorte de langage à syntaxe élémentaire qui permet
d'exprimer toutes les fonctions calculables § Le
lambda-calcul est considéré comme la base mathématique de tous les langages
de programmation § Formalisation
développée par Alonzo Church
et Stephen Kleene en 1932 § Étudié comme
langage universel par Jean-Louis Krivine |
|
§ Le langage
correspond à l'application d'une fonction à ses arguments § Toute entité
est formalisée par o
soit une variable o
soit l'application d'une fonction à une autre o
soit comme l'abstraction (réduction) d'une fonction |
|
Principe du langage avec un exemple |
|
|
§ Une variable x
|
égale à 7 |
|
§ Un
fonction de x dite lx |
égale à 3x + 5 |
|
§ Lambda
expression |
lx . 3x + 5 |
|
§ Une application
(abstraction) |
(lx . 3x + 5) 7 |
|
§ Sa réduction
(calcul) |
( 3x + 5) [7/x] = 3 x 7 + 5 = 26 |
|
Note: on a utilisé 3x + 5 alors que "addition
et multiplication" ne sont pas encore définies; C'est
un exemple |
|
|
§ Le
lambda-calcul est la base, surtout, des langages fonctionnels comme o LISP o Haskell (logo d' -) o
Miranda o
ML , OCaml § Il est aussi
utilisé comme métalangage o
pour obtenir des définitions formelles |
|
§ Langage fonctionnel: programmation
en écrivant des fonctions qui appellent d'autres fonctions, qui appellent des
fonctions... (Lisp pur, Miranda,
Haskell …) § Langage impératif :
langage de programmation décrivant le parcours d'un algorithme précis
(Pascal, C++ …) § Langage impératif fonctionnel: Lisp, ML Voir
exemples en Programmation |
Un niveau
|
§ Variable
objet |
mur |
x = a |
|
§ Fonction |
peindre en bleu |
f |
|
§ Lambda-fonction |
l objet . peindre en bleu l'objet |
lx . f |
|
§ Lambda-abstraction |
(l objet . peindre en bleu l'objet) mur |
(lx . f) a |
|
§ Réduction |
peindre en bleu le mur |
f [a/objet] |
Deux niveaux en cascade
|
Données |
|
|
|
§ Variable
objet § Variable
couleur |
mur rouge |
x = a y = b |
|
§ Fonction |
peindre en couleur
l'objet |
f |
|
Lambda
de premier niveau |
||
|
§ Lambda-fonction |
l couleur . l objet . peindre en couleur l'objet |
ly . lx . f |
|
§ Lambda-abstraction |
(l couleur . l objet . peindre en couleur l'objet) rouge |
(ly . lx . f) b |
|
§ Réduction |
peindre en rouge l'objet |
lx . f [b/couleur] |
|
Lambda
avec les deux niveaux |
||
|
§ Application
complète |
((l couleur . l objet . peindre en couleur l'objet) rouge) mur |
((ly . lx . f) b) a |
|
§ Réduction
d'un niveau |
(l objet . peindre en rouge l'objet) mur |
(lx . f [b/couleur]) a |
|
§ Nouvelle
application |
peindre en rouge le mur |
f [b/couleur,
a/objet] |
Alpha réduction
|
lx. E ® lz {z/x} E |
P = …x … x … P = …z … z … |
|
§ Dans la
fonction E, tous les x peuvent être remplacé par z |
|
|
lx . peindre objet ® peindre le mur |
|
Bêta réduction
|
(lx. P) Q ® [Q/x]
P |
P = …x … x … P = …Q … Q … |
|
§ Dans la
fonction P, tous les x peuvent être remplacé par Q |
|
|
(lx . x) toto ® toto |
|
|
Exemple en cascade |
|
|
( (lx . ly . x)
singe ) cacahuète ® ? § Expression
entre parenthèses rouges: ( (lx . ly . x) singe ) cacahuète ® (ly . cacahuète)
singe § En
effet, il faut remplacer dans la fonction x tout ce qui est x
par cacahuète § Nous
avons obtenu: (ly . cacahuète) singe § Dans
la fonction cacahuète nous devons remplacer tout y par singe § Or, il
n'y a pas singe dans cacahuète § La
fonction ne peut pas de réduire en une expression en "singe" § Elle
reste dans son état général de cacahuète (ly . cacahuète) singe ® cacahuète |
|
Fonctions duales
|
VRAI |
FAUX |
|
§ Reprenons
l'exemple précédent ( (lx . ly . x)
b )
a ® (ly . a) b ® a |
§ Idem
avec une nuance ( (lx . ly . y)
b )
a ® (ly . y) b ® b |
|
§ Cette
application sur a donne toujours a § C'est
la fonction "vrai" |
§ Cette
application sur a donne toujours b § C'est
la fonction "faux" |
|
Vrai =
(lx . ly . x) |
Faux =
(lx . ly . y) |
Définition des nombres
|
0, 1, 2, … |
|
§ La formulation
fait allusion à la répétition de l'application 0 = lf . lx . x 1 = lf . lx . (f) x 2 = lf . lx . (f) (f) x 3 = lf . lx . (f) (f) (f) x … |
Thèse de Church
|
§ Toute fonction calculable peut l'être avec un ensemble réduit
d'instructions § Affirmation philosophique indémontrable, base de toute
l'algorithmique |
Théorème de Church-Rosser
|
§ Le résultat
final de substitutions lors des réductions ne dépend pas de l'ordre dans
lequel ces substitutions sont effectuées |
Modèle de calcul universel
|
§ Tout calcul
exprimable en machine de Turing est aussi exprimable en lambda-calcul |
Haut de page
(ou double-clic)
|
Voir |
|
|
Sites |
|
|
Livre |
"L'intelligence dévoile enfin sa vraie nature - Toute pensée est un calcul" |
|
Cette page |