Академия: Введение в функциональное программирование. 8 неделя, ч. 2: создаем домен-специфические языки с помощью функциональных парсеров
Привет. Я участвую в проекте Академия от @ontofractal и публикую конспекты курса Введение в функциональное программирование от Delft University of Technology. В этой части конспекта я пролжу рассказывать о функциональных парсерах. В прошлый раз мы научились комбинировать отдельные парсеры в общую структуру с помощью монад. Сегодня я продолжу эту тему и к концу занятия расскажу, как построить парсер, способный вычислять простые выражения
Еще немного парсеров
Для начала напишем еще несколько парсеров, которые могут пригодиться нам в будущем
Например, мы можем написать функцию, которая принимает предикат (условное выражение) и символ. Если символ подходит под предикат, мы возвращаем парсер return
(напомню, что он в свою очередь, вссегда возвращает без изменений поступающее к нему значение), а если не подходит - парсер failure
sat p = do x <- item
if p x then
return x
else failure
Функции, которые парсят цифры и специальные символы:
digit :: Parser Char
digit = sat isDigit
char:: Char -> Parser Char
char x = sat (x==)
Кроме того, было бы полезно иметь функцию, которая применяет парсер к входному значению 0 или больше раз:
many :: Parser a -> Parser [a]
many p = many1 p +++ return []
Если функция принимает подходящее значение, она возвращает функцию many1
, если неподходящее - пустой список
Функцию many1
можно определить следующим способом:
many1 p :: Parser a -> Parser [a]
many1 p = do v <- p
vs <- many p
return (v:vs)
Как видите, здесь использован рекурсивный паттерн: мы разбиваем входное значение на начало и остаток (v:vs
), применяем к начальному элементу парсер (v <- p
), а затем применяем к остатку функцию many, которая в свою очередь проверяет входное значение, и если оно подходит, применяет к нему функцию many1
Подобный подход можно применить для функции, которая парсит определенную строку:
string :: String -> Parser String
string [] = return []
string (x:xs) = do char x
string xs
return (x:xs)
Парсим выражения
Итак, кажется, пришло время подвести итоги проделанной работе. Теперь в нашем распоряжении есть отдельные парсеры, способные разобрать простые выражения, а также возможность их скомбинировать с помощью монад и рекурсии. И хотя примеры, которые я привел, выглядят довольно скромно, на самом деле полученных знаний достаточно, чтобы написать парсер, вычисляющий, например, арифметические выражения
Однако, прежде чем приступить к его написанию, нужно немного подумать о синтаксисе выражений. Предположим, что парсер может распознавать два вида арифметических выражений: сложение и умножение, а также знает о правилах ассоциативности и о том, что умножение имеет приоритет перед сложением. Тогда синтаксис выражений можно описать так:
expr -> term '+' expr | term
Здесь мы описываем строение всего выражения: оно состоит из первого слагаемого (term
), и второго слагаемого, которое может быть либо слагаемым (term
), либо другим выражением
Слагаемое в свою очередь описывается так:
term -> factor '*' term | factor
То есть, оно состоит из первого множителя (factor
) и второго множителя, который может быть либо выражением (term
), либо множителем (factor
)
Множитель мы определим так:
factor -> digit | expr
Ну а digit
мы определим как цифры от 0 до 9
Теперь все, что остается - перевести эту грамматику на язык отдельных парсеров и их комбинаций. Начнем с выражений:
expr :: Parser Int
expr = do t <- term
do char '+'
e <- expr
return (t + e)
+++ return t
Теперь определим функцию для слагаемого:
term :: Parser Int
term = do f <- factor
do char '*'
t <- term
return (f * t)
+++ return f
И для множителя:
factor :: Parser Int
factor = do d <- digit
return (digitToInt d)
+++ do char '('
e <- expr
char ')'
return e
И теперь остается лишь определить функцию eval, которая и будет принимать выражения:
eval :: String -> Int
eval xs = fst (head (parse expr xs ))
Домен-специфические языки
Конечно, получившаяся в итоге функция устроена весьма просто и не покрывает даже базовой арифметики, не говоря уже о более сложных операциях. Но она очень важна с точки зрения образовательных целей, так как наглядно демонстрирует подход, используемый при создании новых языков программирования
В своем первом конспекте я рассказывал, что Хаскель изначально использовался исследователями в области компьютерных наук как своего рода экспериментальная площадка, подходящая для быстрого прототипирования и создания новых языков. Подобное преимущество сохраняется и поныне, поэтому Хаскель является удобным средством для создания домен-специфических языков
Еще один рекордсмен в этой области - язык Lisp. Его синтаксис, построенный вокруг последовательной обработки элементов списков, позволяет легко создавать интерпретаторы для новых языков. Поэтому на сегодняшний день существует огромное число диалектов Лиспа, часть из которых используется в качестве языков широкого профиля, часть - в качестве домен-специфических языков (например, AutoLisp, используемый в AutoCAD)
На этом я заканчиваю конспект восьмой недели и закрываю тему функциональных парсеров. В следующей части я расскажу о способах организация ввода и вывода в Хаскеле, которые позволяют сделать программы интерактивными
Что показалось самым интересным на этой неделе?
Больше всего меня заинтересовало описание процесса создания парсера, способного не только анализировать структуру входных значений, но и вычислять простые выражения. Такой парсер по сути является упрощенной версией полноценных интерпретаторов, и позволяет в общих чертах представить себе процесс создания новых языков программирования