Свободные переменные и связанные переменные - Free variables and bound variables

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

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

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

Для всех х , ( х + 1) ² = х ² + 2 х + 1 .

или

Существует x такое, что x ² = 2 .

В любом из этих предложений логически не имеет значения, используется ли x или какая-либо другая буква. Однако использование той же буквы в другом месте в каком-либо сложном предложении может сбить с толку . То есть свободные переменные становятся связанными, а затем в некотором смысле перестают быть доступными в качестве замещающих значений для других значений при создании формул.

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

Примеры

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

В выражении

${\ Displaystyle \ сумма _ {к = 1} ^ {10} е (к, п),}$

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 \ \ существует 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 п ^ {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}$

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

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

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

на суммы или

${\ Displaystyle D \ влево (х \ mapsto х ^ {2} + 2x + 1 \ вправо)}$

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

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

Дерево, обобщающее синтаксис выражения ${\ Displaystyle \ forall Икс \, ((\ существует у \, А (х)) \ Ви В (г))}$

Механизмы связывания переменных встречаются в разных контекстах в математике, логике и информатике. Однако во всех случаях это чисто синтаксические свойства выражений и переменных в них. В этом разделе мы можем обобщить синтаксис, отождествив выражение с деревом , конечными узлами которого являются переменные, константы, функциональные константы или константы предиката, а нелистовые узлы - логические операторы. Затем это выражение может быть определено путем обхода дерева в порядке. Операторы привязки переменных - это логические операторы, которые встречаются почти во всех формальных языках. Оператор привязки 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.

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

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

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

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

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

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

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

${\ Displaystyle \ сумма _ {х \ в S} {х ^ {2}}}$

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

${\ Displaystyle \ сумма _ {S} {(х \ mapsto х ^ {2})}}$

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

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

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

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

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

Лиза _я нашел ее _я книгу. (интерпретация # 1: ее = Лизы )

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

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

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

Лиза _я нашел ее _я собственную книгу. (интерпретация # 1: ее = Лизы )

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

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

Джейн больно себе .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

использованная литература

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