Haskell: Как написать интерактивный переводчик поверх государственной монады?

Question

Мы работаем над модельной файловой системой, которая использует монаду состояний внутри. У нас есть класс типов с такими операциями:

class Monad m => FS m where
  isDirectory  :: Path -> m Bool
  children     :: Path -> m [Path]
  ...

Мы работаем над небольшим интерактивным переводчиком, который будет предлагать такие команды, как cd, ls, cat, и так далее. Операция в интерпретаторе может быть записана так:

fsop :: FS m => Operation -> m Response

Определения Operation а также Response не важны; если хотите, возьмите их за струны.

Проблема, которую я пытаюсь решить, - написать цикл верхнего уровня в монаде ввода-вывода, который интерпретирует файловую систему. Operationс и печатает ответы. Если бы IO был экземпляром FS (то есть, если бы мы работали непосредственно с монадой IO), жизнь была бы простой: мы могли бы написать

loop :: Path -> IO ()
loop currentDir = do
        op <- getLine
        case read op of
          ChangeDir d -> loop d -- should test 'isDirectory d', but let's not
          Ls -> do { files <- children currentDir
                   ; mapM_ putStrLn files
                   ; loop currentDir }
          Exit -> return ()

Но это не то, что я хочу. Я хочу использовать Control.Monad.State:

newtype Filesystem a = Filesystem (State (Data.Map.Map Path Contents) a)

и объявить

instance Monad Filesystem ...
instance FS Filesystem ...

С использованием FS абстракция, я могу написать одношаговую функцию, которая должна работать с любым экземпляром, и в действительности компилируется следующий код:

step :: FS fs => Path -> Operation -> fs (Path, Response)
step currentDir op = 
        case op of
          ChangeDir d -> return (d, "")
          Ls -> do { files <- children currentDir
                   ; return (currentDir, unlines files) }

На данный момент я полностью застрял. Что я хочу сделать, это написать интерактивный цикл в монаде ввода-вывода, который может читать Operationс и печать Responses, но который работает на государственной монаде, которая не обязательно является IO. (Одна из причин наличия модели, которая не находится в IO, заключается в том, что мы можем протестировать свойства QuickCheck.)

Я чувствую, что это должно быть стандартной проблемой - интерактивный цикл read-eval-print поверх динамической абстракции, которая не IO- но я, должно быть, упускаю что-то невероятно очевидное, потому что не могу понять это. Я смотрел онлайн, но не был просвещен.

Любая помощь в написании интерактивных вычислений, выполняющих ввод-вывод, которые могут вызвать step будет принята с благодарностью.

Answer 1

Как насчет использования монадных трансформаторов? Это более или менее стандартный способ объединения монад. Вот упрощенный пример:

type Foo a = StateT String IO a

replT :: Foo ()
replT = do
  str   <- liftIO getLine
  state <- get
  liftIO $ putStrLn ("current state: " ++ state)
  liftIO $ putStrLn ("setting state: " ++ str)
  put str
  replT

Ниже приведены результаты запуска replT из ghci.

*Main> runStateT replT "Initial state"
asd
current state: Initial state
setting state: asd
zxc
current state: asd
setting state: zxc
asdasd

Есть три монадных трансформатора библиотеки. MTL, трансформаторы и монадЛиб. Я не могу рекомендовать ни один из них, так как я не пользуюсь ими много.

Answer 2

Отказ от ответственности: я не могу обещать, что следующее - хороший способ сделать это, но работать через это звучит весело. Давайте возьмем это для вращения, не так ли?

---

Несколько обязательных импортных

Во-первых, давайте отбросим некоторые типы данных. Я собираюсь заполнить некоторые детали и немного подправить вещи, чтобы определить простую "файловую систему", с которой мы можем реально взаимодействовать.

type Path = String
type Response = Maybe String
type Contents = [String]

data Operation = Cd Path 
               | Ls 
               | MkDir Path
               | Quit
    deriving (Read, Show)

Далее мы сделаем что-то немного остроумное... раздеть все монады. Какие? Это безумие! Возможно, но иногда вся скрытая сантехника >>= обеспечивает скрывает вещи слишком много.

Для самой файловой системы мы просто сохраним текущий рабочий каталог и карту путей к их дочерним элементам. Нам также понадобится несколько функций для взаимодействия с ним.

data Filesystem = Filesystem { wd :: Path, files :: M.Map Path Contents }
    deriving Show

newFS = Filesystem "/" (M.singleton "/" [])

isDirectory p fs = M.member p $ files fs
children p fs = fromMaybe [] . M.lookup p $ files fs
cd p fs = fs { wd = p }
create p fs = let newPath = wd fs ++ p ++ "/"
                  addPath = M.insert newPath [] . M.adjust (p:) (wd fs)
              in (newPath, fs { files = addPath $ files fs })

Теперь для безнадежной версии step функция. Нужно взять Operation и Filesystemи вернуть Response и (возможно, модифицированный) Filesystem:

step :: Operation -> Filesystem -> (Response, Filesystem)
step (Cd d) fs = (Just "Ok\n", cd d fs)
step (MkDir d) fs = first (\d -> Just $ "Created " ++ d ++ "\n") $ create d fs
step Ls fs = let files = children (wd fs) fs
             in (Just $ unlines files, fs)
step Quit fs = (Nothing, fs)

... хм, эта сигнатура типа уже очень похожа на State монада. Ну что ж, просто пока проигнорируй это и бросайся вслепую.

Теперь нам нужна функция, которая будет предоставлять универсальный интерфейс для Filesystem переводчик. В частности, мы хотим, чтобы интерфейс был, по крайней мере, несколько автономным, чтобы то, что использует интерфейс, не приходилось выполнять вручную, но мы хотим, чтобы интерфейс был достаточно незаметным для кода, использующего его, чтобы мы могли подключить его к IO монада, какой-то другой Monadили вообще никакой монады.

В первую очередь это говорит нам о том, что нам нужно каким-то образом чередовать внешний код с интерпретатором, а не контролировать какую-либо часть. Теперь, Haskell - функциональный язык, так что это означает, что использование большого количества функций высшего порядка - это хорошо, верно? Это звучит правдоподобно для меня, поэтому вот стратегия, которую мы будем использовать: если функция не знает, что делать дальше, мы передадим ей другую функцию, которая, как мы предполагаем, делает. Повторяйте, пока все не узнают, что происходит. Безупречный план, нет?

Сердце всего этого step функция, поэтому мы начнем просто с вызова этого.

interp1 :: Operation -> Filesystem -> (Response, Filesystem)
interp1 op fs = step op fs

... ну, это начало. Похоже. Но подождите, где находится Operation приходящий из? Нам нужен внешний код, чтобы обеспечить это, но мы не можем просто попросить его, не перепутав все с сомнительными символами, такими как IO, Таким образом, мы получили еще одну функцию, которая сделает за нас грязную работу:

interp2 :: ((Operation -> (Response, Filesystem)) -> t) -> Filesystem -> t
interp2 inp fs = inp (\op -> step op fs)

Конечно, теперь все, что у нас есть, это немного глупо t что мы даже не знаем что это такое. Мы знаем, что это должно иметь Response и Filesystem где-то в нем, но мы ничего не можем с этим поделать, поэтому мы передадим его обратно другой функции вместе с некоторыми инструкциями о том, как действовать... что, конечно, потребует передачи еще большего количества функций. Вы знаете, что это все функции внизу.

interp3 :: ((Operation -> (Response, Filesystem)) -> a)
           -> (a -> ((Response, Filesystem) -> b) -> c)
           -> (Filesystem -> b)
           -> (String -> Filesystem -> b) 
           -> Filesystem 
           -> c
interp3 inp check done out fs = check (inp (\op -> step op fs)) test
    where test (Nothing, fs) = done fs
          test (Just s, fs)  = out s fs

... ну, это довольно уродливо. Но не волнуйтесь, все идет по плану. Мы можем сделать пару замечаний дальше:

• Тип a существует только между inp а также checkТаким образом, оглядываясь назад, мы могли бы также объединить их заранее и просто передать составную функцию интерпретатору.
• Когда мы звоним done, это должно означать именно то, что написано на банке. Так что тип возвращаемого значения для done должен быть таким же, как весь переводчик, то есть b а также c должен быть того же типа.

Сейчас если done заканчивается все это, что out? Как следует из названия, не слишком тонкого, он обеспечивает вывод во внешний код, но куда он идет после этого? Он должен каким-то образом возвращаться к интерпретатору, и мы могли бы заметить, что наш интерпретатор еще не рекурсивен. Путь вперед ясен - переводчик, как и Йормунганд, таким образом захватывает свой собственный хвост; возвращаться к бесконечности, пока не закончится интерпретация (или пока Ragnarök, в зависимости от того, что произойдет раньше).

interp4 :: ((Operation -> (Response, Filesystem)) 
               -> ((Response, Filesystem) -> r) -> r)
           -> (Filesystem -> r)
           -> (String -> Filesystem -> (Filesystem -> r) -> r)
           -> Filesystem
           -> r
interp4 checkInp done out fs = checkInp (\op -> step op fs) test
    where loop = interp4 checkInp done out
          test (Nothing, fs) = done fs
          test (Just s, fs)  = out s fs loop

... о, я уже говорил, что это работает сейчас? Нет, серьезно!

Вот некоторые IO код для использования интерфейса:

ioIn f k = putStr "> " >> (k . f =<< readLn)
ioDone fs = putStrLn "Done" >> return fs 
ioOut x fs k = putStr x >> k fs

ioInterp :: IO Filesystem
ioInterp = interp4 ioIn ioDone ioOut newFS

А вот код, который запускает список команд, создавая список выходных строк:

scriptIn f k (x:xs) = k (f x) xs
scriptDone fs xs = ["Done\n"]
scriptOut r fs k xs = r : k fs xs

scriptInterp :: [Operation] -> [String]
scriptInterp = interp4 scriptIn scriptDone scriptOut newFS

Примеры запуска обоих в GHCi, если только код не поразил ваше воображение.

---

Ну вот и все. Либо это? Честно говоря, этот переводчик - это код, который может любить только мама. Есть ли что-то, что элегантно связало бы все это? Что-то, чтобы раскрыть основную структуру кода?

... хорошо, так что довольно очевидно, к чему это приведет. Общий дизайн функций, вызывающих друг друга по кругу, очень похож на стиль продолжения, и не один, а два раза в сигнатуре типа интерпретатора можно найти характерный образец (foo -> r) -> r, более известный как продолжение монады.

К сожалению, даже после всего этого от продолжений у меня болит голова, и я не уверен, как лучше распутать специальную структуру интерпретатора в вычислении, выполняемом в MonadCont,

Answer 3

Я могу придумать два решения здесь:

1) Используйте библиотеку монад трансформеров. Я не могу улучшить ответ Шимуара, кроме некоторых подробностей о библиотеках. Трансформеры сами по себе не дают необходимых примеров; вам нужно будет использовать преобразователи и monads-tf или monads-fd, которые предлагают реализации, основанные на семействах типов и fundeps, соответственно. Я предпочитаю monads-tf, если вы идете по этому пути. API почти идентичен с MTL. У меня нет опыта работы с MonadLib, но он тоже выглядит неплохо.

2) Напишите свой основной цикл в IO, и для каждой итерации цикла вызовите runState для оценки монады состояния. Что-то вроде следующего:

loop path state = do
  op <- readOp
  let ((newpath, resp), newstate) = runState (step path op) state
  print resp
  loop newpath newstate

Это должно работать, но это гораздо менее идиоматично, чем использование монадных трансформаторов.

Answer 4

Требовать ваши экземпляры FS быть примером MonadIO, не просто Monad:

class MonadIO m => FS m where ...

Тогда вам будут доступны liftIO способ поднять FS в IO:

liftIO :: MonadIO m => m a -> IO a

так что вы можете написать в IO монада:

files <- liftIO $ children currentDir

и т.д. Конечно, это означает, что вам нужно будет реализовать liftIOдля каждого FS прежде чем вы даже напишите экземпляр FS, но для этого приложения (не увидев реальных деталей) это звучит так, как будто все должно быть просто.