Accueil Orientation générale Barre de recherche

DicoNombre DicoMot Math DicoCulture

Atlas des maths Rubriques Index alphabétique

Nouveautés Actualités Références

Édition du: 13/01/2023 M'écrire Brèves de Maths

INDEX Logique Algorithme Programmation Multimédia	LOGIQUE et IA
	Introduction	Algorithmes	Jeux	Théorie
	Humaine	Machine de Turing	Systèmes experts	Rx neuronaux
	Programmation	Automate	Lambda-calcul	Robots
	Historique	Algorithmes TOP 15	ChatGPT	IA Avancée

LAMBDA - CALCUL Base de tous les raisonnements: Mathématiques, Informatiques, et Linguistiques.
	Sommaire de cette page >>> Approche du peintre >>> Tour d'horizon >>> Rudiments de langage >>> Calcul >>> Quelques formulations >>> Propriétés	Débutants Logique Glossaire Logique

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	Systèmes experts Réseaux neuronaux Multimédia Événements chronologiques Dualité Logique Outils de la logique Incomplétude Raisonnement Énigmes et paradoxes
Sites	Lambda calcul par Bruno Courcelle Lambda-calcul et langages fonctionnels par Jean Goubault-Larrecq An Introduction to Lambda Calculus and Scheme
Livre	Science & Vie de février 2002: "L'intelligence dévoile enfin sa vraie nature - Toute pensée est un calcul"
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Logique/IAlambda.htm