Unlambda at breakneck speed
A simple parser
defmodule UnParser do
def parseThing(str) do
{c, sliced} = String.split_at(str, 1)
case c do
"k" -> {:k, sliced}
"s" -> {:s, sliced}
"i" -> {:i, sliced}
"d" -> {:d, sliced}
"c" -> {:c, sliced}
"v" -> {:v, sliced}
"r" -> {{:put, "\n"}, sliced}
"." ->
{char, sliced} = String.split_at(sliced, 1)
{{:put, char}, sliced}
"`" ->
{v, sliced} = parseThing(sliced)
{w, sliced} = parseThing(sliced)
{{:app, v, w}, sliced}
end
end
def parse!(str) do
{op, ""} = parseThing(str)
op
end
end
UnParser.parse!("``r`cd`.*`cd")
A simple evaluator
Author's note: this document is more of a lab note and is riddled with errors. I will write a more complete one as soon as I want to. You have been warned.
We represent unlambda terms as atoms. The only operator is :app
. The functions are s
, k
, i
, v
, {:dot, char}
, d
, and c
. We can also add r
g
(reset and go).
defmodule Eval1 do
# utterly broken, revisit someday
def eval({:app, t0, t1}) do
v = eval(t0)
case v do
{:d} -> {:d, t1}
{:d, t0} -> eval({:app, t0, t1})
{:i} -> eval(t1)
{:s} -> {:s, t1}
{:s, t0} -> {:s, t0, t1}
{:s, t0, t00} -> eval({:app, {:app, t0, t1}, {:app, t00, t1}})
{:k} -> {:k, eval(t1)}
{:k, t} -> t
{:v} -> {:v}
end
end
def eval(x), do: {x}
def main(str), do: eval(UnParser.parse!(str))
end
k = {:k}
i = {:i}
Eval1.main("``kik")
Yeah, it works. Note that it is almost an abstract machine now! Then CPS transform it…
defmodule Eval2 do
def eval({:app, t0, t1}, k) do
eval(t0, fn v ->
case v do
{:d} -> k.({:d, t1})
{:d, t0} -> eval({:app, t0, t1}, k)
{:i} -> eval(t1, k)
{:s} -> k.({:s, t1})
{:s, t0} -> k.({:s, t0, t1})
{:s, t0, t00} -> eval({:app, {:app, t0, t1}, {:app, t00, t1}}, k)
{:k} -> k.({:k, v})
{:k, t} -> eval(t, k)
{:v} -> k.({:v})
end
end)
end
def eval(x, k), do: k.(x)
def main(t), do: eval(t, fn x -> x end)
end
Eval2.main({:app, {:app, {:app, {:s}, {:d}}, {:app, {:k}, {:k}}}, {:i}})
Now defunctionalize the kontinuations.
defmodule Eval3 do
def eval(:i, k), do: applyK(k, {:i})
def eval(:s, k), do: applyK(k, {:s})
def eval(:k, k), do: applyK(k, {:k})
def eval(:v, k), do: applyK(k, {:v})
def eval(:d, k), do: applyK(k, {:d})
def eval(:c, k), do: applyK(k, {:c})
def eval({:put, c}, k), do: applyK(k, {:put, c})
def eval({:app, t0, t1}, k) do
eval(t0, {:bindT, t1, k})
end
def applyT(v, t, k) do
case v do
{:d} -> applyK(k, {:dt, t})
_ -> eval(t, {:bindV, v, k})
end
end
def applyV(v, w, k) do
case v do
{:i} -> applyK(k, w)
{:put, c} ->
IO.write(c)
applyK(k, w)
{:k} -> applyK(k, {:k, w})
{:k, w} -> applyK(k, w)
{:v} -> applyK(k, {:v})
{:c} -> applyV(w, {:c, k}, k)
{:c, k1} -> applyK(k1, w)
{:d} -> applyK(k, {:dv, w})
{:dt, t0} -> eval(t0, {:bindW, w, k})
{:dv, v0} -> applyV(v0, w, k)
{:s} -> applyK(k, {:s, w})
{:s, v0} -> applyK(k, {:s, v0, w})
{:s, v0, v1} -> applyV(v0, w, {:sWait, v1, w, k})
end
end
def applyK(:return, v), do: v
def applyK({:bindT, t, k}, v), do: applyT(v, t, k)
def applyK({:bindV, v, k}, w), do: applyV(v, w, k)
def applyK({:bindW, w, k}, v), do: applyV(v, w, k)
def applyK({:sWait, v1, w, k}, v), do: applyV(v1, w, {:bindV, v, k})
def main(str), do: eval(UnParser.parse!(str), :return)
end
Eval3.main("````sd`ckr`c.*")
And we’ve arrived at an abstract machine! But to make this a virtual machine, we need to do more work.
(an abstract machine operates on a syntax tree, while a virtual machine operates on a flat list.)
First curry it. After currying, the eval function returns a function that accepts a kontinution.
Then make it compositional.
Compositional means that each evaluated term must come from the arguments, not from a stored argument.
defmodule Eval4 do
def combine(f, g) do
fn x -> f.(g.(x)) end
end
def eval(:i), do: applyK({:i})
def eval(:s), do: applyK({:s})
def eval(:k), do: applyK({:k})
def eval(:v), do: applyK({:v})
def eval(:d), do: applyK({:d})
def eval(:c), do: applyK({:c})
def eval({:put, c}), do: applyK({:put, c})
def eval({:app, t0, t1}) do
combine(eval(t0), fn k -> {:bindT, t1, k} end)
end
def applyT(v, t, k) do
# switch uses v and k
switch = fn w ->
case v do
{:d} -> applyK({:dt, {:recur, w}}).(k)
_ -> w.({:bindV, v, k})
end
end
switch.(eval(t)) # not a combine but acceptable
end
# wait a minuite, v is the one to be curried!
def applyV(v, w, k) do
# we wrap everything not v, w and k into a Recur
case v do
{:i} -> applyK(w).(k)
{:put, c} ->
IO.write(c)
applyK(w).(k)
{:k} -> applyK({:k, w}).(k)
{:k, w} -> applyK(w).(k)
{:v} -> applyK({:v}).(k)
{:c} -> applyV(w, {:c, {:recur, fn t -> t.(k) end}}, k)
{:c, {:recur, k1fn}} -> k1fn.(applyK(w)) # applyK(w).(k1)
{:d} -> applyK({:dv, {:recur, fn (w0, k) -> applyV(w, w0, k) end}}).(k)
{:dv, {:recur, v0fn}} -> v0fn.(w, k) # applyV(v0, w, k)
{:dt, {:recur, t0fn}} -> t0fn.({:bindW, w, k}) # eval(t).({:bindW, w, k})
{:s} -> applyK({:s, {
:recur,
fn (w0, k0) ->
applyK({:s, {:recur, fn (w1, k1) -> applyV(w, w1, {:s2, w0, w1, k1}) end}}).(k0)
end
}}).(k)
# all s actions are stuffed here
# applyK({:s, v0, w}).(k)
# applyV(v0, w, {:s2, v1, w, k})
{:s, {:recur, v0fn}} -> v0fn.(w, k)
end
end
def applyK(v), do: fn k -> applyK1(k, v) end
def applyK1(:return, v), do: v
# the only function that applys a term
# this can be easily inlined, so
def applyK1({:bindT, t, k}, v), do: applyT(v, t, k)
# the rest applys values
def applyK1({:bindV, v, k}, w), do: applyV(v, w, k)
def applyK1({:bindW, w, k}, v), do: applyV(v, w, k)
def applyK1({:s2, v1, w, k}, v), do: applyV(v1, w, {:s1, v, k})
def applyK1({:s1, v, k}, w), do: applyV(v, w, k)
def main(str), do: eval(UnParser.parse!(str)).(:return)
end
Eval4.main("````sd`ckr`c.*")
defmodule Eval4a do
def combine(f, g) do
fn x -> f.(g.(x)) end
end
def eval(:i), do: applyK({:i})
def eval(:s), do: applyK({:s})
def eval(:k), do: applyK({:k})
def eval(:v), do: applyK({:v})
def eval(:d), do: applyK({:d})
def eval(:c), do: applyK({:c})
def eval({:put, c}), do: applyK({:put, c})
def eval({:app, t0, t1}) do
# push t1
combine(eval(t0), fn k -> {:bindT, t1, k} end)
end
def applyT(v, t, k) do
# switch uses v and k
switch = fn w ->
case v do
{:d} -> applyK({:dt, {:recur, w}}).(k)
_ -> w.({:bindV, v, k})
end
end
switch.(eval(t)) # not a combine but acceptable
end
# wait a minuite, v is the one to be curried!
def applyV(v, w, k) do
# should be something like combine(eval(v), push(eval(w)))
# but v and w are already evaluated! v from the eval, and w from applyT.
# however, we can be certain this function only applys a finite number of times.
# after this, the baton is passed to applyK.
case v do
{:i} -> applyK(w).(k)
{:put, c} ->
IO.write(c)
applyK(w).(k)
{:k} -> applyK({:k, w}).(k)
{:k, w} -> applyK(w).(k)
{:v} -> applyK({:v}).(k)
{:c} -> applyV(w, {:c, {:recur, fn t -> t.(k) end}}, k)
{:c, {:recur, k1fn}} -> k1fn.(applyK(w)) # applyK(w).(k1)
{:d} -> applyK({:dv, {:recur, fn (w0, k) -> applyV(w, w0, k) end}}).(k)
{:dv, {:recur, v0fn}} -> v0fn.(w, k) # applyV(v0, w, k)
{:dt, {:recur, t0fn}} -> t0fn.({:bindW, w, k}) # eval(t).({:bindW, w, k})
{:s} -> applyK({:s, {
:recur,
fn (w0, k0) ->
applyK({:s, {:recur, fn (w1, k1) -> applyV(w, w1, {:sWait, w0, w1, k1}) end}}).(k0)
end
}}).(k)
# all s actions are stuffed here
# applyK({:s, v0, w}).(k)
# applyV(v0, w, {:s2, v1, w, k})
{:s, {:recur, v0fn}} -> v0fn.(w, k)
end
end
def applyK(v), do: fn k -> applyK1(k, v) end
def applyK1(:return, v), do: v
# the only function that applys a term
# this can be easily inlined, so
def applyK1({:bindT, t, k}, v), do: applyT(v, t, k)
# the rest applys values
def applyK1({:bindV, v, k}, w), do: applyV(v, w, k)
def applyK1({:bindW, w, k}, v), do: applyV(v, w, k)
def applyK1({:sWait, v1, w, k}, v), do: applyV(v1, w, {:bindV, v, k})
def main(str), do: eval(UnParser.parse!(str)).(:return)
end
Eval4a.main("``cc.*")
defmodule Eval4b do
def combine(f, g) do
fn x -> f.(g.(x)) end
end
def eval(:i), do: applyK({:i})
def eval(:s), do: applyK({:s})
def eval(:k), do: applyK({:k})
def eval(:v), do: applyK({:v})
def eval(:d), do: applyK({:d})
def eval(:c), do: applyK({:c})
def eval({:put, c}), do: applyK({:put, c})
def eval({:app, t0, t1}) do
combine(eval(t0), push(eval(t1)))
end
def push(r1) do
fn k -> {:bindT, r1, k} end
end
def switch(v, k) do
fn w ->
case v do
{:d} -> applyK({:dt, {:recur, w}}).(k)
_ -> w.({:bindV, v, k})
end
end
end
def applyV(v, w, k) do
case v do
{:i} -> applyK(w).(k)
{:put, c} ->
IO.write(c)
applyK(w).(k)
{:k} -> applyK({:k, w}).(k)
{:k, w} -> applyK(w).(k)
{:v} -> applyK({:v}).(k)
{:c} -> applyV(w, {:c, k}, k)
{:c, k1} -> applyK(w).(k1)
{:d} -> applyK({:dv, w}).(k)
{:dt, {:recur, t0fn}} -> t0fn.({:bindW, w, k})
{:dv, v0} -> applyV(v0, w, k)
{:s} -> applyK({:s, w}).(k)
{:s, v0} -> applyK({:s, v0, w}).(k)
{:s, v0, v1} -> applyV(v0, w, {:sWait, v1, w, k})
end
end
def applyK(v), do: fn k -> applyK1(k, v) end
def applyK1(:return, v), do: v
# the only function that applys a term
# this can be easily inlined, so
def applyK1({:bindT, r, k}, v), do: switch(v, k).(r)
# the rest applys values
def applyK1({:bindV, v, k}, w), do: applyV(v, w, k)
def applyK1({:bindW, w, k}, v), do: applyV(v, w, k)
def applyK1({:sWait, v1, w, k}, v), do: applyV(v1, w, {:bindV, v, k})
def main(str), do: eval(UnParser.parse!(str)).(:return)
end
Eval4b.main("````sc`ckr`c.*")
After this, we can extract all functions from eval into an Ops module
defmodule Compile5 do
def combine(f, g) do
Enum.concat(g, f)
end
def eval(:i), do: applyK({:i})
def eval(:s), do: applyK({:s})
def eval(:k), do: applyK({:k})
def eval(:v), do: applyK({:v})
def eval(:d), do: applyK({:d})
def eval(:c), do: applyK({:c})
def eval({:put, c}), do: applyK({:put, c})
def eval({:app, t0, t1}) do
# push t1
push = [{:push, eval(t1)}]
combine(eval(t0), push)
end
def applyK(v), do: [{:pass, v}]
def main(str), do: eval(UnParser.parse!(str))
end
defmodule Eval5 do
def eval([{:pass, v} | ins], k) do
case ins do
[] -> applyK(k, v)
_ -> IO.inspect(ins)
end
end
def eval([{:push, i} | ins], k) do
k = push(i).(k)
eval(ins, k)
end
def push(i1) do
fn k -> {:bindT, fn k -> eval(i1, k) end, k} end
end
def switch(v, k) do
fn w ->
case v do
{:d} -> applyK(k, {:dt, {:recur, w}})
_ -> w.({:bindV, v, k})
end
end
end
def applyV(v, w, k) do
case v do
{:i} -> applyK(k, w)
{:put, c} ->
IO.write(c)
applyK(k, w)
{:k} -> applyK(k, {:k, w})
{:k, w} -> applyK(k, w)
{:v} -> applyK(k, {:v})
{:c} -> applyV(w, {:c, k}, k)
{:c, k1} -> applyK(k1, w)
{:d} -> applyK(k, {:dv, w})
{:dt, {:recur, t0fn}} -> t0fn.({:bindW, w, k})
{:dv, v0} -> applyV(v0, w, k)
{:s} -> applyK(k, {:s, w})
{:s, v0} -> applyK(k, {:s, v0, w})
{:s, v0, v1} -> applyV(v0, w, {:sWait, v1, w, k})
end
end
def applyK(:return, v), do: v
# the only function that applys a term
# this can be easily inlined, so
def applyK({:bindT, r, k}, v), do: switch(v, k).(r)
# the rest applys values
def applyK({:bindV, v, k}, w), do: applyV(v, w, k)
def applyK({:bindW, w, k}, v), do: applyV(v, w, k)
def applyK({:sWait, v1, w, k}, v), do: applyV(v1, w, {:bindV, v, k})
def main(ins), do: eval(ins, :return)
end
compiled = Compile5.main("````sd`ckr`c.*")
IO.inspect(compiled)
# Eval5.main(compiled)
defmodule Compile6 do
def combine(f, g) do
Enum.concat(g, f)
end
def eval(:i), do: applyK({:i})
def eval(:s), do: applyK({:s})
def eval(:k), do: applyK({:k})
def eval(:v), do: applyK({:v})
def eval(:d), do: applyK({:d})
def eval(:c), do: applyK({:c})
def eval({:put, c}), do: applyK({:put, c})
def eval({:app, t0, t1}) do
# push t1
push = combine(eval(t1), [:push])
combine(eval(t0), push)
end
def applyK(v), do: [v]
def main(str), do: eval(UnParser.parse!(str))
end
compiled = Compile6.main("````sd`ckr`c.*")
IO.inspect(compiled)
defmodule Abstract do
def elim("", _), do: ""
def elim(str, name) do
{c, rest} = String.split_at(str, 1)
head = case c do
"`" -> "``s"
^name -> "i"
str -> "`k#{str}"
end
head <> elim(rest, name)
end
def lam(name, body), do: elim(body, name)
end
Abstract.lam("x", Abstract.lam("y", "`yx"))
one = "i"
inc = "`s``s`ksk"
add = "``si`k`s``s`ksk"
mul = "``s`ksk"
pow = "i"
two = "`#{inc}#{one}"
three = "`#{inc}#{two}"
four = "`#{inc}#{three}"
IO.puts "````#{pow}#{three}``#{pow}#{four}#{four}ii"