Формулы и ленивые комбинаторы

Библиотека для работы с формулами

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

def notify?(rate) when rate > 2.0, do: true def notify?(_), do: false 

Мы позволяем клиентам добавлять такие проверки динамически. А значит, нам нужен более или менее надежный механизм для проверки условий, добавленных только что.

Да, Code.eval_string/3 как-то работает, но оно компилирует условие каждый чертов раз перед собственно проверкой. Очевидно, что это напрасная трата ресурсов без всякой причины. Которая усугубляется тем, что мы получаем и обрабатываем примерно 10000 курсов для разных валютных пар ежесекундно.

Так мы придумали прекомпилированные формулы. Крошечная библиотека formulae создает модуль для каждого заданного условия и компилирует формулу, введенную пользователем, в код, — единожды.

NB библиотеку следует использовать с осторожностью, потому что имена модулей хранятся в виде атомов и слепое безусловное их создание для всего, что клиент хочет проверить, может привести к атомной DoS-атаке на виртуальную машину эрланга при более-менее долгом времени исполнения. Мы используем максимально допустимый шаг значения в 0.01, который дает максимум 200 тысяч атомов при худшем сценарии развития событий.

Ленивые Комбинаторы

Но главная цель этой заметки — не рассказать о прекомпилированных формулах. Для некоторых пограничных случаев анализа курсов валют нам нужно было рассчитать перестановки довольно длинного списка. Внезапно, стандартная библиотека Elixir не предоставляет готовое решение. Ну, я решил скопировать сигнатуры комбинаторов из Ruby (Array#combination и родственничков). К сожалению, это оказалось не так просто для длинных списков. Комбинации глохли в районе тридцати элементов в списке, пермутации — и того раньше.

Ну, ожидаемо, что уж тут; поэтому я стал играться в ленивую реализацию с использованием Stream. Оказалось, и это не так просто, как я думал. Я придумал что-то вроде кода ниже

list = ~w[a b c d e]a  combinations =   Stream.transform(Stream.with_index(list), :ok, fn {i1, idx1}, :ok ->     {Stream.transform(Stream.with_index(list), :ok, fn         {_, idx2}, :ok when idx2 <= idx1 ->           {[], :ok}          {i2, idx2}, :ok ->           {Stream.transform(Stream.with_index(list), :ok, fn             {_, idx3}, :ok when idx3 <= idx2 ->               {[], :ok}              {i3, idx3}, :ok ->               {Stream.transform(Stream.with_index(list), :ok, fn                   {_, idx4}, :ok when idx4 <= idx3 ->                     {[], :ok}                    {i4, _idx4}, :ok ->                     {[[i1, i2, i3, i4]], :ok}                 end), :ok}           end), :ok}       end), :ok}   end) 

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

В коде выше просматриваются три различных шаблона. Успешная ветка, из которой мы выбрасываем список. Быстрый выброс пустого списка. И трансформация потока с индексом. Похоже, что мы могли бы попытаться создать AST для вышеуказанного.

Это тот редкий случай, когда использование Kernel.SpecialForms.quote/2, вероятно, все только усложнит, так что я пошел по пути наименьшего сопротивления: мы будем лепить старый добрый голый AST.

Я начал с того, что в консоли вызвал quote do: на этом коде, и до рези в глазах изучил результат. Да, есть закономерности. Ну, поехали.

Итак, начинать надо с создания общего каркаса.

defmacrop mapper(from, to, fun),   do: quote(do: Enum.map(Range.new(unquote(from), unquote(to)), unquote(fun)))  @spec combinations(list :: list(), count :: non_neg_integer()) :: {Stream.t(), :ok} defmacro combinations(l, n) do   Enum.reduce(n..1, {[mapper(1, n, &var/1)], :ok}, fn i, body ->     stream_combination_transform_clause(i, l, body)   end) end 

Теперь нам нужно начать мыслить в категориях не кода, но AST, чтобы увидеть повторяющиеся шаблонные части. Это весело!

Начнем с вспомогательных макросов для упрощения кода:

def var(i), do: {:"i_#{i}", [], Elixir} def idx(i), do: {:"idx_#{i}", [], Elixir} 

Внутренний кусок AST, выдранный из общего представления:

def sink_combination_clause(i) when i > 1 do   {:->, [],     [       [         {:when, [],         [           {​{:_, [], Elixir}, idx(i)},           :ok,           {:<=, [context: Elixir, import: Kernel], [idx(i), idx(i - 1)]}         ]}       ],       {[], :ok}     ]} end 

Все внутренние куски вместе:

def sink_combination_clauses(1, body) do   [{:->, [], [[{var(1), idx(1)}, :ok], body]}] end  def sink_combination_clauses(i, body) when i > 1 do   Enum.reverse([     {:->, [], [[{var(i), idx(i)}, :ok], body]}     | Enum.map(2..i, &sink_combination_clause/1)   ]) end 

И, наконец, внешняя обертка вокруг всего этого.

def stream_combination_transform_clause(i, l, body) do   clauses = sink_combination_clauses(i, body)    {​{​{:., [], [{:__aliases__, [alias: false], [:Stream]}, :transform]}, [],     [       {​{:., [], [{:__aliases__, [alias: false], [:Stream]}, :with_index]}, [], [l]},       :ok,       {:fn, [], clauses}     ]}, :ok} end 

Все перестановки выполняются практически одинаково, единственное изменение — это условие во внутренних вызовах. Это было несложно, да? Весь код можно посмотреть в репозитории.

Приложение

Хорошо, так как мы можем эту красоту использовать-то? Ну, как-то так:

l = for c <- ?a..?z, do: <<c>> # letters list with {stream, :ok} <- Formulae.Combinators.Stream.permutations(l, 12),   do: stream |> Stream.take_every(26) |> Enum.take(2)  #⇒ [["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"], #   ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "l", "w"]] 

Мы теперь даже можем накормить Flow прямо из этого потока, чтобы распараллелить вычисления. Да, все равно это будет медленно и печально, но, к счастью, такая задача стоит перед нами не в реальном времени, а для аналитики, которую можно запустить ночью, и которая будет неторопливо проходить через все комбинации и куда-нибудь записывать получившиеся результаты.

Если есть вопросы по AST в Elixir — задавайте, я на нем собаку съел.