Re: Lua code generation vs. goto

[David Given <dg@...>]

On Fri, 2008-07-25 at 13:54 -0400, Norman Ramsey wrote:
> > Is there some trick that would allow me to emulate unconditional jumps
>  > in plain Lua (even if it kind of hard to implement)?
> 
> The standard trick in functional languages is to make every label a
> function and every goto a tail call.  If you make the functions nested
> local functions you will find this very efficient in Lua.

I've actually been thinking of something similar for Clue, as the
current patching-the-bytecode approach to GOTO is pretty nasty.

The problem is, I have lots of shared state between the labels --- in
essence:

function somefunc()
  local H1, H2, H3 ... H50
 label0:
  H1 = H2 + 1
  goto label2
 label1:
  H2 = H3 + 1
  goto label0
 label2:
  return
end

So, in order to do this using tail calls, I'd need:

function somefunc()
  local H1, H2, H3 ... H50
  local label0, label1, label2
  label0 = function()
    H1 = H2 + 1
    return label2()
  end
  label1 = function()
    H2 = H3 + 1
    return label0()
  end
  label2 = function()
    return
  end
  return label0()
end

This means that every time somefunc() is called, I need to construct a
bunch of closures --- which is going to cause memory churn. The current
approach does no memory allocation on function call except for C stack
extension, which amortises to zero.

The other approach is something like:

function somefunc()
  local H1, H2, H3 ... H50
  local state = 0
  while true do
    if state == 0 then
      H1 = H2 + 1
      state = 2
    elseif state == 1 then
      H2 = H3 + 1
      state = 0
    elseif state == 2 then
      return
    end
  end
end

(This is actually what I have to do with the Javascript backend,
although at least I can use a switch for that.) This is pretty grotesque
--- but it still doesn't require memory allocation on function calls.

Any opinions as to which approach is the least bad? Eventually I'd like
to transform the code to optimise away GOTOs when possible, as Mike Pall
suggested earlier, but that's not going to be a universal solution; I
still need to make this work somehow...
  
-- 
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
│ 
│ "Quantum materiae materietur marmota monax si marmota monax meteriam
│ possit materiari?" --- Henry Beard

Attachment: signature.asc
Description: This is a digitally signed message part