Hosting a small language (Ovo2) from scratch in Elixir, pt 4
Building an AST and a parse-print-parse feedback loop

full code hosted on github

• Part 1 : gathering requirements from a previous experiment
• Part 2 : tokenization
• Part 3 : parsing
• Part 4 : AST emission and print-parse-print loop
• Part 5 : evaluation
• Part 6 : basic recursion : environment as processes
• Part 7 : weird features, towards a global stateful machine
• Part 8 : a graphical environment with liveview

From the last post, I advanced on the parser and AST node emission, fixing bugs in the tokenizer as I added complexity, and went to implement a simple printer. Last time I worked on this mini-language, I found that having a printer as early as possible was quite useful to check general soundness : if you can prove at any time that parse(input) equals parse(print(parse(input))), this immensely helps for debugging.

The printer output itself isn’t that useful at this stage.

First, I found a bug in the tokenizer when I went on to tokenize nested lists, or nested parenthesized expressions. My tokenizer concept was that it emitted a token at each state change. But two consecutive ] tokens did not make for a state change.

I then added an idea of “repeatable tokens” to my token producing function :

  @repeatable_states [
    :open_paren,
    :close_paren,
    :end,
    :open_bracket,
    :close_bracket
  ]

  @doc """
  Goes to next state while accumulating a token if the buffer wasn't empty, mainly for deduplication purposes.
  """
  @spec accumulate(
          [String.t()],
          atom(),
          list(Ovo.Token.t()),
          binary() | nil,
          atom(),
          binary() | nil
        ) :: list(Ovo.Token.t())
  def accumulate(rest, prev_state, out, buf, next_state, next_buf \\ "") do
    if prev_state != next_state or prev_state in @repeatable_states do
      walk(rest, next_state, [{prev_state, buf} | out], next_buf)
    else
      walk(rest, next_state, out, next_buf)
    end
  end

After that, I could expand the complexity of my parser by implementing list parsing, function call parsing, expression parsing, with combinators :

  # Parsing a program is parsing a list of expressions
  def parse(tokens) do
    case C.repeat(&parse_expression/1).(tokens) do
      {:ok, ast, []} -> {:ok, Ast.root(ast), []}
      b -> b
    end
  end

  # Parsing an expression is any of the supported expressions :
  def parse_expression(tokens) do
    case C.any([
           &parse_lambda/1,
           &parse_if/1,
           &parse_call/1,
           &parse_parenthesized_expression/1,
           &parse_value/1
         ]).(tokens) do
      {:ok, nodes, rest} -> {:ok, Ast.expr(nodes), rest}
      b -> b
    end
  end

For lists, lambdas, and function heads, I split the parsers depending on arity / list length to de-clutter the code a bit :

  def parse_lambda(tokens) do
    case C.all([
           C.match(:backslash),
           C.any([
             &parse_multiple_arity_lambda/1,
             &parse_single_arity_lambda/1,
             &parse_zero_arity_lambda/1
           ]),
           C.match(:arrow),
           &parse_block/1,
           &parse_end/1
         ]).(tokens) do

I had made a mistake in the last session, because parser combinators emitted nil / an element / a list of elements, and standardized to emit lists, before expanding my Ast node collection. The Ast emission is quite straightforward as soon as the parsers produce the right nodes :

  def parse_multiple_arg_call(tokens) do
    case C.all([
           &parse_symbol/1,
           C.match(:open_paren),
           C.repeat(C.then(&parse_expression/1, &parse_comma/1)),
           &parse_expression/1,
           C.match(:close_paren)
         ]).(tokens) do
      {:ok, [a | b], rest} -> {:ok, Ast.call(a, b), rest} # Here, we produce an Ast node for a function call.
      b -> b
    end
  end

The Ast module is only a collection of helpers (that will also help me add @spec and @type annotations) :

...
  def expr(val), do: make(:expr, val, [])

  def block(nodes), do: make(:block, nil, nodes)

  def condition([a, b, c]), do: make(:condition, nil, [a, b, c])

  def lambda(head, body), do: make(:lambda, head, body)

  def call(val, children \\ []), do: make(:call, val, children)
...

To this point, I wrote a few detailed tests to help me build those parsing and node generation steps to the expected outcome.

  test "Parses a multi-arg function call" do
    {:ok,
     %Ovo.Ast{
       kind: :root,
       value: nil,
       nodes: [
         %Ovo.Ast{
           kind: :expr,
           value: %Ovo.Ast{
             kind: :call,
             nodes: [
               %Ovo.Ast{kind: :expr, value: %Ovo.Ast{kind: :symbol}},
               %Ovo.Ast{kind: :expr, value: %Ovo.Ast{kind: :symbol}}
             ]
           }
         }
       ]
     }, []} = parse("foo(bar, baz)")
  end

To debug my parser with more complex expressions, I switched to a test helper (that also previously emitted the text representation of the program) :

  def parse_print_parse(input) do
    {:ok, parsed, _} = input |> parse()
    printed = parsed |> Ovo.Printer.print()
    {:ok, reparsed, _} = printed |> parse()
    assert parsed == reparsed
  end

  test "Print loop" do
    parse_print_parse("foo(bar)")
  end

  test "Complex print loop" do
    code = """
    if (foo) then
      ([5])
    else
      ([4, [5, 4, []], [[[]]], 6])
      (baz)
    end
    """

    parse_print_parse(code)
  end

The printer is a collection of function heads to parse nodes and recurse through the tree structure :

defmodule Ovo.Printer do
  def print(%Ovo.Ast{} = ast) do
    Enum.reduce(ast.nodes, "", fn node, output ->
      output <> print_node(node) <> "\n"
    end)
  end

  def print_node(%Ovo.Ast{kind: :expr, value: val}), do: print_node(val)

  def print_node(%Ovo.Ast{kind: :call, value: val, nodes: children}) do
    "#{val.value}(#{Enum.map_join(children, ", ", &print_node/1)})"
  end

  def print_node(%Ovo.Ast{kind: :symbol, value: val}) do
    "#{val}"
  end

  def print_node(%Ovo.Ast{kind: :integer, value: val}) do
    "#{val}"
  end

  def print_node(%Ovo.Ast{kind: :lambda, value: head, nodes: body}) do
    """
      \\#{Enum.map_join(head, ", ", &print_node/1)} ->
        #{print_node(body)}
      end
    """
  end
...

For fun, and to help me go to the next step (evaluation), I also wrote a very quick Elixir printer since my language looks a lot like a watered-down Elixir syntax without everything that shines in Elixir.

defmodule Ovo.ElixirPrinter do
  def print_node(%Ovo.Ast{kind: :lambda, value: head, nodes: body}) do
    """
      fn (#{Enum.map_join(head, ", ", &print_node/1)}) ->
        #{print_node(body)}
      end
    """
  end
end

This will allow me to have interpretation of Ovo via “compiling to Elixir”, via interpretation from Elixir, and maybe via a third way.. we’ll see later ;^)

  def run_as_elixir(input, bindings \\ []) do
    tokens = Ovo.Tokenizer.tokenize(input)
    {:ok, ast, _} = Ovo.Parser.parse(tokens)
    code = Ovo.ElixirPrinter.print(ast)
    Code.eval_string(code, bindings)
  end

  def demo() do
    {res, _bindings} =
      run_as_elixir(
        """
          if (foo) then
            ([5])
          else
            ([4, [5, 4, []], [[[]]], 6])
          end
        """,
        foo: false
      )

    res
  end