From the Mind of Trevor Stone

Another December, another adventure with Advent of Code (previously: 2021, 2020). This year I used it as an opportunity to learn Elixir. Since an elixir is (per Wikipedia a sweet liquid used for medical purposes, to be taken orally and intended to cure one's illness, I decided to write reflections each day about something interesting about Elixir the language and about some sort of elixir or other beverage.

Elixir is built on top of the Erlang programming language and runtime system. Erlang was designed by Ericsson for running large-scale telephone networks, so the language goals include distributed communication, high availability/uptime, fault tolerance, and avoidance of data corruption. I had heard that Erlang was nice for building concurrent software but had a reputation for confusing syntax, so I was interested to learn about Elixir, which was created by a notable member of the Ruby on Rails community and brought a syntax and coding style that's more familiar to developers who've used "functional style" in modern imperative languages. Some of the notable features of Elixir (via Erlang) are

• All data structures are immutable
• Functions are dispatched and assignments are made based on structural typing
• Code is generally written in a functional programming style

Elements of functional programming have been coming to mainstream languages like JavaScript, Java, Python, and Ruby over the last decade and change, largely around handling collections of data. Stepping through an array by incrementing indices and modifying a result is falling out of vogue in favor of constructs like items.map(item => item.price).filter(price => price > 0).reduce((p, accumulator) => accumulator + p) (and convenience methods like sum() to avoid writing common reduce functions). Although I'm quite familiar with this style, I've always done it within the context of an imperative language, where I can write a linear function flow and drop into functional style for processing collections, then imperatively act on the results. Writing the whole program in a functional approach required switching my brain a bit, particularly since the Advent of Code problems are often specified by explaining a series of instructions which map more literally to an imperative program than a functional one. I also noticed that functional and recursive thinking is also more challenging when I'm sleep deprived after a few weeks of late night programming :-)

Structural typing is a very interesting approach, and allows logic flows to be written without a lot of if-else statements. Elixir's main data types are (with some simplification) numbers, strings, atoms, tuples, (singly-linked) lists, and maps. Pattern matching can be used to declare different "function heads", like this example which computes the absolute value:

def abs(x) when x < 0, do: -1 * x
def abs(x), do: x

or this one which computes the sum of distances of a list 2D points from the origin:

# base case: sum of an empty list is zero
def distance_sum([]), do: 0
# sum of a list is distance of the first point plus the sum of the rest of the list
def distance_sum([{x, y} | tail]), do: abs(x) + abs(y) + distance_sum(tail)


By default, Elixir programs crash if there isn't a structural match for a value that's being matched, which allowed some confidence when writing code that makes assumptions about the Advent of Code input: "if it doesn't look like one of the cases I've covered, the program will crash and it will be very obvious" rather than "who knows what will happen if I get unexpected input." Since pattern matching works on fixed-length string prefixes, I was able to get through more than 2 weeks of AoC without using any regular expressions, including some neat string pattern matching logic like this.

Immutable-only data structures were generally nice to work with, and avoid a whole category of bugs related to modifying things at the wrong time, or trying to treat an object as both the new state and the old one (common for Advent of Code problems where you're moving a bunch of things around one step at a time). The downside of immutable data structures is that using something like a cache isn't particularly straightforward. The general functional programming approach to a cache is a function which "adds" to a map by creating a copy of the old map but with the new value in addition, and pass that new cache value to each recursive call. But since later calls may add even more items to the cache (for example in a depth-first traversal of a graph), the recursive functions also need to return their modified cache, which ends up with a lot of bookkeeping. I also discovered that (no great surprise) creating a new map a million times with a million items in it generates a lot of memory pressure, slowing down runtime. Fortunately Erlang offers a concurrent "mutable" table with efficient access which I discussed for day 16. The other occasion where immutability became a challenge was when I built a doubly-linked list as a circular buffer using an Agent to keep each node's mutable state. Elixir's normally speedy execution time didn't do well with this design, taking about a minute to run. Interestingly, I didn't realize the problem description had an unstated assumption about how looping is handled, so while I was racking my brain to find the bug I implemented the same algorithm in Go using mutable data structures. The Go version ran orders of magnitude faster, suggesting there's a significant cost for communicating between Erlang processes (even though it's significantly cheaper than OS-level inter-process communication would be). I haven't yet taken the time to implement an Elixir version without Agents which recreates the whole circular list each time, or a Go version which uses goroutines to mimic the Agent behavior to compare concurrency overhead.

Overall I was pretty happy with Elixir as a language. The standard library is somewhat spartan (there's no priority queue, for example), but you can get a lot of mileage from Enum and the other core modules. The documentation is pretty good, though I did get caught up in one case where an example used low-valued integers and indices in the same example and I confused the order. I'm still getting used to all functions being defined on modules rather than being able to call "methods" on "objects" (so Map.update(my_map, some_key, new_value) rather than my_map.update(some_key, new_value)), but Elixir's pipeline syntax makes up for it: input |> Enum.map(some_func) |> Enum.map(other_func) |> Enum.sum(). In contrast to Raku I hardly spent any time at all debugging code where my assumption of what it was doing didn't match what the language was actually doing. These cases were mostly caught by the compiler or at runtime by a failed structural match. Compile times are generally under one second, as was runtime for most solutions, so much so that I would worry I'd hit an infinite loop if my program ran for more than five seconds. This strikes a good balance for rapid development in a contest-like environment.

Going in to the month, one of my main goals was to go to bed at a reasonable hour and not get burnt out. It turns out that "get a working solution, then clean up the code, come up with a brewing or beverage metaphor, then write a few paragraphs about an interesting facet of the program, then post it all to Reddit" wasn't a very effective way of reliably going to bed. In the first week or so when the problems are pretty easy I would get all excited and stay up past 2am reading and chatting about other people's solutions. So when it came for the hard problems in the third week, I was already running on not enough sleep, and sometimes stayed up past three (my worst was a 5am bedtime), only to spend half the day at work thinking about other approaches to the problem. Fortunately I didn't have a major breakdown at the end of the cycle like I did last year, partly because there wasn't anything as frustrating as 2021 day 24 and partly because I didn't have extra pent up frustration with the programming language.