Введение

Как-то раз я сидел и грустно смотрел на написанный в рамках изучения эрланговский код. Очень хотелось написать на нем что-нибудь более полезное, чем крестики-нолики, но как назло никаких подходящих задач в голову не приходило. Зато есть 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) и соответствующих им действий;
При вызове подменяется контекст, так что все эти &commat;a (== this.a) указывают на специально подготовленные свойства (properties), позволяющие парсеру понять, какие значения куда привязывать;
Далее при вызове с конкретным значением идет сравнение с шаблоном (пока можно считать, что идет рекурсивный обход шаблона и значения и сравнения конкретных значений, чуть ниже будет подробнее об этом);
Если значение совпало с шаблоном, то вызывается функция-действие. У нее мы тоже подменим контекст, подставив соответствующие значения.

Так что если взять пример выше, то &commat;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 на них не влияют.
Решение: пока не придумал

Надеюсь, что-то окажется полезным. Спасибо за внимание.

Pattern-matching (еще один) в coffeescript