Thursday 15 September 2011

Strict Tables in Lua

Spelling Mistakes are Runtime Errors

Undeclared variables in dynamic languages are a well-known pain point. The compiler has to make an assumption about the scope of any undeclared variable; in Python, such variables are assumed to be local, and in Lua they are assumed to be global. (This is not entirely correct because of function environments, but will do for a first pass.) Furthermore, Lua does not distinguish between 'undefined' and 'null'; the value of such variables will always be nil, which is of course a perfectly valid value for a variable.

The consequence is that misspelt variables will evaluate to nil; if you are lucky the code will crash nearby with an error, but the nil can be passed along until it's not clear who to blame. So serious Lua programmers are strict about detecting undefined globals.

There is a dynamic approach provided by etc/strict.lua, which is part of the standard Lua distribution. Globals are looked up in the global table _G, which is otherwise a normal Lua table. You can give it a metatable and a __index metamethod, which is only called if the variable was not already present in the table. By keeping a table of known declared globals, this can throw an error on any undeclared variable access. This is definitely a case where you need to fail hard and early as possible!

(Another approach is static analysis, for instance David Manura's LuaInspect which has the advantage of making mispellings into compile-time errors. It has experimental integration into the SciTE editor.)

The pattern I will describe brings stricter run-time checking to other Lua tables using the same principle. But first let's examine some practices that are common in Lua code. Named arguments to functions are not supported, but it's easy to use tables to get the same result:

 function named(t)
   local name = t.name or 'anonymous'
   local os = t.os or '<unknown>'
   local email = t.email or t.name..'@'..t.os
   ...
 end
 named {name = 'bill', os = 'windows'}

Although this is not the most efficient way to pass arguments to a function, it serves the purpose well, particularly with Lua's function-call syntax sugar that lets us leave out the parentheses in this case.

This idiomatic use of anonymous structures is common in Lua code. Need to keep a few things together in one place? Make a table! The pattern also appears in JavaScript which has the same identity between t['key'] and t.key in dictionaries. And LuaJIT can optimize field accesses in inner loops to C-like speeds.

Such ad-hoc tables are always open to extension, so people add extra fields as the need occurs. At this point strong-typing people are starting to hyperventilate: how can such code be ever reasoned about correctly? The answer is, fine - up to a certain point of program complexity. Thereafter you need to get disciplined.

Lua is not inherently a weakly-typed language, but there is a tendency to use it like so. One problem is how to document this pattern, for instance, how to document the function named above? If functions take specific named types for their arguments, then we can refer to the definition of those types in their documentation. Identity is also very useful for debugging and dynamic type-checking.

Give a Dog a Name ....

I'll show how the idea of 'strict tables' helps this structuring problem and also how to catch another class of misspellings accurately. First, a strict strict has a known set of fields with default values (which also establish the type of the fields):

 Strict.Alice {
     x = 1;
     y = 2;
     name = '';
 }

This statement causes a constructor Alice to be introduced into the current environment:

 a = Alice {x = 10, y = 20, name = "alice"}

Any of these fields may be absent in the constructor call, and in particular Alice() will give you a new Alice-struct with the initial default values. However, setting an unknown field or setting a known field to the wrong type is a run-time error:

 b = Alice {x = 10, Y = 20, name = "bob"} -- > error: field 'Y' is not in Alice
 c = Alice {x = 10, y = 20, name = 44} -- > error: field 'name' must be of type string

What does 'wrong type' mean? Here the convention is that we compare the type names, but if the types are tables or userdata we compare their metatables.

Trying to access an unknown field of an Alice-object will likewise result in an error:

 print(a.Y) -- > error: field 'Y' is not in Alice
 a.Y = 2  -- > error: field 'Y' is not in Alice

The second failed assignment shows that Alice-objects are closed, which is a further restriction. (In the case of the original strict.lua, the global table is always open to new variables.) A little less freedom often relieves us of later anxiety, and here allows for checking field spelling mistakes immediately when they happen.

We basically incur no extra run-time overhead for this checking. This is because __index (and its cousin '__newindex`) only fires if lookup fails. (In Lua 4, such functions were called fallbacks, which remains a fine bit of descriptive terminology.)

By default, these objects know how to convert themselves to strings sensibly:

 print(a) --> Alice {y=20,x=10,name=alice}

They directly solve the documentation problem by being themselves documentable:

 -------
 -- Check alices.
 -- @param anAlice an @{Alice} object
 -- @see Alice
 function check_alice(anAlice)
 ...
 end
 -----
 -- Alice.
 -- @field x
 -- @field y
 -- @field name
 -- @table Alice

The benefits of named, unique types are well known:

  • error messages are explicit (we know what kind of dog caused the problem.)
  • debugging is easier, since these dogs know their name and their kind
  • type identity makes type checking possible (Is this dog an Alsatian?)

This will be self-evident to any Java (or Python) programmer; why isn't this pattern more widely used in Lua? First, anonymous types are very good at creating recursive structures akin to S-expressions - which will be self-evident to any Lisp programmer. Second, the idea of extended type is not built-in to the language, resulting in multiple ways of declaring dogs and interoperability issues. And finally, because it can be so convenient to play fast and loose with your data. For instance, you want to deliver something to another part of the system and there's no 'official' way to do it. But you know that there's an object which will end up there later, so you attach some data to the object and make a special case at the receiver. It's a bit like the informal arrangements people make like 'when you're in Singapore can you pick up that new toy for me?' rather than using a courier. (I have enough disciplined instincts to know that this is not the way to produce software that's clear to others, but it's a convenient way to get what you need.)

Although not strictly necessary, it was hard to resist adding a few features. Consider this:

 Strict.Boo {
     name = 'unknown';
     age = 0;
     __tostring = function(self) -- can override __tostring
         return '#'..self.name
     end;
     __eq = true;   --- default member-equals comparison
     __lt = 'age';  --- use this field for less-than comparison
 }

The default string conversion may not be desired, so you may override it using the __tostring metamethod. Note in fact that the 'specification' table becomes the metatable for all named objects, so you can specify any of the available metamethods. (In Lua 5.2 you can even specify a finalizer using __gc.)

As a convenience, setting __eq to true means that you want a plain naive field-by-field comparison (otherwise objects are all unique table values.) And __lt can be given the name of the field for < comparisons.

Defining the < operator means that you can directly sort lists of these objects:

 ls = {Boo{age=13,name='F13'},Boo{age=5,name='F5'},Boo{age=20,name='F20'}}
 table.sort(ls)
 for _,b in ipairs(ls) do print(b) end
 --- > output:
 #F5
 #F13
 #F20

A Question of Notation

The notation for defining new strict tables I've chosen needs some elaboration. Without any sugar, it would look like this:

 Strict("Person",{ name = '', age = 0 })

We get closer to the desired notation by currying (that is, expressing a function of several arguments as a chain of single-argument functions):

 function Strict(name)
     return function(spec)
       ...
     end
 end

Which would allow

 Strict "Person" {name = '', age = 0}

To get Strict.Person {...} is easy; Strict is a table which is given a __index metamethod; accessing any new name causes it to be called, and it will then return the actual function as above:

 Strict = setmetatable({},{
     __index = function(self,name)
         return function(spec)
         ...
         end
     end
 })

Further Elaborations

There are other approaches to the problem of checking the structure/type of Lua tables, of course: have a look at how LuaRocks does a sanity check on the rockspec format. This is akin to the idea of defining a 'schema' for XML, although a good deal more readable.

The implementation discussed here focuses on creating a closed, named type with declared fields and their types. It's currently just over a hundred lines, which is my self-imposed limit with these article demonstrations, but there's a number of cool features which could be added. Any library has a real implementation and an imaginary part, which is the space of possibilities; it would be boring to neglect the latter.

If we wanted to enforce type-checking on these fields (such as a.name = 42) then we need an extra indirection using the proxy-table pattern. That is, the Alice-object itself would not contain anything except a table containing its values; then __index will always fire and would look up the key in this value table, after performing some sanity checks. In that case, performance would be affected (although if such lookups did not happen in inner loops then the penalty may well be not measurable anyway.)

It could be useful to optionally allow for field ordering:

 Strict.OrderedPerson {
     "Represents a Person for our catalog";
     {name = ''; "full name of person"},
     {age = 0; "age in years"}
 }

which would allow the constructor syntax OrderedPerson("Dilbert",38). The doc-strings would not be obligatory but can be used (for instance) to automatically generate a basic entry dialog for the data.

It would be possible to also add methods to these strict tables but they are really meant to represent classic dumb data; for more conventional OOP in Lua there are many options (As the great Grace Hopper said, the wonderful thing about standards is that there's so many of them to choose from; my personal favorite which I use in Penlight is here).

An extended concept of 'type' is problematic precisely because there are so many object-oriented schemes possible. For instance, there are a number of imcompatible inheritance schemes that make asking the question 'is A a subtype of B?' particularly tricky.

But we could extend the type specifications used by strict tables in useful ways. Currently the type of a field is the type of its default; what if the type was a Lua string pattern? So '^%S+$' would mean 'a string with no spaces'. Or if {0} meant 'an array of numbers'?

 Strict.Data {
     name = '^%S+$';  --- or give the pattern a name, e.g. Strict.no_spaces
     factor = Strict.range(0,1);
     children = {Child()}
 }

(This would further enable our hypothetical data-to-dialog generator to give more specific validation of user input.)

The idea of 'documentability' can be taken further; if I had a function that received an object that had a read method, then the obvious equivalent to strict tables would be interfaces:

 Interface.Readable {
     read = true
 }

My function could then say Interface.check(1,rdr,Readable) to give a meaningful assertion on the first argument rdr. Even if I didn't use these assertions, simply making the argument more documentable could be a sufficient reason to have named interfaces. The contract can be specified and optionally enforced; it cannot be specified in such great detail as in statically-typed language, but it's still useful.

Finally, not everyone is as lax as I am about creating new globals. Strict returns the new type, but also creates it in the current environment. A more careful person would probably want to remove the line that creates this global. Maybe Stricter ?

This article was based on the original lua-users wiki entry; here is the code.

1 comment: