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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  «Свободные переменные и связанные переменные»  -  новости  · газеты  · книги  · ученый  · JSTOR ( декабрь 2008 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

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

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

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

или же

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

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

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

Примеры [ править ]

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

В выражении

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

- это некоторые общие операторы привязки переменных . Каждый из них связывает переменную х для некоторого множества 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. ^[1]

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

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

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

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

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

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