Steering your submarine with Elixir, Leex and Yecc (AoC'21, day 2)

After solving a Advent of Code challenge by treating the input as a program last year, I wanted more this year. The opportunity came today and I decided to take it. Instead of Parlet and Ruby, though, I decided to use Elixir/Erlang tooling to get the job done.

The problem

In the Day 2 this year you need to pilot your submarine. This is done by a series of commands, such as this:

forward 5
down 5
forward 8
up 3
down 8
forward 2

We have a command, followed by a number - one pair per line. There are three commands:

• forward moves the submarine horizontally by number
• down moves it down, increasing the depth we're at
• up does exactly the opposite of down

A series of commands - that's a program! To execute it, we need basically 3 things: a lexer, a parser and an interpreter. Fortunately, Elixir gives us a tooling for first two for free, and the last one is easy. Let's do it.

Solution

Lexer

We are going to start with creating a new mix project with mix new submarine_lang. Our first step will be to create a lexer, which will tokenize the input. This is what I put in src/lexer.xrl:

Definitions.
FORWARD       = (forward)
UP            = (up)
DOWN          = (down)
WHITESPACE    = [\s\t\n]
DIGITS        = [0-9]+

Rules.
{WHITESPACE} : skip_token.
{FORWARD}    : {token, {move, forward}}.
{UP}         : {token, {move, up}}.
{DOWN}       : {token, {move, down}}.
{DIGITS}     : {token, {number, list_to_integer(TokenChars)}}.

Erlang code.

This lexer is not perfect. It could me more strict, for example to not allow two commands in the same line, but it serves its purpose for this task, while at the same time remains relatively simple. We basically have three commands, a number (DIGITS) and whitespace.

Let's take our parser for a test drive then, with iex -S mix. The important thing to remember is that Leex only takes Erlang strings as inputs, so you either have to use single-quoted strings or use to_charlist method from Elixir.Kernel.

Here are some examples:

Interactive Elixir (1.12.2) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> :lexer.string('forward 5')
{:ok, [move: :forward, number: 5], 1}
iex(2)> :lexer.string('forward 5\ndown 1\ndown 100')
{:ok,
 [move: :forward, number: 5, move: :down, number: 1, move: :down, number: 100],
 3}
iex(3)> :lexer.string('backward 6')                 
{:error, {1, :lexer, {:illegal, 'b'}}, 1}

Note that since the result is a list of tuples with two elements, iex displays it as a keyword list (because that's what a keyword list is).

Parser

Since the lexing/tokenizing part is done, we are now going to move on to parser, which will put some basic meaning into our tokens. The parser will reside in src/parser.yrl and it is really simple:

Nonterminals command command_list.
Terminals number move.
Rootsymbol command_list.

command      -> move number : {'$1', '$2'}.
command_list -> command : ['$1'].
command_list -> command command_list : ['$1' | '$2'].

We have two terminal symbols, two non-terminal to group them and a non-terminal command_list should be the root. Let's test it:

iex(1)> {:ok, tokens, _} = :lexer.string('forward 5\ndown 1\ndown 100')
{:ok,
 [move: :forward, number: 5, move: :down, number: 1, move: :down, number: 100],
 3}
iex(2)> :parser.parse(tokens)
{:ok,
 [
   {{:move, :forward}, {:number, 5}},
   {{:move, :down}, {:number, 1}},
   {{:move, :down}, {:number, 100}}
 ]}

Ok, nice. We have a list of tuples, where each one of them contains two other tuples - a move command and a number. With that, we can move on to a very basic interpreter.

Interpreter

We have the semiotic part done, now let's add some semantic into it. Our interpreter is going to just take a list of commands and apply them one by one, along with some representation of context or state. This is exactly what Enum.reduce does and so we are going to use it.

defmodule SubmarineLang do
  def eval_file(name) do
    input =
      name
      |> File.read!()
      |> to_charlist()

    {:ok, tokens, _} = :lexer.string(input)
    {:ok, ast} = :parser.parse(tokens)
    eval(ast)
  end

  defp eval(ast) when is_list(ast), do: Enum.reduce(ast, {0, 0}, &eval/2)
  defp eval({{:move, :forward}, {:number, x}}, {h, depth}), do: {h + x, depth}
  defp eval({{:move, :down}, {:number, x}}, {h, depth}), do: {h, depth + x}
  defp eval({{:move, :up}, {:number, x}}, {h, depth}), do: {h, depth - x}
end

And this is it. When we run the interpreter, it will go through the commands one by one and adjust the context (a tuple with horizontal position and a depth) accordingly. The result will be such a tuple after applying all the commands. All that's left is to multiply first element by the second.

The second part

I'm not going to go into details about second part, but there the meaning of each command changes - now it makes a different modification to the context. Therefore you need to change the interpreter and only the interpreter.

My complete solution is available on Github, if you want to take a look.

Some reading

• Erlang/Elixir: Using Leex and Yecc Parsing Domain Language (DSL)
• Using Leex and Yecc in Elixir

Comments

[Adolfo Neto]

Very interesting approach!