Свободные переменные и связанные переменные

Концепция математики или информатики

В математике и других дисциплинах, включающих формальные языки , включая математическую логику и информатику , переменную можно назвать либо свободной, либо связанной. Свободная переменная — это обозначение (символ), указывающее места в выражении , где может иметь место замена , и не является параметром этого или любого другого выражения-контейнера. В некоторых старых книгах термины «реальная переменная» и « кажущаяся переменная» используются для обозначения свободной переменной и связанной переменной соответственно. Идея связана с заполнителем ( символом , который позже будет заменен каким-либо значением) или подстановочным знаком , обозначающим неопределенный символ.

В компьютерном программировании термин «свободная переменная» относится к переменным, используемым в функции , которые не являются ни локальными переменными , ни параметрами этой функции. Термин «нелокальная переменная» часто является синонимом в этом контексте.

Напротив, экземпляр переменного символа является привязанным , если значение этого переменного символа было привязано к определенному значению или диапазону значений в области дискурса или вселенной . Этого можно достичь за счет использования логических кванторов, операторов привязки переменных или явного указания допустимых значений для переменной (например, «...где является положительным целым числом».) Символ переменной в целом является связанным , если хотя бы одно его появление связано. ^{[1] стр. 142--143} Поскольку один и тот же переменный символ может появляться в нескольких местах выражения, некоторые вхождения переменного символа могут быть свободными, в то время как другие связаны, ^{[1] стр. 78,} следовательно, «свободный» и «связанный». " сначала определяются для вхождений, а затем обобщаются по всем вхождениям указанного переменного символа в выражении. Как бы это ни было сделано, переменная перестает быть независимой переменной, от которой зависит значение выражения, будь то значение истинности или числовой результат вычисления, или, в более общем смысле, элемент набора изображений некоторого функция. ${\displaystyle n}$

Несмотря на то, что во многих контекстах предметная область понятна, если явный диапазон значений для связанной переменной не указан, может потребоваться указать предметную область, чтобы правильно оценить выражение. Например, рассмотрим следующее выражение, в котором обе переменные связаны логическими кванторами:

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

Это выражение имеет значение false , если областью определения и являются действительные числа, но верно, если областью определения являются комплексные числа. ${\displaystyle x}$ ${\displaystyle y}$

Термин «фиктивная переменная» также иногда используется для связанной переменной (чаще в общей математике, чем в информатике), но его не следует путать с одноименной, но несвязанной концепцией фиктивной переменной , используемой в статистике, чаще всего в регрессивный анализ.

Примеры

Прежде чем дать точное определение свободной переменной и связанной переменной, ниже приведены несколько примеров, которые, возможно, прояснят эти две концепции более ясно, чем это определение:

В выражении

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

n — свободная переменная, а k — связанная переменная; следовательно, значение этого выражения зависит от значения n , но нет ничего под названием k , от которого оно могло бы зависеть.

В выражении

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

y — свободная переменная, а x — связанная переменная; следовательно, значение этого выражения зависит от значения y , но нет ничего под названием x , от которого оно могло бы зависеть.

В выражении

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

x — свободная переменная, h — связанная переменная; следовательно, значение этого выражения зависит от значения x , но нет ничего под названием h , от которого оно могло бы зависеть.

В выражении

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

z — свободная переменная, а x и y — связанные переменные, связанные с логическими кванторами ; следовательно, логическое значение этого выражения зависит от значения z , но нет ничего под названием x или y , от которого оно могло бы зависеть.

В более широком смысле в большинстве доказательств используются связанные переменные. Например, следующее доказательство показывает, что все квадраты положительных четных целых чисел делятся на ${\displaystyle 4}$

Пусть — положительное четное целое число. Тогда существует целое число такое, что . Поскольку , мы делимся на ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n=2k}$ ${\displaystyle n^{2}=4k^{2}}$ ${\displaystyle n^{2}}$ ${\displaystyle 4}$

в доказательстве в качестве связанных переменных в целом использовались не только k , но и n .

Операторы привязки переменных

Следующее

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

— некоторые распространенные операторы привязки переменных . Каждый из них связывает переменную x для некоторого множества S.

Многие из них являются операторами , которые действуют на функции связанной переменной. В более сложных контекстах такие обозначения могут стать неудобными и запутанными. Может быть полезно переключиться на обозначения, которые делают привязку явной, например

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

на суммы или

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

для дифференциации.

Формальное объяснение

Дерево, обобщающее синтаксис выражения ${\displaystyle \forall x\,((\exists y\,A(x))\vee B(z))}$

Механизмы привязки переменных встречаются в разных контекстах в математике, логике и информатике. Однако во всех случаях это чисто синтаксические свойства выражений и переменных в них. В этом разделе мы можем обобщить синтаксис, отождествив выражение с деревом , чьи листовые узлы являются переменными, константами, константами функций или константами предикатов, а нелистовые узлы являются логическими операторами. Затем это выражение можно определить, выполнив обход дерева по порядку . Операторы связывания переменных — это логические операторы , которые встречаются почти во всех формальных языках. Оператор связывания Q принимает два аргумента: переменную v и выражение P , и при применении к его аргументам создает новое выражение Q( v , P ). Значение операторов привязки задается семантикой языка и нас здесь не касается.

Привязка переменных связывает три вещи: переменную v , местоположение a для этой переменной в выражении и неконечный узел n формы Q( v , P ). Примечание. Мы определяем местоположение в выражении как листовой узел синтаксического дерева. Привязка переменной происходит, когда это местоположение находится ниже узла n .

В лямбда-исчислении это xсвязанная переменная в терме M = λx. Tи свободная переменная в терме T. Мы говорим x: связан Mи свободен T. Если Tсодержит подтермин λx. U, то xпроисходит отскок в этом термине. xГоворят, что эта вложенная внутренняя привязка «затеняет» внешнюю привязку. Появления xв Uявляются свободными появлениями нового x. ^[2]

Переменные, связанные на верхнем уровне программы, являются технически свободными переменными в терминах, к которым они привязаны, но часто обрабатываются особым образом, поскольку их можно скомпилировать как фиксированные адреса. Аналогично, идентификатор, привязанный к рекурсивной функции , технически также является свободной переменной внутри своего тела, но обрабатывается особым образом.

Закрытый термин — это термин, не содержащий свободных переменных.

Функциональные выражения

В качестве примера из математики рассмотрим выражение, определяющее функцию

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

где t — выражение. t может содержать некоторые, все или ни одного из x ₁ , …, x _n , а также может содержать другие переменные. В этом случае мы говорим, что определение функции связывает переменные x ₁ , …, x _n .

Таким образом, выражения определения функции, показанные выше, можно рассматривать как оператор привязки переменных, аналогичный лямбда-выражениям лямбда-исчисления . Другие операторы привязки, такие как знак суммы , можно рассматривать как функции более высокого порядка , применяемые к функции. Так, например, выражение

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

можно рассматривать как обозначение

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

где — оператор с двумя параметрами — однопараметрическая функция и набор для вычисления этой функции. Остальные операторы, перечисленные выше, могут быть выражены аналогичным образом; например, квантор универсальности можно рассматривать как оператор, который вычисляет логическую конъюнкцию булевозначной функции P , применяемой к (возможно, бесконечному) множеству S. ${\displaystyle \sum _{S}{f}}$ ${\displaystyle \forall x\in S\ P(x)}$

Естественный язык

При анализе формальной семантики можно увидеть, что естественные языки имеют свободные и связанные переменные. В английском языке личные местоимения, такие как he , she , They и т. д., могут выступать в качестве свободных переменных.

Лиза нашла свою книгу.

В приведенном выше предложении притяжательное местоимение her является свободной переменной. Это может относиться к ранее упомянутой Лизе или к любой другой женщине. Другими словами, ее книга может относиться к книге Лизы (пример кореференции ) или к книге, принадлежащей другой женщине (например, книга Джейн). Кто бы ни был ее референтом , можно установить в соответствии с ситуативным (т.е. прагматическим ) контекстом. Идентичность референта может быть показана с помощью индексов коиндексации, где i указывает один референт, а j указывает второй референт (отличный от i ). Таким образом, предложение, которое Лиза нашла в своей книге, имеет следующие интерпретации:

Лиза, _я нашел ее _{, забронировал} . (интерпретация №1: она = Лиза )

Лиза, _я нашел ее _книгу . (интерпретация №2: она = женщина, не являющаяся Лизой)

Это различие не представляет чисто академического интереса, поскольку в некоторых языках на самом деле существуют разные формы для her _i и her _j : например, норвежский и шведский переводят кореферент her _i как грех , а некореферент her _j как hennes .

Английский язык позволяет указать кореференцию, но это необязательно, поскольку обе интерпретации предыдущего примера действительны (неграмматическая интерпретация отмечена звездочкой):

Лиза, _я нашел ее _{, у меня} есть книга. (интерпретация №1: она = Лиза )

* Лиза, _я нашла ее _{собственную} книгу. (интерпретация №2: она = женщина, не являющаяся Лизой)

Однако возвратные местоимения , такие как «сам» , «сама », «сам » и т. д., а также взаимные местоимения , такие как друг друга , действуют как связанные переменные. В таком предложении:

Джейн поранилась .

само рефлексивное может относиться только к ранее упомянутому антецеденту , в данном случае к Джейн , и никогда не может относиться к другому человеку женского пола. В этом примере сама переменная привязана к существительному Джейн , которое встречается в позиции подлежащего . Что касается коиндексации, то первая интерпретация, в которой Джейн и она сама коиндексированы, допустима, но другая интерпретация, в которой они не индексируются, является неграмматической :

Джейн , _я поранилась _. (интерпретация №1: она сама = Джейн )

* Джейн _{, я} поранилась _j . (интерпретация №2: она сама = женщина, не являющаяся Джейн)

Привязка кореференции может быть представлена ​​с помощью лямбда-выражения , как упоминалось в предыдущем разделе формального объяснения. Предложение с возвратным рефлексом можно представить как

(λ x . x больно x )Джейн

в котором Джейн является аргументом-референтом субъекта, а λx.x больно x — предикатная функция (лямбда-абстракция) с лямбда-нотацией, а x указывает как семантический субъект, так и семантический объект предложения как связанные. Это возвращает семантическую интерпретацию : ДЖЕЙН причинила боль ДЖЕЙН , причем ДЖЕЙН является одним и тем же человеком.

Местоимения также могут вести себя по-другому. В предложении ниже

Эшли ударила ее .

Местоимение «ее» может относиться только к женщине, не являющейся Эшли. Это означает, что это никогда не может иметь рефлексивного значения, эквивалентного удару Эшли себя . Грамматические и грамматические интерпретации:

* Эшли, _я ударил _ее . (интерпретация №1: она = Эшли )

Эшли, _я ударил _ее . (интерпретация №2: она = женщина, не Эшли)

Первая интерпретация невозможна. Грамматика допускает только вторую интерпретацию.

Таким образом, можно видеть, что рефлексивные и обратные значения являются связанными переменными (технически известными как анафоры ), в то время как истинные местоимения являются свободными переменными в некоторых грамматических структурах, но переменными, которые не могут быть связаны в других грамматических структурах. Явления связывания, обнаруженные в естественных языках, были особенно важны для синтаксического управления и теории связывания (см. Также: Связывание (лингвистика) ).

Смотрите также

• Замыкание (информатика)
• Комбинаторная логика
• Лямбда лифтинг
• Привязка имени
• Область применения (программирование)

Рекомендации

1. WVO Quine, Математическая логика (1981). Издательство Гарвардского университета, 0-674-55451-5.
2. Томпсон 1991, с. 33.

• Томпсон, Саймон (1991). Теория типов и функциональное программирование . Уокингем, Англия: Аддисон-Уэсли. ISBN 0201416670. ОСЛК  23287456.

дальнейшее чтение

• Гауэрс, Тимоти ; Барроу-Грин, июнь ; Лидер, Имре , ред. (2008). Принстонский спутник математики . Принстон, Нью-Джерси : Издательство Принстонского университета . стр. 15–16. дои : 10.1515/9781400830398. ISBN 978-0-691-11880-2. JSTOR  j.ctt7sd01. LCCN  2008020450. МР  2467561. OCLC  227205932. ОЛ  19327100М. Збл  1242.00016.