Замыкания и Контекстно-свободные грамматики

Question

Я просматриваю свою программу занятий по теоретической информатике, и в разделе Контекстно-свободные грамматики в ней перечислены "свойства замыкания".Я просмотрел свой учебник по этому предмету и нашел совсем немного.То немногое, что в нем есть, на данный момент немного выше моего понимания (я еще не прошел курс), но я кое-что понимаю.

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

(Немного больше контекста:Я пишу электронное письмо профессору с вопросом, можно ли перевести курс с Perl на Ruby или Python.Если эти концепции взаимосвязаны, это может быть еще одной причиной, по которой мы должны использовать Ruby вместо Perl.)

Answer 1

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

• Оператор является "замкнутым" на наборе значений, если применение этого оператора к значениям из набора всегда приводит к значению из данного набора.Например, сложение замкнуто на целых числах, а деление - нет (4/2 является целым числом, а 5/2 - нет).Таким образом, сложение целых чисел является каким-то образом "полным" в том смысле, в каком деление - нет.

• "Транзитивное" замыкание отношения "завершает" отношение путем следования (всем возможным) нескольким приложениям.В повседневных терминах понятие "является потомком" является транзитивным замыканием отношения "является дочерним элементом".

• Функциональное "замыкание" "завершается", например,указание того, как должны быть разрешены свободные переменные.В псевдокодовом выражении:

  bump = function(x) (x + y)
  

  x является аргументом для bump, но определение, по-видимому, оставляет "открытым" вопрос о разрешении y.С другой стороны, если мы определим:

  bumper = function(y) (function(x) (x + y))
  

  затем вызывая bumper возвращает функцию, которая добавляет исходный аргумент bumper к аргументу созданной функции, так что:

  add3 = bumper(3)
  

  эквивалентно определению:

  add3 = function(x) (x + 3)
  

  Вложенное определение "закрывается" (или дополняется) переменными, доступными в точке его определения.

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

Answer 2

Свойство замыкания выглядит так: если L и M являются языками, не зависящими от контекста, то и L | M. Закрытия функций - это способ реализации первоклассных функций. Так что нет, они не имеют ничего общего друг с другом.

Почему тогда то же имя? Закрытие функции «закрыто» над ее свободными переменными:

def adder(n): return lambda m: n + m

Здесь n - свободная переменная лямбды. Название подчеркивает это, потому что Лисп изначально не закрывал свободные переменные - они брали свое значение из любой привязки в стеке при вызове внутренней функции.

Закрытие для свойств в математике немного более очевидно: если набор закрывается под операцией, то применение этой операции в этом наборе не выведет вас из нее. Если вы добавите целые числа, то вы получите целое число.

Answer 3

Дарий прав; " закрывающие свойства " не имеют ничего общего с "замыканиями функций". Есть так много слов, чтобы обойти: - (

Идея свойств замыкания применяется во всей компьютерной науке, но она широко применяется в разных классах языков. Различные классы языков важны, потому что вам нужны разные технологии для сканирования или распознавания высказываний. Например, регулярные выражения могут сказать вам, если у вас есть зарезервированное слово, но они не могут сказать вам, если у вас есть выражение со сбалансированными скобками - для этого вам нужна контекстно-свободная грамматика.

Людей, как правило, интересует, есть ли у вас другой язык в том же классе, если вы берете определенный язык и пересекаетесь или объединяетесь с другим языком или просто дополняете его. Например, можно ли написать регулярное выражение, которое точно соответствует тем токенам, которые являются не зарезервированными словами? Мы можем ответить на громкое «да» потому что обычные языки закрыты в дополнении, то есть дополнение обычного языка само по себе является обычным языком. Это пример свойства замыкания. Обычно доказательство является конструктивным, то есть оно не только говорит вам, что существует регулярное выражение, описывающее все токены, которые не являются зарезервированными словами, доказательство свойства closure скажет вам, как найти такое регулярное выражение.