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