В целях обучения я делаю переводчик для минимального языка с вызовами и возвратами подпроцедуры.
data P = Px Int | Ps [P] | Pc P | Pr
Значение: Px x инструкция x, Ps xs последовательность инструкций, Pc x вызов подпроцедуры x, Pr досрочное возвращение. Конфигурация во время вычислений - это просто Int, а инструкция Px увеличивает ее (просто для визуализации этого минимального примера, я на самом деле применяю эту вещь к большему языку). Так, например, run 0 $ Ps [Px 1, Px 2] = [1,3] - это полный след выполнения, начиная с конфигурации 0.
Я понял, что для обработки раннего возврата мне нужны продолжения, поэтому я сделал следующее
runm :: Int -> P -> ([Int] -> Cont [Int] [Int]) -> Cont [Int] [Int]
runm c p k = case p of
Px x -> return [c+x]
Ps [] -> return []
Ps (x:xs) -> do
s <- runm c x k
let c2 = if not (null s) then last s else c
k' r = k $ s ++ r
ss <- runm c2 (Ps xs) k'
return $ s ++ ss
Pc x -> callCC $ runm c x
Pr -> k []
Кажется, что он работает правильно, например:
> evalCont $ runm 0 (Ps [Px 1, Pc $ Ps [Px 2, Pr, Px 100], Px 3]) undefined
[1,3,6]
Выполняет «1», «2» и «3», но правильно пропускает «100», как это происходит после возврата.
В этой ситуации меня немного беспокоит то, что я должен каким-то образом управлять продолжением escape в случае Ps, который не имеет ничего общего с возвратом. Поэтому я подумал, что писательская монада может быть полезна.
Идея состоит в том, что писательская монада позаботится о «добавлении» последовательных конфигураций, в то время как продолжение обрабатывает «обратный переход» возврата.
Будучи не очень знакомым с продолжениями и монадными трансформаторами, я все равно не добился большого успеха. Я даже не могу понять, в каком порядке мне строить стек монад.
Например:
runwc :: Int -> P -> ([Int] -> ContT [Int] (Writer [Int]) [Int]) -> ContT [Int] (Writer [Int]) [Int]
runwc c p k = case p of
Px x -> (lift $ tell [c+x]) >> return []
Ps [] -> return []
Ps (x:xs) -> do
(_,s) <- lift $ listen $ evalContT $ runwc c x k
let c2 = if not (null s) then last s else c
runwc c2 (Ps xs) k
Pc x -> callCC $ runwc c x
Pr -> k []
Это на самом деле не возвращает:
> execWriter $ evalContT $ runwc 0 (Ps [Px 1, Pc $ Ps [Px 2, Pr, Px 100], Px 3]) undefined
[1,3,103,106]
Я думаю, я не совсем понял, почему.
Противоположный порядок показался мне более многообещающим, но это тоже не работает:
runcw :: Int -> P -> (() -> WriterT [Int] (Cont [Int]) ()) -> WriterT [Int] (Cont [Int]) ()
runcw c p k = case p of
Px x -> tell [c+x]
Ps [] -> return ()
Ps (x:xs) -> do
(_,s) <- listen $ runcw c x k
let c2 = if not (null s) then last s else c
runcw c2 (Ps xs) k
Pc x -> WriterT $ callCC $ \j -> runWriterT $ do
let k' = \_ -> WriterT $ j ((), [])
runcw c x k'
Pr -> k ()
Возвращает слишком много:
> evalCont $ execWriterT $ runcw 0 (Ps [Px 1, Pc $ Ps [Px 2, Pr, Px 100], Px 3]) undefined
[1,4]
Разница в том, что здесь, я думаю, я понимаю это лучше: функция escaper j должна вызываться с собранной историей из последующего вызова runwc c x k', но она не получает ее. В j ((), []) все отбрасывается, а callCC возвращает пустой результат для Pc случая.
Моя идея состояла в том, что монада-писатель будет "независимо" собирать трассу, чтобы она присутствовала даже при прыжке через продолжения escaper, но, похоже, это не сработает, поскольку у j нет способа получить «прошлое» (я попробовал некоторую рекурсию из последующего вызова runcw, но это Loop).
Чтобы уточнить, что я ожидал сделать, я могу сделать это с помощью более мощной монады состояния:
runcs :: Int -> P -> (() -> StateT [Int] (Cont [Int]) ()) -> StateT [Int] (Cont [Int]) ()
runcs c p k = case p of
Px x -> modify (++ [c+x])
Ps [] -> return ()
Ps (x:xs) -> do
s <- runcs c x k >> get
let c2 = if not (null s) then last s else c
runcs c2 (Ps xs) k
Pc x -> StateT $ \s -> callCC $ \j -> flip runStateT s $ do
let k' = \_ -> StateT $ \s' -> j ((), s')
runcs c x k'
Pr -> k ()
Это работает правильно
> evalCont $ execStateT (runcs 0 (Ps [Px 1, Pc $ Ps [Px 2, Pr, Px 100], Px 3]) undefined) []
[1,3,6]
Это последнее решение освобождает меня от обработки продолжения escaper в случае последовательности Ps, и оно может указать - get, что произошло до возврата, чтобы выбросить его в j.
. проблема в том, что это, очевидно, слишком мощно: в любой момент можно получить доступ к полной трассе выполнения и манипулировать через «глобальное» состояние.
Можно ли получить преимущества State решение с использованием только Writer, так что каждый шаг интерпретатора может выполнять лишь небольшую часть добавления результата?
У меня сложилось впечатление, что правильная подпись на самом деле будет ContT r (Writer w) a даже если я получу больше прогресса с WriterT w (ContT r) a. Первый соответствует (a -> (r,w)) -> (r,w), а второй - ((a,w) -> r) -> r, и мне кажется, что этот последний несет в себе слишком большую симметрию между a и w, но здесь моя голова начала процедуру взрыва, и поэтому я спрашиваю, потому что это действительно первый раз, когда я делаю что-то значимое с продолжениями, кроме тривиальных тестов.