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.