Хабрахабр

Аппликативные парсеры на Haskell

Мне казалось, что гораздо лучше всегда следовать принципу KISS и писать велосипеды с использованием элементарных конструкций языка, чем разбираться во всех этих классах типов, чтобы где-то в итоге написать одну якобы удобную конструкцию. Когда я только начинала осваивать Haskell, меня очень раздражало повсеместное использование сложных абстракций вместо каких-то конкретных решений.

Для меня одним из самых удачных таких примеров оказались парсеры. Мне не хватало хорошего примера, где бы окупались усилия, потраченные на освоение "матчасти". Теперь я довольно часто рассказываю про них, когда у меня спрашивают, для каких распространённых задач можно красиво использовать Haskell.

Я хочу предложить начинающим тоже пройти этот путь и создать с нуля небольшую базу функций для удобной реализации парсеров, а затем использовать её для написания собственного парсера, код которого будет практически дословно повторять грамматику, по которой осуществляется разбор.

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

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

В качестве отличной русскоязычной книги для начинающих советую "О Haskell по-человечески" Дениса Шевченко. Для тех, кто на Haskell никогда не писал, но хочет понять, что здесь происходит, рекомендую сначала посмотреть на соответствующую страницу на Learn X in Y minutes.

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

Я рада, что вы их знаете и конечно же с лёгкостью освоили. И да, господа хаскелисты, многие вещи объяснены очень просто и топорно, для частных случаев, не очень абстрактно, без использования терминов из теории категорий и других страшных слов. Я их тоже знаю, но не считаю нужным вываливать такой объём лишней в данном контексте информации на неподготовленных читателей.

Если проводить аналогию с ООП, то классы типов скорее напоминают перегрузку методов и функций. Классы типов в Haskell не имеют ничего общего с классами в С++ и прочих объектно-ориентированных языках.

Например, все числа можно сравнивать на равенство, но упорядочить можно все, кроме комплексных, а функции в общем случае сравнить вообще нельзя. Классы определяют, какие действия можно совершать с объектами тех типов, которые входят в класс. То, что можно напечатать, переведя в строку, принадлежит к классу Show, у него есть "противоположенный" класс Read, который определяет, как преобразовывать строки в объекты нужного типа. Класс типов, которые можно сравнивать, называется Eq, упорядочить — Ord (типы не обязательно должны быть числовыми).

Для набора стандартных классов типов (таких как Eq, Show, Read ...) можно попросить компилятор реализовать нужный функционал стандартным образом, используя ключевое слово deriving после определения типа:

data Point = Point deriving (Eq, Show)

Можно определять свои классы типов:

class PrettyPrint a where pPrint :: a -> String

После ключевого слова where следует список так называемых методов класса, т.е. Здесь PrettyPrint — имя класса, a — переменная типа. функций, которые могут быть применены к объектам, имеющим тип из этого класса.

Для того, чтобы обозначить принадлежность типа данных к классу, используется следующая конструкция:

instance PrettyPrint Point where pPrint (Point x y) = "(" ++ show x ++ ", " ++ show y ++ ")"

Язык позволяет указывать ограничения на классы типов, к которым должны относиться аргументы функции:

showVsPretty :: (Show a, PrettyPrint a) => a -> (String, String)
showVsPretty x = (show x, pPrint x)

Для каждого вызова функции компилятор проверяет, выполнены ли эти требования к типу, и в случае неудачи выводит ошибку (естественно, это происходит на этапе компиляции).

>>> showVsPretty (Point 2 3)
("Point {xCoord = 2.0, yCoord = 3.0}","(2.0, 3.0)") >>> showVsPretty "str"
error: No instance for (PrettyPrint [Char]) arising from a use of ‘showVsPretty’

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

Для описания одного результата работы парсера подойдёт кортеж из двух элементов (String, a), где a — переменная типа, которая может обозначать любой пользовательский тип.

Поскольку парсер разбирает строку по каким-то правилам, опишем его как функцию, принимающую на вход строку и возвращающую список результатов:

newtype Parser a = Parser { unParser :: String -> [(String, a)] }

Реализуем вспомогательную функцию, которая пытается осуществить однозначный разбор строки целиком: Будем считать разбор успешным, если список результатов состоит из одного элемента, и входная строка была полностью обработана.

parseString :: String -> Parser a -> Maybe a
parseString s (Parser p) = case (p s) of [("", val)] -> Just val _ -> Nothing

Простейшие парсеры

Реализуем несколько простых парсеров, которые потом пригодятся в построении более сложных комбинаций.

Если входная строка пуста, то и результатом работы является пустой список. Начнём с разбора одного символа, который должен удовлетворять предикату. Если вернулось значение True, то результатом разбора является этот символ; возвращаем его вместе с остатком строки. В противном случае проверяем значение предиката на первом символе строки. В противном случае разбор также оканчивается неудачей.

predP :: (Char -> Bool) -> Parser Char
predP p = Parser f where f "" = [] f (c : cs) | p c = [(cs, c)] | otherwise = []

Для этого используем только что написанную predP и передадим ей в качестве аргумента функцию, сравнивающую свой аргумент с нужным нам символом: Теперь мы можем написать парсер, принимающий конкретный символ в начале строки.

charP :: Char -> Parser Char
charP char = predP (\c -> c == char)

Назовём его stringP. Следующий простейший случай: парсер, принимающий только определённую строку целиком. В противном случае разбор не удался, и возвращается пустой список результатов. Функция внутри парсера сравнивает входную строку с нужной и, если строки равны, возвращает список из одного элемента: пары из пустой строки (на входе больше ничего не осталось) и исходной.

stringP :: String -> Parser String
stringP s = Parser f where f s' | s == s' = [("", s)] | otherwise = []

При этом результат разбора нам не важен и в дальнейшем не пригодится. Довольно часто нужно пропустить символы, обладающие определённым свойством, пока они идут в начале строки (например, пробельные символы). В качестве результата разбора используем пустой кортеж. Напишем функцию skip, которая пропускает начальные символы строки, пока сохраняется истинное значение предиката.

skip :: (Char -> Bool) -> Parser ()
skip p = Parser (\s -> [(dropWhile p s, ())])

Оба проверяют префикс входной строки, только первый в случае успеха возвращает этот префикс, а второй — пустой кортеж, т.е. Следующие два парсера очень похожи друг на друга. Для реализации используется функция isPrefixOf, определённая в модуле Data. позволяет пропустить произвольную строку в начале входа. List.

prefixP :: String -> Parser String
prefixP s = Parser f where f input = if s `isPrefixOf` input then [(drop (length s) input, s)] else [] skipString :: String -> Parser ()
skipString s = Parser f where f input = if s `isPrefixOf` input then [(drop (length s) input, ())] else []

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

Парсер как функтор

Простейший пример — список в качестве контейнера и функция map, которая есть практически во всех высокоуровневых языках. Можно выделить целый класс типов-контейнеров, для которых верно следующее: если известно, как преобразовывать объекты внутри контейнера, то можно преобразовывать и сами контейнеры. Действительно, можно пройтись по всем элементам списка типа [a], применить к каждому функцию a -> b и получить список типа [b].

Такой класс типов называется Functor, у класса есть один метод fmap:

class Functor f where fmap :: (a -> b) -> f a -> f b

Можно ли сказать, что тогда есть парсер для объектов типа b? Предположим, что мы уже умеем разбирать строки в объекты некоторого типа a, и, кроме того, знаем, как преобразовать объекты типа a в объекты типа b.

Если выразить это в виде функции, то она будет иметь следующий тип:

(a -> b) -> Parser a -> Parser b

Создадим с нуля парсер значений типа b, который будет сначала вызывать первый парсер (он у нас уже есть), а затем применять функцию к результатам его разбора. Этот тип совпадает с типом функции fmap, поэтому попробуем сделать парсер функтором.

instance Functor Parser where fmap :: (a -> b) -> Parser a -> Parser b fmap f (Parser p1) = Parser p2 where p2 :: String -> [(String, b)] p2 s = convert (p1 s) convert :: [(String, a)] -> [(String, b)] convert results = map (\(s, val) -> (s, f val)) results

У функции fmap есть удобный инфиксный синоним: fmap f x == f <$> x.

Если в качестве аргумента fmap использовать функцию, просто заменяющую свой первый аргумент на новое значение, то получим ещё одну полезную операцию, которая уже реализована для всех функторов даже в двух экземплярах (они отличаются только порядком аргументов):

(<$) :: Functor f => a -> f b -> f a
($>) :: Functor f => f a -> b -> f b

Теперь можно его реализовать следующим образом: Помните парсер, который пропускает определённую строку (skipString)?

skipString :: String -> Parser ()
skipString s = () <$ prefixP s

Комбинации парсеров

Это значит, что функция от n аргументов — это на самом деле функция от одного аргумента, возвращающая функцию от n-1 аргументов: В Haskell все функции по умолчанию каррированы и допускают частичное применение.

cons :: Int -> [Int] -> [Int]
cons = (:) cons1 :: [Int] -> [Int]
cons1 = cons 1 -- функция cons применена частично

Типы будут такие: Применим функцию от трёх аргументов к какому-нибудь значению внутри парсера, используя fmap.

f :: c -> a -> b
p :: Parser c
(fmap f p) :: Parser (a -> b)

Конечно, возможна ситуация, когда во входной строке действительно находится представление функции, но хотелось бы иметь возможность применять эту функцию, а точнее комбинировать парсеры Parser (a -> b) и Parser a, чтобы получить Parser b: Получился парсер функции?!

applyP :: Parser (a -> b) -> Parser a -> Parser b

Это даёт интуитивное понимание того, как должна выглядеть реализация функции applyP: получить функцию из контейнера (как результат применения первого парсера), получить значения, к которым должна применяться функция (результат применения второго парсера) и "запаковать" преобразованные с помощью этой функции значения обратно в контейнер (создать новый парсер). Тип этой функции очень похож на тип fmap, только сама функция, которую нужно применить, также находится в контейнере. В реализации будем использовать list comprehension:

applyP :: Parser (a -> b) -> Parser a -> Parser b
applyP (Parser p1) (Parser p2) = Parser f where f s = [ (sx, f x) | (sf, f) <- p1 s, -- p1 применяется к исходной строке (sx, x) <- p2 sf] -- p2 применяется к строке, оставшейся после предыдущего разбора

Второй метод класса называется pure и используется для того, чтобы "завернуть" или "поднять" (lift) значение, в том числе функциональное. Существует класс Applicative, у которого есть метод с таким же прототипом. В случае реализации для парсера функция pure добавляет свой аргумент в результат работы парсера, не изменяя при этом входную строку.

class Functor f => Applicative f where pure :: a -> f a (<*>) :: f (a -> b) -> f a -> f b instance Applicative Parser where pure x = Parser (\s -> [(s, x)]) pf <*> px = Parser (\s -> [ (sx, f x) | (sf, f) <- unParser pf $ s, (sx, x) <- unParser px $ sf])

Типы, принадлежащие к этому классу, называются аппликативными функторами. Функция applyP — это и есть <*> из класса Applicative.

Для аппликативных функторов реализованы две вспомогательные функции, которые будут нам полезны:

(*>) :: f a -> f b -> f b
(<*) :: f a -> f b -> f a

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

Рассмотрим следующий тип данных: Комбинируя <$> и <*>, можно создавать очень удобные конструкции.

data MyStructType = MyStruct { field1 :: Type1 , field2 :: Type2 , field3 :: Type3 }

С конструктором можно работать как и с любой другой функцией. Конструктор значений MyStruct — это тоже функция, в данном случае она имеет тип Type1 -> Type2 -> Type3 -> MyStructType. Предположим, что для типов полей структуры уже написаны парсеры:

parser1 :: Parser Type1
parser2 :: Parser Type2
parser3 :: Parser Type3

С помощью функции fmap можно частично применить MyStruct к первому из этих парсеров:

parserStruct' :: Parser (Type2 -> Type3 -> MyStructType)
parserStruct' = MyStruct <$> parser1

Для этого уже нужно использовать <*>: Попробуем дальше применять функцию, которая теперь находится "внутри" парсера.

parserStruct'' :: Parser (Type3 -> MyStructType)
parserStruct'' = parserStruct' <*> parser2 parserStruct :: Parser MyStructType
parserStruct = parserStruct'' <*> parser3

То же самое можно сделать в одну строчку: В итоге мы получили парсер для всей структуры (конечно, здесь используется предположение, что в исходной строке представления её полей идут подряд).

parserStruct :: Parser MyStructType
parserStruct = MyStruct <$> parser1 <*> parser2 <*> parser3

Такие конструкции будут часто встречаться в примере использования.

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

data Operand = IntOp Int | IdentOp String

Этот парсер представляет собой альтернативу из двух других, поэтому нам нужна функция, умеющая комбинировать парсеры таким образом, чтобы результаты их работы объединялись. Если мы уже умеем разбирать целые числа и идентификаторы (например, как в языке С), то нам нужен один парсер для операндов который может разобрать одно или другое. Реализуем функцию altP, комбинирующую два парсера: Результатом работы парсера является список, а объединение списков — это их конкатенация.

altP :: Parser a -> Parser a -> Parser a
altP (Parser p1) (Parser p2) = Parser (\s -> p1 s ++ p2 s)

Тогда парсер операнда можно реализовать, используя эту функцию (здесь предполагается, что parserInt и parserIdent уже где-то описаны:

parserOperand :: Parser Operand
parserOperand = altP parserIntOp parserIdentOp where parserIntOp = IntOp <$> parserInt parserIdentOp = IdentOp <$> parserIdent

В нём есть ещё один метод, empty, описывающий нейтральный элемент для операции альтернативы. Конечно, и для альтернатив уже придумали отдельный класс, который так и называется Alternative. всегда возвращает пустой список результатов. В нашем случае это парсер, который никогда ничего не разбирает, т.е. Для парсера реализация методов класса Alternative выглядит так:

class Applicative f => Alternative f where empty :: f a (<|>) :: f a -> f a -> f a instance Alternative Parser where empty = Parser (const []) px <|> py = Parser (\s -> unParser px s ++ unParser py s)

Операция <|> — это и есть функция altP, только в инфиксной записи, которую удобнее использовать, комбинируя несколько парсеров подряд.

Каждая из них может быть выражена через другую: Для всех типов в этом классе реализованы две функции, some и many типа f a -> f [a].

some v = (:) <$> v <*> many v
many v = some v <|> pure []

В случае использования some последовательность должна быть непустой. В терминах парсеров эти функции позволяют разбирать последовательности данных, если известно, как разобрать один элемент данных.

Теперь у нас всё готово для того, чтобы написать свой парсер, например, для простых арифметических выражений со следующей грамматикой:

expr ::= constExpr | binOpExpr | negExpr const ::= int int ::= digit{digit} digit ::= '0' | ... | '9' binOpExpr ::= '(' expr ' ' binOp ' ' expr ')' binOp ::= '+' | '*' negExpr ::= '-' expr

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

Примеры правильной записи выражений:

"123" "-(10 + 42)" "(1 + ((2 + 3) * (4 + 5)))"

Примеры неправильной записи:

" 666 " "2 + 3" "(10 * 10)"

Объявим необходимые типы данных (само выражение и бинарная операция):

data Expr = ConstExpr Int | BinaryExpr Expr Operator Expr | NegateExpr Expr data Operator = Add | Mul

Само выражение состоит из трёх альтернатив. Можно приступать к разбору! Так и запишем:

-- expr ::= constExpr | binOpExpr | negExpr
exprParser :: Parser Expr
exprParser = constParser <|> binParser <|> negParser

В нашем типе данных оно "завёрнуто" в конструктор, поэтому мы не можем использовать парсер для целого числа напрямую, но можем применить fmap, чтобы получить значение нужного типа. Константа — целое положительное число.

-- const ::= int
constParser :: Parser Expr
constParser = ConstExpr <$> intParser

Для разбора одной цифры используем вспомогательную функцию predP и предикат isDigit из модуля Data. Целое число, согласно грамматике, представляется как непустая последовательность цифр. Теперь для построения парсера для разбора последовательности цифр используем функцию some (не many, потому что должна быть хотя бы одна цифра). Char. Например, если входная строка "123ab", список результатов будет следующим: [("ab", "123"), ("3ab", "12"), ("23ab", "1")]. Результат работы такого парсера возвращает список всех возможных вариантов разбора, начиная с самой длинной записи. Целиком реализация выглядит следующим образом: Нам нужно разобрать самую длинную последовательность цифр и преобразовать её к типу Int.

-- int ::= digit{digit}
-- digit ::= '0' | ... | '9'
intParser :: Parser Int
intParser = Parser $ \s -> let res = unParser (some digitParser) s in case res of [] -> [] ((rest, i) : xs) -> [(rest, read i)] where digitParser = predP isDigit

Согласно грамматике, во входной строке сначала должна идти открывающая скобка, первый операнд, пробел, символ операции, ещё один пробел, второй операнд и закрывающая скобка. Следующий вариант записи выражения — применение бинарной операции. Операнды — это выражения, а для их разбора парсер уже есть (exprParser). Для разбора отдельных символов (скобок и пробелов) используем функцию charP. Остаётся аккуратно скомбинировать этот набор парсеров. Для разбора символа бинарной операции опишем вспомогательный парсер чуть ниже. Для этого используем *> и <*: В начале и в конце выражения должны быть скобки: нужно это проверить, но сам результат отбросить.

binParser :: Parser Expr
binParser = charP '(' *> ??? <* charP ')'

Не забудем про пробелы вокруг символа операции, используя тот же метод, что и для скобок. Между этими парсерами для скобок должно происходить конструирование выражения с помощью конструктора BinaryExpr и парсеров для выражения и операции. Эта часть выглядит следующим образом:

BinaryExpr <$> exprParser -- первый операнд <*> (charP ' ' *> binOpParser <* charP ' ') -- операция, окружённая пробелами <*> exprParser -- второй операнд

Подставим это выражение вместо знаков вопроса:

-- binOpExpr ::= '(' expr ' ' binOp ' ' expr ')'
binParser :: Parser Expr
binParser = charP '(' *> (BinaryExpr <$> exprParser <*> (charP ' ' *> binOpParser <* charP ' ') <*> exprParser ) <* charP ')'

Бинарная операция — это либо символ +, который разбирается в значение Add, либо *, который разбирается в Mul:

-- binOp ::= '+' | '*'
binOpParser :: Parser Operator
binOpParser = plusParser <|> multParser where plusParser = charP '+' $> Add multParser = charP '*' $> Mul

С символом - поступаем так же, как со скобками и пробелами. Осталась самая простая часть грамматики, отрицание выражения. Далее применяем конструктор NegateExpr к результату рекурсивного разбора:

-- negExpr ::= '-' expr
negParser = charP '-' *> (NegateExpr <$> exprParser)

Код во многом напоминает грамматику и полностью совпадает с ней по структуре. Итак, все части парсера реализованы.

Исходный код доступен на GitLab: https://gitlab.com/fierce-katie/applicative-parsers-demo.

Проект можно собрать утилитой Stack и запустить примитивный интерпретатор, использующий парсер, который мы написали: Там проще оценить его объём и степень выразительности, поскольку комментариев гораздо меньше.

$ stack build
$ stack exec demo-parser

Тем, кто хочет потренироваться дальше самостоятельно, могу посоветовать следующее:

  • Грамматику можно всячески улучшить, например, допускать ведущие и висячие пробелы, добавить новые операции и т.д.
  • Парсер переводит строку во внутреннее представление выражения. Это выражение можно вычислить и преобразовать интерпретатор так, чтобы он печатал не результат разбора а результат вычисления.
  • Изучить возможности библиотек parsec, attoparsec, applicative-parsec и optparse-applicative, попробовать их применить.

Спасибо за внимание!

  1. Learn Haskell in Y minutes
  2. Денис Шевченко. "О Haskell по-человечески"
  3. Библиотека parsec
  4. Библиотека attoparsec
  5. Библиотека applicative-parsec
  6. Библиотека optparse-applicative
Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Хабрахабр

Аппликативные парсеры на Haskell

Мне казалось, что гораздо лучше всегда следовать принципу KISS и писать велосипеды с использованием элементарных конструкций языка, чем разбираться во всех этих классах типов, чтобы где-то в итоге написать одну якобы удобную конструкцию. Когда я только начинала осваивать Haskell, меня очень раздражало повсеместное использование сложных абстракций вместо каких-то конкретных решений.

Для меня одним из самых удачных таких примеров оказались парсеры. Мне не хватало хорошего примера, где бы окупались усилия, потраченные на освоение "матчасти". Теперь я довольно часто рассказываю про них, когда у меня спрашивают, для каких распространённых задач можно красиво использовать Haskell.

Я хочу предложить начинающим тоже пройти этот путь и создать с нуля небольшую базу функций для удобной реализации парсеров, а затем использовать её для написания собственного парсера, код которого будет практически дословно повторять грамматику, по которой осуществляется разбор.

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

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

В качестве отличной русскоязычной книги для начинающих советую "О Haskell по-человечески" Дениса Шевченко. Для тех, кто на Haskell никогда не писал, но хочет понять, что здесь происходит, рекомендую сначала посмотреть на соответствующую страницу на Learn X in Y minutes.

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

Я рада, что вы их знаете и конечно же с лёгкостью освоили. И да, господа хаскелисты, многие вещи объяснены очень просто и топорно, для частных случаев, не очень абстрактно, без использования терминов из теории категорий и других страшных слов. Я их тоже знаю, но не считаю нужным вываливать такой объём лишней в данном контексте информации на неподготовленных читателей.

Если проводить аналогию с ООП, то классы типов скорее напоминают перегрузку методов и функций. Классы типов в Haskell не имеют ничего общего с классами в С++ и прочих объектно-ориентированных языках.

Например, все числа можно сравнивать на равенство, но упорядочить можно все, кроме комплексных, а функции в общем случае сравнить вообще нельзя. Классы определяют, какие действия можно совершать с объектами тех типов, которые входят в класс. То, что можно напечатать, переведя в строку, принадлежит к классу Show, у него есть "противоположенный" класс Read, который определяет, как преобразовывать строки в объекты нужного типа. Класс типов, которые можно сравнивать, называется Eq, упорядочить — Ord (типы не обязательно должны быть числовыми).

Для набора стандартных классов типов (таких как Eq, Show, Read ...) можно попросить компилятор реализовать нужный функционал стандартным образом, используя ключевое слово deriving после определения типа:

data Point = Point deriving (Eq, Show)

Можно определять свои классы типов:

class PrettyPrint a where pPrint :: a -> String

После ключевого слова where следует список так называемых методов класса, т.е. Здесь PrettyPrint — имя класса, a — переменная типа. функций, которые могут быть применены к объектам, имеющим тип из этого класса.

Для того, чтобы обозначить принадлежность типа данных к классу, используется следующая конструкция:

instance PrettyPrint Point where pPrint (Point x y) = "(" ++ show x ++ ", " ++ show y ++ ")"

Язык позволяет указывать ограничения на классы типов, к которым должны относиться аргументы функции:

showVsPretty :: (Show a, PrettyPrint a) => a -> (String, String)
showVsPretty x = (show x, pPrint x)

Для каждого вызова функции компилятор проверяет, выполнены ли эти требования к типу, и в случае неудачи выводит ошибку (естественно, это происходит на этапе компиляции).

>>> showVsPretty (Point 2 3)
("Point {xCoord = 2.0, yCoord = 3.0}","(2.0, 3.0)") >>> showVsPretty "str"
error: No instance for (PrettyPrint [Char]) arising from a use of ‘showVsPretty’

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

Для описания одного результата работы парсера подойдёт кортеж из двух элементов (String, a), где a — переменная типа, которая может обозначать любой пользовательский тип.

Поскольку парсер разбирает строку по каким-то правилам, опишем его как функцию, принимающую на вход строку и возвращающую список результатов:

newtype Parser a = Parser { unParser :: String -> [(String, a)] }

Реализуем вспомогательную функцию, которая пытается осуществить однозначный разбор строки целиком: Будем считать разбор успешным, если список результатов состоит из одного элемента, и входная строка была полностью обработана.

parseString :: String -> Parser a -> Maybe a
parseString s (Parser p) = case (p s) of [("", val)] -> Just val _ -> Nothing

Простейшие парсеры

Реализуем несколько простых парсеров, которые потом пригодятся в построении более сложных комбинаций.

Если входная строка пуста, то и результатом работы является пустой список. Начнём с разбора одного символа, который должен удовлетворять предикату. Если вернулось значение True, то результатом разбора является этот символ; возвращаем его вместе с остатком строки. В противном случае проверяем значение предиката на первом символе строки. В противном случае разбор также оканчивается неудачей.

predP :: (Char -> Bool) -> Parser Char
predP p = Parser f where f "" = [] f (c : cs) | p c = [(cs, c)] | otherwise = []

Для этого используем только что написанную predP и передадим ей в качестве аргумента функцию, сравнивающую свой аргумент с нужным нам символом: Теперь мы можем написать парсер, принимающий конкретный символ в начале строки.

charP :: Char -> Parser Char
charP char = predP (\c -> c == char)

Назовём его stringP. Следующий простейший случай: парсер, принимающий только определённую строку целиком. В противном случае разбор не удался, и возвращается пустой список результатов. Функция внутри парсера сравнивает входную строку с нужной и, если строки равны, возвращает список из одного элемента: пары из пустой строки (на входе больше ничего не осталось) и исходной.

stringP :: String -> Parser String
stringP s = Parser f where f s' | s == s' = [("", s)] | otherwise = []

При этом результат разбора нам не важен и в дальнейшем не пригодится. Довольно часто нужно пропустить символы, обладающие определённым свойством, пока они идут в начале строки (например, пробельные символы). В качестве результата разбора используем пустой кортеж. Напишем функцию skip, которая пропускает начальные символы строки, пока сохраняется истинное значение предиката.

skip :: (Char -> Bool) -> Parser ()
skip p = Parser (\s -> [(dropWhile p s, ())])

Оба проверяют префикс входной строки, только первый в случае успеха возвращает этот префикс, а второй — пустой кортеж, т.е. Следующие два парсера очень похожи друг на друга. Для реализации используется функция isPrefixOf, определённая в модуле Data. позволяет пропустить произвольную строку в начале входа. List.

prefixP :: String -> Parser String
prefixP s = Parser f where f input = if s `isPrefixOf` input then [(drop (length s) input, s)] else [] skipString :: String -> Parser ()
skipString s = Parser f where f input = if s `isPrefixOf` input then [(drop (length s) input, ())] else []

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

Парсер как функтор

Простейший пример — список в качестве контейнера и функция map, которая есть практически во всех высокоуровневых языках. Можно выделить целый класс типов-контейнеров, для которых верно следующее: если известно, как преобразовывать объекты внутри контейнера, то можно преобразовывать и сами контейнеры. Действительно, можно пройтись по всем элементам списка типа [a], применить к каждому функцию a -> b и получить список типа [b].

Такой класс типов называется Functor, у класса есть один метод fmap:

class Functor f where fmap :: (a -> b) -> f a -> f b

Можно ли сказать, что тогда есть парсер для объектов типа b? Предположим, что мы уже умеем разбирать строки в объекты некоторого типа a, и, кроме того, знаем, как преобразовать объекты типа a в объекты типа b.

Если выразить это в виде функции, то она будет иметь следующий тип:

(a -> b) -> Parser a -> Parser b

Создадим с нуля парсер значений типа b, который будет сначала вызывать первый парсер (он у нас уже есть), а затем применять функцию к результатам его разбора. Этот тип совпадает с типом функции fmap, поэтому попробуем сделать парсер функтором.

instance Functor Parser where fmap :: (a -> b) -> Parser a -> Parser b fmap f (Parser p1) = Parser p2 where p2 :: String -> [(String, b)] p2 s = convert (p1 s) convert :: [(String, a)] -> [(String, b)] convert results = map (\(s, val) -> (s, f val)) results

У функции fmap есть удобный инфиксный синоним: fmap f x == f <$> x.

Если в качестве аргумента fmap использовать функцию, просто заменяющую свой первый аргумент на новое значение, то получим ещё одну полезную операцию, которая уже реализована для всех функторов даже в двух экземплярах (они отличаются только порядком аргументов):

(<$) :: Functor f => a -> f b -> f a
($>) :: Functor f => f a -> b -> f b

Теперь можно его реализовать следующим образом: Помните парсер, который пропускает определённую строку (skipString)?

skipString :: String -> Parser ()
skipString s = () <$ prefixP s

Комбинации парсеров

Это значит, что функция от n аргументов — это на самом деле функция от одного аргумента, возвращающая функцию от n-1 аргументов: В Haskell все функции по умолчанию каррированы и допускают частичное применение.

cons :: Int -> [Int] -> [Int]
cons = (:) cons1 :: [Int] -> [Int]
cons1 = cons 1 -- функция cons применена частично

Типы будут такие: Применим функцию от трёх аргументов к какому-нибудь значению внутри парсера, используя fmap.

f :: c -> a -> b
p :: Parser c
(fmap f p) :: Parser (a -> b)

Конечно, возможна ситуация, когда во входной строке действительно находится представление функции, но хотелось бы иметь возможность применять эту функцию, а точнее комбинировать парсеры Parser (a -> b) и Parser a, чтобы получить Parser b: Получился парсер функции?!

applyP :: Parser (a -> b) -> Parser a -> Parser b

Это даёт интуитивное понимание того, как должна выглядеть реализация функции applyP: получить функцию из контейнера (как результат применения первого парсера), получить значения, к которым должна применяться функция (результат применения второго парсера) и "запаковать" преобразованные с помощью этой функции значения обратно в контейнер (создать новый парсер). Тип этой функции очень похож на тип fmap, только сама функция, которую нужно применить, также находится в контейнере. В реализации будем использовать list comprehension:

applyP :: Parser (a -> b) -> Parser a -> Parser b
applyP (Parser p1) (Parser p2) = Parser f where f s = [ (sx, f x) | (sf, f) <- p1 s, -- p1 применяется к исходной строке (sx, x) <- p2 sf] -- p2 применяется к строке, оставшейся после предыдущего разбора

Второй метод класса называется pure и используется для того, чтобы "завернуть" или "поднять" (lift) значение, в том числе функциональное. Существует класс Applicative, у которого есть метод с таким же прототипом. В случае реализации для парсера функция pure добавляет свой аргумент в результат работы парсера, не изменяя при этом входную строку.

class Functor f => Applicative f where pure :: a -> f a (<*>) :: f (a -> b) -> f a -> f b instance Applicative Parser where pure x = Parser (\s -> [(s, x)]) pf <*> px = Parser (\s -> [ (sx, f x) | (sf, f) <- unParser pf $ s, (sx, x) <- unParser px $ sf])

Типы, принадлежащие к этому классу, называются аппликативными функторами. Функция applyP — это и есть <*> из класса Applicative.

Для аппликативных функторов реализованы две вспомогательные функции, которые будут нам полезны:

(*>) :: f a -> f b -> f b
(<*) :: f a -> f b -> f a

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

Рассмотрим следующий тип данных: Комбинируя <$> и <*>, можно создавать очень удобные конструкции.

data MyStructType = MyStruct { field1 :: Type1 , field2 :: Type2 , field3 :: Type3 }

С конструктором можно работать как и с любой другой функцией. Конструктор значений MyStruct — это тоже функция, в данном случае она имеет тип Type1 -> Type2 -> Type3 -> MyStructType. Предположим, что для типов полей структуры уже написаны парсеры:

parser1 :: Parser Type1
parser2 :: Parser Type2
parser3 :: Parser Type3

С помощью функции fmap можно частично применить MyStruct к первому из этих парсеров:

parserStruct' :: Parser (Type2 -> Type3 -> MyStructType)
parserStruct' = MyStruct <$> parser1

Для этого уже нужно использовать <*>: Попробуем дальше применять функцию, которая теперь находится "внутри" парсера.

parserStruct'' :: Parser (Type3 -> MyStructType)
parserStruct'' = parserStruct' <*> parser2 parserStruct :: Parser MyStructType
parserStruct = parserStruct'' <*> parser3

То же самое можно сделать в одну строчку: В итоге мы получили парсер для всей структуры (конечно, здесь используется предположение, что в исходной строке представления её полей идут подряд).

parserStruct :: Parser MyStructType
parserStruct = MyStruct <$> parser1 <*> parser2 <*> parser3

Такие конструкции будут часто встречаться в примере использования.

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

data Operand = IntOp Int | IdentOp String

Этот парсер представляет собой альтернативу из двух других, поэтому нам нужна функция, умеющая комбинировать парсеры таким образом, чтобы результаты их работы объединялись. Если мы уже умеем разбирать целые числа и идентификаторы (например, как в языке С), то нам нужен один парсер для операндов который может разобрать одно или другое. Реализуем функцию altP, комбинирующую два парсера: Результатом работы парсера является список, а объединение списков — это их конкатенация.

altP :: Parser a -> Parser a -> Parser a
altP (Parser p1) (Parser p2) = Parser (\s -> p1 s ++ p2 s)

Тогда парсер операнда можно реализовать, используя эту функцию (здесь предполагается, что parserInt и parserIdent уже где-то описаны:

parserOperand :: Parser Operand
parserOperand = altP parserIntOp parserIdentOp where parserIntOp = IntOp <$> parserInt parserIdentOp = IdentOp <$> parserIdent

В нём есть ещё один метод, empty, описывающий нейтральный элемент для операции альтернативы. Конечно, и для альтернатив уже придумали отдельный класс, который так и называется Alternative. всегда возвращает пустой список результатов. В нашем случае это парсер, который никогда ничего не разбирает, т.е. Для парсера реализация методов класса Alternative выглядит так:

class Applicative f => Alternative f where empty :: f a (<|>) :: f a -> f a -> f a instance Alternative Parser where empty = Parser (const []) px <|> py = Parser (\s -> unParser px s ++ unParser py s)

Операция <|> — это и есть функция altP, только в инфиксной записи, которую удобнее использовать, комбинируя несколько парсеров подряд.

Каждая из них может быть выражена через другую: Для всех типов в этом классе реализованы две функции, some и many типа f a -> f [a].

some v = (:) <$> v <*> many v
many v = some v <|> pure []

В случае использования some последовательность должна быть непустой. В терминах парсеров эти функции позволяют разбирать последовательности данных, если известно, как разобрать один элемент данных.

Теперь у нас всё готово для того, чтобы написать свой парсер, например, для простых арифметических выражений со следующей грамматикой:

expr ::= constExpr | binOpExpr | negExpr const ::= int int ::= digit{digit} digit ::= '0' | ... | '9' binOpExpr ::= '(' expr ' ' binOp ' ' expr ')' binOp ::= '+' | '*' negExpr ::= '-' expr

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

Примеры правильной записи выражений:

"123" "-(10 + 42)" "(1 + ((2 + 3) * (4 + 5)))"

Примеры неправильной записи:

" 666 " "2 + 3" "(10 * 10)"

Объявим необходимые типы данных (само выражение и бинарная операция):

data Expr = ConstExpr Int | BinaryExpr Expr Operator Expr | NegateExpr Expr data Operator = Add | Mul

Само выражение состоит из трёх альтернатив. Можно приступать к разбору! Так и запишем:

-- expr ::= constExpr | binOpExpr | negExpr
exprParser :: Parser Expr
exprParser = constParser <|> binParser <|> negParser

В нашем типе данных оно "завёрнуто" в конструктор, поэтому мы не можем использовать парсер для целого числа напрямую, но можем применить fmap, чтобы получить значение нужного типа. Константа — целое положительное число.

-- const ::= int
constParser :: Parser Expr
constParser = ConstExpr <$> intParser

Для разбора одной цифры используем вспомогательную функцию predP и предикат isDigit из модуля Data. Целое число, согласно грамматике, представляется как непустая последовательность цифр. Теперь для построения парсера для разбора последовательности цифр используем функцию some (не many, потому что должна быть хотя бы одна цифра). Char. Например, если входная строка "123ab", список результатов будет следующим: [("ab", "123"), ("3ab", "12"), ("23ab", "1")]. Результат работы такого парсера возвращает список всех возможных вариантов разбора, начиная с самой длинной записи. Целиком реализация выглядит следующим образом: Нам нужно разобрать самую длинную последовательность цифр и преобразовать её к типу Int.

-- int ::= digit{digit}
-- digit ::= '0' | ... | '9'
intParser :: Parser Int
intParser = Parser $ \s -> let res = unParser (some digitParser) s in case res of [] -> [] ((rest, i) : xs) -> [(rest, read i)] where digitParser = predP isDigit

Согласно грамматике, во входной строке сначала должна идти открывающая скобка, первый операнд, пробел, символ операции, ещё один пробел, второй операнд и закрывающая скобка. Следующий вариант записи выражения — применение бинарной операции. Операнды — это выражения, а для их разбора парсер уже есть (exprParser). Для разбора отдельных символов (скобок и пробелов) используем функцию charP. Остаётся аккуратно скомбинировать этот набор парсеров. Для разбора символа бинарной операции опишем вспомогательный парсер чуть ниже. Для этого используем *> и <*: В начале и в конце выражения должны быть скобки: нужно это проверить, но сам результат отбросить.

binParser :: Parser Expr
binParser = charP '(' *> ??? <* charP ')'

Не забудем про пробелы вокруг символа операции, используя тот же метод, что и для скобок. Между этими парсерами для скобок должно происходить конструирование выражения с помощью конструктора BinaryExpr и парсеров для выражения и операции. Эта часть выглядит следующим образом:

BinaryExpr <$> exprParser -- первый операнд <*> (charP ' ' *> binOpParser <* charP ' ') -- операция, окружённая пробелами <*> exprParser -- второй операнд

Подставим это выражение вместо знаков вопроса:

-- binOpExpr ::= '(' expr ' ' binOp ' ' expr ')'
binParser :: Parser Expr
binParser = charP '(' *> (BinaryExpr <$> exprParser <*> (charP ' ' *> binOpParser <* charP ' ') <*> exprParser ) <* charP ')'

Бинарная операция — это либо символ +, который разбирается в значение Add, либо *, который разбирается в Mul:

-- binOp ::= '+' | '*'
binOpParser :: Parser Operator
binOpParser = plusParser <|> multParser where plusParser = charP '+' $> Add multParser = charP '*' $> Mul

С символом - поступаем так же, как со скобками и пробелами. Осталась самая простая часть грамматики, отрицание выражения. Далее применяем конструктор NegateExpr к результату рекурсивного разбора:

-- negExpr ::= '-' expr
negParser = charP '-' *> (NegateExpr <$> exprParser)

Код во многом напоминает грамматику и полностью совпадает с ней по структуре. Итак, все части парсера реализованы.

Исходный код доступен на GitLab: https://gitlab.com/fierce-katie/applicative-parsers-demo.

Проект можно собрать утилитой Stack и запустить примитивный интерпретатор, использующий парсер, который мы написали: Там проще оценить его объём и степень выразительности, поскольку комментариев гораздо меньше.

$ stack build
$ stack exec demo-parser

Тем, кто хочет потренироваться дальше самостоятельно, могу посоветовать следующее:

  • Грамматику можно всячески улучшить, например, допускать ведущие и висячие пробелы, добавить новые операции и т.д.
  • Парсер переводит строку во внутреннее представление выражения. Это выражение можно вычислить и преобразовать интерпретатор так, чтобы он печатал не результат разбора а результат вычисления.
  • Изучить возможности библиотек parsec, attoparsec, applicative-parsec и optparse-applicative, попробовать их применить.

Спасибо за внимание!

  1. Learn Haskell in Y minutes
  2. Денис Шевченко. "О Haskell по-человечески"
  3. Библиотека parsec
  4. Библиотека attoparsec
  5. Библиотека applicative-parsec
  6. Библиотека optparse-applicative
Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть