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"