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