Использование Cont для приобретения ценностей из будущего и прошлого

Я пишу интерпретатор брейкфак на Хаскелле и придумал очень интересное описание программы:

data Program m = Instruction (m ()) (Program m)
               | Control (m (Program m))
               | Halt

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

Немного более предварительной информации. Смотрите эту версию на GitHub репо для всех деталей.

type TapeM = StateT Tape IO
type TapeP = Program TapeM
type TapeC = Cont TapeP

branch :: Monad m => m Bool -> Program m -> Program m -> Program m
branch cond trueBranch falseBranch =
  Control ((\b -> if b then trueBranch else falseBranch) `liftM` cond)

loopControl :: TapeP -> TapeP -> TapeP
loopControl = branch (not <$> is0)

Вот что я попробовал:

toProgram :: String -> TapeP
toProgram = (`runCont` id) . toProgramStep

liftI :: TapeM () -> String -> TapeC TapeP
liftI i cs = Instruction i <$> toProgramStep cs

toProgramStep :: String -> TapeC TapeP
toProgramStep ('>':cs) = liftI right cs
-- similarly for other instructions
toProgramStep ('[':cs) = push (toProgramStep cs)
toProgramStep (']':cs) = pop (toProgramStep cs)

push :: TapeC TapeP -> TapeC TapeP
push mcontinue = do
  continue <- mcontinue
  cont (\breakMake -> loopControl continue (breakMake continue))

pop :: TapeC TapeP -> TapeC TapeP
pop mbreak = do
  break <- mbreak
  cont (\continueMake -> loopControl (continueMake break) break)

Я подумал, что мог бы как-то использовать продолжения для передачи информации из '[' дело в ']' случай и наоборот, но у меня нет достаточно четкого понимания Cont, чтобы на самом деле что-то делать, кроме как собирать дикие догадки о том, что похоже, что это может сработать, как видно выше с push а также pop, Это компилируется и запускается, но результаты являются мусором.

Можно Cont быть использован, чтобы связать узел соответственно для этой ситуации? Если нет, то какую технику я должен использовать для реализации toProgram?

Примечание 1: у меня ранее была небольшая логическая ошибка: loopControl = branch is0 если бы Bools поменял местами

Примечание 2: мне удалось использовать MonadFix (как предложено jberryman) с State найти решение (см. текущее состояние хранилища github). Я все еще хотел бы знать, как это можно сделать с Cont вместо.

Примечание 3: Мой наставник Racketeer собрал для меня похожую программу Racket (см. Все ревизии). Может ли его техника "труба-труба" быть переведена на Хаскель с помощью Cont?

Мне удалось сделать это с помощью MonadFix, а кому-то другому удалось сделать это с помощью комбинаторов продолжения Racket. Я уверен, что это можно сделать с Cont в Хаскеле. Можете ли вы показать мне, как?

Источник

2 ответа

Решение

Состояние передвижения вперед с монадой продолжения выглядит так:

Cont (fw -> r) a

Затем тип аргумента cont является

(a -> fw -> r) -> fw -> r

Итак, вы получите fw прошло из прошлого, которое вы должны передать в продолжение.

Путешествие в обратном направлении выглядит следующим образом:

Cont (bw, r) a

Затем тип аргумента cont является

(a -> (bw, r)) -> (bw, r)

Т.е. вы получаете bw от продолжения, которое вы должны передать в прошлое.

Их можно объединить в одну монаду продолжения:

Cont (fw -> (bw, r)) a

Есть ловушка при применении этого к вашему парсеру, потому что toProgramStep строит программу в обратном порядке, поэтому список точек ']' - это состояние вперед, а список точек '[' - состояние назад. Кроме того, я стал ленивым и пропустил часть Maybe, которая должна отлавливать ошибки сопоставления с образцом в openBrace а также closeBrace,

type ParseState = Cont ([TapeP] -> ([TapeP], TapeP))

toProgram :: String -> TapeP
toProgram = snd . ($ []) . (`runCont` (\a _ -> ([], a))) . toProgramStep


openBrace :: ParseState TapeP -> ParseState TapeP
openBrace mcontinue = do
  continue <- mcontinue
  cont $ \k (break:bs) -> let (cs, r) = k (loopControl continue break) bs in (continue:cs, r)

closeBrace :: ParseState TapeP -> ParseState TapeP
closeBrace mbreak = do
  break <- mbreak
  cont $ \k bs -> let (continue:cs, r) = k (loopControl continue break) (break:bs) in (cs, r)
Источник

Быть очень ленивым с этим ответом, так как мне не нравится Cont MonadFix - это то, что вы ищете? State это экземпляр, хотя и не Cont, и это позволяет вам делать вещи, которые выглядят как (используя нотацию "recursive do"):

{-# LANGUAGE DoRec #-}
parseInst str = do
    rec ctl <- parseInstructionsLinkingTo ctl str

Это было решение, которое я обнаружил для своей библиотеки актеров: мы хотим spawn операция, которая возвращает почтовый ящик порожденного актера, но тогда как мы можем запустить актеров, взаимодействующих друг с другом? Или актер с доступом к своему почтовому ящику?

С подходящим MonadFix Например, мы можем сделать:

fork3 = do
    rec mb1 <- spawn $ actorSpamming mb2 mb3
        mb2 <- spawn $ actorSpamming mb1 mb2
        mb3 <- spawn $ actorSpamming mb2 mb3
    send "go" mb1

Надежда выше дает вам идеи.

Источник
Другие вопросы по тегам