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

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

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 — задавайте, я на нем собаку съел.

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