Skip to content

Instantly share code, notes, and snippets.

@m1dnight
Last active March 14, 2021 20:57
Show Gist options
  • Save m1dnight/053494cdc35b89af6fe0b3b63283abd0 to your computer and use it in GitHub Desktop.
Save m1dnight/053494cdc35b89af6fe0b3b63283abd0 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment