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

Question

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

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

(Немного больше контекста: я пишу электронное письмо профессору с вопросом, можно ли переключить курс на Ruby или Python с Perl. Если эти понятия связаны, это может быть еще одна причина, по которой мы должны использовать 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 скажет вам, как найдите такое регулярное выражение.