I’m currently following along the magnificent book Crafting Interpreters by Robert Nystrom. The author gradually builds up an interpreter from scratch. The first implementation (there are two implementations build throughout the book) is built with Java as the host language. The language being interpreted is a simplified version of lua including a few OO features (methods, classes, inheritance). The author calls this educational language “Lox”.

I’m trying to follow along doing the same exercise in Elixir. A lot of people have gone before me. There are even two implementations in Elixir. It’s a fun challenge, and I learned a lot already (most surprisingly about binary matching and protocols).

But I’m kinda stuck now. Until now I’ve had to translate solutions that were built using the OO features of Java into their immutable equivalent in Elixir. A good exercise! Every time state was being held as an instance field, I had to come up with a way to pass that same state around on the stack. The interpreter being built employs a strategy for parsing called recursive descent.

At this point I’m trying to implement local functions and closures. The concept of an “environment” has slowly evolved in the previous chapters. Each environment is associated with a scope or block and can have a chain of ancestors to allow lexical scoping. Until now I could pass an environment around, create new child-environments, or discard environments when leaving a scope. But closures make me scratch my head… Consider this fragment of Lox code:

fun makeCounter() {
  var i = 0;
  fun count() {
    i = i + 1;
    print i;
  }

  return count;
}

var counter = makeCounter();
counter(); // "1"
counter(); // "2"

When defining the inner count() function, its environment needs to be captured. But both calls to counter() need use and update the same captured environment. With the recursive descent strategy in an OO language, the captured environment of each function is being held as a reference that can be mutated when needed. That’s not something I can create an alternative for with immutable data structures. I can’t pass those captured environments through the stack, because they are associated with each function definition (as opposed to each function call).

I can come up with a solution that employs the Process dictionary as a form of mutable state. A similar solution could be built with spawning processes, an ets table or an Agent. But all these solutions feel much less elegant and more verbose than their OO equivalent. Another downside of these alternatives is that there won’t be any trigger to release allocated state in those environments once they become unreferenced. The OO solution can rely on the underlying garbage collector to clean up unreferenced heap allocated state.

My main question is if there are variations of the recursive descent parser strategy that play nice with functional languages that employ immutable data structures. Or if that’s just a bad fit to begin with, that would be also nice to know.

My humble attempt at crafting this interpreter can be found here: GitHub - linusdm/ex_lox: An Elixir implementation of an interpreter for the Lox language (from the book Crafting Interpreters by Robert Nystrom).

Cheers, and thanks for reading this far!