Подтвердить что ты не робот

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

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

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 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) }

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 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

Существует три моноблочных трансформатора libs. mtl, трансформаторы и monadLib. Я не могу рекомендовать ни одного из них, так как я их не использую.

Ответ 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 и a Filesystem и вернуть a 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)

... hmm, подпись этого типа уже очень похожа на мужество монады 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 и a 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? Поскольку имя не слишком тонко подразумевает, оно обеспечивает вывод внешнего кода, но куда оно идет после этого? Ему нужно как-то вернуться в интерпретатор, и мы могли бы заметить, что наш интерпретатор еще не рекурсивный. Путь вперед ясен - переводчик, подобно Йормунганду, захватывает собственный хвост; цикл заканчивается бесконечно до тех пор, пока интерпретация не закончится (или пока Рагнарок, в зависимости от того, что наступит раньше).

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.

Ответ 3

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

1) Используйте библиотеку трансформатора монады. Я не могу улучшить ответ Shimuuar, за исключением некоторых деталей в библиотеках. Трансформаторы сами по себе не предоставляют необходимых экземпляров; вам понадобится использовать трансформаторы и monads-tf или monads-fd, которые предлагают реализации на основе семейств типов и платформ, соответственно. Я предпочитаю monads-tf, если вы идете по этому маршруту. Api почти идентичен 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

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

Ответ 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, но для это приложение (не увидев фактических данных) похоже, что это должно быть просто.