lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


You may want to consider the Finite State Machine described here:
http://lua-users.org/wiki/FiniteStateMachine

Jorge gave me this example:
I implemented a kind-of asynchronous state machine too. I looked into
tail calls, but skipped on them due to asynchronous part and also
because i won't be the one defining the state machine and is easier to
explain how to do it using a explicit transition table.
I posted a question on this list a while ago, and based my solution on
code posted by Roberto (i think it was, can't find it now)


Initialize a state machine using:

local function FSM(t)
       local a = {}
       for _,v in ipairs(t) do
               local old, matches_event, new, action = "" v[2], v[3], v[4]
                       if a[old] == nil then a[old] = {} end
                       table.insert(a[old],{new = new, action = "" matches_event = matches_event})
               end
       return a
end

A sample state machine with two states and two possible transitions could be:

--{state, predicate, new state, action}
local fsm = FSM{
       {"ini", cond1,  "end",  action1 },
       {"ini", cond2,  "end",  action2 },
       {"end", nil,    nil,    nil     }
}

where cond* are functions that evaluate whether a event is met, and action* are functions to be run on transitions.


Then, to advance the machine a single step you could use (current_state should start as "ini"):

       local state=fsm[current_state]
       local a
       --search first transition that verifies event
       for _, l in ipairs(state) do
               if l.matches_event and l.matches_event(event) then
                       a=l
                       break
               end
       end
       if a.action then a.action() end
       current_state = a.new

Hope that helps,

Jorge

On Fri, Jul 25, 2008 at 6:19 PM, David Given <dg@cowlark.com> wrote:
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...

--
┌─── dg@cowlark.com ───── http://www.cowlark.com ─────

│ "Quantum materiae materietur marmota monax si marmota monax meteriam
│ possit materiari?" --- Henry Beard