|
NOMBRES -
Curiosités, théorie et usages Accueil / Dictionnaire / Rubriques / Index / Références / Nouveautés ORIENTATION GÉNÉRALE - M'écrire - Édition du: 24/09/2005 |
|
-Ý- RUBRIQUE: INTELLIGENCE ARTIFICIELLE |
|||
|
§
Jeux |
§
Théorie |
||
|
§
Automate |
|||
|
§
|
§
|
||
|
Sommaire
de cette page >>> APPROCHE DU PEINTRE >>> TOUR D'HORIZON >>> RUDIMENTS DE
LANGAGE >>> CALCUL >>> QUELQUES
FORMULATIONS >>> PROPRIÉTÉS |
Pages sur sujets voisins §
Dualité §
Logique |
||
|
LAMBDA - CALCUL Base de
tous les raisonnements: §
Mathématiques §
Informatiques § Linguistiques |
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 ! |
-Ý- APPROCHE DU PEINTRE
|
§
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 |
-Ý- TOUR D'HORIZON
|
§
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 |
-Ý- RUDIMENTS DE LANGAGE
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] |
-Ý- CALCUL
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 |
|
-Ý- QUELQUES FORMULATIONS
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 … |
-Ý- PROPRIÉTÉS
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 |
|
Voir |
||
|
|
Sites |
§ Lambda calcul par Bruno Courcelle § Lambda-calcul et langages fonctionnels par Jean Goubault-Larrecq |
|
|
Livre |
§ Science & Vie de février 2002: "L'intelligence dévoile enfin sa vraie nature - Toute pensée est un calcul" |