A simple expression parser & evaluator (playing with Elixir meta-programming)

Expr.ex

defmodule Expr do
  @moduledoc """
  A simple expression parser & evaluator.

  To use it, call run/1:

    iex> Expr.run "1*2*3*4*5+1000"
    1120 

  It also supports let bindings:

    iex> Expr.run "let x = 10 in x * x"
    100

  The source code is transformed into an Elixir syntax tree with
  Code.string_to_quoted, we then remove the metadata that Elixir
  includes with remove_meta/1 and translate the Elixir syntax tree
  into our mini-language with to_expr.

  The evaluator runs the expression in an environment where
  let bindings are kept.
  """

  def eval({:num, n}, _env) when is_number(n) do
    n
  end

  def eval({:+, a, b}, env) do
    eval(a, env) + eval(b, env)
  end

  def eval({:*, a, b}, env) do
    eval(a, env) * eval(b, env)
  end

  def eval({:var, var}, env) do
    case Keyword.fetch(env, var) do
      {:ok, value} -> value
      _ -> raise "Variable not bound #{var}"
    end
  end

  def eval({:let, name, value, body}, env) do
    eval(body, extend(name, eval(value, env), env))
  end

  def eval({:app, fun, arg}, env) do
    fun_ = eval(fun, env)
    arg = eval(arg, env)
    case fun_ do
      {:fun, {:var, name}, body} ->
        eval(body, extend(name, arg, env))
      _ -> raise "Applying non-function"
    end
  end

  def eval({:fun, arg, body} = ast, env) do
    ast
  end

  def extend(name, value, env) do
    Keyword.put(env, name, value)
  end

  def remove_meta({op, _, args} = ast) when is_list(args) do
    args = Enum.map(args, &remove_meta/1)
    List.to_tuple([op | args])
  end

  def remove_meta({op, _, _}), do: op
  def remove_meta(op), do: op

  def to_expr({:let, {:=, var, {:in, value, body}}}) do
    {:let, var, to_expr(value), to_expr(body)}
  end

  def to_expr(num) when is_number(num), do: {:num, num}

  def to_expr({:*, a, b}) do
    {:*, to_expr(a), to_expr(b)}
  end

  def to_expr({:+, a, b}) do
    {:+, to_expr(a), to_expr(b)}
  end

  def to_expr({:fun, {arg, {:to, body}}}) do
    {:fun, to_expr(arg), to_expr(body)}
  end

  def to_expr(var) when is_atom(var), do: {:var, var}

  def to_expr({f, x}) do
    {:app, to_expr(f), to_expr(x)}
  end

  def example() do
    run "let double = (fun x to x + x) in
         double 4"
  end

  def run(source) do
    source |> Code.string_to_quoted!() |> remove_meta |> to_expr |> eval([])
  end

  def program do
    quote do
      let f = (fun x to x+x) in
      f 4
    end
  end
end