Stupid pet tricks: functions as state

It seems the real culprit for containing state isn’t mentioned: closure.

Returning state via a function closure, for example, is at the core of implementing trampolines in JavaScript in order to implement stackless recursion.

And then there is this (2003):

• Objects are merely a poor man’s closures
• Closures are a poor man’s object

It’s not entirely true in Elixir because of one thing - you can’t mutate data in the closure. It’s entirely true in runtimes with mutable data.

There’s one disadvantage of the described pattern - the state is opaque. This will become problematic in some debugging situations - the function is basically opaque and you can’t “look into” it with default logging to figure out what’s going on (unless you use some tricks like :erlang.fun_info(fun, :env) to get the data bound in the closure).

I’d propose a slightly different, but I believe similarly convenient mechanism of a “continuation token”:

def next_job(token) do
  case Batcher.next(token) do # instead of state.()
   {:done, token} -> token
   {{subject, batch}, token} -> {create_job(subject, batch), token}
  end
end

def next({next, rest, batches, acc}) do
  next_batch(next, rest, batches, acc)
end

defp next_batch(_current, [], [], []) do
  done_tuple()
end

defp next_batch(_current, [], [], [[next | rest] | batches]) do
  {{next, rest}, {next, rest, batches, []} # instead of fn -> next_batch(next, rest, batches, []) end}
end

# and similar

This provides similar benefits of encapsulating the continuation state, but makes it more debuggable. Similar approach is used in things like :ets.select/1 for batched traversal of the ets table.

Yes, that also works and indeed has advantages in terms of transparency.

In this particular case: the generator functions are unit tested and pure, so the only things needed in tracing are the created jobs (which are done with the return values of the state function, but which are not the return values of the state function) and the initial state which is known and visible when the state is initialized.

So while it is opaque, in this case it is in an entirely benign way. A benefit is that one does not need to know what function is being called at all → it could be calling any function in any module, and the generator itself could live elsewhere as well … and if what it calls (and in what order) changes, this is also opaque to the caller. Having to know that the token “belongs with” Batcher.next/1 is not quite as cute, and it makes it harder to move the closure to an entirely other handler at runtime, since each handler needs to know what function that token “goes with”.

Still, there are indeed times that is not useful / worth it / possible without contortion, and then it is much better to pass the data about.

1. In Elixir you can’t mutate any of the data structures that serve as object surrogates either.
2. Parables aren’t that literal.

The point is that a closure can serve as a container of related data, a role in which objects are typically used and that to some degree one can be used to emulate the other - which you promptly exploit by proposing to replace the closure with a token.

Java for the longest time was using inner classes as surrogate closures and the command pattern emulates a closure.

indeed … with generators being one possible specialization of closures: when they are used to control iteration. (Not to suggest all generators are closures, as we know from e.g. comprehensions ..)

I actually think that we can do some Y-combinator-like trickery here to create a closure that, when called, returns new versions of itself that include updated data.

Not that that would be extremely useful, probably, since it would indeed mostly make introspection difficult.

@aseigo Thanks for sharing this technique though! I am wondering currently if it is possible to use some more higher-level stream combinators instead of writing out the recursion of `next_batch manually; this might improve readability. I’ll give it a try.

The category is “stupid pet tricks” … they don’t need to be useful, only fun

Should be possible … would be interested in seeing what you come up with if you toy with it a bit!

Please tell me if this code does not follow the requirements to the mapping of data, but here it is:

defmodule PairwiseComputation do

  def create_all_jobs(data) do
    data
    |> Enum.chunk_every(3) # We now have a list of batches
    |> Enum.reverse
    |> Enum.scan([], fn batch, later_batches -> [batch] ++ later_batches end) # now every item contains a list with all later batches (including current one) in there.
    |> Enum.reverse # reversing again is only necessary if you rely on order of results.
    |> Enum.map(&create_jobs/1)

  end


  defp create_jobs([]), do: []
  defp create_jobs([first_batch | batches]) do
    case first_batch do
      [] -> {:error, "unexpected format of first batch."}
      [pivot | first_batch] ->
        [first_batch | batches]
        |> Enum.map(&create_job(pivot, &1))
    end
  end

  defp create_job(pivot, elem), do: IO.puts "creating job for #{inspect pivot} <=> #{inspect elem}"
end

PairwiseComputation.create_all_jobs(1000..1100)

The output is a list of lists of :oks, which you might improve upon by gathering errors that might have occured in the creation tasks and combining them, if required.

While that probably works (didn’t run it to confirm, but I trust you ), it has a serious shortcoming given that this is a combinatorial algorithm: it scales super poorly. An average request from our workload generates ~100,000,000 pairs, which when batched up create some 200k batch jobs (which itself is chunking size that is an optimization over space and compute time).

We don’t want them all created up front as it would mean holding all the jobs for every request in memory at the same time and means we can’t start any jobs until they are all created in the first place. That ends up being non-trivial, especially once we start adding parallel requests into the mix.

But in the realm of “can it be done”, you’ve shown it can