Как комбинаторы с фиксированной запятой могут завершить рекурсивные конструкции?
Комбинаторы с фиксированной запятой дают возможность анонимным функциям ссылаться на себя или создавать взаимно рекурсивные структуры. Хотя они полезны в лямбда-исчислении, они по существу излишни в современных языках программирования, потому что большинство, если не все, поддерживают рекурсию, лямбды и замыкания.
Кроме того, комбинаторы с фиксированной точкой могут приводить к завершению рекурсивных конструкций, таких как леворекурсивные грамматические парсеры. Рассмотрим Ликмана 1995 года, который доказывает завершение своей реализации, но в действительности никогда не упоминает, как оно работает (это просто пошаговый вывод из теории решеток в реализацию haskell) и почему ему нужны комбинаторы с фиксированной точкой в языке, который уже поддерживает рекурсию изначально.
Как это работает и зачем ему комбинатор с фиксированной запятой?
2 ответа
После быстрого сканирования, в конце 5.3, Ликман пишет: "Как определено выше, исправление fixS гарантировано достаточно продуктивно для всех непрерывных входов".
Суть в том, чтобы оператор точки фиксации выдавал достаточно выходных данных, чтобы анализ мог продолжаться. Вы не можете сделать это для генерала fix :: (a -> a) -> a но специализирующийся a в Set a, или позже Parser a, дает достаточно структуры (а именно структуры решетки) для работы.
Опять же, я только что внимательно просмотрел тезис, но думаю, что доказательство (в разделе 5.5) утверждения "h :: Parser a -> Parser a сохраняет свойство производительности ==> fixP h продуктивно "является ключевым.
Конечно, вещь. Вот простая правильно-рекурсивная грамматика с тремя правилами:
S -> b T
T -> a S
T -> a
Эти три правила позволяют нам создать синтаксический анализатор для распознавания этих строк:
type Parser = String -> (Bool, String)
s :: Parser
s "" = (False, "")
s (c : cs) = if c == 'b' then t cs else (False, cs)
t :: Parser
t "" = (False, "")
t (c : cs)
| c == 'a' && cs == "" = (True, "")
| c /= 'a' = (False, cs)
| otherwise = s cs
Если вы хотите сделать более общий анализ, просто специализируйте Bool вместо этого иметь некоторую структуру данных, возможно, хранящуюся в Maybe указать на неудачу. возврате (False, ___) при неудачном разборе помогло бы, если бы у S были и другие правила, например, например S -> T T а также T -> b b, Затем, когда мы получаем 'b', за которым следует (False, ___), мы перематываем, чтобы попытаться S -> T T, Эти виды грамматики могут быть сделаны с небольшим количеством жира локтя и рекурсии.
Три вышеприведенных правила будут успешно соответствовать строкам, таким как "ba", "baba" и так далее. Мы могли бы также написать эти строки влево-рекурсивно как:
S -> T a
T -> S b
T -> b
Что произойдет, если вы попытаетесь написать те же парсеры выше? Бесконечный цикл, если вы смотрите на начало строки. Проблема в том, что функция S сначала вызовет функцию T, а затем T сначала вызовет S, и они будут взаимно повторяться до бесконечности. Компьютер недостаточно умен, чтобы знать, что постусловия ("сопровождаемые a", "сопровождаемые a b") делают невозможным дальнейшее решение; он просто погружается в ваши функции и верит, что вы знаете, что делаете.
Как помогает хороший комбинатор с фиксированной точкой? Хорошо, думайте об этих правилах как об описании дерева: тогда оценка функции сначала проходит это дерево по глубине, и это конкретное дерево бесконечно в этом направлении. С другой стороны, обход в ширину может быть основан на этих правилах и может получить результат, который использует наименьшее количество этих функций, и это "наименьшая фиксированная точка" для определенной функции, основанной на этой грамматике. Вот почему правильный комбинатор с фиксированной точкой (основанный либо на diag в статье или комбинатор теории решетки) может завершаться при описании этих правил, а наивная рекурсия - нет.