SWIG and Lua

So I've been trying out SWIG with Lua recently. This was to wrap a 3rd party C library that I didn't have source for.

The initial wrapping went pretty smoothly. The only problem was that the library had its own typedef of 'bool' as an unsigned char, but SWIG treated that as a syntax error. I had hoped to avoid making copies of the header files, but ended up doing that and so commented out the typedef.

I was also a bit disappointed with the handling of some pointer types. Suppose you've got a function that takes a pointer to a double. I had expected that I could just call the wrapped Lua function with a Lua number and have that handled automatically. But I ended up declaring some pointer types, creating those C-based objects, and using those. There is some means with SWIG to declare pointer args, but I need to read that section of the docs again.

Similarly, I wanted to just pass in a table of strings and have that automatically converted to 'char **', but that is not automatic either. So that code on the Lua side is klunky too. I'm not sure that can be fixed.

I'll have to investigate luabind and toLua more.

List Library for Lua

I've updated my List Library for Lua which is inspired by Haskell's Data.List library.

I've had some interesting discussions about possibly specifying the arity of the list functions like for map() and filter(). Other implementations of these list functions take only one list, and any extra arguments are passed to the function called by map().

This lead to me trying an implementation where the 2nd argument to map() was the arity of the function passed in, call it N. The next N arguments are lists to be iterated over, and any arguments beyond that are passed as-is to the function. A quick example can easily illustrate:

function div(x, y) return x / y end

map(div, 2, {99, 21, 6}, {11, 7, 3}) -> {9, 3, 2}

map(div, 1, {99, 21, 6}, 3) -> {33, 7, 2}

Finally though I decided (at least for my own library) that explicitly specifying the arity was too cumbersome. If you need to a more sophisticated used is needed, some kind of wrapper for currying will be needed. Here's the 2nd use of map() above:

map(function(x) return div(x, 3) end, {99, 21, 6}) -> {33, 7, 2}

Obviously this is a little clunky. If you're using MetaLua lambda construct (or the power patch), this is considerably shortened:

map(|x| div(x, 3), {99, 21, 6}) -> {33, 7, 2}

I would really like the lambda construct accepted into mainline Lua.

Fortunately, I had another copy on my phone...

This is just an amusing anecdote.

I was trying to download and install Reuben Thomas' stdlib. However, I'd been having problems actually downloading the file from LuaForge.

However, since I had set up the same Lua development environment on my Android phone, and I had previously installed stdlib release 12 on that, I was able to just scp over the tar archive to my laptop.

I'm still trying to remember how we all got by the the dark ages before we had the Internet. And phones that have gigabytes of storage. Seriously, what did I do before wireless LAN was widely available?

Resource Cleanup in Lua

I recently got the Lua Programming Gems book, in part because I was interested in John Belmonte's chapter on Exceptions.

Here's the scope function that John created for the GEM article. Please refer to that article for further explanation of the rationale.

I've made some minor modifications to it to use the coxpcall function from Kepler.

function scope(f)
    local function run(list, err)
        for _, f in ipairs(list) do f(err) end
    end
    local function append(list, item)
        list[#list+1] = item
    end
    local success_funcs, failure_funcs, exit_funcs = {}, {}, {}
    local manager = {
        on_success = function(f) append(success_funcs, f) end,
        on_failure = function(f) append(failure_funcs, f) end,
        on_exit =    function(f) append(exit_funcs,    f) end,
    }
    local old_fenv = getfenv(f)
    setmetatable(manager, {__index = old_fenv})
    setfenv(f, manager)
    local status, err = copcall(f)
    setfenv(f, old_fenv)
    -- NOTE: behavior undefined if a hook function raises an error
    run(status and success_funcs or failure_funcs, err)
    run(exit_funcs, err)
    if not status then error(err, 2) end
end

David Manura wrote a couple test scripts for his Resource Acquisition Is Initialization proposal. Here they are modified for John's scope() function.

This is a basic test:

-- Define some resource type for testing.
-- In practice, this is a resource we acquire and
-- release (e.g. a file, database handle, Win32 handle, etc.).
local Resource = {}; do
  Resource.__index = Resource
  function Resource:__tostring() return self.name end
  function Resource.open(name)
    local self = setmetatable({name=name}, Resource)
    print("open", name)
    return self
  end
  function Resource:close() print("close", self.name) end
  function Resource:foo()   print("hello foo", self.name) end
end

local test3 = function()
    scope(function()
        local f = Resource.open('D')
        on_exit(function() f:close() end)
        f:foo()
        print("inside test3\n")
        error("oops")
    end)
end

local test2 = function()
    scope(function()
        on_failure(function(e) print("leaving test2 ", e) end)
        local f = Resource.open('C')
        on_exit(function() f:close() end)
        test3()
    end)
end

local test1 = function()
    local retval
    scope(function()
        local g1 = Resource.open('A')
        on_exit(function() g1:close() end)
        local g2 = Resource.open('B')
        on_exit(function() g2:close() end)
        print(copcall(test2))
        retval = 55
    end)
    return retval
end

print ("test1 = ", test1())

And here's a more complex example using coroutines and a little argument-passing:

-- Define some resource type for testing.
-- In practice, this is a resource we acquire and
-- release (e.g. a file, database handle, Win32 handle, etc.).
local Resource = {}; do
  Resource.__index = Resource
  function Resource:__tostring() return self.name end
  function Resource.open(name)
    local self = setmetatable({name=name}, Resource)
    print("open", name)
    return self
  end
  function Resource:close() print("close", self.name) end
  function Resource:foo()   print("hello foo", self.name) end
end     
        
local test3 = function(n)
    scope(function()
        local f = Resource.open('D' .. n)
        on_exit(function() f:close() end)
        coroutine.yield()
        f:foo()
        print("inside test3\n")
        coroutine.yield()
        error("oops happened in test3")
        print("this should not print\n")
    end)
end

local test2 = function(n)
    scope(function()
        on_failure(function(e)
            print(coroutine.running(),
                  "test2 failure ", e) end)
        local f = Resource.open('C' .. n)
        on_exit(function() f:close() end)
        test3(n)
    end)
end

local test1 = function(n)
    local retval
    scope(function()
        local g1 = Resource.open('A' .. n)
        on_exit(function() g1:close() end)
        coroutine.yield()
        local g2 = Resource.open('B' .. n)
        on_exit(function() g2:close() end)
        coroutine.yield()
        print(coroutine.running(), "test2 = ", copcall(test2, n))
        coroutine.yield()
        retval = n * 100
    end)
    return retval
end

local cos = {coroutine.create(test1), coroutine.create(test1)}
local retval, x
while true do
    local is_done = true
    for n=1,#cos do
        if coroutine.status(cos[n]) ~= "dead" then
            retval, x = coroutine.resume(cos[n], n)
            if retval and x then
                print("test1 =", x)
            end
            is_done = false
        end
    end
    if is_done then break end
end

So nesting the scope() call inside your regular function is a little clunky, but it's really not too bad. Lua's lexical scoping makes arguments to functions like test1() work they way you'd expect.

I hope the Lua developers decide accept a syntax extension to make this nicer. However, I can definitely live with it the way it is now.

I think some kind of scope management is necessary for reliable resource cleanup. The potential for bugs is too great otherwise.

Since all the above code is pure Lua (including coxpcall), there's no reason not to use it for your next project!

Curses Library for Lua

I've made a new release of Tiago Dionizio's Lua curses library. The original download link is broken, so this is version 0.2. The initial release was from 2004, and there doesn't seem to have been any updates since then. I've just made some minor updates so that it works with Lua 5.1. It has not be heavily tested yet, but some of the demos work.

The fairly extensive documentation by Tiago is included in the archive file, though you should also refer to the standard curses documentation. I haven't tried it yet on Windows, but have on several version of Ubuntu Jaunty (32-bit x86, 64-bit x86, 32-bit ARM).

I just found this out, that LuCI also includes a copy of lcurses. I'll need to investigate what changes they might have made.

Edit: included original link, and info on LuCI.

Lua, Javascript, and the Object Capability Model

I had mentioned Lua to Mark S. Miller in a private email message, and he asked me how similar it was to Javascript. I thought I'd turn the reply into a blog post along with a short discussion of the Object-Capability Model as it relates to Lua.

Let's run off a quick comparison with Javascript first. Similarities in both: imperative, dynamic typing, run-time eval, first class functions, inner functions, closures, variadic functions, exceptions and exception handling.

Differences. Well, first off, Lua isn't an object-oriented language. However, you can implement OO programming with tables and meta-tables in Lua, so that is similar to Javascript's associative arrays which are used to implement objects. Notably though, it is possible to implement single-inheritance, multiple inheritance, and information hiding.

Of great concern to the obj-cap community is how well you can lock down the programming language. Meaning that a particular piece of code only has access to the information and procedures that it really needs to do its job, and nothing further. This is related to the Principal of Least Authority.

I think this is an area where Lua really shines. It is easy enough to execute a function in a restricted environment. So you can just take all the "dangerous" modules out of the function's global environment, and leave nothing, or put in place safe versions of things like 'print()'. Everything you use, from importing libraries to IO to C interfaces are accessed via functions in the global environment.

Restricting execution time is also possible. For some game AI, I am exploring the use of the Lua Debug Interface. So you can set a limit on the number of bytecodes a Lua routine uses. There is some question as to whether this works properly with continuations. But even if it doesn't right now, it should be possible to fix that. I don't know if there are any explicit hooks to control the memory allocation at the level of functions, though you can restrict the amount of memory used at the thread level.

So I haven't done a full analysis, but there does seem to be the potential to use Lua for object-capability security without any changes to the core language. It all depends on how you initialize it.

Edit: Some discussion of all this is going on over on the cap-talk mailing list.

Edit 2: There seems to be some consensus that the o-cap model will probably work in Lua, with appropriate taming of the standard library. I think it is pretty neat that the core language seems to provide all we need to implement o-cap security without any drastic changes.

n-ary zip() and friends in Lua

I've been implementing more list functions in Lua. Source code here has more comments embedded.

The core of three of them (zip, map, filter) is zip_with_helper():

function zip_with_helper(func, result_helper, ...)
     local results_l= {}
     local args = {...}     -- a table of the argument lists
     local args_pos = 1     -- position on each of the individual argument lists
     local have_args = true

     while have_args do
        local arg_list = {}
        for i = 1, #args do
            local a = nil
            a = args[i][args_pos]
            if a then
                arg_list[i] = a
            else
                have_args = false
                break
            end
        end
        if have_args then
            result_helper(func, arg_list, results_l)
        end
        args_pos = args_pos + 1
    end

     return results_l
end

function zip_helper(func, arg_list, results_l)
    table.insert(results_l, arg_list)
end

function zip(...)
    return zip_with_helper(nil, zip_helper, ...)
end

On the one hand, it is kind of distressing to see how many lines of code it takes to implement it in Lua compared to Haskell. However, these implementations of map(), filter() and zip() are n-ary functions. So if you add up all the code for Haskell's map(), zipWith() (which is map() using a two-argument function), zipWith3(), zipWith4(), etc. It doesn't look bad at all. In fact, there's a lot of repeated code on the Haskell side. Maybe Template Haskell can take care of that, I don't know.

So with the hard part done, here's the code for map() and filter():

function map_helper(func, arg_list, results_l)
    table.insert(results_l, func(unpack(arg_list)))
end

function map(func, ...)
    return zip_with_helper(func, map_helper, ...)
end

function filter_helper(func, arg_list, results_l)
    local result = func(unpack(arg_list))
    if result then
        if #arg_list == 1 then
            table.insert(results_l, arg_list[1])
        else
            table.insert(results_l, arg_list)
        end
    end
end

function filter(func, ...)
    return zip_with_helper(func, filter_helper, ...)
end

In retrospect, I think I'll get rid of the named helper functions and used anonymous ones instead... at least for map() and zip().

I've also figured out a n-ary version of unzip() as well:

function unzip(...)
    local tables = {...}
    if #tables < 1 then
        return nil
    end
    local multi_return = #tables > 1
    if not multi_return then
        tables = tables[1]  -- Given a table of tables, so unzip that.
    end
    local result_tables = {}
    local length = #tables
    if length < 1 then
        return nil
    end
    local width = #tables[1]
    if width < 1 then
        return nil
    end
    
    for i = 1, length do
        for j = 1, width do
            if i == 1 then
                result_tables[j] = {}
            end
            result_tables[j][i] = tables[i][j]
        end
    end
    
    if multi_return then
        return unpack(result_tables)
    else
        return result_tables
    end
end

The fun thing with this is that you can give it three tables as arguments, or one table that holds the other tables. It doesn't matter... up to a couple thousand list entries. So yeah, I don't know how practical that actually is, but it is cool that it is possible at all.

Firefly + Virga?

I was thinking recently about the combination of two very different SF universes: Whedon's Firefly / Serenity and Karl Schroeder's Virga series. No, I am not completely insane. If you are familiar with both, please let me explain...

The Firefly 'verse is (as explained in the movie) a single star system with dozens of habitable planets and hundreds of habitable moons. If you have taken a basic astronomy course, then you know how it is likely that there is only one planet (at best) in the "green zone". That is where water is liquid, so the planet is not too hot like Venus, nor too cold like Mars. You can't pack a bunch of planets into the green zone because they would perturb each other's orbits, at best flinging themselves out of the green zone, at worst into the sun or on collision course with something else. This all would occur shortly after the solar system itself formed, so you'd never see dozens of fully formed planets in the green zone in a mature star system.

Even though I really enjoyed the series and the movie, Whedon's attention to scientific realism is almost non-existent. I realize that Whedon's goal is not plausibility, but to tell good / fun stories. But if a SF work is going to reach my highest regard, it has to take care of all the details I can think of.

Karl Schroeder's Virga is basically a giant ball filled with atmosphere. There's a large central sun called Candesce (which is artificial) and a bunch of smaller ones. This large space is populated by humans living in free-fall (no gravity).

Virga is apparently constructed with advanced molecular nanotechnology, which implies superhuman intelligences. These entities decided to make a zoo / game preserve and populate it with regular pre-singularity humans. Perhaps to see what kind of societies would form when living in a free-fall environment. And by interfering with the operation of electronics (a strong EMI field pervades Virga), their tech level is limited it about 1940's level, but without much electronics.

At any rate, the Virga setting provides the environment and scale that is really needed for the Firefly 'verse. The towns and cities are days and sometimes weeks of travel between each other. The Firefly central planets have a mid-21st century tech level (at least in terms of computers and medicine) and the border moons have mostly 19th century tech, so the overall tech level is about right.

Actually, with Virga you don't need the massive energy requirements for interplanetary travel (or more realistically Star Trek style interstellar travel). Jet powered vehicles of all sizes are used in Virga now.

The Firefly computers and Internet (called the Cortex) are not really a problem, most of the shows don't revolve around that. With regards to electronics in general, we might decide to modify Virga's EMI field a bit. Maybe open up the lower frequency bands to allow at least AM radio and other primitive electronics to work. You definitely don't need to allow for high speed electronics. So no video calls, which would impact some scenes a little bit, but I don't think the overall story or pacing would be affected.

You'd still have the Alliance and the core worlds (now just cities). The Alliance vs. the Browncoats is actually quite similar to the struggles of the large and small nations described in the Virga novels.

What got me thinking about this combo of SF universes was really the Reavers. The idea that these ultra-savages still have enough discipline to run spaceships is absurd. If our own space exploration is a guide, then even with very highly trained and non-batshit-crazy personnel, there are plenty of opportunities for fatal accidents. In a more "realistic" SF universe, the Reavers would have killed off themselves immediately.

However, in Virga, it works. The Reavers don't need to worry about atmospheric containment, complex navigation, really high energy systems (like nuclear fission / fusion reactors) and all that stuff. They could plausibly maintain (at least for a short while) 19th century level tech. Or heck, have them ride flying dragons or something.

So if we wanted to re-do the episodes, we'd need to re-do a lot of the visuals, mostly the exterior shots and anything that takes place apparently on the surface of a planet. Instead of landing on planets you'd be docking in towns and such. For the outdoor scenes we need to invent some new kinds of wilderness that don't exist in Virga now. And I think we'd need flying zero-gee horses or something. The ships wouldn't have interior gravity, unless we spin them or something. Perhaps it would be better to re-shoot everything, or else make CG models of all the actors and do the whole thing that way.

Episode-by-episode revision notes:

Serenity (series pilot): Instead of cryo-sleep, maybe just have River in a drug-induced coma.

The Train Job: Have it be a convoy instead. Paradiso could be a mining town next to a floating asteroid. They're not terraforming planets in general, but making new towns and "settling" chunks of matter (dirt, water, forests, etc.) floating about.

Bushwhacked: Might still need "space suits" for warmth, the outer reaches of Virga get cold too.

Shindig: Mostly the action takes place in town, so no major changes. Zero-gee cows or spin Serenity for artificial gravity?

Safe: Just need to figure out what the village in the hills would be exactly... a small town wheel, or maybe the people are living out in the wilds.

Our Mrs. Reynolds: Wagon pulled by horses may become a small ship pulled by flying animals. Have to change some details about the capture field, but that's not a big problem. Might need Serenity stuck in a jet-stream like current which keeps in on course with the capture field.

Jaynestown: Giant clay asteroid next to the mining town.

Out of Gas: Takes place in the cold outer area of Virga. Need to modify references to running out of air to be something else. Maybe just make it about not being able to go and hypothermia.

Ariel: No advanced computer tech, so no fancy MRI w/ 3-D virtual interface. Have Simon find records of the mind-altering drugs and other procedures performed on River. Scale back the medical tech a bit in general.

War Stories: Wilderness will need to be revised as usual. Wash flies Serenity to dock with Niska's town wheel at night, without the use of the jet engines... noise would alert the guards.

Trash: The floating villas now don't need anti-gravity to float above a Virga-style ocean.

The Message: This one is a problem, organ transplant and genetic engineering implies a higher level of tech than the proposed universe can allow. Need to have Tracy smuggle something else.

Heart of Gold: The bordello is a small town wheel itself. Flying horses again.

Objects in Space: Vacuum not a danger of course, though getting shoved off into open air without transport could easily be fatal. Though it worked out for Venera Fanning.

Serenity (movie): Much more use of video that would need to be fixed. How to re-do the opening sequence? How does Mr. Universe figure out what triggered River? River managed to find a scrap from an old map that mentions Miranda. The crew try to look up Miranda in the latest set of paper encyclopedias. Mr. Universe may just have a big AM transmitter, though are people going to be convinced by an audio broadcast the way they might be for a video broadcast? Maybe have Serenity bring back more hard evidence from Miranda.

So yeah, you'd have to re-shoot the whole thing, but the stories and characters would mostly be unchanged in the new setting. And make a whole lot more sense to boot.

map in Lua

Been looking at the Functional Library for Lua this week.

The map() implementation only works for single-argument functions. Here's a version for multiple arguments:

function map(func, ...)
   local newtbl = {}
   local tables = {...}
   local listpos = 1
   local have_args = true

   while have_args do
      local arg_list = {}
      for i = 1, #tables do
          local a = nil
          a = tables[i][listpos]
          if a then
              arg_list[i] = a
          else
              have_args = false
              break
          end
      end
      if have_args then
          newtbl[listpos] = func(unpack(arg_list))
      end

      listpos = listpos + 1
   end
   return newtbl
end

It is a bit more complicated, but not too bad. If anyone has suggestions on how to make it shorter and more concise, I'd appreciate it. I'm glad to be able to implement it fairly easily, in some languages it can be quite a bother.

I need to work out new version for the other functions like filter(), and post an updated version on the Lua users' wiki. foldl() might be a little interesting...

New Battery for G1

Just got a new 2600mAh battery for the G1. Now the phone is fat and heavy. :-)

It should run over twice as long as the original 1150mAh battery, and not just because of the increased capacity. It has to do with the current draw in relation to the overall battery capacity. Even if we were drawing 300mA from each battery (for example) the larger battery is going to last a little longer than just the capacity difference would seem to indicate. Basically, you're not straining the battery as much.

Hmmm... the battery only seems to be charging up to 3.91V, as measured by the phone. So it thinks it is only 91% charged. Edit: Nevermind, it came up to 4.178V and now says it is fully charged. Cool.

If this seems to run well in the next couple weeks, I'll probably post a review on the site I purchased it from, as well as leave a comment here.

Lua on Java on DalvikVM on Android

Yes, you read that right.

I was poking around with Lua implementations and ran across LuaJ, which is an implementation of Lua written in Java.

Well, after following Davanum Srinivas's instructions on how to convert a standard JAR into one that can be installed in Android, I was able to get it to run Lua scripts inside the Android emulator.

It shouldn't be too hard to write a regular Android application that would allow the user to type in Lua chunks and run them. I haven't seen much in terms of scripting capabilities for the Android platform... Lua would be a good fit for that.

The only caveat is that the LuaJ implementation is generating and running Lua bytecodes in a Lua VM. Which is running on top of the Dalvik VM. So it is going to be crazy slow. It's kind of amazing that it runs at all, Google must have implemented a lot of the core Java stuff, including reflection.

Now here's an interesting tidbit... The Dalvik VM is register based, as opposed to the stack based JVM. And the Lua VM is register based. So what are the possibilities for "native" (by this I mean Dalvik) code generation by the LuaC compiler?

Does the Dalvik VM even support having some memory buffer contain some bytecode that it will then execute? Would we have to go through the filesystem instead (meaning generating a .dex archive or such)? Inquiring minds want to know.

There seems to be a lot of potential in general for a decent scripting language on the Android platform.

ConnectBot issue fixed

I mentioned having a problem with ConnectBot previously. Downloaded the source, found the problem, submitted a patch, it was accepted, downloaded the development snapshot... and it works! Life is good.

2009H1 Update

Here's a semi-yearly update of what's going on in my tech life:

Haven't been hacking any Haskell lately. It's a brilliant language, but one I never got comfortable enough with. We're trying to use Python for application and test script development at work, which is OK so far.

I've been investigating Lua a lot recently. We've experimented with it for a couple embedded projects so far. It is just about the only scripting language that will fit into small embedded platforms... everything else is just too hard to port. You can easily configure Lua to just include the parts you want. So for that reason alone, I think I'll be pushing for its use on future projects.

The more I've learned about the design of Lua, the more I like it. The language itself has a lot of neat features. It is very compact, very Scheme-like. But better than Scheme in that its fundamental data structure is the table, instead of a linked list. It has pretty good support for functional programming, tail call optimization, and coroutines too.

The implementation is small enough to learn and hack easily. As opposed to GHC... Don't get me wrong, it is a phenomenal work, but if you've ever looked under the hood of that compiler... yikes.

---

In other news I bought an Android Developer G1 phone. I've downloaded a popular community firmware, and also loaded Ubuntu on it. Still got some configuration issues to work out, and ConnectBot is giving me some problems while running VIM. Just have a 2.5G data service plan, which is a little pokey when out and about. But it's looking good so far.

I've wanted a decent, portable Linux machine to do hacking on for a long time... dating back to the days when I was messing around with trying to get a cut-down version of Linux running on a HP 100 LX palmtop. And now I'm there... with the Ubuntu userland installed it has Python and Lua, VIM, screen, ssh, rsync and GCC. A decent browser, always-on (if slow) Internet, WiFi, Bluetooth, expandable storage... and it makes phone calls too! How cool is that?