Haskell - Monad Transformers - ограничить количество оценок в интерпретаторе - PullRequest
Новая
       44

Haskell - Monad Transformers - ограничить количество оценок в интерпретаторе

0 голосов
/ 25 ноября 2018

Я изучаю Monad Transformers и решил написать переводчик для простого языка (с циклическими конструкциями), похожего на Brainfuck, используя Monad Transformers.Я хотел бы прервать работу интерпретатора после определенного числа операторов.

Этот простой язык состоит из одной ячейки памяти, способной содержать Int и 5 команд ввода, вывода, приращения, уменьшения и цикла.Цикл завершается, когда значение в памяти равно нулю.Входные данные читаются из списка, а аналогичные выходные данные записываются в другой список.Инкремент и декремент делает +1 и -1 к памяти соответственно.

Я использую тип World для отслеживания ввода, вывода (потоков) и памяти, Sum Int для подсчета количества оцененных инструкций.Except World для завершения оценки после определенных операторов. 

module Transformers where

import qualified Data.Map                      as Map
import           Data.Maybe
import           Control.Monad.State.Lazy
import           Control.Monad.Writer.Lazy
import           Control.Monad.Except


data Term = Input
  | Output
  | Increment
  | Decrement
  | Loop [Term]
  deriving (Show)

data World = World {
  inp :: [Int],
  out :: [Int],
  mem :: Int
} deriving Show

op_limit = 5

loop
  :: [Term]
  -> StateT World (WriterT (Sum Int) (Except World)) ()
  -> StateT World (WriterT (Sum Int) (Except World)) ()
loop terms sp = sp >> do
  s <- get
  if mem s == 0 then put s else loop terms (foldM (\_ t -> eval t) () terms)

limit :: StateT World (WriterT (Sum Int) (Except World)) ()
limit = do
  (s, count) <- listen get
  when (count >= op_limit) $ throwError s

tick :: StateT World (WriterT (Sum Int) (Except World)) ()
tick = tell 1

eval :: Term -> StateT World (WriterT (Sum Int) (Except World)) ()
eval Input =
  limit >> tick >> modify (\s -> s { inp = tail (inp s), mem = head (inp s) })
eval Output       = limit >> tick >> modify (\s -> s { out = mem s : out s })
eval Increment    = limit >> tick >> modify (\s -> s { mem = mem s + 1 })
eval Decrement    = limit >> tick >> modify (\s -> s { mem = mem s - 1 })
eval (Loop terms) = loop terms (void get)

type Instructions = [Term]

interp :: Instructions -> World -> Either World (World, Sum Int)
interp insts w =
  let sp = foldM (\_ inst -> eval inst) () insts
  in  runExcept (runWriterT (execStateT sp w))

Пример выполнения в ghci: 

*Transformers> interp [Loop [Output, Decrement]]  $ World [] [] 5
Right (World {inp = [], out = [1,2,3,4,5], mem = 0},Sum {getSum = 10})

Монада limit основана на количестве и должна решить либо Сбой с текущим состояниемили ничего не делатьНо я заметил, что count в (s, count) <- listen get всегда равен нулю.Я не понимаю, почему это происходит.Пожалуйста, помогите мне понять, где я ошибся.

  • Правильно ли упорядочен мой трансформатор в стеке?Существуют ли какие-либо правила (неформальные) для определения наслоения?

1 Ответ

0 голосов
/ 26 ноября 2018

Вычисления внутри монады Writer не могут иметь доступа к своему собственному аккумулятору.Более того: во время вычислений аккумулятор никогда не запускается, даже в WHNF.Это относится к и строгим и ленивым вариантам Writer - строгий вариант является строгим в смысле, не связанном с аккумулятором.Эта неизбежная лень в аккумуляторе может стать источником утечек в космосе, если вычисления выполняются слишком долго.

Ваша функция limit не разветвляется на значение "mainline" WriterT аккумулятора,Действие get (вы используете mtl) просто считывает состояние со слоя StateT и не выполняет никаких эффектов в других слоях: оно добавляет mempty к своему аккумулятору WriterT и не выдает ошибку.

Затем listen извлекает аккумулятор Writer действия get (только из get, а не всего вычисления) и добавляет его в аккумулятор "mainline".Но это извлеченное значение (возвращаемое в кортеже) всегда будет mempty, то есть Sum 0!

Вместо WriterT вы можете поместить счетчик в StateT состояние, как упомянул @chi.Вы также можете использовать AccumT, что очень похоже на WriterT, но позволяет осматривать аккумулятор (он также позволяет принудительно перевести его в WHNF с использованием шаблонов взрыва).

AccumT, похоже, не имеет соответствующего класса типов mtl, поэтому вам нужно будет посыпать несколько лифтов, чтобы использовать его.

...