lua-users home
lua-l archive

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

I created a Turing object in C++ (with a Ragel parser) that implements state machines for a show a while ago. It's a very powerful tool to deal with conditionals/default values and states. The syntax is

[when in state X] [receiving token Y]:[do action A] -> [and goto state Z]

Here's an example (# = comments and "." means "any state"):

# heart beats (marie)
# default state change on "100" token = goto state "m1"
. 100          -> m1
# default action in state "m1" = toggleh()
m1 :toggleh()  -> m1

# C minor
# Claire
. 200         -> m2
m2 2:play(36) -> m2
m2 5:play(31) -> m2
m2 6:play(38) -> m22
m2 1:play(37) -> m2  #-- security: goto start
You could use graphviz to debug the graphs or just print the transition tables (see [1]).

This object used a Ragel based parser to parse the code and fill the lookup tables. During execution, most of the job was done in C++, with callbacks in Lua for code execution. Since I'll have to rewrite this object for Lubyk, I will probably work the other way around: parse with Ragel but use Lua for all the processing, storage and housekeeping. The construct proposed by Michael could be used directly instead of the function calls and lookup tables:

I tried to map the C minor example to Michael's proposition:

jump state do
  'm2' do
    jump token do
      2 do play(36) break end
      5 do play(31) break end
      6 do play(38); state = 'm22' break end
      1 do play(37) break end
    # Default actions
    jump token do
      200 do state = 'm2' end

I don't like the need for the "break" everywhere (I hate it in C switch) and since the common idiom is to "break" why not remove it and use "continue" when we need to continue evaluating rules ? I also do not understand the need for the 'val = xxx in "yyy"' construct. Why not simply use "jump fmt:byte(i) do" ?



On Sat, May 14, 2011 at 5:26 PM, Michael Rose <> wrote:

I've read many of the discussions about 'switch' statements, the 'continue' statement and 'computed goto' in the mailing list as well as in the wiki.
I have programmed my own 'continue' statement for Lua 5.2-alpha just to
get a feeling for the parser though there is a patch for an earlier version of Lua available in the WIKI. I won't propose my implementation here (though its fully functional), because I think its a matter of taste if this construct is really necessary in the language or just
some avoidable blow up. I think I would appreciate general gotos and labels in the language as well as line number annotations just for the purpose to be able to build something like Metalua which outputs direct Lua code instead of using its own bytecode-emitter with all the maintainance issues and compatibility problems (Metalua doesn't work with Luajit), but I understand, that Luajit has effiency rationales against such a general goto-construct. I agree that new language constructs must be carefully selected.

But still there is one kind of construct, which I find quite usefull and therefore I just want to ask the community and especially the core Lua team, whether this construct might be valuable or not for a later Lua release. I call it jumptable and it has something in common with
a computed goto (without labels) as well as of a switch statement (reduced basically to integers). My point of view is that a switch statement would be pointless (just syntactic sugar) if it is internally mapped to an if-elseif chain. But often there is a need for state machines or code selection based on integers or string characters (-> string.format) which leads to very compact data coding. I know that jumps on e.g. integers can be realized by
function tables in O(1) time, but for inner loops and especially when it seems to be natural to deal with common local variables in the different
"jump targets", functions have some overhead and are also a bit clumpsy.
I attached a readme file about my rationale as .txt file and also a zipped patch for Lua 5.2-alpha, which demonstrates this new language construct with some (admittedly) silly examples just to give some ideas.
Note that this patch seems to work without restrictions but is only roughly testet by me. It serves just to explain the idea.

Discussion welcome ...


Michael Rose

Here is some code snipped, which demonstrates the basics:

-- File: tst_format.lua
-- One example for jump tables in format issues.

local format = "We have  %d%% off for %s in %s!\n"
local args   = {10,"butter","our nice grocery"}

function my_format(p,fmt,...)
  local args = {...}
  local start,i,n,argi = 1,1,#fmt,0
  while i < n do
     if fmt:sub(i,i) == "%" then
        if start < i then p(fmt:sub(start,i-1)) end
        start = i + 2
        i     = i + 1
        jump val = fmt:byte(i) in "sSdDcC" do
           "dD" do args[argi+1] = tostring(args[argi+1]) end
           "sS" do argi = argi+1; p(args[argi]) break end
           "cC" do argi = argi+1; p(args[argi]:sub(1,1)) break end
           -- add other values...
           do p(string.char(val)) end  -- default target
     i = i + 1
  if start <= i then p(fmt:sub(start,i)) end

my_format(io.write, format, table.unpack(args))

-- End of File: tst_format.lua