Variables libres et variables liées - Free variables and bound variables

En mathématiques , et dans d'autres disciplines impliquant des langages formels , y compris la logique mathématique et l' informatique , une variable libre est une notation (symbole) qui spécifie les endroits dans une expression où la substitution peut avoir lieu et n'est pas un paramètre de cette expression ou de toute autre expression conteneur. Certains livres plus anciens utilisent les termes variable réelle et variable apparente pour variable libre et variable liée, respectivement. L'idée est liée à un espace réservé (un symbole qui sera plus tard remplacé par une valeur) ou à un caractère générique qui représente un symbole non spécifié.

En programmation informatique , le terme variable libre fait référence aux variables utilisées dans une fonction qui ne sont ni des variables locales ni des paramètres de cette fonction. Le terme variable non locale est souvent synonyme dans ce contexte.

Une variable liée est une variable qui était auparavant libre , mais qui a été liée à une valeur spécifique ou à un ensemble de valeurs appelé domaine de discours ou univers . Par exemple, la variable x devient une variable liée lorsque nous écrivons :

Pour tout x , ( x + 1) 2 = x 2 + 2 x + 1 .

ou

Il existe x tel que x 2 = 2 .

Dans l'une ou l'autre de ces propositions, il importe peu logiquement que x ou une autre lettre soit utilisée. Cependant, il pourrait être déroutant d'utiliser à nouveau la même lettre ailleurs dans une proposition composée . C'est-à-dire que les variables libres deviennent liées, puis, dans un sens, cessent d'être disponibles en tant que valeurs de remplacement pour d'autres valeurs dans la création de formules.

Le terme « variable muette » est aussi parfois utilisé pour une variable liée (plus souvent en mathématiques générales qu'en informatique), mais cette utilisation peut créer une ambiguïté avec la définition des variables muettes en analyse de régression .

Exemples

Avant d'énoncer une définition précise de variable libre et variable liée , voici quelques exemples qui rendent peut-être ces deux concepts plus clairs que la définition ne le ferait :

Dans l'expression

n est une variable libre et k est une variable liée ; par conséquent la valeur de cette expression dépend de la valeur de n , mais il n'y a rien appelé k dont elle puisse dépendre.

Dans l'expression

y est une variable libre et x est une variable liée ; par conséquent la valeur de cette expression dépend de la valeur de y , mais il n'y a rien d'appelé x dont elle puisse dépendre.

Dans l'expression

x est une variable libre et h est une variable liée ; par conséquent la valeur de cette expression dépend de la valeur de x , mais il n'y a rien appelé h dont elle puisse dépendre.

Dans l'expression

z est une variable libre et x et y sont des variables liées, associées à des quantificateurs logiques ; par conséquent, la valeur logique de cette expression dépend de la valeur de z , mais il n'y a rien d'appelé x ou y dont elle puisse dépendre.

Plus largement, dans la plupart des preuves, nous utilisons des variables liées. Par exemple, la preuve suivante montre que tout carré d'entier pair est divisible par

Soit un entier pair positif. Alors il existe un entier tel que . Puisque , on a divisible par

non seulement k mais aussi n ont été utilisés comme variables liées dans leur ensemble dans la preuve.

Opérateurs de liaison de variables

Ce qui suit

sont des opérateurs de liaison de variables courants . Chacun d'eux lie la variable x pour un ensemble S .

Notez que beaucoup d'entre eux sont des opérateurs qui agissent sur les fonctions de la variable liée. Dans des contextes plus compliqués, de telles notations peuvent devenir maladroites et déroutantes. Il peut être utile de passer à des notations qui rendent la liaison explicite, comme

pour des sommes ou

pour la différenciation.

Explication formelle

Arbre résumant la syntaxe de l'expression

Les mécanismes de liaison de variables se produisent dans différents contextes en mathématiques, en logique et en informatique. Dans tous les cas, cependant, ce sont des propriétés purement syntaxiques des expressions et des variables qu'elles contiennent. Pour cette section, nous pouvons résumer la syntaxe en identifiant une expression avec un arbre dont les nœuds feuilles sont des variables, des constantes, des constantes de fonction ou des constantes de prédicat et dont les nœuds non feuilles sont des opérateurs logiques. Cette expression peut ensuite être déterminée en effectuant un parcours inordonné de l'arbre. Les opérateurs de liaison de variables sont des opérateurs logiques qui apparaissent dans presque tous les langages formels. Un opérateur de liaison Q prend deux arguments : une variable v et une expression P , et lorsqu'il est appliqué à ses arguments produit une nouvelle expression Q( v , P ). Le sens des opérateurs de liaison est fourni par la sémantique du langage et ne nous concerne pas ici.

La liaison de variable concerne trois choses : une variable v , un emplacement a pour cette variable dans une expression et un nœud non feuille n de la forme Q( v , P ). Remarque : nous définissons un emplacement dans une expression comme un nœud feuille dans l'arbre syntaxique. La liaison de variable se produit lorsque cet emplacement est en dessous du nœud n .

Dans le lambda calcul , xest une variable liée dans le terme M = λx. Tet une variable libre dans le terme T. Nous disons xest lié Met libre dans T. Si Tcontient un sous-terme, λx. Ualors xest un rebond dans ce terme. On dit que cette reliure interne imbriquée x« fait de l'ombre » sur la reliure externe. Les occurrences de xin Usont des occurrences libres du nouveau x.

Les variables liées au niveau supérieur d'un programme sont des variables techniquement libres dans les termes auxquels elles sont liées, mais sont souvent traitées spécialement car elles peuvent être compilées comme des adresses fixes. De même, un identifiant lié à une fonction récursive est aussi techniquement une variable libre dans son propre corps mais est traité spécialement.

Un terme fermé est un terme ne contenant aucune variable libre.

Expressions de fonction

Pour donner un exemple mathématique, considérons une expression qui définit une fonction

t est une expression. t peut contenir certains, tous ou aucun des x 1 , …, x n et il peut contenir d'autres variables. Dans ce cas, nous disons que la définition de la fonction lie les variables x 1 , …, x n .

De cette manière, les expressions de définition de fonction du type indiqué ci-dessus peuvent être considérées comme l' opérateur de liaison de variable, analogue aux expressions lambda de lambda calculus . D'autres opérateurs de liaison, comme le signe de sommation , peuvent être considérés comme des fonctions d'ordre supérieur s'appliquant à une fonction. Ainsi, par exemple, l'expression

pourrait être traité comme une notation pour

où est un opérateur avec deux paramètres : une fonction à un paramètre et un ensemble sur lequel évaluer cette fonction. Les autres opérateurs énumérés ci-dessus peuvent être exprimés de manière similaire ; par exemple, le quantificateur universel peut être considéré comme un opérateur qui évalue la conjonction logique de la fonction booléenne P appliquée sur l'ensemble (éventuellement infini) S .

Langage naturel

Lorsqu'elles sont analysées en sémantique formelle , les langues naturelles peuvent être considérées comme ayant des variables libres et liées . En anglais, les pronoms personnels comme il , elle , ils , etc. peuvent agir comme des variables libres.

Lisa a trouvé son livre.

Dans la phrase ci-dessus, le pronom possessif her est une variable libre. Il peut faire référence à la Lisa mentionnée précédemment ou à toute autre femme. En d'autres termes, son livre pourrait faire référence au livre de Lisa (une instance de coréférence ) ou à un livre qui appartient à une femme différente (par exemple, le livre de Jane). Quel que soit le référent de son est peut être établie en fonction de la situation ( par exemple pragmatique contexte). L'identité du référent peut être montrée à l'aide d'indices de coindexation où i indique un référent et j indique un deuxième référent (différent de i ). Ainsi, la phrase que Lisa a trouvée dans son livre a les interprétations suivantes :

Lisa je l'ai trouvée je livre. (interprétation #1 : elle = de Lisa )
Lisa j'ai trouvé son livre j . (interprétation #2 : her = d'une femelle qui n'est pas Lisa)

La distinction n'est pas purement d'intérêt académique, car certaines langues ont en fait des formes différentes pour her i et her j : par exemple, le norvégien et le suédois traduisent coreferent her i par sin et non coreferent her j par hennes .

L'anglais permet de spécifier la coréférence, mais c'est facultatif, car les deux interprétations de l'exemple précédent sont valides (l'interprétation agrammaticale est indiquée par un astérisque) :

Lisa, je l'ai trouvée dans mon propre livre. (interprétation #1 : elle = de Lisa )
* Lisa i a trouvé son j propre livre. (interprétation #2 : her = d'une femelle qui n'est pas Lisa)

Cependant, les pronoms réfléchis , tels que lui - même , elle - même , eux - mêmes , etc., et les pronoms réciproques , tels que les autres , agissent comme des variables liées. Dans une phrase comme celle-ci :

Jane blessée elle - même .

la réflexive elle-même ne peut se référer qu'à l' antécédent mentionné précédemment , dans ce cas Jane , et ne peut jamais se référer à une personne féminine différente. Dans cet exemple, la variable elle - même est liée au nom Jane qui apparaît en position de sujet . Indiquant la coindexation, la première interprétation avec Jane et elle - même coindexées est permise, mais l'autre interprétation où elles ne sont pas coindexées est agrammaticale :

Jane je me suis blessée je . (interprétation #1 : elle - même = Jane )
* Jane je me suis fait mal j . (interprétation n°2 : elle - même = une femme qui n'est pas Jane)

Notez que la liaison de coréférence peut être représentée à l'aide d'une expression lambda comme mentionné dans la section Explication formelle précédente . La phrase avec le réflexif pourrait être représentée comme

x . x blessé x ) Jane

dans laquelle Jane est l'argument référent du sujet et λx.x bless x est la fonction de prédicat (une abstraction lambda) avec la notation lambda et x indiquant à la fois le sujet sémantique et l'objet sémantique de la phrase comme étant liés. Cela renvoie l'interprétation sémantique JANE JANE mal avec JANE être la même personne.

Les pronoms peuvent également se comporter différemment. Dans la phrase ci-dessous

Ashley a frappé son .

le pronom her ne peut se référer qu'à une femme qui n'est pas Ashley. Cela signifie qu'il ne peut jamais avoir une signification réflexive équivalente à Ashley s'est frappée . Les interprétations grammaticales et agrammaticales sont :

* Ashley i l' a frappée i . (interprétation #1 : elle = Ashley )
Ashley je l'ai frappée j . (interprétation #2 : elle = une femelle qui n'est pas Ashley)

La première interprétation est impossible. Seule la seconde interprétation est permise par la grammaire.

Ainsi, on peut voir que les réflexifs et les réciproques sont des variables liées (appelées techniquement anaphores ) tandis que les vrais pronoms sont des variables libres dans certaines structures grammaticales mais des variables qui ne peuvent pas être liées dans d'autres structures grammaticales. Les phénomènes de liaison trouvés dans les langues naturelles étaient particulièrement importants pour le gouvernement syntaxique et la théorie de la liaison (voir aussi : Liaison (linguistique) ).

Voir également

Les références

  • Thompson, Simon (1991). Théorie des types et programmation fonctionnelle . Wokingham, Angleterre : Addison-Wesley. ISBN 0201416670. OCLC  23287456 .