Play With Lua!

Making Lua Look Like Prolog

without comments

Lua, like most languages, has some object-oriented pieces. But, it doesn’t have classes and modules and objects: it takes the Scheme approach and gives you the tools you need to build the OO paradigm you want to use. In particular, the only data structure it gives you is called a table and is essentially a hashtable married to an array (it’s a hashtable, but it has accelerated access for integer keys, so it’s efficient to use for either one). Tables can be assigned metatables which define special behavior for the table: if you try to access a key that doesn’t exist, it looks in the metatable for “__index” and uses that to find what the value should be.

But if all that was intended was to make it easy to duplicate class-based OO, Lua would just have put in class-based OO, right? Let’s try something different, that uses this same trick to do something cool. Let’s make Lua look like Prolog.

What we’re going to do is make it where we can refer to variables without creating them, and expect them to be automatically created for us with the right plumbing. We’ll do this by making a metatable with an __index method, and sticking it on to a special table called _G, where all the Lua global variables live. So let’s begin:

Let’s say that any variable that begins with a capital letter is a noun, so we want to just create an empty table for it (that we can then use to store its relationships to other nouns).

The next part of the __index function checks for any name that starts with “is_”. Since we’re going to create nouns and give them relationships to each other, we’ll want to query those somehow. So we’ll say that if (for example) the noun Bob is the boss of the noun Fred, then Fred will have boss = Bob as an entry in his table, and Bob will have boss_of = Fred. If someone asks for a function that starts with “is_”, we’ll make them a function that takes two nouns and returns whether they have that relationship. Here’s what the function to make those query functions looks like:

function make_predicate(name)
   local rule = name:match("^is_(.*)")
   return function(a, b)
             return b[rule] == a

So now all we need is to make any other missing name be a function that assigns relationships. Here’s the function to create relationship-makers:

function make_rule(name)
   return function(a, b)
             a[name .. "_of"] = b
             b[name] = a

All that’s left is making the __index function that catches references to variables that don’t exist, and putting it in _G’s metatable:

setmetatable(_G,{ __index =
                  function(globals, name)
                     if name:match("^[A-Z]") then -- entity
                        rawset(globals, name, { })
                     elseif name:match("^is_") then -- predicate
                        local pred = make_predicate(name)
                        rawset(globals, name, pred)
                     else -- rule
                        local rule = make_rule(name)
                        rawset(globals, name, rule)
                     return rawget(globals, name)
                  end })

So now we’ve got a system where we can specify facts and then ask questions about them. It doesn’t have any kind of logical analyzer like an actual Prolog implementation would, but if you wrote one, this could be an excellent way to use Lua to feed facts to it. Let’s toss in a few now:

father(Vader, Luke)
father(Vader, Leia)
friend(Vader, Emperor)
friend(Emperor, Vader)
friend(Han, Luke)
friend(Luke, Han)
brother(Luke, Leia)
sister(Leia, Luke)

And then a few asserts, to verify everything works:

assert(is_father(Vader, Luke))
assert(is_sister(Leia, Luke))
assert(is_friend(Han, Luke))
assert(is_friend(Luke, Han))
assert(not is_friend(Vader, Luke))
assert(not is_friend(Han, Jabba))

And we’re done. You can see all this code in one place on Github here.

Lua and its metatables are really cool, and using them only to fake a boring language feature like classes is just a lack of imagination. It’s a really sharp tool, make cool things with it!

Written by randrews

May 16th, 2011 at 7:37 pm

Posted in Uncategorized