anf.ex

defmodule Anf do
@moduledoc 
"""
Author: Christophe De Troyer
"""
  require Logger

  ##############################################################################
  #                                  API                                       #
  ##############################################################################

  def normalize_term(m) do
    Logger.debug("normalize_term(#{inspect(m)})")
    normalize(m, fn x -> x end)
  end

  def normalize_program(p) do
    Logger.debug("Normalizing: #{inspect(p)}")

    case p do
      [] ->
        []

      [v] ->
        normalize_term(v)

      [t | ts] ->
        t_ = normalize_term(t)
        ts_ = normalize_terms(ts, fn x -> x end)
        [t_ | ts_]
    end
  end

  ##############################################################################
  #                                  Sequence                                  #
  ##############################################################################

  def normalize_term_(m, k) do
    Logger.debug("normalize_term_(#{inspect(m)}) #{inspect(k)}")
    k.(normalize_term(m))
  end

  def normalize_terms([], k) do
    k.([])
  end

  def normalize_terms([t | ts], k) do
    Logger.debug("Normalize terms: #{inspect([t | ts])}, #{inspect(k)}")

    normalize_term_(
      t,
      fn t_ ->
        normalize_terms(
          ts,
          fn ts_ -> k.([t_ | ts_]) end
        )
      end
    )
  end

  ##############################################################################
  #                                  Expressions                               #
  ##############################################################################

  defp normalize([:lambda, params, body], k) do
    Logger.debug("normalize(#{inspect([:lambda, params, body])}, #{inspect(k)})")
    k.([:lambda, params, normalize_term(body)])
  end

  defp normalize([:begin | exps], k) do
    normalize_terms(exps, fn terms -> k.([:begin | terms]) end)
  end

  defp normalize([:let, [] | ms], k) do
    Logger.debug("normalize(#{inspect([:let, [] | ms])}, #{inspect(k)})")
    normalize_terms(ms, fn ms_ -> k.([:let, [] | ms_]) end)
  end

  defp normalize([:let, [[var, m1]] | exps], k) do
    Logger.debug("normalize(#{inspect([:let, [[:x, m1]] | exps])}, #{inspect(k)})")
    normalize(m1, fn n1 -> [:let, [[var, n1]] | normalize_terms(exps, k)] end)
  end

  defp normalize([:letrec, [[var, m1]], m2], k) do
    Logger.debug("normalize(#{inspect([:letrec, [[:x, m1]], m2])}, #{inspect(k)})")
    normalize(m1, fn n1 -> [:letrec, [[var, n1]] | normalize(m2, k)] end)
  end

  defp normalize([:if, m1, m2, m3], k) do
    Logger.debug("normalize(#{inspect([:if, m1, m2, m3])}, #{inspect(k)})")

    normalize_name(m1, fn t ->
      k.([:if, t, normalize_term(m2), normalize_term(m3)])
    end)
  end

  defp normalize([:define, [name | pars], body], k) do
    k.([:define, name, [:lambda, pars, normalize_term(body)]])
  end

  defp normalize([:define, var, exp], k) do
    k.([:define, var, normalize_term(exp)])
  end

  defp normalize([f | ms], k) do
    Logger.debug("normalize(#{inspect([f | ms])}, #{inspect(k)})")

    normalize_name(f, fn t ->
      normalize_names(ms, fn ts ->
        k.([t | ts])
      end)
    end)
  end

  defp normalize(x, k) do
    if value?(x) do
      k.(x)
    else
      raise "Not a valid expression: #{inspect(x)}"
    end
  end

  ############################################################################
  #                           Names                                          #
  ############################################################################

  defp normalize_name(m, k) do
    Logger.debug("normalize_name(#{inspect(m)}, #{inspect(k)})")

    normalize(m, fn n ->
      if value?(n) do
        k.(n)
      else
        t = Varstore.fresh_var()
        [:let, [[t, n]], k.(t)]
      end
    end)
  end

  defp normalize_names([], k) do
    Logger.debug("normalize_names(#{inspect([])}, #{inspect(k)})")
    k.([])
  end

  defp normalize_names([m | ms], k) do
    Logger.debug("normalize_names(#{inspect([m | ms])}, #{inspect(k)})")
    normalize_name(m, fn t -> normalize_names(ms, fn ts -> k.([t | ts]) end) end)
  end

  ############################################################################
  #                           Define                                         #
  ############################################################################

  defp normalize_define(define) do
    case define do
      [:define, [name | pars], body] ->
        [:define, name, [:lambda, pars, normalize_term(body)]]

      [:define, var, exp] ->
        [:define, var, normalize_term(exp)]
    end
  end

  ##############################################################################
  #                                  Helpers                                   #
  ##############################################################################

  defp value?(x) do
    Logger.debug("value?(#{inspect(x)})")

    res =
      case x do
        n when is_number(n) ->
          true

        b when is_boolean(b) ->
          true

        s when is_binary(s) ->
          true

        o when o in [:+, :-, :*, :/, :and, :>, :<, :eq] ->
          true

        v when is_atom(v) ->
          true

        _ ->
          false
      end

    Logger.debug("=> #{res}")
    res
  end
end