Введение
Как-то раз я сидел и грустно смотрел на написанный в рамках изучения эрланговский код. Очень хотелось написать на нем что-нибудь более полезное, чем крестики-нолики, но как назло никаких подходящих задач в голову не приходило. Зато есть JavaScript, в котором есть и функции первого порядка, и каррирование, и map/filter/fold, и, главное, задачу придумать куда проще. А вот pattern matching-а своего нету. Беглый поиск выдал мне несколько библиотек, но предлагаемый ими синтаксис показался мне тяжеловесным. Можно ли сделать лаконичнее, ближе к родному эрланговскому синтаксису?
Спойлер: можно, если взять coffeescript, сделать так:
fn = Match -> [ When {command: “draw”, figure: @figure = {type: “circle”, radius: @radius}}, -> console.log(@figure, @radius) When {command: “draw”, figure: @figure = {type: “polygon”, points: [@first, @second | @rest]}}, -> console.log(@figure, @first, @second, @rest); ] fn {command: “draw”, figure: {type: “circle”, radius: 5, color: “red”}} #output: {type: “circle”, radius: 5, color: “red”} 5 Кому интересно, как это получилось — добро пожаловать под кат.
Краткое описание
Собственно, что тут происходит, если вкратце:
- Match принимает функцию, которая возвращает массив шаблонов (patterns) и соответствующих им действий;
- При вызове подменяется контекст, так что все эти @a (== this.a) указывают на специально подготовленные свойства (properties), позволяющие парсеру понять, какие значения куда привязывать;
- Далее при вызове с конкретным значением идет сравнение с шаблоном (пока можно считать, что идет рекурсивный обход шаблона и значения и сравнения конкретных значений, чуть ниже будет подробнее об этом);
- Если значение совпало с шаблоном, то вызывается функция-действие. У нее мы тоже подменим контекст, подставив соответствующие значения.
Так что если взять пример выше, то @radius в первом аргументе When указывает, какую часть входного объекта нужно изъять (в данном случае — .figure.radius), а во втором аргументе (функции) оно же содержит конкретное значение.
Работа с массивами
В Erlang есть удобный синтаксис для разбиения списка на голову (первый элемент) и хвост (все остальное), который широко используется для разных рекурсивных алгоритмов.
case List of [Head | Tail] -> Head; [] -> {empty}; end. В javascript (и coffeescript) отсутствует возможность переопределить операторы, поэтому штатными средствами можно сделать только что-то вроде:
When [@head, @tail…], -> console.log(@head, @tail) В принципе неплохо, но в erlang как-то симпатичнее. Может все-таки как-то можно, хотя бы для ряда сценариев?
Тут стоит вспомнить как вообще javascript удается выполнить операцию типа:
var object1 = {x:1}, object2 = {y: 2}; console.log(object1 | object2); И получить 0. Это работает так как javascript пытается для начала привести тип к числовому, для чего вызывает у объекта метод valueOf. Если подменить метод у наших объектов и возвращать степень двойки, то в результате можно узнать к каким объектам была применена операция.
var object1 = {x:1}, object2 = {y: 2}, object3 = {z: 3}; object1.valueOf = function() { return 2; } object2.valueOf = function() { return 4; } object3.valueOf = function() { return 8; } console.log(object1 | object2); //6 == 2 | 4 == object1 and object2 Было сделано смелое предположение, что очень редко кто будет использовать массивы конкретных чисел в шаблонах, поэтому если парсер встречает в конце массива число, он пытается определить, не является ли это результатом операции or двух объектов. В итоге стало возможным писать так:
When [@head | @tail], -> console.log(@head, @tail) Выглядит симпатично, но за пределами этой задачи я бы не стал повсеместно использовать такой метод.
Сопоставление с классом
Следующее что хотелось — сделать сопоставление структур как в Erlang, с указанием типа и содержимого.
#person{name = Name} Прямо так, конечно, не удастся, но что-то похожее сделать можно. В итоге я остановился на трех решениях:
When ObjectOf(Point1, {x: 1, y: 2}), -> … When Point2(x:1, y:2), -> … When Point3$(x:1, y:2), -> ... Первое работает «из коробки», второе выглядит почти как case class на scala, но требует вставки вот такой строки в конструктор.
class Point2 constructor: (@x, @y) -> return m if m = ObjectOf(@, Point2, arguments) This нужен чтобы понять, была ли вызвана функция как конструктор или нет, сам конструктор и аргументы попадают в шаблон.
Третий вариант является вариацией на тему первого, просто функцию заготавливаем заранее:
Point3$ = ObjectOf(Point3)
Производительность
Первая наивная версия выполняла сравнение шаблона и значения, проходя их рекурсивно. В принципе, я ожидал, что производительность будет не на высоте, если сравнивать с простым разбором объекта. Но стоило проверить.
coffeeDestruct = (demo) -> {user} = demo return if not user.enabled {firstname, group, mailbox, settings} = user return if group.id != "admin" notifications = settings?.mail?.notify ? [] return if mailbox?.kind != 'personal' mailboxId = mailbox?.id ? null {unreadmails, readmails} = mailbox; return if unreadmails.length < 1 firstUnread = unreadmails?[0] ? [] restUnread = unreadmails?.slice(1) ? [] return if readmails?.length < 1 return if readmails?[0]?.subject != "Hello" rest = readmails?.slice(1) return {firstname, notifications, firstUnread, restUnread, rest, mailboxId}
singlePattern = Match -> [ When {user: { firstname: @firstname, enabled: true, group: {id: "admin"}, settings: {mail: {notify: @notifications}}, mailbox: { id: @mailboxId, kind: "personal", unreadmails: [ @firstUnread | @restUnread ], readmails: [ {subject: "Hello"}, Tail(@rest) ] } }}, -> "ok" ]
Результаты для 10000 сопоставлений:
Regular: 5ms Single Pattern: 140ms Multiple patterns: 429ms
Да, не то что хочется увидеть в production. Почему бы не преобразовать шаблон в код близкий к первому примеру?
Сказано — сделано. Идем по шаблону и составляем список условий и промежуточных переменных.
Здесь вылезла интересная особенность. Первый вариант скомпилированной функции был почти идентичен рукописному разбору, но производительность была хуже раза в полтора. Разница была в способе создания результирующего объекта: оказалось, что создать объект с заданными полями — дешевле, чем создать пустой объект и заполнять его в дальнейшем. Для проверки я сделал вот такой бенчмарк. После чего нашел две статьи на эту тему — вот и вот — и еще и перевод на хабре.
Провели оптимизацию, запускаем:
Regular: 5ms Single Pattern: 8ms Multiple patterns: 164ms
Второе число выглядит неплохо, а что за третье и почему оно все еще большое? Третье — это выражение match с несколькими шаблонами, где срабатывает только последний. Т.к.шаблоны компилируются независимо, мы получаем линейную зависимость от числа шаблонов.
Но в реальности шаблоны будут весьма похожи — мы будем разбирать объекты отличающиеся какими-то деталями, и при этом имеющие схожую структуру. Скажем, вот здесь:
fn = Match -> [ When ["wait", "infinity"], -> console.log("wait forever") When ["wait", @time = Number], -> console.log("wait for " + this.time + "s") ] В обоих случаях массив состоит из двух элементов и первый равен «wait», отличия только во втором. А парсер сделает две почти одинаковые функции и будет вызывать их одну за другой. Попробуем их объединить.
Смысл простой:
- Парсер вместо кода будет выдавать цепочки «команд»;
- Дальше берутся все команды и собираются в одну цепочку с ветвлениями;
- Теперь команды превращаются в код.
Стоит заметить, что если мы зашли в одну цепочку, то в случае неудачи мы должны не выходить, а попробовать следующую цепочку. Я видел три способа этого достичь:
1. Вложенными условиями
if (Array.isArray(val)) { if (val.length === 2) { if (val[0] === ‘wait’) { if (val[1] === ‘infinity’) { return {when: 0}; } if (val[1].constructor.name === ‘Number’) { return {when: 1}; } } } } Смотрится ужасно, да еще и при генерации кода не запутаться бы в скобках. Нет.
2. Вложенными функциями
if (!Array.isArray(val)) return false; if (val.length !== 2) return false; if (val[0] !== ‘wait’) return false; if (res = function fork1() { if (val[1] !== ‘infinity’) return false; return {when: 0} }()) return res; if (res = function fork2() { if (val[1].constructor.name !== ‘Number’) return false; return {when: 1}; }()) return res; Выглядит лучше. Но напрягают дополнительные проверки и return-ы, т.к.нет способа вернуться сразу из внешней функции (ну разве что через исключения, но это несерьезно).
3. Breaking bad label
if (!Array.isArray(val)) return false; if (val.length !== 2) return false; if (val[0] !== ‘wait’) return false; fork1: { if (val[1] !== ‘infinity’) break fork1; return {when: 0} } fork2: { if (val[1].constructor.name !== ‘Number’) break fork2; return {when: 1}; } Выглядит неплохо и мне, как старому сишнику, сразу показалось что этот вариант будет быстрее. Быстрая проверка на jsperf подтвердила мою догадку. Значит на этом варианте и остановимся.
Посмотрим на производительность:
Regular: 5ms Single Pattern: 8ms Multiple patterns: 12ms
Вполне приемлемо. Оставляем как есть.
Архитектура и плагины
После добавления очередной функциональности путем дописывания новых if-ов в двух разных местах я решил переработать архитектуру. Теперь вместо двух больших функций parse и render появились функции parse и render поменьше, которые сами ничего толком не делают, зато каждую часть шаблона посылают по цепочке плагинов. Каждый плагин умеет:
- обрабатывать свой кусок шаблона и превращать его в набор команд;
- говорить что парсить дальше;
- превращать свои команды в код.
Например плагин для сопоставления с конструктором выглядит так:
function pluginConstructor() { return { //этот метод вызывается если в шаблоне встретилась функция //если бы мы ждали объект, то нужно было бы объявить метод parse_object //или метод parse, который вызвался бы для любого значения parse_function: function(part, f) { //добавляем команду с именем "constructor" //после перегруппировки нас попросят превратить команду в код - см. метод ниже f.addCheck("constructor", part.name); }, //этот метод вызывается чтобы "отрисовать" код для команды "constructor" //мы возвращаем условие, оно будет завернуто в if. render_constructor: function(command, varname) { return varname + ".constructor.name === " + JSON.stringify(command.value); } }; } Это позволило с одной стороны упростить добавление новых фич мне самому, а с другой — дать возможность пользователям дописать свой плагин и расширить синтаксис шаблонов. Например, можно добавить поддержку регулярных выражений, чтобы можно было писать так:
fn = Match -> [ When @res = /(\d+):(\d+)/, -> hours: @res[1], mins: @res[2] # or When RE(/(\d+):(\d+)/, @hours, @min), -> hours: @hours, mins: @mins ]
Сравнение с другими решениями
Как писал в самом начале, я попробовал поискать аналогичные решения, и вот что нашлось:
- matches.js — схожий функционал, близкая производительность, но шаблоны задаются строкой — следовательно ни тебе подсветки, ни вынесения общих частей в переменные
- идейный наследник sparkler — судя по всему имеет схожий функционал, но для синтаксиса использует макросы sweet.js, т.е. код придется дополнительно компилировать. В целом проблемы те же, хотя и выглядят шаблоны симпатичнее
- pun.js — синтаксис похож (только в шаблонах вместо @a предлагается писать $(‘a’)), однако возможностей меньше (например не поддерживаются массивы переменной длины) и производительность ниже — видимо они не выполняют компиляцию.
Сравнение производительности с matches.js, pun и ручным разбором можно найти тут.
Заключение
Вот в целом и все. Сам код можно посмотреть тут. Несмотря на то, что синтаксис заточен под coffeescript, сама библиотека написана на javascript и может быть использована в других языках, компилирующихся в js.
Несколько минусов вдогонку:
- Разбиение массивов на «голову» и «хвост» полезно для рекурсивных алгоритмов, но без оптимизации хвостовой рекурсии могут возникнуть проблемы с производительностью и переполнением стека на больших объемах.
Решение: пока не придумал - В шаблонах не получится использовать функции — вернее, использовать-то можно, однако вызовутся они только один раз при компиляции шаблона.
Решение: использовать guards - Из-за этого подмены контекста не получится привязать функции-действия к вашему контексту. С другой стороны, если уж мы пишем в функциональном стиле, то вызовы методов нам вроде бы и не нужны.
Решение: по старинке, self = this - По той же причине скорее всего не получится использовать arrow-functions из ecmascript 6 — они намертво привязывают контекст так, что даже вызовы через call/apply на них не влияют.
Решение: пока не придумал
Надеюсь, что-то окажется полезным. Спасибо за внимание.
ссылка на оригинал статьи http://habrahabr.ru/post/253761/
Добавить комментарий