Variáveis ​​livres e variáveis ​​associadas - Free variables and bound variables

Em matemática , e em outras disciplinas envolvendo linguagens formais , incluindo lógica matemática e ciência da computação , uma variável livre é uma notação (símbolo) que especifica lugares em uma expressão onde a substituição pode ocorrer e não é um parâmetro desta ou de qualquer expressão contêiner. Alguns livros mais antigos usam os termos variável real e variável aparente para variável livre e variável limitada, respectivamente. A ideia está relacionada a um espaço reservado (um símbolo que mais tarde será substituído por algum valor), ou um caractere curinga que representa um símbolo não especificado.

Na programação de computadores , o termo variável livre se refere a variáveis usadas em uma função que não são variáveis ​​locais nem parâmetros dessa função. O termo variável não local é freqüentemente um sinônimo neste contexto.

Uma variável vinculada é uma variável que antes era livre , mas foi vinculada a um valor específico ou conjunto de valores denominado domínio do discurso ou universo . Por exemplo, a variável x torna-se uma variável limitada quando escrevemos:

Para todo x , ( x + 1) ² = x ² + 2 x + 1 .

ou

Existe x tal que x ² = 2 .

Em qualquer uma dessas proposições, não importa logicamente se x ou alguma outra letra é usada. No entanto, pode ser confuso usar a mesma letra novamente em alguma proposição composta . Ou seja, as variáveis ​​livres tornam-se limitadas e, em certo sentido, deixam de estar disponíveis como valores substitutos para outros valores na criação de fórmulas.

O termo "variável fictícia" também é algumas vezes usado para uma variável limitada (mais frequentemente na matemática geral do que na ciência da computação), mas esse uso pode criar uma ambigüidade com a definição de variáveis ​​fictícias na análise de regressão .

Exemplos

Antes de declarar uma definição precisa de variável livre e variável limitada , a seguir estão alguns exemplos que talvez tornem esses dois conceitos mais claros do que a definição faria:

Na expressão

${\ displaystyle \ sum _ {k = 1} ^ {10} f (k, n),}$

n é uma variável livre ek é uma variável limitada; conseqüentemente, o valor dessa expressão depende do valor de n , mas não há nada chamado k de que possa depender.

Na expressão

${\ displaystyle \ int _ {0} ^ {\ infty} x ^ {y-1} e ^ {- x} \, dx,}$

y é uma variável livre e x é uma variável limitada; conseqüentemente, o valor dessa expressão depende do valor de y , mas não há nada chamado x de que possa depender.

Na expressão

${\ displaystyle \ lim _ {h \ rightarrow 0} {\ frac {f (x + h) -f (x)} {h}},}$

x é uma variável livre eh é uma variável limitada; conseqüentemente, o valor dessa expressão depende do valor de x , mas não há nada chamado h de que possa depender.

Na expressão

${\ displaystyle \ forall x \ \ exists y \ {\ Big [} \ varphi (x, y, z) {\ Big]},}$

z é uma variável livre e x e y são variáveis ​​limitadas, associadas a quantificadores lógicos ; conseqüentemente, o valor lógico dessa expressão depende do valor de z , mas não há nada chamado x ou y do qual ela possa depender.

Mais amplamente, na maioria das provas, usamos variáveis ​​ligadas. Por exemplo, a seguinte prova mostra que cada quadrado de inteiro par é divisível por${\ displaystyle 4}$

Let Ser um número inteiro positivo par. Então, há um número inteiro tal que . Desde então , temos divisíveis por${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle n = 2k}$${\ displaystyle n ^ {2} = 4k ^ {2}}$${\ displaystyle n ^ {2}}$${\ displaystyle 4}$

não apenas k, mas também n foram usados ​​como variáveis ​​limitadas como um todo na prova.

Operadores de ligação variável

A seguir

${\ displaystyle \ sum _ {x \ in S} \ quad \ quad \ prod _ {x \ in S} \ quad \ quad \ int _ {0} ^ {\ infty} \ cdots \, dx \ quad \ quad \ lim _ {x \ a 0} \ quad \ quad \ forall x \ quad \ quad \ existe x}$

são alguns operadores de vinculação de variáveis comuns . Cada um deles se liga a variável X para um conjunto S .

Observe que muitos desses são operadores que atuam nas funções da variável associada. Em contextos mais complicados, essas notações podem se tornar estranhas e confusas. Pode ser útil mudar para notações que tornam a ligação explícita, como

${\ displaystyle \ sum _ {1, \ ldots, 10} \ left (k \ mapsto f (k, n) \ right)}$

para somas ou

${\ displaystyle D \ left (x \ mapsto x ^ {2} + 2x + 1 \ right)}$

para diferenciação.

Explicação formal

Árvore que resume a sintaxe da expressão ${\ displaystyle \ forall x \, ((\ existe y \, A (x)) \ vee B (z))}$

Os mecanismos de ligação de variáveis ​​ocorrem em diferentes contextos em matemática, lógica e ciência da computação. Em todos os casos, entretanto, eles são propriedades puramente sintáticas de expressões e variáveis ​​neles. Para esta seção, podemos resumir a sintaxe identificando uma expressão com uma árvore cujos nós folha são variáveis, constantes, constantes de função ou constantes de predicado e cujos nós não folha são operadores lógicos. Essa expressão pode então ser determinada fazendo uma travessia inordenada da árvore. Os operadores de vinculação de variáveis ​​são operadores lógicos que ocorrem em quase todas as linguagens formais. Um operador de ligação Q leva dois argumentos: uma variável ve uma expressão P e, quando aplicado a seus argumentos, produz uma nova expressão Q ( v , P ). O significado dos operadores de ligação é fornecido pela semântica da linguagem e não nos interessa aqui.

A vinculação de variável relaciona três coisas: uma variável v , uma localização a para aquela variável em uma expressão e um nó não folha n da forma Q ( v , P ). Observação: definimos um local em uma expressão como um nó folha na árvore sintática. A vinculação de variável ocorre quando esse local está abaixo do nó n .

No cálculo lambda , xé uma variável limitada no termo M = λx. Te uma variável livre no termo T. Dizemos que xestá ligado Me livre T. Se Tcontiver um subtermo, λx. Uentão xé rebote neste termo. xDiz-se que essa ligação interna aninhada de "sombreia" a ligação externa. As ocorrências de xin Usão ocorrências livres do novo x.

As variáveis ​​vinculadas ao nível superior de um programa são variáveis ​​tecnicamente livres dentro dos termos aos quais estão vinculadas, mas geralmente são tratadas de maneira especial porque podem ser compiladas como endereços fixos. Da mesma forma, um identificador vinculado a uma função recursiva também é tecnicamente uma variável livre dentro de seu próprio corpo, mas é tratado de maneira especial.

Um termo fechado é aquele que não contém variáveis ​​livres.

Expressões de função

Para dar um exemplo da matemática, considere uma expressão que define uma função

${\ displaystyle f = \ left [(x_ {1}, \ ldots, x_ {n}) \ mapsto t \ right]}$

onde t é uma expressão. t pode conter alguns, todos ou nenhum dos x ₁ ,…, x _n e pode conter outras variáveis. Nesse caso, dizemos que a definição da função vincula as variáveis x ₁ ,…, x _n .

Dessa maneira, as expressões de definição de função do tipo mostrado acima podem ser consideradas como o operador de ligação variável, análogo às expressões lambda do cálculo lambda . Outros operadores de ligação, como o sinal de soma , podem ser considerados como funções de ordem superior que se aplicam a uma função. Então, por exemplo, a expressão

${\ displaystyle \ sum _ {x \ in S} {x ^ {2}}}$

poderia ser tratada como uma notação para

${\ displaystyle \ sum _ {S} {(x \ mapsto x ^ {2})}}$

onde é um operador com dois parâmetros - uma função de um parâmetro e um conjunto para avaliar essa função. Os outros operadores listados acima podem ser expressos de maneiras semelhantes; por exemplo, o quantificador universal pode ser pensado como um operador que é avaliada como o conjunto lógico da função de valor booleano P aplicada sobre a (possivelmente infinito) conjunto S . ${\ displaystyle \ sum _ {S} {f}}$ ${\ displaystyle \ forall x \ in S \ P (x)}$

Linguagem natural

Quando analisadas na semântica formal , as linguagens naturais podem ser vistas como tendo variáveis livres e limitadas . Em inglês, pronomes pessoais como he , she , they , etc. podem atuar como variáveis ​​livres.

Lisa encontrou seu livro.

Na frase acima, o pronome possessivo ela é uma variável livre. Pode se referir à mencionada Lisa ou a qualquer outra mulher. Em outras palavras, seu livro pode estar se referindo ao livro de Lisa (uma instância de co-referência ) ou a um livro que pertence a uma mulher diferente (por exemplo, o livro de Jane). Quem quer que o referente de seu é pode ser estabelecida de acordo com a situação (ou seja pragmática contexto). A identidade do referente pode ser mostrada usando subscritos de indexação de moeda, onde i indica um referente ej indica um segundo referente (diferente de i ). Assim, a frase que Lisa encontrou em seu livro tem as seguintes interpretações:

Lisa _i encontrou- _i livro. (interpretação # 1: dela = de Lisa )

Lisa _i encontrou- _j livro. (interpretação # 2: dela = de uma mulher que não é Lisa)

A distinção não é de interesse puramente acadêmico, já que algumas línguas têm, na verdade, formas diferentes para her _i e her _j : por exemplo, norueguês e sueco traduzem coreferent her _i as sin e noncoreferent her _j como hennes .

O inglês permite especificar a co-referência, mas é opcional, pois ambas as interpretações do exemplo anterior são válidas (a interpretação não gramatical é indicada com um asterisco):

Lisa _i encontrou- _i próprio livro. (interpretação # 1: dela = de Lisa )

* Lisa _i encontrou- _j próprio livro. (interpretação # 2: dela = de uma mulher que não é Lisa)

No entanto, pronomes reflexivos , como ele mesmo , ela , eles mesmos , etc., e pronomes recíprocos , como um ao outro , agem como variáveis ​​limitadas. Em uma frase como a seguinte:

Jane se machucou .

a própria reflexiva só pode se referir ao antecedente mencionado anteriormente , neste caso Jane , e nunca pode se referir a uma pessoa diferente do sexo feminino. Neste exemplo, a própria variável está ligada ao substantivo Jane que ocorre na posição de sujeito . Indicando a indexação monetária , a primeira interpretação com Jane e ela mesma indexada é permitida, mas a outra interpretação onde eles não são indexados monetariamente não é gramatical :

Jane, _{eu me} machuquei _i . (interpretação # 1: ela mesma = Jane )

* Jane, _{eu me} machuquei _j . (interpretação # 2: ela mesma = uma mulher que não é Jane)

Observe que a ligação de correferência pode ser representada usando uma expressão lambda, conforme mencionado na seção de explicação formal anterior . A frase com o reflexivo pode ser representada como

(λ x . x machuca x ) Jane

em que Jane é o argumento assunto referente e λx.x ferido x é a função de predicado (a abstração lambda) com a notação lambda e x indicando tanto o sujeito semântica eo objeto semântico da sentença como sendo vinculado. Isso retorna a interpretação semântica que JANE machucou JANE com JANE sendo a mesma pessoa.

Os pronomes também podem se comportar de maneira diferente. Na frase abaixo

Ashley bateu nela .

o pronome ela só pode se referir a uma mulher que não seja Ashley. Isso significa que nunca pode ter um significado reflexivo equivalente a Ashley bater em si mesma . As interpretações gramaticais e não gramaticais são:

* Ashley _eu bati nela _i . (interpretação # 1: ela = Ashley )

Ashley _eu bati nela _j . (interpretação # 2: ela = uma mulher que não é Ashley)

A primeira interpretação é impossível. Apenas a segunda interpretação é permitida pela gramática.

Assim, pode-se ver que reflexivos e recíprocos são variáveis ​​limitadas (conhecidas tecnicamente como anáforas ), enquanto os pronomes verdadeiros são variáveis ​​livres em algumas estruturas gramaticais, mas variáveis ​​que não podem ser limitadas em outras estruturas gramaticais. Os fenômenos de ligação encontrados nas línguas naturais foram particularmente importantes para o governo sintático e a teoria da ligação (ver também: Ligação (linguística) ).

Veja também

• Encerramento (ciência da computação)
• Lógica combinatória
• Lambda levantando
• Vinculação de nome
• Escopo (programação)

Referências

• Thompson, Simon (1991). Teoria dos tipos e programação funcional . Wokingham, Inglaterra: Addison-Wesley. ISBN 0201416670. OCLC  23287456 .