Мотивация

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

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

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

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

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

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

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

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

Классы типов

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

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

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

data Point = Point
    { xCoord :: Float
    , yCoord :: Float
    } deriving (Eq, Show)

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

class PrettyPrint a where
  pPrint :: a -> String

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

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

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

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

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

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

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

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

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

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

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

Тип этой функции очень похож на тип fmap, только сама функция, которую нужно применить, также находится в контейнере. Это даёт интуитивное понимание того, как должна выглядеть реализация функции applyP: получить функцию из контейнера (как результат применения первого парсера), получить значения, к которым должна применяться функция (результат применения второго парсера) и "запаковать" преобразованные с помощью этой функции значения обратно в контейнер (создать новый парсер). В реализации будем использовать 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 применяется к строке, оставшейся после предыдущего разбора

Существует класс Applicative, у которого есть метод с таким же прототипом. Второй метод класса называется pure и используется для того, чтобы "завернуть" или "поднять" (lift) значение, в том числе функциональное. В случае реализации для парсера функция 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

Конечно, и для альтернатив уже придумали отдельный класс, который так и называется Alternative. В нём есть ещё один метод, empty, описывающий нейтральный элемент для операции альтернативы. В нашем случае это парсер, который никогда ничего не разбирает, т.е. всегда возвращает пустой список результатов. Для парсера реализация методов класса 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.Char. Теперь для построения парсера для разбора последовательности цифр используем функцию some (не many, потому что должна быть хотя бы одна цифра). Результат работы такого парсера возвращает список всех возможных вариантов разбора, начиная с самой длинной записи. Например, если входная строка "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

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

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

Автор: fierce-katie

Источник