Введение
Как-то раз я сидел и грустно смотрел на написанный в рамках изучения эрланговский код. Очень хотелось написать на нем что-нибудь более полезное, чем крестики-нолики, но как назло никаких подходящих задач в голову не приходило. Зато есть 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 на них не влияют.
Решение: пока не придумал
Надеюсь, что-то окажется полезным. Спасибо за внимание.
Автор: GRaAL
