Реализация расширения Active Patterns для языка OCaml
Участники проекта
Руководитель
О проекте
Весной 2020 года в рамках весенней практики в Computer Science Center я занимался разработкой новой конструкции для языка программирования OCaml под чутким руководством Дмитрия Косарева.
Почему OCaml
OCaml – это одна из самых успешных и развитых реализаций синкретизма промышленного программирования (отсюда мультипарадигмальность, мультиплатформенность, очень быстрый компилятор, высокая производительность генерируемого кода) и математики (отсюда state-of-the-art система типов с мощной реализацией вывода типов, выразительность и расширяемость языка, близость к математической нотации и семантике).
При этом сообщество языка очень избирательно и не спеша добавляет в язык только крайне востребованные конструкции при условии, что те не привносят ограничений в существующий язык. Поэтому ядро языка очень маленькое и интуитивное, и OCaml с удовольствием используют как промышленные разработчики, так и, скажем, математики с кафедры высшей алгебры и теории чисел СПбГУ.
Для более глубокого погружения в тему предлагаю взглянуть на статьи OCaml for the masses и Why OCaml.
Сейчас ведется работа по реализации для OCaml multicore-системы вкупе с алгебраическими эффектами, что одновременно позволит поднять общую производительность языка и устранить существующие ограничения системы типов, связанные с тем, что язык допускает нечистые вычисления.
Сопоставление с образцом и active patterns
Моя же работа была сосредоточена главным образом вокруг конструкции сопоставления с образцом, широко используемой в языках функционального программирования.
Для иллюстрации рассмотрим простой пример вращения узла бинарного дерева. В наиболее распространенном императивном стиле код, вероятно, будет выглядеть следующим образом:
type 'a tree =
| Node of 'a tree * 'a * 'a tree
| Nil
let rotate_left' t =
if is_node t
then
let a = get_left t in
let p = get_value t in
let r = get_right t in
if is_node r
then
let b = get_left t in
let q = get_value t in
let c = get_right t in
Node(Node(a,p,b),q,c)
else t
else t
А вот тот же самый код, записанный с использованием конструкции сопоставления с образцом:
let rotate_left = function
| Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c)
| Node _ | Nil as x -> x
При использовании такой конструкции мы имеем следующие преимущества:
- высокая выразительность;
- проверка на полноту, являющаяся критически важным свойством для проверки корректности и рефакторинга программ;
- эффективные схемы компиляции.
Проверка на полноту означает, что компилятор, зная определение типа, для каждого сопоставления может проверить, правда ли, что разобраны все возможные альтернативы и что нет недостижимых ветвей, насколько бы при этом сложными ни были образцы и как бы они друг с другом ни пересекались. Таким образом, если вы измените определение типа (добавив новые альтернативы, убрав или изменив существующие), компилятор любезно выдаст вам все места в коде, на которые это непосредственно повлияло.
Например, если я добавил новые конструкции в синтаксическое дерево, компилятор покажет мне код типизации AST с точностью до тела функции, куда необходимо написать код типизации новых конструкций:
Такое свойство делает OCaml очень устойчивым к рефакторингу и иным изменениям кода.
Несмотря на все описанные преимущества, есть и одно очень серьезное ограничение на применимость. Заметили ли вы его? Определение типа должно быть публичным (чтобы компилятор был вправе показать составляющие его альтернативы). А это, разумеется, сразу же ломает даже простейшие абстракции. Например, если мы хотим определить простейший интерфейс списка, невозможно заранее сказать, какое определение типа требуется экспортировать:
module type List = sig
type 'a t (* = ? *)
val cons: 'a -> 'a t -> 'a t
val empty: 'a t
val head: 'a t -> ('a * 'a t) option
end
Однако эта проблема не фундаментальна, и, как было замечено еще в 1987 году, можно добиться и возможности сопоставления с образцом по абстрактным типам.
Постановка задачи
С 1987 года в литературе было представлено множество различных дизайнов для решения поставленной проблемы, вот лишь некоторые из них:
К началу проекта уже была проделана работа по обоснованному и объективному выбору конкретного решения для реализации, наиболее выигрышным оказался расширение Active patterns, реализованное в языке F#.
Целью проекта было начать реализацию Active Patterns для компилятора OCaml и продвинуться насколько удастся.
Active patterns
Сама идея Active patterns (как и аналогичных расширений) очень простая: раз абстракция достигается сокрытием реализации внутри функции, необходимо разрешить внутри сопоставления с образцом вызов функции, которая бы преобразовывала неизвестное значение абстрактного типа данных к известному списку альтернатив. Active patterns кодируют этот список альтернатив прямо внутри имени функции. Так, в интерфейс списка выше необходимо добавить следующую функцию (|Cons|Nil|)
:
module type List = sig
type 'a t
val (|Cons|Nil|): 'a t -> ('a * 'a t, unit) choice2
val cons: 'a -> 'a t -> 'a t
val empty: 'a t
val head: 'a t -> ('a * 'a t) option
end
Результатом является анонимный тип-сумма choice2
, имеющий следующее определение (существуют аналогичные сгенерированные типы вплоть до choice32
):
type ('a, 'b) choice2 =
| Choice2_1 of 'a
| Choice2_2 of 'b
Таким образом, функция (|Cons|Nil|)
выполнит преобразование списка к одной из двух альтернатив: либо к паре из головы и хвоста списка, либо к пустой альтернативе, означающей, что список был пуст.
Определение такой функции для стандартного списка тривиально и будет выглядеть следующим образом:
let (|Cons|Nil|) = function
| [] -> Nil
| x :: xs -> Cons(x, xs)
В качестве примера использования рассмотрим функцию, удаляющую последовательные дубликаты в списке:
(* destutter [1;1;4;3;3;2] = [1;4;3;2] *)
let rec destutter = function
| Nil -> nil
| Cons(x, Nil) -> cons x empty
| Cons(x, Cons(y, rest)) ->
if x = y
then destutter (cons y rest)
else cons x (destutter (cons y rest))
Заметьте, что все достоинства сопоставления с образцом сохранились: синтаксис сопоставления остался тем же и проверки на полноту могут работать в полном объеме. Эффективная компиляция такого решения выходит за рамки этого обзора, но она также возможна.
Ход работы
В рамках данной работы удалось реализовать синтаксический анализ и типизацию расширения для компилятора OCaml версии 4.09, результаты представлены здесь.
Парсер компилятора реализован с использованием продвинутого парсер-генератора Menhir. Menhir имеет достаточно полный и подробный мануал, однако даже с ним не всегда было понятно, как можно задать правило вывода, а как нельзя и почему. Полученный в итоге патч парсера довольно маленький и простой, но путь к нему лежал через 10-15 конфликтов shift-reduce и reduce-reduce, разбор и исправление которых потребовали некоторого времени:
Хочется отдать должное разработчикам Menhir и поблагодарить их за проделанную работу по детализации и пояснению ошибок. Один раз парсер-генератору не удалось проиллюстрировать конфликт и пришлось разбирать его по построенному автомату на 1500 состояний. Это потребовало, конечно, на порядок больше времени.
Типизация расширения далась особенно тяжело. Код типизации занимает около 37 000 строк и почти не задокументирован, новичку тут разобраться непросто. Меня спасла статья Олега Киселева, поясняющая ключевые аспекты реализации.
Еще один вывод, который я для себя сделал — это не забывать пользоваться старыми версиями проекта. Например, вот количественное сравнение одного и того же кусочка типизации версий 2019 и 2005 года:
Версия 2019 года содержит анализ и выдачу предупреждений (warnings) компилятора, а также дополнительные технические подробности, которые меня не интересовали. Для понимания мне достаточно было взглянуть на версию 2005 года, содержащую только ключевые действия.
Наконец, главный вывод, сделанный мной в ходе работы, есть подтверждение того, что документация для open-source проектов критически важна. Каким бы выразительным ни был язык, исходный код может лишь рассказать, как себя ведет функция, а не что она делает или почему она это делает именно так. Очень непросто читать цепочки вызовов type_self_pattern
-> type_cases
-> type_pat
-> type_pat'
-> type_pat_aux
и соображать, которая из функций тебе нужна; или по одному только названию параметра constr
догадываться, какие конструкторы и для чего должны сюда записываться.
Необходимость каждый раз смотреть на случаи использования значительно замедляет программиста и очень быстро утомляет: напомню правило «семь плюс-минус два» — ровно столько объектов человек может в среднем одновременно держать в голове. А когда ты внутри шестой вложенной функции наконец понимаешь смысл параметра и вдруг осознаешь, что не помнишь, зачем он был тебе нужен, или выясняется, что он тебе и не нужен был, — становится очень грустно из-за количества потраченного времени.
Заключение
В рамках проекта мне удалось реализовать синтаксический анализ и типизацию для Active patterns. Пропатченный мной компилятор может разобрать и типизировать файл с любыми примерами использования Active patterns.
Далее необходимо произвести модификацию схемы компиляции (OCaml использует нетривиальную оптимизирующую компиляцию сопоставления с образцом) и проверки схемы на полноту, которые во время работы над проектом были почти полностью переписаны командой разработчиков OCaml-компилятора.
Надеюсь, эта реализация все-таки будет завершена, со мной или без меня. Несмотря на все трудности, было здорово попробовать себя в разработке промышленного компилятора для своего любимого языка.