SémanticlopédieAccueil | À propos | Aide | FAQ | Pages spéciales | Identification
Dictionnaire de sémantique
Catégories de la page: Opérations
Version imprimable | Avertissements

Lambda-calcul

Un article de Sémanticlopédie.

par Philippe Muller


Image:review.png
Relecture en cours
Les commentaires des relecteurs de cet article n'ont pas encore été intégrés. Il n'est peut-être donc pas dans sa forme définitive.


Sommaire

Introduction

Le Lambda-calcul est une façon abstraite de définir une fonction et ses arguments. Il formalise les opérations sur les fonctions elles-mêmes : c'est-à-dire des fonctions de fonctions.

Notation : la fonction carré : xx2 se note λxx2


{} Exemple de fonction de fonction, la fonction \circ de composition s'écrit λfλg⋅(f(g(x))) ou λf g⋅(f(g(x)))

Il faut noter que le symbole λ lie les variables qu'il introduit, on ne peut changer le nom de la variable liée dans la portée de l'expression sans changer toutes ses occurrences.


Syntaxe d'une formule lambda

soit V un ensemble de variables soit L l'ensemble des formules lambda construites à partir de V

  • si vV alors vL
  • si FL et GL alors (F G)∈L (composition )
  • si FL et vV alors λxF est une formule lambda (lambda-abstraction )
  • rien d'autre n'est une formule lambda


Conversion

  • le nom d'une variable liée n'a pas d'importance.
  • λx⋅(f x) a le même sens que λy⋅(f y)
  • il y a équivalence des lambda-termes par conversion des variables liées.


Application et réduction

  • l'application d'une fonction est juste la substitution du ou des arguments
  • xF)(y) = F[x / y]
  • ex: xx2)3 = 32
  • on peut aussi appliquer des variables libres (NB: ici le résultat n'est plus une formule lambda):

xλux2 + u)(y + z)(t) = (y + z)2 + t


Exemple d'utilisation en sémantique : compositionalité

Rappel express de logique

On considère pour l'exemple un langage de représentation logique, avec des termes, des prédicats, des propositions et des quantificateurs :

  • termes : variables xi, constantes cj, images de fonctions f(x)
  • propositions atomiques: prédicats P(x),Q(x1,x2,x3)
  • propositions construites avec ¬ (négation), (et), (ou), (implication matérielle): P(x)∧¬Q(y)
  • quantificateurs : , x[(oiseau(x)∧¬pingouin(x))→vole(x)]


Si l'on admet que la représentation de la phrase

Un homme dort

est la formule x (homme(x)∧dort(x))

Les questions à résoudre pour la construction du sens sont :

quelle est la contribution de chaque élément lexical à l'ensemble de la formule  ?

quelles sont les règles de combinaison de ces éléments qui donnent la formule finale ?


Prenons une petite grammaire hors-contexte comme exemple

S NP V
NP D N
N "homme"
D "un"
V "dort"
Forme Logique de "un" x...
FL de "dort" prédicat
FL de "homme" prédicat

Le lambda-calcul est une façon abstraite de définir une fonction et ses arguments, on va ici n'utiliser que des fonctions dont le résultat final est une formule logique du premier ordre.

ex: λx(oiseau(x)) est la représentation lambda du prédicat oiseau vu comme une fonction booléenne.

Par composition et réduction de formules lambda

λx(oiseau(x))](y) donne oiseau(y).

Les arguments des fonctions peuvent être des prédicats ou même des formules :

λP(∃x(oiseau(x)∧P(x)).

Exemple (suite)

Il faut considérer la sémantique des expressions comme des lambda-abstractions en attente de leurs arguments. Ainsi la sémantique d'un verbe peut être :

[\![dort]\!] = \lambda x\cdot dort(x)

Celle d'un nom commun est similaire :

[\![homme]\!] = \lambda x\cdot homme(x)

Et celle du déterminant peut aussi s'écrire :

[\![un]\!] = \lambda P\lambda R\cdot (\exists x \; P(x) \land R(x))

Le processus de traduction correspond à des schémas d'application liées aux règles de la grammaire :

category1(sem:f(semNP,semVP)) categorie2(sem:semNP) categorie3(sem:semVP)

avec ici, f = application lambda.


En faisant toujours l'application de categorie3 comme argument de categorie2 et en reportant les applications successives sur l'arbre d'analyse syntaxique, on voit :



Rechercher
Naviguer
Accueil
Communauté
Actualités
Modifications récentes
Une page au hasard
Aide
Contenu : Notions | Outils | Théories | Glossaires
Éditer
Modifier cette page
Aide
Page d'option
Page de discussion
Ajouter un commentaire
Version imprimable
Page d'information
Comment citer cet article
Historique de la page
Pages liées
Suivi des liens
Mes options
Identification
Pages spéciales
Nouvelles pages
Liste des images
Statistiques
Rapport d'erreurs
Et plus...