XST 32: Hard Things Easy
I want Lua tables to be more useful as XSets. There’s a hard way. But the current design also offers an easy way. (The answer will surprise you. It surprised me.)
The main use for Lua tables in this app is to build up some data sets. In the fist instance, I’d just like to be able to produce individual records (sets with atomic elements and no duplicate scopes) like this:
{ last-“Jeffries”, first=”Ron” }
Which would “mean”:
{ “Jeffries”“last”, “Ron”“first” }
Which I’d generally write for our purposes as
{ Jeffrieslast, Ronfirst }
It would be pleasant, however, if we could define a set of records the same way:
{
{ last-“Jeffries”, first=”Ron” },
{ last-“Hendrickson”, first=”Chet” }
}
I can see two ways to work toward this. (Should I wait until I think of a third?)
Metatables
All tables in Lua have what’s called a “metatable”. That table is accessed when the original table doesn’t know how to do something. For example, if you have two tables t1 and t2 and you try t1+t2, Lua will not know how to do + on tables, so it will access the metatable for t1 and look for a function named __add. If it finds it, it’ll perform it. If you’ve provided a metatable and that function, you can use it to define “union” or whatever you have in mind when you add two tables.
Similarly, if you were to send a message to a table, such as
t1:card()
The table t1 might actually include a function card and if it did, Lua would call it. If there is no entry in t1 for card, Lua would look in the metatable for t1 for __index (not card), saying that an attempt was made to index t1 and there was nothing to find. The __index function receives the original table and the index that was not found. It can do anything it wants with that information, and whatever it returns will be the result of the table access. If it returns a function in our case, Lua will call it. If it returns a number, Lua will call that, and you’ll get an error.
It turns out that there is no common metatable for all tables. In general, that’s good, because you probably want different tables to act differently, since a class instance is “just” a table with a metatable full of methods.
To make tables act like sets, we would have to at least provide a special metatable to any set that we wanted to have act that way. Some wrapping function or something:
makeSet({ last-"Jeffries", first="Ron" })
We have a big issue with this scheme. We want sets to “inherit” all those set operations, which are implemented as functions in XSet. So for some functions called on our tables, we want to defer over to XSet for the function. For a few others, at least hasAt and elements, we would want to provide the specific functions that access and iterate the table.
Now I think we could do that much. In our __index function, we’d check the key to see if it was hasAt or elements, and if so, do the local operation and then, if it wasn’t one of ours, we could return XSet[key], which would (presumably) be the function named key.
However. Not even just “however”. But. But the functions in XSet make a big assumption, namely that there is a member variable in XSet, named data, and that the data member understands a few methods, including hasAt and elements but also card and elementProject and other possibly optimized functions.
So if we did try to provide a set as self to an XSet method, XSet would soon try to access data, which would not be present … or, worse yet, might be present containing the wrong thing …
It might be possible to sort all this out, but it’s rather clearly going to be complicated. It’s tempting to do it just to see if we can, but we might be able to get the benefits we seek some other way.
An XData Type
That data element in an XSet is supposed to contain an instance that is a kind of XData, that is, subclassed from XData.
Could we “just” put our table into a new kind of XData, say XTable, and then it’s all good?
At the top level, we certainly could. It would be so easy I’m tempted to do it just to show how to do it. And I still might.
The trouble comes if the table contains a table. We can assume that the creator of a nested table intends it to be XSets all the way down, as with my table of records above.
Saying that made me wonder what would happen if, instead of a table intended to be an XSet, we were creating sets whose elements were Lua objects? Or even XSets where we intended the things inside to just be tables, not sets at all.
I was thinking of some simple idea like “if, when iterating an XTable, you encounter an element that is a table, wrap it in an XTable so that it will act like a set”.
We could try doing “whatever it takes” and frankly I think doing tables as an XData subclass would be less intricate than doing the thing with metatables. I’m not certain that the metatable idea can be made to work. Here, I’m not certain that XTable can be made to do what we want, because we don’t always want the same thing.
(This same concern would arise with the metatables, but defaulting to make all tables able to serve as sets, using metatables, would probably be mostly harmless. Maybe.
Weird. I thought when I started this article that I’d probably decide that the XTable approach was better, and do it, and there we’d be all nice and happy.
Now I don’t like this idea either.
Cui Bono?
If I remember my Latin, that means “who benefits?” The person who benefits from whatever I do with tables is the programmer writing Codea Lua code to do set theory. That pretty much comes down to me. What do I need?
I need better ways to write things like this:
_:test("Intersect", function()
local A = XSet()
A:addAt("Jeffries", "last")
A:addAt("Ron", "first")
_:expect(A:card(), "#A").is(2)
local B = XSet()
B: addAt("Ron", "first")
_:expect(B:card(), "#B").is(1)
local C = A:intersect(B)
_:expect(C:hasAt("Ron", "first")).is(true)
_:expect(C:card()).is(1)
_:expect(C:isNull()).is(false)
end)
I guess I’d like to be able to write something like this:
local A = XSet{last="Jeffries", first="Ron"}
local B = XSet{first="Ron"}
local C = A:intersect(B)
Hm. What does XSet do now, when faced with a table? Nothing. We could, however, say this:
local A = XSet:fromTable{last="Jeffries",first="Ron"}
And that works just like the longer form shown above. We have this code:
function XSet:fromTable(tab)
return XSet:on(XGeneric:fromTable(tab))
end
function XGeneric:fromTable(tab)
local stringify = function(e)
return type(e)=="number" and tostring(e) or e
end
local xg = XGeneric()
for scope,element in pairs(tab) do
xg:addAt(stringify(element),stringify(scope))
end
return xg
end
This will not work well with nested tables, however. Let’s just try one and see what happens. Here’s a test where that would come in handy:
_:test("Restrict", function()
local ron = XSet()
ron:addAt("Jeffries","last")
ron:addAt("Ron","first")
ron:addAt("Pinckney","city")
local chet = XSet()
chet:addAt("Hendrickson","last")
chet:addAt("Chet","first")
chet:addAt("Atlanta","city")
local ricia = XSet()
ricia:addAt("Hughes","last")
ricia:addAt("Ricia","first")
ricia:addAt("Pinckney","city")
local A = XSet()
A:addAt(ron,NULL):addAt(chet,NULL):addAt(ricia,NULL)
_:expect(A:card()).is(3)
local pinckney = XSet():addAt("Pinckney","city")
local B = XSet():addAt(pinckney,NULL)
_:expect(B:card()).is(1)
local C = A:restrict(B)
_:expect(C:card()).is(2)
end)
We’d like to recast that like this:
_:test("Restrict", function()
local A = XSet:fromTable{
{last="Jeffries",first="Ron",city="Pinckney"},
{last="Hendrickson",first="Chet",city="Atlanta"},
{last="Hughes",first="Ricia",city="Pinckney"}
}
_:expect(A:card()).is(3)
local B = XSet:fromTable{ {city="Pinckney" } }
_:expect(B:card()).is(1)
local C = A:restrict(B)
_:expect(C:card()).is(2)
end)
Will this work? Let’s find out. I expect “no”.
10: Restrict -- XSet:182: attempt to call a nil value (method 'isSubset')
Right. We have two tables in hand and are trying to ask them whether one is a subset of the other.
What is in the XGeneric in this case? Well, I reckon it has scopes of “1”, ““2, “3”, because those will be the keys when we iterate the input table. The elements under those scopes will be the individual tables, {last=”Jeffries”,first=”Ron”} and so on.
Could we extend fromTable to convert inner tables to XSets and then store them? We could enhance stringify:
function XGeneric:fromTable(tab)
local stringify = function(e)
return type(e)=="number" and tostring(e) or e
end
local xg = XGeneric()
for scope,element in pairs(tab) do
xg:addAt(stringify(element),stringify(scope))
end
return xg
end
The name won’t do but for now it’s OK. First refactor it.
function XGeneric:fromTable(tab)
local stringify = function(e)
if type(e)=="number" then return tostring(e) end
return e
end
local xg = XGeneric()
for scope,element in pairs(tab) do
xg:addAt(stringify(element),stringify(scope))
end
return xg
end
This should run as before, and it does. Now extend:
function XGeneric:fromTable(tab)
local stringify = function(e)
if type(e)=="number" then return tostring(e) end
if type(e)=="table" then return XSet:fromTable(e) end
return e
end
local xg = XGeneric()
for scope,element in pairs(tab) do
xg:addAt(stringify(element),stringify(scope))
end
return xg
end
I think this ought to fix the isSubset error.
Interestingly, the simplified test above does run but I get two new errors:
42: create XSet from table allows XSet elements person set -- Actual: XSet(1 elements), Expected: XSet(2 elements)
42: create XSet from table allows XSet elements tens set -- Actual: XSet(1 elements), Expected: XSet(3 elements)
Best check that out.
_:test("create XSet from table allows XSet elements", function()
local s1 = XSet():addAt("first","Ron"):addAt("last","Jeffries")
local s2 = XSet:tuple{10,20,30}
local tab = {"hello",person=s1,tens=s2}
local set = XSet:fromTable(tab)
_:expect(set:at("1")).is("hello")
_:expect(set:at("person"), "person set").is(s1)
_:expect(set:at("tens"), "tens set").is(s2)
end)
Ah. If we already have an XSet, not just a vanilla table, we should just return it from stringify:
function XGeneric:fromTable(tab)
local stringify = function(e)
if type(e)=="number" then return tostring(e) end
if type(e)=="table" then
if e:is_a(XSet) then return e
else
return XSet:fromTable(e)
end
end
return e
end
local xg = XGeneric()
for scope,element in pairs(tab) do
xg:addAt(stringify(element),stringify(scope))
end
return xg
end
I am hopeful that everything will run now.
My hopes are dashed. I can’t call is_a on a regular table. It has to be a class or instance. So how can we figure out whether the table we have in hand is or is not an XSet?
As a hack, we can look to see if the table has an element named data. That won’t stand up under pressure, but it should let us see whether this idea hangs together at all.
local stringify = function(e)
if type(e)=="number" then return tostring(e) end
if type(e)=="table" then
if e.data then return e
else
return XSet:fromTable(e)
end
end
return e
end
The tests all run. This is actually rather good. The check for XSet isn’t very robust. Let’s check the metatable of the table to see if it is XSet, because all XSet instances have XSet as their metatable.
local stringify = function(e)
if type(e)=="number" then return tostring(e) end
if type(e)=="table" then
if getmetatable(e) == XSet then return e
else
return XSet:fromTable(e)
end
end
return e
end
Tests are green. Commit: XSet/XGeneric fromTable handles nested sets, converting to XSet all the way down. (tested only two levels, but confident).
Let’s see about that code.
function XGeneric:fromTable(tab)
local standardize = function(e)
return type(e)=="number" and tostring(e)
or type(e)=="table" and getmetatable(e)==XSet and e
or type(e)=="table" and XSet:fromTable(e)
or e
end
local xg = XGeneric()
for scope,element in pairs(tab) do
xg:addAt(standardize(element),standardize(scope))
end
return xg
end
I think that’s better. Idiomatic but better for it.
Commit: rename stringify to standardize and refactor.
I think this has been an interesting morning. Let’s think about what just happened.
What DID Just Happen???
What just happened was that I had a rather simple need, to express certain sets more easily than with all those addAt calls. I translated that in my programmer mind into “tables ought to be XSets”. Then I considered a very difficult way to do that, with metatables. Then I considered a less difficult way, with a new kind of XData that could hold a table.
In doing that I finally had to face up to the question of what I really wanted–easy input–and what I wanted sets of sets to do–become XSets of XSets.
Then I sort of forgot about a possible argument that “well, if it was really tables it’d be faster and less storage”, since I know that an additional method call isn’t likely to be the performance bottleneck.
Finally, I stumbled on the fromTable method, which does the conversion on the creation end instead of the operational end. And in the end, it just comes down to the difference between this:
function XGeneric:fromTable(tab)
local stringify = function(e)
return type(e)=="number" and tostring(e) or e
end
local xg = XGeneric()
for scope,element in pairs(tab) do
xg:addAt(stringify(element),stringify(scope))
end
return xg
end
And this:
function XGeneric:fromTable(tab)
local standardize = function(e)
return type(e)=="number" and tostring(e)
or type(e)=="table" and getmetatable(e)==XSet and e
or type(e)=="table" and XSet:fromTable(e)
or e
end
local xg = XGeneric()
for scope,element in pairs(tab) do
xg:addAt(standardize(element),standardize(scope))
end
return xg
end
So that’s fascinating to me. I was really sure that I’d settle in on the easier XData approach, but when I realized that all I care about is easy data entry, the starting solution was clearly fromTable, and then wanting nesting made the next improvement pretty clear.
Now … is this a case where the reader might point to the idea of doing more design up front? They might. But I think they’d be mistaken. Design up front was what I was doing when i was reading about metatables and trying experiments with them. Design up front was what I was doing when I started thinking about how to make a new XData type.
What I did this morning, was two things, thinking, and explaining. Both, I think, were important. It started from the explaining.
I wanted to share my thinking with my readers, because I believe that there’s value to showing folks how decisions get made–and in my case, mostly how mistakes get made. To do the explaining, I had to think more deeply than I had before, reflecting more clearly on the possible ideas than one does when just musing, but far less deeply than if I had gone fully into design mode. Just deeply enough to make sure I could describe the issues, which was deep enough to help me see the difficulties.
So the explaining drove the thinking and the thinking drove the explaining. I came to realize that I really only cared about input style, and at that point started to code. That drove me to fromTable and a couple of translations of tests into more convenient form drove out this very simple implementation that amounts to two (TWO!) lines of code.
I though I was going to choose the easier of two ways. I wound up choosing something even easier, that gives me what I wanted at the code of almost no added complexity.
Explaining, thinking, and letting the code take part in the discussion.
This is the way.
See you next time!