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