Formulas and Lazy Combinators

Formula Library

In fintech, we often need to check that simple arithmetic conditions are satisfied, for example, whether the exchange rate will be greater than the expected value or not. These conditions change very often, and we needed to invent some kind of bicycle in order to add new checks and carry out existing ones in real time. Imagine that several thousand customers expect to receive notifications when the exchange rate for some currency pairs reaches a ratio of two to one. It would be very simple if we could only make the conditions static:

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

We allow customers to add such checks dynamically. So, we need a more or less reliable mechanism for checking the conditions just added.



Yes, Code.eval_string/3



somehow works, but it compiles the condition every damn time before actually checking. Obviously, this is a waste of resources for no reason. Which is compounded by the fact that we receive and process about 10,000 courses for different currency pairs every second.



So we came up with precompiled formulas. The tiny formulae



library creates a module for each given condition and compiles the formula entered by the user into code — once.



The NB library should be used with caution, because the module names are stored in the form of atoms and their blind unconditional creation for everything that the client wants to check can lead to an atomic DoS attack on the Erlang virtual machine with a more or less long execution time. We use the maximum allowable value step of 0.01



, which gives a maximum of 200 thousand atoms in the worst case scenario.

Lazy Combinators

But the main purpose of this article is not to talk about precompiled formulas. For some borderline cases of exchange rate analysis, we needed to calculate the permutations of a rather long list. Suddenly, the Elixir standard library does not provide a turnkey solution. Well, I decided to copy the combinatorial signatures from Ruby ( Array#combination



and cousins). Unfortunately, this was not so easy for long lists. The combinations stalled in the region of thirty elements in the list, permutation - even earlier.



Well, it is expected that already here; so I started playing lazy implementation using Stream. It turned out, and it is not as easy as I thought. I came up with something like the code below

 list = ~w[abcde]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)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

This works, but only for a predetermined number of combinations. Well, this is easily overcomeable: for such a case we have macros, right?



In the code above, three different patterns are viewed. A successful branch from which we drop the list. Quick dump of empty list. And stream transformation with index. It looks like we could try to create an AST for the above.



This is the rare case when using Kernel.SpecialForms.quote/2



will probably only complicate things, so I took the path of least resistance: we will sculpt the good old naked AST.



I started by calling quote do:



in the console on this code, and studied the result to the point. Yes, there are patterns. Let's go.



So, you need to start by creating a common framework.

 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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Now we need to start thinking in terms of not code, but AST, to see repeating template parts. It's fun!



Let's start with helper macros to simplify the code:

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

AST inner piece torn from a general view:

 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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

All inner pieces together:

 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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

And finally, the outer wrapper around it all.

 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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

All permutations are performed almost identically, the only change is the condition in internal calls. It was easy, right? All code can be viewed in the repository .

application

Good, so how can we use this beauty? Well, something like this:

 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"]]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

We can now even feed Flow



directly from this stream to parallelize the calculations. Yes, it will still be slow and sad, but, fortunately, this task is not in real time, but for analytics that can be run at night and that will slowly go through all the combinations and write down the results somewhere.



If you have questions about AST in Elixir - ask, I ate a dog on it.