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:
quoteis used to generate codeunquoteis 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
:defsymbol - 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.