Free variables and bound variables

Original article: w:Free variables and bound variables

For bound variables in computer programming, see Name binding.

"Free variable" redirects here. It is not to be confused with Free parameter or Dummy variable.

수학(mathematics), 및 수학적 논리(mathematical logic)와 컴퓨터 과학(computer science)을 포함하여 형식적 언어(formal languages)와 관련된 다른 분야에서, 자유 변수(free variable)는 대체(substitution)가 발생할 수 있는 표현의 위치를 지정하는 표기법 (기호)이고 이것 또는 임의의 컨테이너 표현의 매개변수가 아닙니다. 일부 오래된 책에서는 자유 변수(free variable)와 경계 변수(bound variable)에 각각 실제 변수(real variable)와 겉보기 변수(apparent variable)라는 용어를 사용합니다. 그 아이디어는 자리-표시자(placeholder, 나중에 일부 값으로 대체될 기호), 또는 지정되지 않은 기호를 나타내는 와일드카드 문자(wildcard character)와 관련이 있습니다.

컴퓨터 프로그래밍(computer programmin)에서, 자유 변수라는 용어는 해당 함수의 지역적 변수(local variables)도 아니고 매개변수(parameters)도 아닌 함수(function)에 사용되는 변수(variables)를 참조합니다. 비-지역적 변수(non-local variable)라는 용어는 종종 이 문맥에서 동의어입니다.

경계 변수는, 이에 반해, 담론의 도메인(domain of discourse)이나 우주(universe)에서 특정한 값이나 값의 범위에 경계진 변수입니다. 이것은 논리적 한정어, 변수-바인딩 연산자, 또는 변수에 대해 허용되는 값의 명시적 설명 (예를 들어, "...여기서 $n$은 양의 정수임")의 사용을 통해 달성될 수 있습니다. 예제는 다음 섹션에서 제공됩니다. 어쨌든, 그것이 행해졌을 때, 변수는 그 값이 진리 값이든 계산의 수치적 결과이든, 또는, 더 일반적으로, 함수의 이미지 집합의 원소이든 관계없이 표현의 값이 의존하는 더 이상 독립 변수가 아닙니다. 많은 맥락에서 담론의 도메인이 이해되는 동안, 경계 변수에 대해 값의 명시적 범위가 제공되지 않을 때, 표현을 적절하게 평가하기 위해 도메인을 지정해야 할 수 있습니다. 예를 들어, 두 변수가 논리적 한정어에 의해 경계인 다음 표현을 생각해 보십시오:

$$\forall y\,\exists x\,\left(x={\sqrt {y}}\right).$$

이 표현은 $x$와 $y$의 도메인이 실수이면 거짓으로 평가되지만, 도메인이 복소수이면 참으로 평가됩니다.

"가짜 변수(dummy variable)"라는 용어는 때때로 경계 변수 (컴퓨터 과학보다 일반 수학에서 더 공통적임)에 사용되지만, 이것은 통계, 보다 공통적으로 회귀 분석에서 사용되는 동일하게 이름-지정되었지만 관련-없는 가짜 변수(dummy variable)의 개념과 혼동되어서는 안 됩니다.

Examples

자유 변수(free variable)와 경계 변수(bound variable)의 정확한 정의를 언급하기 전에, 다음은 이들 두 가지 개념을 정의보다 더 명확하게 만드는 몇 가지 예제입니다:

다음 표현에서

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

n은 자유 변수이고 k는 경계 변수입니다; 결과적으로 이 표현의 값은 n의 값에 의존하지만, 그것이 의존할 수 있는 k라고 불리는 어떤 것은 없습니다.

다음 표현에서

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

y는 독립 변수이고 x는 경계 변수입니다; 결과적으로 이 표현의 값은 y의 값에 의존하지만, 그것이 의존할 수 있는 x라고 불리는 어떤 것은 없습니다.

다음 표현에서

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

x는 자유 변수이고 h는 경계 변수입니다; 결과적으로 이 표현의 값은 x의 값에 의존하지만, 그것이 의존할 수 있는 h라고 불리는 어떤 것은 없습니다.

다음 표현에서

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

z는 자유 변수이고 x와 y는 논리적 한정어(logical quantifiers)와 결합된 경계 변수입니다; 결과적으로 이 표현의 논리적 값(logical value)은 z의 값에 의존하지만, 그것이 의존할 수 있는 x 또는 y라고 불리는 어떤 것은 없습니다.

보다 광범위하게, 대부분의 증명에서, 경계 변수가 사용됩니다. 예를 들어, 다음 증명은 짝수의 모든 제곱이 4로 나누어진다는 것을 보여줍니다:

$n$을 양의 짝수 정수라고 놓습니다. 그런-다음 $n=2k$를 만족하는 정수 $k$가 있습니다. $n^{2}=4k^{2}$이므로, $n^{2}$는 4로 나누어집니다.

k뿐만 아니라 n도 증명에서 전체로 경계 변수로 사용되었습니다.

Variable-binding operators

다음은

$\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 \exists x$

일부 공통적인 변수-바인딩 연산자(variable-binding operators)입니다. 그것들 각각은 일부 집합 S에 대해 변수 x를 바인딩합니다.

이들 중 많은 것은 경계 변수의 함수에 작용하는 연산자(operators)입니다. 보다 복잡한 맥락에서, 그러한 표기법은 어색하고 혼란스러울 수 있습니다. 바인딩을 명시적으로 만드는 합에 대해 다음과 같은

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

또는 미분에 대해 다음과 같은

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

표기법으로 전환하는 것이 유용할 수 있습니다.

Formal explanation

Tree summarizing the syntax of the expression $\forall x\,((\exists y\,A(x))\vee B(z))$

변수-바인딩 메커니즘은 수학, 논리 및 컴퓨터 과학의 다양한 맥락에서 발생합니다. 모든 경우에서, 어쨌든, 그것들은 순수하게 표현과 그 안에서 변수의 구문적(syntactic) 속성입니다. 이 섹션에 대해 리프 노드가 변수, 상수, 함수 상수 또는 술어 상수이고 비-리프 노드가 논리 연산자인 트리를 갖는 표현을 식별함으로써 구문을 요약할 수 있습니다. 이 표현은 그런-다음 트리의 중위 순회(inorder traversal)를 수행함으로써 결정될 수 있습니다. 변수-바인딩 연산자는 거의 모든 각 형식적 언어에서 발생하는 논리적 연산자(logical operators)입니다. 바인딩 연산자 Q는 변수 v와 표현 P의 두 가지 인수를 취하고, 해당 인수에 적용될 때 새로운 표현 Q(v, P)를 생성합니다. 바인딩 연산자의 의미는 언어의 의미론(semantics)에 의해 제공되고 여기서 우리와 관련이 없습니다.

변수 바인딩은 변수 v, 표현에서 해당 변수에 대한 위치 a 및 Q(v, P) 형식의 비-리프 노드 n의 세 가지와 관련됩니다. 참고: 우리는 표현에서 위치를 구문 트리에서 리프 노드로 정의합니다. 변수 바인딩은 해당 위치가 노드 n 아래에 있을 때 발생합니다.

람다 계산법(lambda calculus)에서, x는 항 M = λx. T에서 경계 변수이고 항 T에서 자유 변수입니다. 우리는 x가 M에 경계이고 T에서 자유라고 말합니다. 만약 T가 부분항 λx. U을 포함하면, x는 이 항에서 리바운드됩니다. x의 이러한 중첩된, 내부 바인딩은 외부 바인딩을 "그림자"라고 말합니다. U에서 x의 발생은 새로운 x의 자유 발생입니다.

프로그램의 최상위 수준에서 경계진 변수는 그것들이 경계진 항 내에서 기술적으로 자유 변수이지만 그것들이 고정된 주소로 컴파일될 수 있기 때문에 종종 특수하게 취급됩니다. 유사하게, 재귀 함수에 경계진 식별자도 자체 본문 내에서 기술적으로 자유 변수(recursive function)이지만 특별히 취급됩니다.

닫힌 항(closed term)은 자유 변수를 포함하지 않는 항입니다.

Function expressions

수학의 예제를 제공하기 위해, 다음 함수를 정의하는 표현을 생각해 보십시오:

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

여기서 t는 표현입니다. t는 x₁, …, x_n 중 일부, 전부 또는 전혀 포함하지 않을 수 있고 다른 변수를 포함할 수 있습니다. 이 경우에서, 우리는 함수 정의가 변수 x₁, …, x_n를 바인딩한다고 말합니다.

이러한 방식으로, 위에 표시된 종류의 함수 정의 표현은 람다 계산법(lambda calculus)의 람다 표현과 유사한 그 변수 바인딩 연산자로 생각될 수 있습니다. 합계(summation) 기호와 같은 다른 바인딩 연산자는 함수에 적용되는 고차 함수(higher-order functions)로 생각될 수 있습니다. 예를 들어, 다음 표현은

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

다음에 대한 표기법으로 취급될 수 있습니다:

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

여기서 $\sum _{S}{f}$는 두 매개변수—하나-매개변수 함수와 해당 함수를 평가할 집합을 갖는 연산자입니다. 위에 나열된 다른 연산자도 비슷한 방법으로 표현될 수 있습니다; 예를 들어, 보편적 한정어 $\forall x\in S\ P(x)$는 (가능한 무한한) 집합 S에 적용된 부울-값 함수(boolean-valued function) P의 논리곱(logical conjunction)으로 평가되는 연산자로 생각될 수 있습니다.

Natural language

When analyzed in formal semantics, natural languages can be seen to have free and bound variables. In English, personal pronouns like he, she, they, etc. can act as free variables.

Lisa found her book.

In the sentence above, the possessive pronoun her is a free variable. It may refer to the previously mentioned Lisa or to any other female. In other words, her book could be referring to Lisa's book (an instance of coreference) or to a book that belongs to a different female (e.g. Jane's book). Whoever the referent of her is can be established according to the situational (i.e. pragmatic) context. The identity of the referent can be shown using coindexing subscripts where i indicates one referent and j indicates a second referent (different from i). Thus, the sentence Lisa found her book has the following interpretations:

Lisa_i found her_i book. (interpretation #1: her = of Lisa)

Lisa_i found her_j book. (interpretation #2: her = of a female that is not Lisa)

The distinction is not purely of academic interest, as some languages do actually have different forms for her_i and her_j: for example, Norwegian and Swedish translate coreferent her_i as sin and noncoreferent her_j as hennes.

English does allow specifying coreference, but it is optional, as both interpretations of the previous example are valid (the ungrammatical interpretation is indicated with an asterisk):

Lisa_i found her_i own book. (interpretation #1: her = of Lisa)

*Lisa_i found her_j own book. (interpretation #2: her = of a female that is not Lisa)

However, reflexive pronouns, such as himself, herself, themselves, etc., and reciprocal pronouns, such as each other, act as bound variables. In a sentence like the following:

Jane hurt herself.

the reflexive herself can only refer to the previously mentioned antecedent, in this case Jane, and can never refer to a different female person. In this example, the variable herself is bound to the noun Jane that occurs in subject position. Indicating the coindexation, the first interpretation with Jane and herself coindexed is permissible, but the other interpretation where they are not coindexed is ungrammatical:

Jane_i hurt herself_i. (interpretation #1: herself = Jane)

*Jane_i hurt herself_j. (interpretation #2: herself = a female that is not Jane)

Note that the coreference binding can be represented using a lambda expression as mentioned in the previous Formal explanation section. The sentence with the reflexive could be represented as

(λx.x hurt x)Jane

in which Jane is the subject referent argument and λx.x hurt x is the predicate function (a lambda abstraction) with the lambda notation and x indicating both the semantic subject and the semantic object of sentence as being bound. This returns the semantic interpretation JANE hurt JANE with JANE being the same person.

Pronouns can also behave in a different way. In the sentence below

Ashley hit her.

the pronoun her can only refer to a female that is not Ashley. This means that it can never have a reflexive meaning equivalent to Ashley hit herself. The grammatical and ungrammatical interpretations are:

*Ashley_i hit her_i. (interpretation #1: her = Ashley)

Ashley_i hit her_j. (interpretation #2: her = a female that is not Ashley)

The first interpretation is impossible. Only the second interpretation is permitted by the grammar.

Thus, it can be seen that reflexives and reciprocals are bound variables (known technically as anaphors) while true pronouns are free variables in some grammatical structures but variables that cannot be bound in other grammatical structures. The binding phenomena found in natural languages was particularly important to the syntactic government and binding theory (see also: Binding (linguistics)).

See also

• Closure (computer science)
• Combinatory logic
• Lambda lifting
• Name binding
• Scope (programming)

References

• Thompson, Simon (1991). Type theory and functional programming. Wokingham, England: Addison-Wesley. ISBN 0201416670. OCLC 23287456.