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

Я пишу интерпретатор brainfuck в Haskell, и я придумал то, что, по моему мнению, очень интересное описание программы:

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

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

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

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 для меня (см. все ревизии). Может ли его техника труба/трубопровод быть переведена в Haskell с помощью Cont?

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

Ответ 1

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

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)

Ответ 2

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

{-# 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

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