Variables libres y variables ligadas - Free variables and bound variables

En matemáticas , y en otras disciplinas que involucran lenguajes formales , incluida la lógica matemática y la informática , una variable libre es una notación (símbolo) que especifica lugares en una expresión donde puede tener lugar la sustitución y no es un parámetro de esta o cualquier expresión contenedora. Algunos libros más antiguos usan los términos variable real y variable aparente para variable libre y variable limitada, respectivamente. La idea está relacionada con un marcador de posición (un símbolo que luego será reemplazado por algún valor), o uncarácter comodín que representa un símbolo no especificado.

En programación de computadoras , el término variable libre se refiere a las variables utilizadas en una función que no son variables locales ni parámetros de esa función. El término variable no local es a menudo un sinónimo en este contexto.

Una variable ligada es una variable que anteriormente estaba libre , pero que ha sido ligada a un valor específico o conjunto de valores llamado dominio de discurso o universo . Por ejemplo, la variable x se convierte en una variable ligada cuando escribimos:

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

o

Existe x tal que x ² = 2 .

En cualquiera de estas proposiciones, no importa lógicamente si se usa x o alguna otra letra. Sin embargo, podría resultar confuso volver a utilizar la misma letra en otra parte de alguna proposición compuesta . Es decir, las variables libres se vuelven vinculadas y luego, en cierto sentido, dejan de estar disponibles como valores sustitutos para otros valores en la creación de fórmulas.

El término "variable ficticia" también se usa a veces para una variable ligada (más a menudo en matemáticas generales que en informática), pero ese uso puede crear una ambigüedad con la definición de variables ficticias en el análisis de regresión .

Ejemplos de

Antes de establecer una definición precisa de variable libre y variable ligada , los siguientes son algunos ejemplos que quizás aclaren estos dos conceptos más de lo que lo haría la definición:

En la expresion

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

n es una variable libre y k es una variable ligada; en consecuencia, el valor de esta expresión depende del valor de n , pero no hay nada llamado k de lo que pueda depender.

En la expresion

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

y es una variable libre y x es una variable ligada; en consecuencia, el valor de esta expresión depende del valor de y , pero no hay nada llamado x de lo que pueda depender.

En la expresion

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

x es una variable libre y h es una variable ligada; en consecuencia, el valor de esta expresión depende del valor de x , pero no hay nada llamado h de lo que pueda depender.

En la expresion

${\ Displaystyle \ forall x \ \ existe y \ {\ Big [} \ varphi (x, y, z) {\ Big]},}$

z es una variable libre y x y y son variables ligadas, asociados con cuantificadores lógicos ; en consecuencia, el valor lógico de esta expresión depende del valor de z , pero no hay nada llamado x o y de lo que pueda depender.

Más ampliamente, en la mayoría de las demostraciones usamos variables ligadas. Por ejemplo, la siguiente prueba muestra que cada cuadrado de un entero par es divisible por${\ Displaystyle 4}$

Sea un entero par positivo. Entonces hay un número entero tal que . Dado que tenemos divisible por${\ Displaystyle n}$${\ Displaystyle k}$${\ Displaystyle n = 2k}$${\ Displaystyle n ^ {2} = 4k ^ {2}}$${\ Displaystyle n ^ {2}}$${\ Displaystyle 4}$

no solo k sino también n se han utilizado como variables ligadas como un todo en la demostración.

Operadores de enlace variable

El seguimiento

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

son algunos operadores de enlace de variables comunes . Cada uno de ellos se une la variable x para algún conjunto S .

Tenga en cuenta que muchos de estos son operadores que actúan sobre funciones de la variable vinculada. En contextos más complicados, tales notaciones pueden volverse incómodas y confusas. Puede ser útil cambiar a notaciones que hagan explícito el enlace, como

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

por sumas o

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

para la diferenciación.

Explicación formal

Árbol que resume la sintaxis de la expresión ${\ Displaystyle \ forall x \, ((\ existe y \, A (x)) \ vee B (z))}$

Los mecanismos de vinculación de variables ocurren en diferentes contextos en matemáticas, lógica e informática. En todos los casos, sin embargo, son propiedades puramente sintácticas de expresiones y variables en ellas. Para esta sección podemos resumir la sintaxis identificando una expresión con un árbol cuyos nodos hoja son variables, constantes, constantes de función o constantes de predicado y cuyos nodos no hoja son operadores lógicos. Luego, esta expresión se puede determinar haciendo un recorrido en orden del árbol. Los operadores de vinculación de variables son operadores lógicos que se encuentran en casi todos los lenguajes formales. Un operador de vinculación Q toma dos argumentos: una variable v y una expresión P , y cuando se aplica a sus argumentos produce una nueva expresión Q ( v , P ). El significado de los operadores vinculantes lo proporciona la semántica del lenguaje y no nos concierne aquí.

La vinculación de variables relaciona tres cosas: una variable v , una ubicación a para esa variable en una expresión y un nodo n no hoja de la forma Q ( v , P ). Nota: definimos una ubicación en una expresión como un nodo hoja en el árbol de sintaxis. El enlace variable se produce cuando esa ubicación está por debajo del nodo n .

En el cálculo lambda , xes una variable ligada en el término M = λx. Ty una variable libre en el término T. Decimos que xestá atado My libre T. Si Tcontiene un subtermo, λx. Uentonces xse rebota en este término. Se xdice que esta unión interna anidada de "sombrea" la unión externa. Las apariciones de xin Uson apariciones gratuitas de lo nuevo x.

Las variables vinculadas al nivel superior de un programa son variables técnicamente libres dentro de los términos a los que están vinculadas, pero a menudo se tratan especialmente porque pueden compilarse como direcciones fijas. De manera similar, un identificador vinculado a una función recursiva también es técnicamente una variable libre dentro de su propio cuerpo, pero se trata de manera especial.

Un término cerrado es aquel que no contiene variables libres.

Expresiones de función

Para dar un ejemplo de las matemáticas, considere una expresión que define una función

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

donde t es una expresión. t puede contener algunos, todos o ninguno de los x ₁ , ..., x _n y puede contener otras variables. En este caso decimos que la definición de la función une las variables x ₁ ,…, x _n .

De esta manera, las expresiones de definición de funciones del tipo que se muestra arriba se pueden considerar como el operador de vinculación de variables, análoga a las expresiones lambda del cálculo lambda . Otros operadores vinculantes, como el signo de suma , pueden considerarse funciones de orden superior que se aplican a una función. Entonces, por ejemplo, la expresión

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

podría tratarse como una notación para

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

donde es un operador con dos parámetros: una función de un parámetro y un conjunto para evaluar esa función. Los otros operadores enumerados anteriormente se pueden expresar de manera similar; Por ejemplo, el cuantificador universal puede ser pensado como un operador que se evalúa como la conjunción lógica de la función booleana de valor P aplican sobre la (posiblemente infinito) conjunto S . ${\ Displaystyle \ sum _ {S} {f}}$ ${\ Displaystyle \ forall x \ in S \ P (x)}$

Lenguaje natural

Cuando se analizan en semántica formal , se puede ver que los lenguajes naturales tienen variables libres y ligadas . En inglés, los pronombres personales como él , ella , ellos , etc. pueden actuar como variables libres.

Lisa encontró su libro.

En la oración anterior, el pronombre posesivo ella es una variable libre. Puede referirse a la Lisa mencionada anteriormente o a cualquier otra mujer. En otras palabras, su libro podría estar refiriéndose al libro de Lisa (una instancia de correferencia ) o a un libro que pertenece a una mujer diferente (por ejemplo, el libro de Jane). Quienquiera que sea el referente de ella puede establecerse de acuerdo con el contexto situacional (es decir, pragmático ). La identidad del referente se puede mostrar usando subíndices de coindexación donde i indica un referente yj indica un segundo referente (diferente de i ). Por lo tanto, la oración que Lisa encontró en su libro tiene las siguientes interpretaciones:

Lisa _i encontró _i libro. (interpretación # 1: ella = de Lisa )

Lisa _i encontró su _j libro. (interpretación # 2: ella = de una mujer que no es Lisa)

La distinción no es puramente de interés académico, ya que algunas lenguas tienen formas diferentes para ella _i y su _j : por ejemplo, el noruego y el sueco traducen correferente her _i como pecado y no correferente her _j como hennes .

El inglés permite especificar la correferencia, pero es opcional, ya que ambas interpretaciones del ejemplo anterior son válidas (la interpretación agramatical se indica con un asterisco):

Lisa _i la encontró _i propio libro. (interpretación # 1: ella = de Lisa )

* Lisa _i encontró su _j propio libro. (interpretación # 2: ella = de una mujer que no es Lisa)

Sin embargo, los pronombres reflexivos , como él mismo , ella misma , ellos mismos , etc., y los pronombres recíprocos , como los demás , actúan como variables ligadas. En una oración como la siguiente:

Jane daño a sí misma .

la reflexiva misma solo puede referirse al antecedente mencionado anteriormente , en este caso Jane , y nunca puede referirse a una persona femenina diferente. En este ejemplo, la propia variable está vinculada al sustantivo Jane que aparece en la posición de sujeto . Indicando la coindexación, la primera interpretación con Jane y ella coindexadas está permitida, pero la otra interpretación en la que no están coindexadas no es gramatical :

Jane _me lastimé a sí misma _i . (interpretación # 1: ella misma = Jane )

* Jane _me lastimé _j . (interpretación # 2: ella misma = una mujer que no es Jane)

Tenga en cuenta que el enlace de correferencia se puede representar mediante una expresión lambda como se menciona en la sección anterior Explicación formal . La oración con el reflexivo podría representarse como

(λ x . x herido x ) Jane

en el que Jane es el argumento de referencia del sujeto y λx.x hurt x es la función de predicado (una abstracción lambda) con la notación lambda yx indicando que tanto el sujeto semántico como el objeto semántico de la oración están ligados. Esto devuelve la interpretación semántica que JANE hirió a JANE con JANE siendo la misma persona.

Los pronombres también pueden comportarse de manera diferente. En la oración de abajo

Ashley golpeó su .

el pronombre ella solo puede referirse a una mujer que no sea Ashley. Esto significa que nunca puede tener un significado reflexivo equivalente al de Ashley golpearse a sí misma . Las interpretaciones gramaticales y agramaticales son:

* Ashley _i golpeó _i . (interpretación # 1: ella = Ashley )

Ashley _i golpeó su _j . (interpretación # 2: ella = una mujer que no es Ashley)

La primera interpretación es imposible. La gramática sólo permite la segunda interpretación.

Así, se puede ver que los reflexivos y recíprocos son variables ligadas (conocidas técnicamente como anáforas ) mientras que los pronombres verdaderos son variables libres en algunas estructuras gramaticales pero variables que no pueden estar ligadas en otras estructuras gramaticales. Los fenómenos vinculantes que se encuentran en los lenguajes naturales fueron particularmente importantes para el gobierno sintáctico y la teoría vinculante (ver también: Vinculación (lingüística) ).

Ver también

• Cierre (informática)
• Lógica combinatoria
• Levantamiento de lambda
• Vinculación de nombre
• Alcance (programación)

Referencias

• Thompson, Simon (1991). Teoría de tipos y programación funcional . Wokingham, Inglaterra: Addison-Wesley. ISBN 0201416670. OCLC  23287456 .