XST 39: Wake Up to Trees

Bill Wake is trying to get me to think in terms of trees. I don’t want to, but he does have some good ideas. Thanks, Bill!

Bill Wake tweeted in reply to my posting of yesterday:

Cool to see this coming. When you have “A:Restrict(B):elementProject(“p”):elementProject(“name”)” - is it the case that today that causes a direct evaluation. Am I right that these will instead turn into nodes, so the result will be a tree of nodes? …

So you’ll have the opportunity to rearrange the tree, then evaluate it. Can the nodes do their own evaluation still, or will everything go through the interpreter? (In an OO language nodes could do it, but I’m not so clear on Codea’s model.)

I replied:

Well, it’s not a tree exactly. List of ops with parms. Ops can execute but at this writing the ops are not one per setup, just a thing that knows it’s op is “restrict”. Otoh … a Lua method name is just a string, so … 😀

Now Bill has been trying to get me to do this thing with trees of operators for ages now, and I mostly don’t want to, because it seems to me to be a bigger bite than I’m willing to take all at once, and because I see issues that I don’t know how to deal with.

For example, optimization will amount to “rearranging the tree”, as Bill puts it, and I’m not at all clear on how to recognize patterns in a general tree. I’m a Smalltalker, Jim, not a Lisper.¹

Unfortunately, when I go to bed I think about this stuff, and when I am just waking up, I think about this stuff, and I do have some ideas that are not unlike what Bill is saying. Which is to say, he sort of got through to me, but this is my article and I plan to take as much credit as I can.

Let’s reflect on what we have now.

What DO We Have Now?

I haven’t looked, but if I recall correctly, what we have is the idea of an XPR, which represents a single set operation with inputs and outputs. (OK, I looked.) It has a result, and as many parameters as are required (up to two at the moment), and the parameters and result are all names, which are looked up in the symbol table, cleverly named Symbols.

That was enough to get me moving, and these days that’s all we’re looking for.

However.

That “design”, to give it a better name than it deserves², requires that all sets be given names and saved in the symbol table. However, set operations don’t want names, they want sets, and they don’t produce names, they produce sets.

Digression, small but important.

We’ll come back to that but let’s also recall my really not very clever at all scheme for interpreting the XPR structure:

function XPR:execute()
    if self.op == "Restrict" then
        self:restrict()
    else
        error("no operation named "..self.op)
    end
end

A method name in Lua is just a string, looked up in the object. Therefore we can write this instead:

function XPR:execute()
    local LC = string.lower(self.op)
    if self[LC] then
        return self[LC](self)
    else
        error("no operation named "..self.op)
    end
end

That works for now, but it isn’t robust. It’ll fail on any methods with mixed upper and lower case.

Let’s change the rules and require the method name and the name in the XPR to match.

function XPR:execute()
    if self[self.op] then
        return self[self.op](self)
    else
        error("no operation named "..self.op)
    end
end

Now I need to change the tests a bit:

        _:test("restrict", function()
            Symbols:save("A",XSet("A"))
            Symbols:save("B",XSet("B"))
            local operation = XPR{into="C", op="restrict", arg1="A", arg2="B"}
            _:expect(operation.op).is("restrict")
            Interpreter{operation}:execute()
            local C = Symbols:at("C")
            _:expect(C.name).is("restrict A with B")
        end)

Green. Commit: XPR looks for op in itself and just calls the function if present.

You should be asking me why I did that, and why I did it now: surely we don’t need it, and we’re about to change things anyway.

That’s true. I did it because I want to drill the idea into my mind, and I want to express that idea in the code, because it seems potentially very valuable, in that it will mean that I don’t need to build some kind of dispatch table: the object itself can serve as one.

And I did it now rather than write a card for it, because now, with the idea in my head, is the best time to get it into the code.

End Digression

More Like XSets? More Like Trees?

XSet operators generally take sets as input (and occasionally other things) and generally produce a set as output (and occasionally other things). That makes me think that our XPR operators, which surely represent set operations, should be the same. But now, they expect names and produce all their effects in the Symbols table.

What if there were two new XPR operators to access Symbols:

setNamed(aName), which returns the set of the given name, as stored in Symbols;
saveAs(aName, aSet), which saves the set in Symbols with the given name.

And then, what if other XPRs, like restrict expected, not names, but actual XSets as their inputs, and produced, not names, but actual XSets as their output?

Then if we had some series of operations that passed a set to another set, instead of generating names and tucking things away into Symbols, we could just string them together. Kind of like–oh no–a tree.

I think I have to try this just to prove that Bill was entirely, um, well, right. Rewrite the test and let the chips fly.

Set Naming Operators

Here’s the rewritten test:

        _:test("restrict", function()
            Symbols:save("A",XSet("A"))
            Symbols:save("B",XSet("B"))
            local receiver = XPR{op="setNamed", arg1="A"}
            local restrictor = XPR{op="setNamed", arg1="B"}
            local operation = XPR{op="restrict", arg1=receiver, arg2=restrictor}
            local save = XPR{op="saveAs",arg1="C", arg2=operation}
            Interpreter{save}:execute()
            local C = Symbols:at("C")
            _:expect(C.name).is("restrict A with B")
        end)

The basic idea here was to define two sets that already exist, A and B, going into the test. then we produce the sets with two instances of setNamed, which we make the two parameters of our restrict, which becomes the input to our saveAs operation. We execute the saveAs, expecting it to execute the whole tree to get the result.

I can’t imagine that that’s going to work, ever. But we’ll run the test until we give up. Here and now I expect an error not understanding saveAs, probably, since that’s the one we execute:

1: restrict -- Tests:41: no operation named saveAs

Easy. Implement saveAs:

function XPR:saveAs(name,xpr)
    local result = xpr:execute()
    Symbols:save(name, result)
end

We’ve formed the convention that execute returns the result of whatever the XPR is.

Now I expect that we’ll get into `restrict, which looks like this:

function XPR:restrict()
    local receiver = Symbols:at(self.arg1)
    local parm = Symbols:at(self.arg2)
    local result = receiver:restrict(parm)
    Symbols:save(self.result, result)
end

The ats are going to error “no symbol”. But no:

1: restrict -- Tests:53: attempt to index a nil value (local 'xpr')

That happened because of this:

function XPR:execute()
    if self[self.op] then
        return self[self.op](self)
    else
        error("no operation named "..self.op)
    end
end

We’re not passing in any of the arguments. Fix:

function XPR:execute()
    if self[self.op] then
        return self[self.op](self,self.arg1,self.arg2)
    else
        error("no operation named "..self.op)
    end
end

1: restrict -- SymTab:8: attempt to concatenate a table value (local 'key')

Oops. That’s here:

function SymTab:at(key)
    return self.symbols[key] or error("no symbol "..key)
end

The key we passed in was a table. Yes, that’s surely still the restrict operator being confused about what it’s supposed to do.

Now let me note that Ted M. Young would be after me here, because I’m not clear in my mind as to just what’s going on. I’m letting the tests guide me, and not my brain. My excuse is that the tests know what’s going on, and I don’t. I’m OK with that.

I’ll just rewrite this:

function XPR:restrict()
    local receiver = Symbols:at(self.arg1)
    local parm = Symbols:at(self.arg2)
    local result = receiver:restrict(parm)
    Symbols:save(self.result, result)
end

function XPR:restrict()
    return self.arg1:restrict(self.arg2)
end

Ops assume now that they have the input they need, and we now need sets, and return sets in our set ops.

Run the tests.

Oh darn:

1: restrict -- Tests:46: attempt to call a nil value (method 'restrict')

I think we need to execute all our arguments.

function XPR:restrict()
    local receiver = self.arg1:execute()
    local restrictor = self.arg2:execute()
    return receiver:restrict(restrictor)
end

This fails because we don’t have setNamed:

1: restrict -- Tests:41: no operation named setNamed

function XPR:setNamed(name)
    return Symbols:at(name)
end

With this addition, the test runs green. Do you believe it? I don’t. I need to see more. Let me change the test to force a failure:

...
            Interpreter{save}:execute()
            local C = Symbols:at("C")
            _:expect(C.name).is("like restrict A with B")

Run tests

1: restrict  -- Actual: restrict A with B, Expected: like restrict A with B

How did that actual string get generated? I don’t recall. Remember that our XSet is a dummy class.

function XSet:init(name)
    self.name = name
end

function XSet:restrict(anXSet)
    local result = XSet("restrict "..self.name.." with "..anXSet.name)
    return result
end

And our original sets gave themselves those names:

        _:test("restrict", function()
            Symbols:save("A",XSet("A"))
            Symbols:save("B",XSet("B"))

If I were to rename the set itself, the test would fail in a new and interesting way:

        _:test("restrict", function()
            Symbols:save("A",XSet("A"))
            Symbols:save("B",XSet("B B King"))

1: restrict  -- Actual: restrict A with B B King, Expected: like restrict A with B

OK, I’m convinced, this ran all the way through as intended.

Fix the test back to working.

        _:test("restrict", function()
            Symbols:save("A",XSet("A"))
            Symbols:save("B",XSet("B"))
            local receiver = XPR{op="setNamed", arg1="A"}
            local restrictor = XPR{op="setNamed", arg1="B"}
            local operation = XPR{op="restrict", arg1=receiver, arg2=restrictor}
            local save = XPR{op="saveAs",arg1="C", arg2=operation}
            Interpreter{save}:execute()
            local C = Symbols:at("C")
            _:expect(C.name).is("restrict A with B")
        end)

Test is green. Commit: Add setNamed and saveAs XPRs, modify restrict to expect XSets, not names, as new convention.

Where Are We?

That was a major design change. We moved from a scheme where our operators look up set values in a symbol table, to one where the main operators expect that their parameters are all executable set operations, and just execute them.

In the old days of XST at Comshare, we thought of the set operations being a series of straws and the metaphor was that we would suck on a straw to pull up its data, much as I sip on my iced Chai, here to my right. Excuse me while I do just that.

Nom.

I think our execute metaphor is likely pretty much the same idea but a bit more computer sciency and elegant.

What have we done here? Well, we’ve almost invented LISP, which doesn’t entirely please me, but there we are. We have built a list structure in our test:

saveAs
    "C"
    restrict
        setNamed
            "A"
        setNamed
            "B"

We could write that as

(saveAs "C" (restrict (setNamed "A") (setNamed "B")))

If we were that kind of person. And, to tell the truth, that’s not a bad notation. I wonder if I could parse it well enough. I wonder if anyone has ever implemented LISP in Lua …

But for now …

Sufficient Thereto is the Good of the Day

Not quite an accurate quote, but an accurate feeling on my behalf. This has been a righteous little change. It’s not really more complicated, despite the fact that we just implemented a recursive version of our interpreter that used to think of itself as a loop. Which reminds me. We probably don’t need our interpreter at all, do we?

Instead of this:

        _:test("restrict", function()
            Symbols:save("A",XSet("A"))
            Symbols:save("B",XSet("B"))
            local receiver = XPR{op="setNamed", arg1="A"}
            local restrictor = XPR{op="setNamed", arg1="B"}
            local operation = XPR{op="restrict", arg1=receiver, arg2=restrictor}
            local save = XPR{op="saveAs",arg1="C", arg2=operation}
            Interpreter{save}:execute()
            local C = Symbols:at("C")
            _:expect(C.name).is("restrict A with B")
        end)

Can’t we just say this:

        _:test("restrict", function()
            Symbols:save("A",XSet("A"))
            Symbols:save("B",XSet("B"))
            local receiver = XPR{op="setNamed", arg1="A"}
            local restrictor = XPR{op="setNamed", arg1="B"}
            local operation = XPR{op="restrict", arg1=receiver, arg2=restrictor}
            local save = XPR{op="saveAs",arg1="C", arg2=operation}
            save:execute()
            local C = Symbols:at("C")
            _:expect(C.name).is("restrict A with B")
        end)

Tests run, therefore we can. Also therefore, we can remove the entire Interpreter class:

Interpreter = class()

function Interpreter:init(tab)
    self.tab = tab
end

function Interpreter:execute()
    for _i,xpr in ipairs(self.tab) do
        xpr:execute()
    end
end

Commit: Interpreter no longer needed.

I think that if we go back and look at what Bill was suggesting yesterday is exactly what happened. Silly me, I thought it was too hard to do that in one step. Maybe it wasn’t. Today, it wasn’t: we could have started over, but doing it incrementally kept us on track.

So Bill was right, though as always, it wasn’t so much that he said in so many words, do this not that. Bill’s gentle that way. He just asks questions and expresses ideas, and if you pay attention, you get to learn stuff.

Very cool. Thanks, Bill.

I’ll see you all (!) next time!

Leonard McCoy, probably. ↩
Sketch is more like it. ↩