Академия: Введение в функциональное программирование. 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)

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

Что показалось самым интересным на этой неделе?

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

“Конспект подготовлен для Академии Голоса @academy.

академияfp101программированиеобразование
68
-39.410 GOLOS
0
В избранное
ninjas
На Golos с 2017 M05
68
0
Комментарии (1)
Сортировать по:
Популярности
Зарегистрируйтесь, чтобы проголосовать за пост или написать комментарий
Авторы получают вознаграждение, когда пользователи голосуют за их посты. Голосующие читатели также получают вознаграждение за свои голоса.