Reification call stack by coroutine

From the article Philosophy of coroutines, the author mentions a 'stunf' of coroutines:

Another slightly unexpected ‘stunt’ use of coroutines is to use them to reconstruct the call-stack structure of ordinary subroutines: replace every normal function call with a coroutine-style yield operation which makes a newly constructed instance of the subroutine start running next, and whenever a coroutine terminates, resume the one that invoked it.

This reminds me Daniel Friedman's The Role of the Study of Programming Languages in the Education of a Programmer". The code below is also a correctness-preserved transformation.

Here is my try in Lua, in which coroutine is first-class value.

We want to transfer some recursive function to the form with explicit call stack structure. Here is an example of counting element of array in recursive style:

local function length_rec(t)
  if t == nil or #t == 0 then
    return 0
  end

  return 1 + length_rec({table.unpack(t, 2)})
end

And re-write it with coroutine will be:

local function length(t)
  if t == nil or #t == 0 then
    coroutine.yield("ret", 0)
  else
    local l = coroutine.yield("call", {table.unpack(t, 2)})
    coroutine.yield("ret", l + 1)
  end
end

And we need to create infrastructure to run this coroutine style function. Here is one possible implementation:

local function run(f, arg)
  local init_co = coroutine.create(f)
  local stacks = {{init_co, "init", arg}}

  while #stacks ~= 0 do
    local frame = stacks[#stacks]
    local co  = frame[1]
    local frame_type = frame[2]
    local frame_val = frame[3]

    if frame_type == "ret" then
      table.remove(stacks)

      if #stacks == 0 then
        return frame_val
      else
        co = stacks[#stacks][1]
      end
    elseif frame_type == "call" then
      co = coroutine.create(f)
      -- else frame_type == "init" then
      --  just use the current frame.
    end
    local _, new_frame_type, new_frame_val = coroutine.resume(co, frame_val)
    if frame_type == "ret" or frame_type == "init" then
      stacks[#stacks][2] = new_frame_type
      stacks[#stacks][3] = new_frame_val
    else
      table.insert(stacks, {co, new_frame_type, new_frame_val})
    end
  end
end

And run it:

print(run(length, {1, 2, 3, 4}))
-- print 4

Then here is another a little bit more complex example:

  local function tree_sum(t)
  if t == nil then
    coroutine.yield("ret", 0)
  else
    local l = coroutine.yield("call", t['left'])
    local r = coroutine.yield("call", t['right'])
    coroutine.yield("ret", l + r + t['v'])
  end
end

Run it:

print(executor(tree_sum, {v=1, left={v=2, left={v=4}}, right={v=3, right={v=5}}}))
-- print 15

Application of the tranformation

The following case will run into "stack overflow" error.

local function sum_rec(n)
  if n == 0 then
    return 0
  else
    local s = sum_rec(n - 1)
    return s + n
  end
end

print(sum_rec(1000000))

But with this transformation and re-written, it can produce result correctly:

local function sum(n)
  if n == 0 then
    coroutine.yield("ret", 0)
  else
    local s = coroutine.yield("call", n - 1)
    coroutine.yield("ret", s + n)
  end
end

print(executor(sum, 1000000))
-- print 500000500000