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

Информацию о связанных переменных в компьютерном программировании см. В разделе Привязка имен. "Бесплатная переменная" перенаправляется сюда. Его не следует путать со свободным параметром или фиктивной переменной.

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

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

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

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

или

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

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

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

• 1 Примеры
  • 1.1 Операторы привязки переменных
• 2 Формальное объяснение
  • 2.1 Функциональные выражения
• 3 Естественный язык
• 4 См. Также
• 5 ссылки

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

В выражении

${\ 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 1,…, x n, а также может содержать другие переменные. В этом случае мы говорим, что определение функции связывает переменные x 1,…, 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.