Сохранение состояния в мире без государства

Я конвертирую контекстно-свободную грамматику в нормальную форму Грейбаха (GNF). Основное преобразование (от Hopcroft & Ullman) представляет собой последовательность итераций по индексированным переменным грамматики. По сути, это «безгражданство». Я реализовал это как последовательность сгибов по соответствующим индексам (реализация довольно проста):

gnf :: Ord a => Set (Rule a) -> Set (Rule a)
gnf rl = foldl step1 rl [1..maxIndex rl]
 where step1 rl' k = foldl step2 rl' [1..k - 1]
        where step2 rl'' j = noLR k (subst rl'' k j)

maxIndex rl возвращает максимальный индекс переменной в наборе правил; subst rl k j выполняет замену правил с индексом k правилами, правая часть которых начинается с переменной с индексом j. После выполнения gnf мне нужно выполнить последний проход по грамматике в обратном порядке.

Проблема заключается в noLR, который преобразует грамматику с леворекурсивными k-индексированными правилами. Это функция с отслеживанием состояния, поскольку для каждого правила (или k-индексированного правила), к которому применяется noLR, должна быть создана уникальная переменная. Итак, я написал функцию с отслеживанием состояния

noLR :: Ord a => Int -> Set (Rule a) -> State [Sym a] (Set (Rule a))
noLR rl = do (n:ns) <- get; put ns;
             let rl' = ... remove left recursion rl n ...
              in return rl'

Я могу упорядочить вместе noLR, чтобы обновить n, который noLR принимает в качестве параметра. Однако я не знаю, как выполнить noLR внутри шага 2 в приведенной выше функции. Кажется, я не могу использовать схему let... in, потому что вычисление с отслеживанием состояния встроено в несколько рекурсивных функций.

Я хочу, чтобы n была неким типом глобальной переменной, похожей на явную поточность n, которую я могу вызывать и обновлять внутри шага2, поэтому изначально я написал функцию как складку с эта-расширением (для n). Кто-нибудь знает, как я могу структурировать gnf внутри монады состояния для достижения такого эффекта? За исключением последнего вычисления в сгибе, ничто другое не является «с сохранением состояния», и мне удобно использовать монаду состояния только с «тривиальными» примерами. Я скорее потерян.


state haskell monads context-free-grammar
person danportin    schedule 23.11.2010    source источник
comment
см. foldM. gnf, конечно, будет начинаться с вызова evalState верхнего уровня.   -  person sclv    schedule 23.11.2010

Ответы (2)


arrow_upward
4
arrow_downward

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

gnf :: Ord a => Set (Rule a) -> Set (Rule a)
gnf rl = evalState (foldM step1 rl [1..maxIndex rl]) ( ... generate the initial state [Sym a] here ...)
 where step1 rl' k = foldM step2 rl' [1..k - 1]
        where step2 rl'' j = noLR k (subst rl'' k j)

Ваша переменная состояния существует на протяжении всего вычисления, и этот факт должен быть явно указан в коде.

Если все, что вам нужно, это чтобы вновь сгенерированные имена переменных не конфликтовали друг с другом, то вы можете сделать noLR чистым, сгенерировав новое имя символа из индексов k и j — что-то вроде «foo_42_16» для k == 42 и j == 16. Однако если входная грамматика уже содержит имена символов такого типа, у вас могут возникнуть проблемы.

Если вам нужно, чтобы ваши символы были уникальными в рамках грамматики, то почему бы не сказать именно об этом?

newSymbol :: Set (Rule a) -> Sym a
newSymbol rl = ... find a symbol name not used in rl ...

Однако это определенно неэффективно, если вы не замените Set (Правило a) другим типом, который позволит более эффективно реализовать операцию newSymbol.

person wolfgang    schedule 23.11.2010
comment
Второе предложение очень красивое! Соедините набор с целым числом, представляющим максимальный символ, используемый в нем. В каком-то смысле это просто делает монаду явной, но в этом случае она выглядит гораздо более элегантной. - person sclv; 24.11.2010
comment
Переоценка следующей переменной в этом случае, вероятно, является лучшим решением. Это делает код чище в целом. Но пример с foldM прояснил для меня его использование: он передает значения s и a через левую складку, накапливаясь на a. Когда встречается вычисление с отслеживанием состояния, оно выполняется, и s обновляется. Довольно круто, спасибо! - person danportin; 25.11.2010

arrow_upward
3
arrow_downward

Я бы попытался переписать noLR, чтобы он был чистым. Вы уверены, что не можете переписать его, чтобы сгенерировать символ, который зависит только от имени правила и его индекса (или чего-то подобного)?

noLR k j = noLR' k j $ newSymbol k j
    where newSymbol k j = ... -- some concatenation of k and j
          noLR' k j sym = ... -- your now pure function
person luispedro    schedule 23.11.2010
comment
Поскольку складки накапливают наборы правил, я мог бы переписать noLR, чтобы переоценить следующую возможную переменную из текущего набора правил. Из-за того, как это настроено, поиск следующей переменной является довольно простой операцией свертки по набору правил. Однако в качестве учебного упражнения я часто сталкиваюсь с этой проблемой (единственное вычисление с сохранением состояния, которое мне нужно, встроено глубоко внутри рекурсии). Я хотел бы знать, как кто-то будет выражать это монадически. - person danportin; 24.11.2010