Комбинаторные разборщики - мощь Applicative, а также сделаем-ка мы монады!
Начало, оно же - предыдущая глава. Я отредактировал её, чтобы она была полноценным модулем, который мы сейчас переиспользуем.
Как обычно, текст можно использовать в качестве исходного кода.
>module ParsersTyped where
Я начал с функций вместо полномасштабных монадических или аппликативных комбинаторов пытаясь показать мощь языка в описании конкретных задач. Я смею надеятся, что мне удалось показать, как же выводятся типы для задачи и как далеко можно добраться, не абстрагируясь, а работая в конкретной предметной области.
Тем не менее, есть небольшой резон сделать разборщик чуть более абстрактным. Пока займёмся сокрытием внутренностей и реализацией трёх классов: Applicative, Alternative и Monad.
>import Control.Applicative -- классы Applicative и Alternative.
>-- класс Monad импортируется в Prelude, включаемом по умолчанию модуле.
>-- тем не менее, мы включим модуль Control.Monad для некоторых полезных функций:
>import Control.Monad (when)
>
>-- Используем код предыдущей главы, чтобы не повторяться лишний раз.
>-- некоторые символы будут конфликтовать, поэтому будем использовать указание префикса.
>import qualified ParsersFunc as P
Скрываем внутренности:
>newtype Parser a = Parser { runParser :: P.Parser a }
Почему newtype? У нас всего один конструктор, это раз. Если мы зададим значения через newtype, то у нас не будет лишнего уровня ссылок (не будет тэга конструктора) и не будет лишних ленивых вычислений. Хаскель таскает реализации классов отдельными скрытыми параметрами-записями, поэтому мы не добавляем накладных расходов сверх уже имеющихся и убираем некоторые возможные накладные расходы.
Applicative требует реализации оператора <*> и функции pure. Они у нас уже есть, их надо просто внести под конструктор:
>instance Applicative Parser where
> (Parser a) <*> (Parser b) = Parser $ a P.<*> b
> pure a = Parser $ P.pure a
То же самое с Alternative:
>instance Alternative Parser where
> (Parser a) <|> (Parser b) = Parser $ a P.<|> b
> empty = Parser $ P.stop
Оба класса имеют два метода, что надо определить и выводимые из определённых. Выше я определил ровно то, что минимально необходимо и вдогонку мы получили методы *> (f *> g - разобрать f, выбросить результат и вернуть результат разбора g), <* (то же самое, только выбрасываем результат правого разборщика), some, которые в предыдущей главе назывался many1 и many.
Для Applicative нам ещё понадобится Functor:
>instance Functor Parser where
> fmap f (Parser p) = Parser $ \s -> map (\(a,rest) -> (f a, rest)) (p s)
Чем интересны и полезны Alternative и Applicative? Они задают довольно жесткую структуру выражений, которая часто может быть вычислена статически. Эта статическая структура может быть обработана особым образом, более эффективно, чем более мощные варианты типа использования класса Monad.
В обсуждении к предыдущей главе как раз обсуждалось, что контекстно-зависимый разбор делается для Applicative/Alternative сложнее. Но при этом мы можем, например, скомпилировать это ограничение в железо (описание разбора на языке VHDL/Verilog), что затруднительно для класса Monad.
Теперь надо сделать реализацию класса Monad и продемонстрировать его мощь:
>instance Monad Parser where
> return = pure
> (Parser f) >>= q = Parser $ \s ->
> [(b,afterQ) | (a,afterS) <- f s, let (Parser g) = q a, (b, afterQ) <- g afterS]
Обратите внимание - мы вычисляем выражение Parser g на основе уже вычисленного значения a. Мы динамически формируем код разборщика в зависимости от разообранного значения. Поэтому, если значение действительно используется, мы будем создавать замыкания, тогда как код на Applicative/Alternative может быть преобразован в машину состояний.
Теперь дополним наши комбинаторы тем, что уже имелось:
>item :: Parser Char
>item = Parser P.item
>
>check :: (a -> Bool) -> Parser a -> Parser a
>check pred parser = do
> x <- parser
> if pred x then return x else empty -- используем условие!
>
>char :: Char -> Parser Char
>char c = check (==c) item
Ещё нам понадобится вызов разбора:
>parse :: String -> Parser a -> Either String a
>parse text (Parser p) = P.parse text p
Теперь сравним подходы по удобству. То, что в A/A требовало знаний на верхнем уровне, не требует такового в монадическом коде. Вот пример гипотетического разборщика контекстно-зависимой грамматики:
>-- XML. Как настоящий!
>data Xml = Empty | Tag String [Xml] | Text String
> deriving Show
>
>-- Верхний уровень разбора.
>aaXml :: P.Parser [Xml]
>aaXml = P.many (aaXmlTag P.<|> P.pure Text P.<*> (aaXmlText '<'))
>
>-- Разбор текста XML. Текст будет не пуст. Он не будет включать в себя
>-- символ exclude.
>aaXmlText :: Char -> P.Parser String
>aaXmlText exclude = P.many1 (P.check (/= exclude) P.item)
>
>-- Разобрать текст тэга, включая угловые скобки. Для closing ещё и '/' учитывается.
>aaXmlTagText :: Bool -> P.Parser String
>aaXmlTagText closing
> -- я поленился писать операторы <$>, <* и *> для предыдущих парсеров,
> -- поэтому код многословней, чем мог бы быть.
> | closing = P.pure (\_ _ t _ -> t) P.<*> P.char '<' P.<*> P.char '/' P.<*> aaXmlText '>' P.<*> P.char '>'
> | otherwise = P.pure (\_ t _ -> t) P.<*> P.char '<' P.<*> aaXmlText '>' P.<*> P.char '>'
>
>-- Разобрать часть XML, что окружена тэгами.
>aaXmlTag = P.pure (\(o,b,_) -> Tag o b) P.<*>
> (P.check (\(o,b,c) -> o == c) (P.pure (,,) P.<*> aaXmlTagText P.<*> aaXml P.<*> aaXmlTagText True))
>
>-- Тестирующий код.
>aaXmlTest = P.parse xmlTestString aaXml
Отдельно - строка для тестирования:
>xmlTestString = "opentextmore textclose"
И тот же функционал, только уже с монадическими комбинаторами:
>tyXml :: Parser [Xml]
>tyXml = many (tyXmlTag <|> Text <$> tyXmlText '<')
>tyXmlText :: Char -> Parser String
>tyXmlText exclude = some (check (/=exclude) item)
>tyXmlTagText :: Bool -> Parser String
>tyXmlTagText closing = do
> char '<'
> when closing (char '/' >> return ())
> text <- tyXmlText '>'
> char '>'
> return text
>tyXmlTag = do
> open <- tyXmlTagText False
> body <- tyXml
> close <- tyXmlTagText True
> when (open /= close) empty -- отказываемся признать разбор правильным.
> return $ Tag open body
>tyXmlTest = parse xmlTestString tyXml
Вот результаты прогона:
*ParsersTyped> tyXmlTest
Right [Text "open",Tag "tag1" [Text "text",Tag "tag2" [Text "more text"]],Text "close"]
*ParsersTyped> aaXmlTest
Right [Text "open",Tag "tag1" [Text "text",Tag "tag2" [Text "more text"]],Text "close"]
В общем, большая мощность требует жертв, но позволяет записывать код чуть более наглядно.
Следующий пост по этой теме будет про трансформеры - как реализовать всё вышеописанное на трансформерах. Это на удивление просто, надо следовать типам!
Как обычно, текст можно использовать в качестве исходного кода.
>module ParsersTyped where
Я начал с функций вместо полномасштабных монадических или аппликативных комбинаторов пытаясь показать мощь языка в описании конкретных задач. Я смею надеятся, что мне удалось показать, как же выводятся типы для задачи и как далеко можно добраться, не абстрагируясь, а работая в конкретной предметной области.
Тем не менее, есть небольшой резон сделать разборщик чуть более абстрактным. Пока займёмся сокрытием внутренностей и реализацией трёх классов: Applicative, Alternative и Monad.
>import Control.Applicative -- классы Applicative и Alternative.
>-- класс Monad импортируется в Prelude, включаемом по умолчанию модуле.
>-- тем не менее, мы включим модуль Control.Monad для некоторых полезных функций:
>import Control.Monad (when)
>
>-- Используем код предыдущей главы, чтобы не повторяться лишний раз.
>-- некоторые символы будут конфликтовать, поэтому будем использовать указание префикса.
>import qualified ParsersFunc as P
Скрываем внутренности:
>newtype Parser a = Parser { runParser :: P.Parser a }
Почему newtype? У нас всего один конструктор, это раз. Если мы зададим значения через newtype, то у нас не будет лишнего уровня ссылок (не будет тэга конструктора) и не будет лишних ленивых вычислений. Хаскель таскает реализации классов отдельными скрытыми параметрами-записями, поэтому мы не добавляем накладных расходов сверх уже имеющихся и убираем некоторые возможные накладные расходы.
Applicative требует реализации оператора <*> и функции pure. Они у нас уже есть, их надо просто внести под конструктор:
>instance Applicative Parser where
> (Parser a) <*> (Parser b) = Parser $ a P.<*> b
> pure a = Parser $ P.pure a
То же самое с Alternative:
>instance Alternative Parser where
> (Parser a) <|> (Parser b) = Parser $ a P.<|> b
> empty = Parser $ P.stop
Оба класса имеют два метода, что надо определить и выводимые из определённых. Выше я определил ровно то, что минимально необходимо и вдогонку мы получили методы *> (f *> g - разобрать f, выбросить результат и вернуть результат разбора g), <* (то же самое, только выбрасываем результат правого разборщика), some, которые в предыдущей главе назывался many1 и many.
Для Applicative нам ещё понадобится Functor:
>instance Functor Parser where
> fmap f (Parser p) = Parser $ \s -> map (\(a,rest) -> (f a, rest)) (p s)
Чем интересны и полезны Alternative и Applicative? Они задают довольно жесткую структуру выражений, которая часто может быть вычислена статически. Эта статическая структура может быть обработана особым образом, более эффективно, чем более мощные варианты типа использования класса Monad.
В обсуждении к предыдущей главе как раз обсуждалось, что контекстно-зависимый разбор делается для Applicative/Alternative сложнее. Но при этом мы можем, например, скомпилировать это ограничение в железо (описание разбора на языке VHDL/Verilog), что затруднительно для класса Monad.
Теперь надо сделать реализацию класса Monad и продемонстрировать его мощь:
>instance Monad Parser where
> return = pure
> (Parser f) >>= q = Parser $ \s ->
> [(b,afterQ) | (a,afterS) <- f s, let (Parser g) = q a, (b, afterQ) <- g afterS]
Обратите внимание - мы вычисляем выражение Parser g на основе уже вычисленного значения a. Мы динамически формируем код разборщика в зависимости от разообранного значения. Поэтому, если значение действительно используется, мы будем создавать замыкания, тогда как код на Applicative/Alternative может быть преобразован в машину состояний.
Теперь дополним наши комбинаторы тем, что уже имелось:
>item :: Parser Char
>item = Parser P.item
>
>check :: (a -> Bool) -> Parser a -> Parser a
>check pred parser = do
> x <- parser
> if pred x then return x else empty -- используем условие!
>
>char :: Char -> Parser Char
>char c = check (==c) item
Ещё нам понадобится вызов разбора:
>parse :: String -> Parser a -> Either String a
>parse text (Parser p) = P.parse text p
Теперь сравним подходы по удобству. То, что в A/A требовало знаний на верхнем уровне, не требует такового в монадическом коде. Вот пример гипотетического разборщика контекстно-зависимой грамматики:
>-- XML. Как настоящий!
>data Xml = Empty | Tag String [Xml] | Text String
> deriving Show
>
>-- Верхний уровень разбора.
>aaXml :: P.Parser [Xml]
>aaXml = P.many (aaXmlTag P.<|> P.pure Text P.<*> (aaXmlText '<'))
>
>-- Разбор текста XML. Текст будет не пуст. Он не будет включать в себя
>-- символ exclude.
>aaXmlText :: Char -> P.Parser String
>aaXmlText exclude = P.many1 (P.check (/= exclude) P.item)
>
>-- Разобрать текст тэга, включая угловые скобки. Для closing ещё и '/' учитывается.
>aaXmlTagText :: Bool -> P.Parser String
>aaXmlTagText closing
> -- я поленился писать операторы <$>, <* и *> для предыдущих парсеров,
> -- поэтому код многословней, чем мог бы быть.
> | closing = P.pure (\_ _ t _ -> t) P.<*> P.char '<' P.<*> P.char '/' P.<*> aaXmlText '>' P.<*> P.char '>'
> | otherwise = P.pure (\_ t _ -> t) P.<*> P.char '<' P.<*> aaXmlText '>' P.<*> P.char '>'
>
>-- Разобрать часть XML, что окружена тэгами.
>aaXmlTag = P.pure (\(o,b,_) -> Tag o b) P.<*>
> (P.check (\(o,b,c) -> o == c) (P.pure (,,) P.<*> aaXmlTagText P.<*> aaXml P.<*> aaXmlTagText True))
>
>-- Тестирующий код.
>aaXmlTest = P.parse xmlTestString aaXml
Отдельно - строка для тестирования:
>xmlTestString = "opentextmore textclose"
И тот же функционал, только уже с монадическими комбинаторами:
>tyXml :: Parser [Xml]
>tyXml = many (tyXmlTag <|> Text <$> tyXmlText '<')
>tyXmlText :: Char -> Parser String
>tyXmlText exclude = some (check (/=exclude) item)
>tyXmlTagText :: Bool -> Parser String
>tyXmlTagText closing = do
> char '<'
> when closing (char '/' >> return ())
> text <- tyXmlText '>'
> char '>'
> return text
>tyXmlTag = do
> open <- tyXmlTagText False
> body <- tyXml
> close <- tyXmlTagText True
> when (open /= close) empty -- отказываемся признать разбор правильным.
> return $ Tag open body
>tyXmlTest = parse xmlTestString tyXml
Вот результаты прогона:
*ParsersTyped> tyXmlTest
Right [Text "open",Tag "tag1" [Text "text",Tag "tag2" [Text "more text"]],Text "close"]
*ParsersTyped> aaXmlTest
Right [Text "open",Tag "tag1" [Text "text",Tag "tag2" [Text "more text"]],Text "close"]
В общем, большая мощность требует жертв, но позволяет записывать код чуть более наглядно.
Следующий пост по этой теме будет про трансформеры - как реализовать всё вышеописанное на трансформерах. Это на удивление просто, надо следовать типам!