2009 → Выпуск 3

Как построить Google Wave из Erlang и Tcl при помощи OCaml

Дмитрий Астапов, Алексей Щепин

Аннотация: Статья рассказывает о том, как утилита camlp4, предназначенная для создания DSL, использовалась для автоматической генерации программного кода клиент-серверного приложения на Erlang (сервер) и Tcl (клиент).


Article describes the construction of the DSL for network protocol processing definition in a server-client setting and associated toolchain. Ocamlp4-based DSL translator was used to simultaneously transform DSL into Erlang code (for the server) and Tcl code (for the client).



Обсуждение статьи ведется по адресу
http://community.livejournal.com/fprog/4804.html.

1  Введение: что такое Google Wave и операционные преобразования

Сравнительно недавно компания Google анонсировала ограниченный доступ к первым версиям нового онлайн сервиса под названием Google Wave. Обещают, что сервис предоставит невиданные ранее возможности для совместной работы и редактирования документов с самым разнообразным содержимым — текстом, видео, изображениями и так далее, благодаря чему Google Wave уже успели окрестить рядом громких эпитетов вроде «убийца email» или «киллер сервисов мгновенных сообщений».

Впрочем, оставим в стороне маркетинговую шумиху. Что же такое Google Wave в контексте совместной работы над документами? Попросту говоря, — это серверное приложение с «тонким» клиентом (работающим в веб-браузере), которое обрабатывает команды редактирования от всех участников процесса и сводит их к единому непротиворечивому представлению документа1. Помимо инфраструктуры (клиента и сервера), разработанной Google, допускается использование сторонних реализаций (так называемый механизм «объединения волн», англ. «wave federation»). В частности, предполагается, что технология Google Wave может быть интегрирована в существующие службы мгновенного обмена сообщениями на базе протокола XMPP, позволив людям не только коллективно обмениваться сообщениями, но и при этом коллективно работать над документами.

Если углубиться в детали еще больше, окажется, что в основе Google Wave лежит протокол передачи изменений в XML документах. Протокол используется клиентами для того, чтобы отправлять на сервер информацию о сделанных правках, и принимать от него информацию о чужих изменениях. Любая операция по редактированию документа представляется в рамках этого протокола в виде последовательности команд: «сдвинуть курсор на n символов вправо», «вставить в позиции курсора такие-то символы», «удалить справа от курсора n символов» и т. п.

Получив информацию о «чужих» изменениях, клиент не может бездумно применить команды к своей версии документа, так как в результате может случиться рассогласование. Например, пусть клиент A вставил один символ в 8-й позиции, а клиент B в то же время удалил 15-й символ. Если клиент A буквально применит информацию о изменении, совершенном B, то в копии документа на клиенте A удаленным окажется символ на одну позицию левее нужной (см. рис. 1)

Исходный документ:
«Казнить нельзя, помиловать»
Клиент A:
Insert 8 ’,’ → «Казнить, нельзя, помиловать» Клиент B:
Delete 15 → «Казнить нельзя помиловать»
Клиент A получает и буквально применяет изменения B:
Delete 15 → «Казнить, нельз, помиловать» Клиент B получает и буквально применяет изменения A:
Insert 8 ’,’ → «Казнить, нельзя помиловать»
Рис. 1: Конфликты, возникающие при наивном подходе к объединению правок

Существуют способы формального представления подобных операций редактирования и их обработки, которые позволяют избежать подобных проблем. Этот формализм известен под названием «операционное преобразование»2 (см. [7], [8]). При использовании ОП клиент A сначала преобразует полученное от B изменение относительно своего документа, получив в результате команду «удалить 21-й символ» (это называется «включающее преобразование»), и только после этого применит полученную команду к своей версии документа, получив результат, идентичный имеющемуся у B.

В систему ОП, используемую в Google Wave (см. [4]), помимо набора из десяти команд для представления операций редактирования входят также две функции: включающее преобразование и композиция. Первая была рассмотрена выше, а вторая — это объединение нескольких последовательных операций редактирования в одну. Внутреннее представление документа в Google Wave включает в себя номер версии, который увеличивается после каждого изменения. Клиенты посылают свои изменения с указанием номера версии «своего» документа, а центральный сервер производит включающее преобразование изменений относительно своей версии документа, и рассылает результат остальным клиентам. Все прочие клиенты, в свою очередь, преобразовывают полученные изменения относительно своих необработанных (не отправленных) изменений и применяют к своей версии документа.

Если клиент прислал изменения к версии, которая «моложе» последней актуальной версии документа на сервере, то сервер использует композицию для объединения изменений, примененных на сервере после той версии, что указал клиент.

Подробное описание операций композиции и включающего преобразования с примерами их использования можно найти в [6].

2  Постановка задачи

Выбор команд и функций, входящих в систему ОП Google Wave, не является единственных возможным. Существуют другие системы ОП, обладающие теми или иными достоинствами или недостатками (см. [8]). Одной из целей ограниченного бета-тестирования Google Wave как раз и является проверка выбранной системы ОП в условиях, «приближенных к боевым». Кроме того, Google активно сотрудничает с другими компаниями для «обкатки» протокола интеграции со сторонними решениями (пресловутый federation).

В рамках этой деятельности одному из авторов потребовалось реализовать поддержку ОП из Google Wave в двух программных продуктах: Jabber-сервере ejabberd и Jabber-клиенте Tkabber. Главные требования, которые предъявлялись к реализации — это удобство поддержки, модификации и развития кода.

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

Всего существует десять различных команд редактирования — три команды для вставки текста, три команды для удаления, три команды для работы с атрибутами текста и команда для пропуска определенного количества символов без изменения (см. [5], раздел 7.2). Кроме того, любой из исходных списков может быть пустым, поэтому всего существует 11 × 11 = 121 различных теоретически возможных комбинаций команд примитивной композиции. В реальности, правда, имеют смысл всего 75 из них, и для каждой из них необходимо описать результат операции примитивной композиции.

Казалось бы, ничто не мешает взять и написать реализации на Erlang и Tcl «с нуля» вручную, но есть несколько потенциальных проблем, о которых лучше подумать заранее:

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

3  Возможный подход к решению

Попробуем создать специальный мини-язык программирования для задачи описания операций с ОП. Текст на этом языке будет транслироваться в тексты на целевых языках — Erlang и Tcl. В английской литературе подобные мини-языки традиционно называются domain-specific languages, и в дальнейшем создаваемый мини-язык будет сокращенно называться просто «DSL».

Трансляция программного текста, записанного на одном языке, в эквивалентный код, записанный на другом языке — это задача, традиционно решаемая компиляторами. Если пойти по пути создания компилятора DSL, то понадобится:

На первый взгляд, решение этой вспомогательной задачи намного сложнее, чем решение оригинальной задачи.

Нельзя ли упростить процесс, и использовать какие-то готовые средства? Что если DSL будет синтаксически похож на какой-то существующий язык программирования (назовем его язык-носитель, англ. host language)? Тогда:

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

Мы же поступаем наоборот: наш DSL синтаксически похож на язык-носитель, и в ходе трансляции происходит его «отчуждение» от языка-носителя, с превращением кода на DSL в код на Erlang и Tcl.

Тем не менее, нельзя ли взять язык-носитель с развитыми средствами метапрограммирования и попытаться использовать их для решения нашей задачи?

Остаток статьи описывает создание транслятора DSL с использованием языка OCaml и утилиты camlp4 (см. [2]). Почему были выбраны именно эти средства? Во-первых, автор реализации хорошо с ними знаком. Во-вторых, camlp4 представляет собой практически идеальный инструмент для решения поставленной задачи. Его функциональность в области синтаксического анализа и модификации деревьев абстрактного синтаксиса можно легко расширять при помощи модулей, написанных на OCaml.

4  Проектирование DSL

Для начала необходимо спроектировать будущий DSL. Как было сказано выше, его синтаксис должен быть максимально похожим на синтаксис OCaml (чтобы облегчить разработку). Осталось определиться с тем, какими специфичными для задачи объектами и операциями необходимо дополнить OCaml.

Для чего будет использоваться DSL? Для описания того, как выполняется композиция или включающее преобразование отдельных команд в системе операционных преобразований Google Wave.

В каком контексте будет использоваться это описание? Из него будет получен программный код на целевом языке, который, вероятнее всего, будет оформлен в виде отдельной функции.

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

В синтаксисе OCaml это можно упрощенно смоделировать следующим образом:

let main = ... let result = compose local_commands remote_commands in ... (* Это базовые правила композиции двух списков, которые никогда не будут меняться *>*) let compose local remote = match local, remote with | [], [] -> [] | _, _ -> let {result = res; xs = local'; ys = remote'} = compose_one_cmd local remote in res :: compose local' remote' (* Отсюда начинается часть программы, которую необходимо описывать с помощью DSL *>*) let compose_one_cmd xs ys = match xs, ys with | Cmd1 (arg1_1, arg1_2) :: xt, Cmd1 (arg2_1, agr2_2) :: yt -> let res = Cmd1 (arg1_1 + arg2_1, max arg2_1 arg2_2) in let xs' = xt in let ys' = Cmd1 (arg2_1 - arg1_1, arg2_2) :: yt in { result = res; xs = xs'; ys = ys'} | Cmd1 ..., Cmd2 ... -> ... | Cmd1 ..., Cmd3 ... -> ... | ... | Cmd1 ..., Cmd11 ... -> ... | ... | Cmd11 ..., Cmd1 ... -> ... | ... | Cmd11 ..., Cmd11 ... -> ...

Получается, что объектами языка будут, во-первых, входные списки команд, а во-вторых — структуры, описывающие команды. Поскольку в качестве базы для DSL берется OCaml, то списки команд будут представлены списками, а команды — конструкторами алгебраического типа данных.

В качестве операций в языке должны присуствовать, во-первых, операции над аргументами команд (как в приведенном выше примере), и, во-вторых, операции по изменению исходных списков: изменение головного элемента или переход к следующим элементам списка. Так как аргументами команд могут быть только строки, целые числа, их пары, или списки вышеперечисленных значений, для операций над аргументами можно использовать стандартные операции OCaml, не вводя новых. В приведенном выше примере головные элементы списков выделяются с помощью операций сопоставления с образцом, а в DSL для этих целей можно ввести специальные ключевые слова или переменные с зарезервированными именами.

Кроме этого, чтобы упростить трансляцию DSL в код на целевом языке, необходимо ограничить синтаксис, в котором описывается сама операция композиции: пусть там будут допустимы только условные выражения (if) и создание новых команд.

Читателям, заинтересовавшимся практическими аспектами проектирования DSL, рекомендуем обратиться к книге Мартина Фаулера (см. [9]).

5  Реализация DSL на OCaml/camlp4

Подход к реализации DSL с помощью camlp4 можно кратко описать так (см. 2):

Рис. 2: Процесс

Продемонстрируем синтаксис DSL на примере композиции двух операций сдвига курсора вправо. Интуитивно понятно, что, объединяя результаты сдвига вправо на x_len символов и сдвига вправо на y_len символов, можно сразу сдвинуть курсор вправо на min x_len y_len символов, а затем рассмотреть, как объединить оставшийся необработанным сдвиг на abs (x_len - y_len) символов и последующие команды. Соответственно, необходимо выяснить, какая из команд сдвига «короче», перенести ее в результат композиции, перейти к следующей команде в этом списке, а команду сдвига в другом списке «уменьшить» на нужное количество символов.

Код на DSL, который выполняет эти действия, выглядит так:

let compose_rules = make_compose ( match y, x with | Retain y_len, Retain x_len -> if x_len < y_len then {ys = Retain (y_len - x_len) :: yt; xs = xt; out = x} else if x_len > y_len then {ys = yt; xs = Retain (x_len - y_len) :: xt; out = y} else {ys = yt; xs = xt; out = x} | ...

Слово make_compose, которое хоть и выглядит как вызов функции, на самом деле является «точкой входа» для программы на DSL, и именно с нее camlp4 начинает трансляцию AST программы (как это реализовано — см. ниже).

Как уже было сказано ранее, в результате трансляции кода на DSL порождается не самодостаточная программа, а программный модуль с заранее известным интерфейсом. Входные и выходные параметры этого модуля делаются доступными для кода на DSL с помощью переменных со специальными именами: xs и ys — это обрабатываемые списки команд редактирования, при этом x, y, xt, yt — это головы и хвосты этих списков. Результатом работы каждой ветки в match является запись (англ. record), в которой указываются новые значения xs и ys, и команда out, которую нужно добавить к результату композиции.

Как выполняется трансляция программы на DSL? Утилита camlp4 производит синтаксический анализ файла с программой на DSL, и обрабатывает полученное дерево абстрактного синтаксиса с помощью модуля «трансляции AST», который, упрощенно, выглядит так:

let translate_ast = Ast.map_expr (function | <:expr< make_compose $e$ >> -> convert_compose e | <:expr< make_transform $e$ >> -> convert_compose e | x -> x ) in AstFilters.register_str_item_filter translate_ast#str_item

Этот код предписывает camlp4 вызывать для каждого узла AST, соответствующего ключевым словам make_compose или make_transform, функцию convert_compose, передавая ей в качестве аргумента AST выражения, «стоящего за» соответствующим ключевым словом3. В обоих случаях используется одна и та же функция convert_compose, так как в процессе разработки оказалось, что для описания операции композиции и включающего преобразования можно обойтись одним и тем же DSL и общей структурой AST.

Функция convert_compose выполняет рекурсивный спуск по AST, последовательно преобразовывая выражения, из которых состоит «тело» инструкции match (y,x) with:

let convert_compose = function | <:expr< match (y, x) with [ $cases$ ] >> -> convert_compose_cases cases | _ -> assert false let rec convert_compose_cases = function | <:match_case@_loc< ($bpat$, $apat$) -> $e$ | $rest$ >> -> <:expr< [($convert_pat bpat$, $convert_pat apat$, $convert_expr e$) :: $convert_compose_cases rest$] >> | <:match_case@_loc< ($bpat$, $apat$) -> $e$ >> -> <:expr< [($convert_pat bpat$, $convert_pat apat$, $convert_expr e$) :: []] >> | _ -> assert false let rec convert_expr = function | <:expr@_loc< if $e1$ then $e2$ else $e3$ >> -> <:expr< PIf ($convert_expr e1$, $convert_expr e2$, $convert_expr e3$) >> | ...

То есть, выражение match (y, x) with cs заменяется на результат работы функции convert_compose_cases, которая, в свою очередь, последовательно преобразовывает все составные части выражения с помощью функций convert_pat и convert_expr.

В результате порождается упрощенное AST кода на DSL в виде списка вложенных друг в друга кортежей (англ. tuples). В частности, для примера, приведенного выше, будет порождено такое упрощенное AST (фрагмент):

let compose_rules = [ ((POp (PRetain (PIdent "y_len"))), (POp (PRetain (PIdent "x_len"))), (PIf (((PAp (PAp (PIdent "<", PIdent "x_len"), PIdent "y_len")), (PRes { rys = PAp (PAp (PIdent "::", POp (PRetain (PAp (PAp (PIdent "-", PIdent "y_len"), PIdent "x_len")))), PIdent "yt"); rxs = PIdent "xt"; rout = Some (PIdent "x"); ry_out = None; rx_out = None; ry_depth = PIdent "y_depth"; rx_depth = PIdent "x_depth"; }), (PIf (((PAp (PAp (PIdent ">", PIdent "x_len"), PIdent "y_len")), ...

Далее это упрощенное AST (являющееся результатом работы фукнции translate_ast) передается последовательно в функции-кодогенераторы.

Сам кодогенератор, фактически, сводится к сопоставлению с образцом очередного элемента упрощенного AST и порождению на его основе соответствующей конструкции целевого языка:

match ast_node with | PIf (e1, e2, e3) -> Printf.sprintf "if\n%s ->\n%s;\n%s\nend" (expr_to_string e1) (expr_to_string e2) (else_branch e3) ...

Порождаемый в результате код на Erlang выглядит так:

compose([{retain, YLen} = Y | Yt], [{retain, XLen} = X | Xt], Res) -> if XLen < YLen -> compose([{retain, YLen - XLen} | Yt], Xt, [X | Res]); XLen > YLen -> compose(Yt, [{retain, XLen - YLen} | Xt], [Y | Res]); true -> compose(Yt, Xt, [X | Res]) end; ...

Код довольно сильно похож на оригинальную программу на DSL. Команды представляются в виде кортежей {имя_команды, параметр1, параметр2, …}, что позволяет использовать сопоставление с образцом для выбора нужного варианта композиции. Все конструкции DSL вида if ... then ... else ... преобразованы в Erlang-специфичный оператор if, допускающий наличие нескольких наборов «условие → действие». Добавление результата композиции к списку результатов реализовано с помощью хвостового рекурсивного вызова (англ. tail-recursive) функции compose.

Для сравнения, вот как выглядит соответствующий порожденный код на Tcl:

set res {} set xi 0 set yi 0 set x "" set y "" while {1} { if {[llength $x] == 0} {set x [lindex $xs $xi]; incr xi} if {[llength $y] == 0} {set y [lindex $ys $yi]; incr yi} if {[llength $x] == 0} {set x "empty"} if {[llength $y] == 0} {set y "empty"} if {[lindex $y 0] eq "retain" && [lindex $x 0] eq "retain"} { set y_len [lindex $y 1] set x_len [lindex $x 1] if {$x_len < $y_len} { lappend res $x set y [list retain [expr {$y_len - $x_len}]] set x "" } elseif {$x_len > $y_len} { lappend res $y set y "" set x [list retain [expr {$x_len - $y_len}]] } else { lappend res $x set y "" set x "" } } elseif {...

Команды в коде на Tcl представлены в виде списков [«имя команды» «параметр 1» «параметр 2»]. Так как в Tcl отсутсвует возможность использовать сравнение с образцом, выбор нужного варианта композиции выполняется с помощью многоуровневой конструкции if ... elseif ... elseif .... В списки Tcl эффективнее добавлять элементы справа (а не в начало списка), поэтому для формирования результата используется глобальная переменная-список res, к которой добавляются команды при помощи lappend. Кроме того, структурная рекурсия по спискам исходных комманд работала бы в Tcl неэффективно, так как операция взятия «хвоста» списка является довольно дорогостоящей. В связи с этим для итерации по входным спискам используются переменные-индексы xi и yi.

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

6  Заключение

Итак, можно смело утверждать, что все поставленные в начале разработки цели были достигнуты:

Единое централизованное описание:
код пишется только на DSL, нет необходимости синхронизировать реализации на Erlang и Tcl в ходе отладки или при изменении спецификаций ОП.
Унификация описания композиции и включающего преобразования:
в обоих местах используется один и тот же DSL.
Абстрагирование от особенностей целевых языков:
функция-кодогенератор инкапсулирует в себе все детали реализации на целевом языке, и программист, к примеру, не испытывает психологический дискомфорт от невозможности сравнивать данные с образцом в Tcl.
Возможность расширения подхода на другие целевые языки:
для подключения еще одного целевого языка достаточно написать еще одну функцию-кодогенератор по образу и подобию уже существующих.

Стоила ли «овчинка выделки»? Может, объем вспомогательного кода в разы превысил объем полезного кода на Erlang и Tcl, и проще было бы не связываться с OCaml и DSL, и все-таки реализовать все вручную? Посмотрим на объемы кода программных модулей:

Программный модульКоличество строкБайт
Транслятор AST1756200
Кодогенераторы60011000
Программа на DSL60015500
Итого137532700
Сгенерированный код на Erlang50020000
Сгенерированный код на Tcl75028000
Итого125048000
Таблица 1: Объем кода программных модулей

С учетом того, какие преимущества при отладке и модификации кода дает DSL, становится понятно, что выбранный подход полностью себя оправдал несмотря на незначительную разницу в объеме вспомогательного и полезного кода. Кроме того, на момент завершения написания статьи стало известно, что ту же самую функциональность необходимо будет реализовывать на JavaScript, и тут использование DSL даст решающее преимущество.

Список литературы

[1]
Abstract syntax tree. Страница в Wikipedia (en), http://en.wikipedia.org/wiki/Abstract_syntax_tree.
[2]
Camlp4 wiki. Официальная документация по camlp4 (en), http://brion.inria.fr/gallium/index.php/Camlp4.
[3]
Concrete syntax tree. Страница в Wikipedia (en), http://en.wikipedia.org/wiki/Concrete_syntax_tree.
[4]
Google wave operational transformation. Официальная спецификация, http://www.waveprotocol.org/whitepapers/operational-transform.
[5]
Google wave operational transformation, current draft. Текущая рабочая версия, http://www.waveprotocol.org/draft-protocol-specs/draft-protocol-spec.
[6]
Google wave: Under the hood. Техническая презентация, http://code.google.com/events/io/2009/sessions/GoogleWaveUnderTheHood.html.
[7]
Operational transformation. Страница в Wikipedia (en), http://en.wikipedia.org/wiki/Operational_transformation.
[8]
Операциональные преобразования. Страница в Wikipedia (ru), http://ru.wikipedia.org/?oldid=19384049.
[9]
Martin Fowler. Domain Specific Languages, http://martinfowler.com/dslwip/.
1
Более подробное описание и видео-демонстрация на английском доступны на странице http://wave.google.com/help/wave/about.html.
2
Далее «операционное преобразование» будет часто сокращаться до «ОП». Статья в русской Wikipedia использует перевод «операциональное преобразование», с чем авторы решительно не согласны.
3
Читателям, привыкшим к другим средствам метапрограммирования может помочь информация о том, что <:expr <...> > — это quotation, а $...$ — это antiquotation.
Этот документ был получен из LATEX при помощи HEVEA