[Программирование] Реализация расширения Active Patterns для языка OCaml
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
О проекте
Весной 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
При использовании такой конструкции мы имеем следующие преимущества:
- высокая выразительность;
- проверка на полноту, являющаяся критически важным свойством для проверки корректности и рефакторинга программ;
- эффективные схемы компиляции.
Проверка на полноту означает, что компилятор, зная определение типа, для каждого сопоставления может проверить, правда ли, что разобраны все возможные альтернативы и что нет недостижимых ветвей, насколько бы при этом сложными ни были образцы и как бы они друг с другом ни пересекались. Таким образом, если вы измените определение типа (добавив новые альтернативы, убрав или изменив существующие), компилятор любезно выдаст вам все места в коде, на которые это непосредственно повлияло.
Например, если я добавил новые конструкции в синтаксическое дерево, компилятор покажет мне код типизации АСТ с точностью до тела функции, куда необходимо написать код типизации новых конструкций:
Такое свойство делает 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.
===========
Источник:
habr.com
===========
Похожие новости:
- [Программирование, Разработка систем связи, Стандарты связи] SDR DVB-T2 receiver на C++
- [Программирование, Проектирование и рефакторинг, Алгоритмы, Терминология IT] Как генерируются UUID (перевод)
- [Карьера в IT-индустрии, Программирование] Первый опыт использования API.hh.ru
- [Программирование, Git, Системы управления версиями, DevOps, Микросервисы] Монорепозитории NX и Lerna, или Туда и обратно
- [JavaScript, Программирование, Разработка веб-сайтов] Основные команды bash, git, npm и yarn, а также немного о package.json и semver
- [Компиляторы, Программирование] Using Flex (Fast Lexical Analyzer Generator)
- [Программирование, Учебный процесс в IT, Карьера в IT-индустрии, Конференции] Бесплатные онлайн-мероприятия по разработке (7 октября — 15 октября)
- [Программирование микроконтроллеров] Передача аналогового тв сигнала с помощью STM32
- [JavaScript, Программирование, ReactJS] Как использовать Axios в React
- [Open source, Машинное обучение, Программирование, Разработка робототехники, Робототехника] Приглашаем на конкурс разработки open-source пакетов на Robot Operating System
Теги для поиска: #_programmirovanie (Программирование), #_ocaml, #_active_patterns, #_pattern_matching, #_blog_kompanii_obrazovatelnye_proekty_jetbrains (
Блог компании Образовательные проекты JetBrains
), #_programmirovanie (
Программирование
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 20:21
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
О проекте Весной 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 При использовании такой конструкции мы имеем следующие преимущества:
Проверка на полноту означает, что компилятор, зная определение типа, для каждого сопоставления может проверить, правда ли, что разобраны все возможные альтернативы и что нет недостижимых ветвей, насколько бы при этом сложными ни были образцы и как бы они друг с другом ни пересекались. Таким образом, если вы измените определение типа (добавив новые альтернативы, убрав или изменив существующие), компилятор любезно выдаст вам все места в коде, на которые это непосредственно повлияло. Например, если я добавил новые конструкции в синтаксическое дерево, компилятор покажет мне код типизации АСТ с точностью до тела функции, куда необходимо написать код типизации новых конструкций:  Такое свойство делает 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. =========== Источник: habr.com =========== Похожие новости:
Блог компании Образовательные проекты JetBrains ), #_programmirovanie ( Программирование ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 20:21
Часовой пояс: UTC + 5