Реализация расширения 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-компилятора.

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

Автор:

Башкиров Александр — студент Computer Science Center и 4 курса бакалавриата «Программная Инженерия» СПбГУ, сотрудник компании JetBrains.