Author: gabriele renzi

During my 2024 Advent of Code, I decided to try and write some solutions in Elixir. I knew almost nothing of it, and after a month or so with it, I still know basically nothing but I had fun.

I also solved the problem with Ruby, so most days I limited myself to translating the solution from one language to the other, which is pretty straightforward: both Elixir and Ruby have high level data types (lists, sets, dictionaries, regular expressions), similar functions/methods to work with them (map, reduce, sum, etc) and you can typically convert things line by line. There’s one big difference tho.

State

Elixir is mainly a functional language, so if I had written something in ruby which used mutable state (pretty natural) I’d have to do a bit more work when translating it.

For example, many AoC problems require writing a depth-first-search or a variation of that (Dijkstra, A* etc), I’d write that imperatively in Ruby mutating state (e.g. push/pop things from a queue), but doing it in Elixir you’d carry the state in an additional function argument.

This generally works fine, but at some point I wanted to try something different, since there’s a lot of AoC problems solved with dynamic programming and memoization.

Typically, the first part of the problem is something that can be brute forced, and the second part requires you to apply memoization in a smart way, understanding what is the “state” you care about.

In languages such as Ruby/Python/Perl/Raku you generally do this with some metaprogramming that converts a method/function into its memo-ized equivalent, so you’d go from something like e.g.

  def fib(n)
    if n < 2 do
      n
    else
      fib(n - 1) + fib(n - 2)
    end
  endCode language: Ruby (ruby)

to

  memoize def fib(n)
    if n < 2 do
      n
    else
      fib(n - 1) + fib(n - 2)
    end
  endCode language: Ruby (ruby)

Alas, this was a bit tricky to do in Elixir.

Memoization in Elixir, done bad

At first, I thought I’d write a higher order function that just wrapped the code with a cache check

    def make_memo(fun) do
      cache = %{}
      fn args ->
        case Map.get(cache, args) do
          nil ->
            result = apply(fun, args)
            cache = Map.put(cache, args, result)
            result

          result ->
            result
        end
      end
    endCode language: Elixir (elixir)

Something like this might work in Scheme or other mostly-functional languages, but this does not work in Elixir: re-assigning to cache creates a different variable, rather than update the existing one. The Map object is also immutable, so I can’t update it in-place.

Luckily, Erlang (and thus Elixir) come with two mutable dictionaries you can use!

The Erlang Term Storage (ETS) is a shared dictionary that is writable by the current process and readable by all. The Process dictionary is, well, a per-process dictionary which is also mutable. I do not really know what the specific limitations are for either, and I was going to have a single process anyway, so I went with the latter purely on aesthetical reasons.

Thus I could write code like this

  defmodule Demo do
    def make_memo(fun) do
      fn arg ->
        # try to avoid the most obvious name collisions
        case Process.get({:memo, fun, arg}) do
          nil ->
            result = fun.(arg)
            # mutable state baby!
            Process.put({:memo, fun, arg}, result)
            result

          result ->
            result
        end
      end
    end

    def slow_math(n) do
      IO.puts("slow computation..")
      n * n
    end

    def main() do
      IO.puts(slow_math(10))
      fast_math = make_memo(&slow_math/1)
      IO.puts("should only execute this once:")
      IO.puts(fast_math.(10))
      IO.puts(fast_math.(10))
    end
  end

  Demo.main()Code language: Elixir (elixir)

And executing this seems to show the memoized function is indeed only executed once

  $ elixir fib.ex
  slow computation..
  100
  should only execute this once:
  slow computation..
  100
  100Code language: Bash (bash)

My code is still broken tho! While it works for this simple function, it would not work for e.g. a standard recursive fibonacci:

    def fib(n) do
      IO.puts("fib(#{n})")
      case n do
        0 -> 0
        1 -> 1
        _ -> fib(n - 1) + fib(n - 2)
      end
    end

    def main() do
      fast_fib = make_memo(&fib/1)
      IO.puts(fast_fib.(4))
    endCode language: Elixir (elixir)

This outputs

  $ elixir fib.ex
  fib(4)
  fib(3)
  fib(2)
  fib(1)
  fib(0)
  fib(1)
  fib(2)
  fib(1)
  fib(0)
  3Code language: Bash (bash)

And you can see the output multiple times for each number.

What is wrong here is that the function calls itself, and not the memoized function. If you wrote a memoizing function in Ruby or Python you’d (likely) be shadowing the existing one, so that each call would then hit the memoized one.

But I can’t do this in Elixir (or perhaps I can and I just don’t know how, I’m a newbie).

The obvious fix would be to alter the function to receive a reference to itself as an extra argument, but that means I need to also update all call sites which is ugly and boring. There’s a solution which is more fun.

Macro all the things!

Elixir is largely built from macros. Many (all?) of the various defsomething are macros. The Elixir developers advice against overusing macros but a project that you’re doing for fun and literally lasts one day seems like a good fit.

The idea is the following: rather than define a base function and then wrapping it with something else, we will define a function using a body and wrapping it with our caching logic.

The only function will be the one we define, and thus any recursive call will hit the same macro-defined memoized function.

The main thing to remember about Elixir macros is:

• quote is used to generate code
• unquote is used to insert values into a quoted expression

It may help to think of them as “defining a string” and “interpolate a value in a string“.

The standard example from the Elixir docs is to define an unless (“if not”) macro

  # usage: macro_unless(condition, do: something)
  defmacro macro_unless(clause, do: expression) do
    quote do
      if(!unquote(clause), do: unquote(expression))
    end
  endCode language: Elixir (elixir)

you can imagine this as more or less

 macro_unless = "if !#{clause}, do: #{expression}"Code language: Ruby (ruby)

You can see how the macro will get the block of code in the do argument, via either the inline do: or the block-based do ... end form.

But function definitions have more than a single word as condition, what is their shape? Well, you can find out easily, spin up an elixir shell and use quote

  iex(1)> quote do def fun(arg), do: whatever end
  {:def, [context: Elixir, imports: [{1, Kernel}, {2, Kernel}]],
  [
    {:fun, [context: Elixir], [{:arg, [], Elixir}]},
    [do: {:whatever, [], Elixir}]
  ]}
Code language: PHP (php)

AKA

• literally the :def symbol
• some “context”, whatever that is
• an array containing
  • the “head” of the function (name, more context, arguments, etc)
  • the “body” of the function.

Elixir provides a handy helper Macro.decompose_call/1 to extract function name and argument names (and ignore the various “contexts”), so our final implementation of a defmemo macro looks like this

  defmacro defmemo(head, do: block) do
    {func_name, args} = Macro.decompose_call(head)
    quote do
      def unquote(func_name)(unquote_splicing(args)) do
        key = {:memo_cache, __MODULE__, unquote(func_name), unquote(args)}
        case Process.get(key) do
          nil ->
            result = unquote(block)
            Process.put(key, result)
            result

          result ->
            result
        end
      end
    endCode language: Elixir (elixir)

Notice the unquote_splicing, in our “macros are string definition+interpolation” simile, this is the equivalent of “join the values with a comma“.

The last step is putting this all together, the only thing to keep in mind is you need to put the macro in a separate module before using it

  defmodule Memo do
    defmacro defmemo(head, do: block) do
      {func_name, args} = Macro.decompose_call(head)
      quote do
        def unquote(func_name)(unquote_splicing(args)) do
          key = {:memo_cache, __MODULE__, unquote(func_name), unquote(args)}
          case Process.get(key) do
            nil ->
              result = unquote(block)
              Process.put(key, result)
              result

            result ->
              result
          end
        end
      end
    end
  end

  defmodule Demo do
    require Memo

    Memo.defmemo fib(n) do
      IO.puts("fib(#{n})")
      case n do
        0 -> 0
        1 -> 1
        _ -> fib(n - 1) + fib(n - 2)
      end
    end

    def main() do
      IO.puts(fib(4))
    end
  end

  Demo.main()Code language: PHP (php)

And executing this it seems to work

  $ elixir fib.ex
  fib(4)
  fib(3)
  fib(2)
  fib(1)
  fib(0)
  3Code language: Bash (bash)

Success!

defmemo, how are thee broken? Let me count the ways. 

This implementation was enough for me to solve Day 19 of the 2024 Advent of Code, and I am very proud of myself for having managed to do it, tho 90% of the credit goes to Saša Jurić for his articles on elixir macros.

But beware: this code is still utterly broken, and that is my fault 🙂

For example, functions in Elixir can be defined multiple times using pattern matching, and can have guard clauses

  def fib(0), do: 0
  def fib(1), do: 1
  def fib(n) when n > 1 do
    fib(n - 1) + fib(n - 2)
  endCode language: Elixir (elixir)

If you try to replace def with defmemo it will not work.

Likewise, functions can be defined multiple times with different arity (number of arguments), and that will also not work. Functions can also have default arguments, and I’ve not even tried to see how those work.

I’m also not sure I used the Process dictionary properly, and I think there’s a lot of room for name clashes. So, in short do not use this code.

If you’re looking for a proper defmemo you better use one of the established modules such as https://github.com/melpon/memoize.

Still, I hope you enjoyed this short tour of how to write an elixir defmemo macro as much as I did. And notice I’m still a wildly incompetent Elixir programmer, so feel free to correct me in comments if anything I wrote is too far from the truth.