XST 20: Tuples
I’m sure a lot of you have been saying ‘Yes, but what about tuples?’, or “Why XST anyway?’. Today, we address those fascinating concerns.
When I say “a lot”, I mean “all two or three of you who are reading these articles”. But those who are not reading, well, they’re missing out on more than they realize. Not only set theory, but we’re crafting some rather nice code here, and even learning some lessons about incremental development. Anyway, even if you’re not reading this, I’m just doing it for the finger and brain exercise anyway.
Tuples. Tuples, as you may imagine, are sets of things in order. Not necessarily sort order, just one after another.
In XST, the tuple <a,z,b,y,c,x> is defined to be
{ a1, z2, b3, y4, c5, x6 }
Now, funny story, this here is why XST had to be invented1. Prior to Dave Childs creating Extended Set Theory, mathematicians defined the ordered pair <a,b> as {a, {a,b}}. The reason it needed a definition is, well, that’s what mathematicians do, and there had to be some way to tell the difference between <a,b> and {a,b}. Unfortunately, when we start trying to do the set-theoretic information stuff we’re doing, we also need a way to distinguish <a,b> from {a,{a,b}}. So Dave reformalized all of set theory with the new element-scope formulation.
OK, maybe not too funny. Anyway, there is a formal definition of a tuple and it is, roughly
An n-tuple T is a set of elements with scopes in the range 1-n, where if x ∈k T and y ∈k then x=y. That is, each scope in 1-n occurs exactly once.
Why do we care about that just now?
I’m glad you asked that. Recall that we just implemented elementProject, which, given a scope, returns the element of a set that is under that scope, if there is only one. Now imagine a tuple P of records, say people records, numbered from 1 to 500. And suppose you wanted record number 23. You’d just say
P:elementProject(23)
And right there in your hand is that record. Or suppose you had a set containing all the record numbers of the set where the state is “MI”. Our other new operator, scopeRestrict would return all the MI records and no others. Sound familiar? Remind you of indexing? It should. Let’s think a bit about indexing and how we think we might implement it with set operations.
Indexing
The basic idea for indexing is that we’ll store indexed data in tuples, 1,2,3, like that. And we’ll generate indexes that contain the scopes of the records we’re interested in. Then, when we do something like a restrict, instead of searching the records, we’ll grab our index sets, maybe massage them, wind up with a set of scope values and then scopeRestrict will fetch the desired records, thus avoiding all those comparisons. And, if the data reside on a slow medium, avoiding unnecessary accesses.
We’ll want some data stored in tuples. I think we’ll create a new XData type for tuple, since they have some slightly different behavior.
In addition, we’ll probably want to review some of our other operations to ensure that they do things we like with the scopes.
The first thing I want to test is whether numeric scopes even work.
_:test("Numeric Scopes", function()
local S = XSet():addAt("a",1):addAt("b",2):addAt("c",3)
local b = S:elementProject(2)
_:expect(b).is("b")
end)
Perfect. That test runs. Let’s do tuples.
_:test("Tuple", function()
local T = Tuple():add("a"):add("b"):add("c"):add("d")
local c = T:elementProject(3)
_:expect(c).is("c")
end)
This should fail not knowing Tuple.
32: Tuple -- Tests:428: attempt to call a nil value (global 'Tuple')
And let’s code:
Tuple = class(XData)
function Tuple:init()
self.tuple = {}
end
function Tuple:add(element)
table.insert(self.tuple, element)
end
function Tuple:card()
return #self.tuple
end
function Tuple:elementProject(scope)
return self.tuple[scope]
end
I’m not expecting this to work, but let’s see.
32: Tuple -- Tests:428: attempt to index a nil value
Ah. Forgot to return self from add:
function Tuple:add(element)
table.insert(self.tuple, element)
return self
end
That’s needed to allow me to concatenate the adds that way.
The test runs. I am slightly surprised. Mostly I just want to be sure we used the fast method. A quick print reassures me. I went off the plan and implemented card. Better add the test:
_:test("Tuple", function()
local T = Tuple():add("a"):add("b"):add("c"):add("d")
_:expect(T:card()).is(4)
local c = T:elementProject(3)
_:expect(c).is("c")
end)
Test runs. We don’t have elements. I guess I can just call it …
_:test("Tuple", function()
local T = Tuple():add("a"):add("b"):add("c"):add("d")
_:expect(T:card()).is(4)
local c = T:elementProject(3)
_:expect(c).is("c")
local t = {}
for e,s in T:elements() do
t[s]=e
end
_:expect(t[1]).is("a")
_:expect(t[2]).is("b")
_:expect(t[3]).is("c")
_:expect(t[4]).is("d")
end)
32: Tuple -- XData:72: Must implement elements!
function Tuple:elements()
-- return an iterator
return coroutine.wrap(function()
for s,e in ipairs(self.tuple) do
coroutine.yield(e,s)
end
end)
end
Tests run. I don’t like having used the word tuple for the member variable and it has already confused me once. I think I’ll call it contents. Change made. Tests run.
I think we need hasAt:
_:test("Tuple", function()
local T = Tuple():add("a"):add("b"):add("c"):add("d")
_:expect(T:card()).is(4)
local c = T:elementProject(3)
_:expect(c).is("c")
_:expect(T:hasAt("b",2)).is(true)
_:expect(T:hasAt("c",2)).is(false)
local t = {}
for e,s in T:elements() do
t[s]=e
end
_:expect(t[1]).is("a")
_:expect(t[2]).is("b")
_:expect(t[3]).is("c")
_:expect(t[4]).is("d")
end)
Ah, this one is tricky, because we have to do the complex equality check. I think I’ll do the naive check and then do a new test for the complex one.
function Tuple:hasAt(e,s)
local element = self.contents[s]
return element and e==element
end
Test passes. Tempted to commit, but let’s finish the hasAt first.
_:test("Tuple", function()
local set = XSet():addAt("Jeffries","last")
local equ = XSet():addAt("Jeffries","last")
local T = Tuple():add("a"):add("b"):add("c"):add("d"):add(set)
_:expect(T:card()).is(5)
local c = T:elementProject(3)
_:expect(c).is("c")
_:expect(T:hasAt("b",2)).is(true)
_:expect(T:hasAt("c",2)).is(false)
_:expect(T:hasAt(set,5),"identical").is(true)
_:expect(T:hasAt(equ,5),"equal").is(true)
local t = {}
for e,s in T:elements() do
t[s]=e
end
_:expect(t[1]).is("a")
_:expect(t[2]).is("b")
_:expect(t[3]).is("c")
_:expect(t[4]).is("d")
end)
This test is getting long. I know your teachers will tell you to write new tests for each new idea. That’s good advice. I’ve been doing this for a long time, and I prefer a test that tells more of a story, but I’m probably wrong to feel that way.
Anyway, I expect this to fail on “equal” but not “identical”.
32: Tuple equal -- Actual: false, Expected: true
Yes. The first one passed because the check for equal checks for identity. The second failed because the check for equal checks for identity.
I think we can just check to see if we have an XSet in hand and if so, call equals on it:
function Tuple:hasAt(e,s)
local element = self.contents[s]
if type(e)~="table" then
return element and e==element
else
return type(e)=="table" and element:equals(e)
end
end
I had to check type instead of is_a because we can’t call is_a on primitives like numbers and strings.
OK, I think we can commit: Tuple implemented with rapid access by scope.
Let’s reflect.
Reflection
First of all, I want to point something out that is quite good, although I’m not sure it’s much credit to me. This code is made up of a hierarchy of small objects with very small methods. Almost all the methods I’ve implemented in the past few days have worked the first time.
Frequent readers will know that this is quite unlike me. I frequently get things almost right. Sometimes I get confused. Sometimes I get confused enough that I revert and try again.
What is happening here is that we have a fundamental notion, the XSet, which has a rather broad interface, but it is implemented against an abstract object XData, which has a very narrow interface, just hasAt and elements, plus any additional overrides we might make. We generally make those overrides explicitly for speed, because we create XData subclasses for specific purposes, and often that purpose is some kind of speed advantage.
And, owing to the simplicity of set theory, the hasAt is generally simple and owing to the simplicity of Lua, the iterator elements is generally simple as well.
This reminds me of the great value that comes from simple design. Often, we do not have a solid theoretical basis for what we write, but when we continually refactor toward small simple objects, we tend to move faster, because the amount of work we have to do is smaller, and it comes in smaller chunks.
Here again we see the great value to what GeePaw Hill calls MMMSS: Many More Much Smaller Steps.
I’m also seeing the advantage of my tests. I have 36 tests, and they are each fairly comprehensive. There are over 100 calls to _:expect(). The tests give me confidence that things continue to work, and rarely but once in a while, one of them will find a mistake.
Simple design, accompanied by simple tests that cover all our code. Can’t be beat.
However.
Often it takes longer to write a test than it does to make the test run, or at least it seems that way. There are two reasons.
- It’s in writing the test that much of the design takes place, and it’s the hard part that starts from “how the heck should I even say this?”.
- Creating examples is often tedious and requires intricate typing.
In general, these are the price one pays for testing, and while it often feels slow, I am quite certain that for me, it always pays off in faster production of working code. That’s not to say that I never write a test that’s a waste: it’s just that most of them pay off so well that the occasional clunker is paid for. And when I don’t write tests, I often get away with it, but the occasional clunker often turns into an hour or two of confusion and debugging.
Like any human, I don’t always do the best thing I know of, I just do the best thing I could manage at the time. But I know, deeply, that the tests are worth it. In particular, I’m happy that I started with tests here, because even though they are a pain to type, they are helping.
Speaking of Pain to Type
I have an idea for a simpler form of tuple creation, at least for testing, but also in general.
I’ll replicate part of my Tuple test to show you.
_:test("Tuple Shorthand", function()
local T = Tuple{"a","b","c","d"}
_:expect(T:card()).is(4)
local c = T:elementProject(3)
_:expect(c).is("c")
_:expect(T:hasAt("b",2)).is(true)
_:expect(T:hasAt("c",2)).is(false)
end)
I propose to allow provision of an array of values to create a tuple. Now this is going to open up some questions, but let’s make the test work.
All the expectations fail, of course, because the set has no contents, yet. No one said add.
function Tuple:init(aTable)
-- slightly intricate to deal with { x=5 } etc
self.contents = {}
for _ignored,e in ipairs(aTable or {}) do
table.insert(self.contents,e)
end
end
Here I make a point of dealing only with the array part of the input table. I’ll mess it up a bit to illustrate the problem.
_:test("Tuple Shorthand", function()
local T = Tuple{"a",x=5, "b",z={},"c","d"}
_:expect(T:card()).is(4)
local c = T:elementProject(3)
_:expect(c).is("c")
_:expect(T:elementProject(4)).is("d")
_:expect(T:hasAt("b",2)).is(true)
_:expect(T:hasAt("c",2)).is(false)
end)
Test runs. Commit: Tuple accepts array input on creation.
I’m really happy with these little tests. Perhaps I have mentioned that before. (Yes, I know I have.)
I’ve been at this for just about long enough for a morning. But let’s try one more thing.
_:test("People Tuple", function()
local csv = XSet:on(CSVSet(CSVnames, CSVdata))
local PT = Tuple()
for e,s in csv:elements() do
PT:add(e)
end
_:expect(PT:card()).is(500)
end)
This doesn’t prove much, just that I got the right number of items. But let’s do a couple of other things:
Strong Advice: Skip down to “HERE”
Wow. I wish I had stopped. That test succeeds, so I extended it to run restrict on it. That game me a message saying restrict wasn’t understood, so I added the `is XSet” check below:
_:test("People Tuple", function()
local csv = XSet:on(CSVSet(CSVnames, CSVdata))
local PT = Tuple()
for e,s in csv:elements() do
PT:add(e)
end
_:expect(PT:card()).is(500)
_:expect(PT:is_a(XSet),"is XSet").is(true)
local restrictor = XSet()
for _i,state in ipairs({"MI", "AK", "KY", "NE", "NY"}) do
restrictor:addAt(XSet():addAt(state,"state"),NULL)
end
local restricted = PT:restrict(restrictor) -- was csvRestrict
_:expect(restricted:card()).is(69)
end)
That fails:
34: People Tuple is XSet -- Actual: false, Expected: true
I’ll insert a simpler test and ignore this one.
_:test("Tuple is an XSet", function()
local PT = Tuple()
_:expect(PT:is_a(XData),"pt is d").is(true)
_:expect(PT:is_a(XSet),"pt is x").is(true)
end)
34: Tuple is an XSet pt is x -- Actual: false, Expected: true
What’s up with that? Does inheritance not work? Ah, I bet I know. Probably the tabs are in the wrong order, so that XData doesn’t inherit from XSet? Yes, I think there’s something going on there, since some of the XData subclasses use XSet. I think I’m going to have to declare all my classes in one tab.
Yes, creating a new tab fixes the problem:
-- define classes here for proper referencing
XSet = class()
XData = class(XSet)
Those are the only two that need to be declared here. Naturally they cannot also be declared in the tabs with the methods, unless we combined all the methods in the tab above.
Now to unignore my restrict.
Huh. I still get this error:
35: People Tuple -- Tests:476: attempt to call a nil value (method 'restrict')
OK, I’ve made too much of a mess. I’m going to revert.
Now the first thing I want to test is whether you can inherit more than one level. I’m sure you can, but when deeply confused, check everything:
_:test("hierarchy", function()
local a = A()
local b = B()
local c = C()
_:expect(a:is_a(A)).is(true)
_:expect(b:is_a(B)).is(true)
_:expect(b:is_a(A)).is(true)
_:expect(c:is_a(C)).is(true)
_:expect(c:is_a(B)).is(true)
_:expect(c:is_a(A)).is(true)
end)
OK, that assures me that inheritance works as I intend.
Now let’s check our classes.
_:test("XSet hierarchy", function()
local x = XSet()
local d = XData()
local t = Tuple()
_:expect(x:is_a(XSet)).is(true)
_:expect(d:is_a(XData)).is(true)
_:expect(d:is_a(XSet),"d xset").is(true)
_:expect(t:is_a(Tuple),"t tuple").is(true)
_:expect(t:is_a(XData),"t data").is(true)
_:expect(t:is_a(XSet),"t xset").is(true)
end)
I had to comment out the init message on XData to let an abstract class be created. The errors are interesting:
2: XSet hierarchy d xset -- Actual: false, Expected: true
2: XSet hierarchy t xset -- Actual: false, Expected: true
The first explains the second. I have the XData sets broken out from the XSet, to simplify code search and such. Right now, XData tab is to the left of XSet. That means XData will be defined while XSet is nil. I’ll try reversing the order of those two.
That gives me a compile error on XGeneric(), here:
function XSet:init()
self.data = XGeneric()
end
I think I do need to consolidate all the class definitions.
-- class definitions all go here
XSet = class()
XData = class(XSet)
XExpression = class(XData)
XGeneric = class(XData)
Tuple = class(XData)
CSVSet = class(XData)
CSVLineSet = class(XData)
I am hopeful but concerned. Test. Innumerable failures.
Most of them say this:
2: Is element -- XSet:30: attempt to call a nil value (method 'card')
OK, back to basics. Here’s that test:
_:test("Is element", function()
local A = XSet()
A:addAt("Jeffries", "last")
A:addAt("Chet", "first")
_:expect(A:hasAt("Jeffries", "last"), "has").is(true)
_:expect(A:hasAt("Chet", "last"),"hasnt").is(false)
_:expect(A:isNull()).is(false)
_:expect(A:card()).is(2)
end)
Let’s look at XSet.
function XSet:card()
return self.data:card() or self:reduce(0, function(r,e,s) return r+1 end)
end
What is our data:
function XSet:init()
self.data = XGeneric()
end
function XGeneric:init()
self.contents = {}
end
function XData:card()
return nil
end
XGeneric is supposed to inherit card from XData.
Arrgh. I think this is a deep issue in how classes are implemented. I think that when a class is created, its superclass is copied at that time. Here’s the source code for class:
-- class
-- Use this function to perform your initial setup
function setup()
print("Hello World!")
X = class()
function X:init()
print("X init")
end
Y = class(X)
function Y:init()
self._base:init()
print("Y init")
end
x = X()
print(x:is_a(X))
print("---")
y = Y()
end
-- This function gets called once every frame
function draw()
-- This sets a dark background color
background(40, 40, 50)
-- This sets the line thickness
strokeWidth(5)
-- Do your drawing here
end
-- Class.lua
function class(base)
local c = {} -- a new class instance
if type(base) == 'table' then
-- our new class is a shallow copy of the base class!
for i,v in pairs(base) do
c[i] = v
end
c._base = base
end
-- the class will be the metatable for all its objects,
-- and they will look up their methods in it.
c.__index = c
-- expose a constructor which can be called by <classname>(<args>)
local mt = {}
mt.__call = function(class_tbl, ...)
local obj = {}
setmetatable(obj,c)
if class_tbl.init then
class_tbl.init(obj,...)
else
-- make sure that any stuff from the base class is initialized!
if base and base.init then
base.init(obj, ...)
end
end
return obj
end
c.is_a = function(self, klass)
local m = getmetatable(self)
while m do
if m == klass then return true end
m = m._base
end
return false
end
setmetatable(c, mt)
return c
end
It appears that the methods are copied there at the beginning. That’s saying to me that I have to define, not just the class itself, but its methods, before I can define a subclass.
I must test that. Revert again.
I add the hierarchy test back. Commit: failing hierarchy test.
Now to verify my theory:
_:test("hierarchy", function()
local a = A()
local b = B()
local c = C()
_:expect(a:is_a(A)).is(true)
_:expect(b:is_a(B)).is(true)
_:expect(b:is_a(A)).is(true)
_:expect(c:is_a(C)).is(true)
_:expect(c:is_a(B)).is(true)
_:expect(c:is_a(A)).is(true)
_:expect(c:yes()).is("yes")
_:expect(c:no()).is("no")
end)
I define no after the subclasses are declared:
A = class()
function A:yes()
return "yes"
end
B = class(A)
C = class(B)
function A:no()
return "no"
end
Test fails:
1: hierarchy -- TestHierarchy:24: attempt to call a nil value (method 'no')
OK, so we now know that all our classes must be totally defined before we can declare any subclasses of them.
Why didn’t moving the XSet tab ahead of XData work?
If I do that, I get a compile error on this, saying “attempt to call a nil value (XGeneric)”. I do not understand why this is a compile error.
function XSet:init()
self.data = XGeneric()
end
Ah. I get it. This is happening at compile time:
XSet.NULL = XSet()
NULL = XSet.NULL
NULL.addAt = function() return NULL end
NULL.card = function() return 0 end
NULL.elements = function() return pairs({}) end
NULL.hasAt = function() return false end
So it’s trying to create an XSet, so it needs XGeneric, etc etc. I’ll do this:
function XSet:init()
-- avoid compile error defining NULL
self.data = XGeneric and XGeneric() or nil
end
That runs. Also that was weird. I am so tempted to erase all this. I’ll tell folks to skip down to
HERE
OK, I think we’re back on track. Must reflect on what happened there. There’s a lesson to be learned, if I can.
Anyway I think the restrict test from long ago should work now.
_:test("People Tuple", function()
local csv = XSet:on(CSVSet(CSVnames, CSVdata))
local PT = Tuple()
for e,s in csv:elements() do
PT:add(e)
end
_:expect(PT:card()).is(500)
_:expect(PT:is_a(XSet),"is XSet").is(true)
local restrictor = XSet()
for _i,state in ipairs({"MI", "AK", "KY", "NE", "NY"}) do
restrictor:addAt(XSet():addAt(state,"state"),NULL)
end
local restricted = PT:restrict(restrictor) -- was csvRestrict
_:expect(restricted:card()).is(69)
end)
Yes, that runs fine now. All that hassle was because of defining NULL so that it had to access XGeneric, which wasn’t defined yet.
I extend the test a bit:
_:test("People Tuple", function()
local csv = XSet:on(CSVSet(CSVnames, CSVdata))
local PT = Tuple()
for e,s in csv:elements() do
PT:add(e)
end
_:expect(PT:card()).is(500)
_:expect(PT:is_a(XSet),"is XSet").is(true)
local restrictor = XSet()
for _i,state in ipairs({"MI", "AK", "KY", "NE", "NY"}) do
restrictor:addAt(XSet():addAt(state,"state"),NULL)
end
local restricted = PT:restrict(restrictor) -- was csvRestrict
_:expect(restricted:card()).is(69)
local j = restricted:elementProject(2)
_:expect(j:elementProject("first_name")).is("Josephine")
end)
Note that I found Josephine in the restricted set, still with her original scope, 2. That’s because restrict retains the original scope:
function XSet:restrict(B)
-- return all elements (a) of self such that
-- there exists a record (b) in B such that
-- b:subset(a)
return self:select(function(a,s)
return B:exists(function(b,_ignored)
return b:isSubset(a)
end)
end)
end
function XSet:select(predicate)
return self:reduce(XSet(), function(r,e,s)
return predicate(e,s) and r:addAt(e,s) or r
end)
end
That’s interesting. It may or may not be something we love, but in fact that’s how Dave defines it, I believe. There’s a chance he requires the scopes to match as well, but I don’t think that makes sense if it’s true.
Anyway, tests are green and commit: Tuples can support the restrict operation.
Well past time to sum up, it’s nearly 1 PM. Wow.
Summary
Well, a big diversion aside, this has gone well. The tests supported the work, the Tuple went in smoothly, and the tests even discovered the subtle and confusing error with NULL.
Reflecting on the NULL issue, I wasn’t terribly tired when it came up, so I won’t argue that I’d have been wise to stop earlier. I think it was going to be confusing until I finally confronted why that was a compile error, and that only after discovering that my inheritance wasn’t working.
I think it would have taken me just as long to find and fix the issue, even had I put it off until tomorrow. And it is rather subtle. I think we should define NULL differently, so that it doesn’t get built at compile time. Perhaps XSet should inherit from NULL. I’ll have to think about that.
I hope you skipped forward when I advised you to.
Anyway we’re at another good point, with the Tuple data type working, with rapid access to its contents. We’re moving in small steps toward indexing. And after that … maybe … some kind of expression tree or language.
What’s not to like? Tests take a bit longer to set up than I’d like. I tell myself again that we need a little work on the Making side of this app.
Will we improve that? I hope so, it’s a pain now.
See you next time!
-
re: “This here”. I do know proper English. I just do this kind of thing sometimes to entertain myself. I feel it makes me seem more human. I like to seem human. ↩