Today I plan to experiment with creating some form of expressions that might be optimized. I expect to stumble a lot. Come along, point, and laugh.

I’ll begin by creating a new Codea project, XPR, and connecting it to WorkingCopy. The project will of course include CodeaUnit.

Next, I rename the CUBase test, fix the foo bug, and now I am ready to go with these tests and no code:

-- RJ 20220105

function testXPRessions()

    _:describe("XSet Expressions", function()

        _:before(function()
        end)

        _:after(function()
        end)

        _:test("HOOKUP", function()
            _:expect("Foo", "testing fooness").is("Foo")
        end)

    end)
end

Unfortunately, now I have to figure out something to do. Here’s what I’ve got so far.

What It Is

I’m envisioning a new “language” here for defining sets using set operations. We’re working primarily on the internal form of that language. Suppose that the user interface is a command line sort of thing, where you could say something like

LET C = A RESTRICT B

I’m not going to work out that language first, because I want to focus on the internal form and the optimization thereof. Codea’s not a great place for a command line language, although we might be able to do it. But right now, we’re working on the internal form.

Starting Ideas

So far, most of the set operations have only one or two parameters. They have the receiver, the set to which we send the operation message, and usually another parameter, the input set:

C = A:Restrict(B)
N = C:card()

And, we generally save the result somewhere, as shown above, although we need not, if we just want to send another message to the result:

print(A:Restrict(B):elementProject("p"):elementProject("name"))

If the restrict above returned one element with a scope of “p” and that element contained an element with a scope of “name”, the code above would print the name. (I’ve not tested it, so read that as a rough description of what we can do.)

I’m envisioning the XPR objects as having an operation name, and a short list of parameters, in order of receiver, arg1, arg2, etc. An XPR “request” will consist of a well-formed list of these.

I think we’ll need a “symbol table”, a table of set names and the associated tests. I’m not sure quite how these things will hook together.

Let me be more clear: I have almost no idea how these things will hook together. I expect to discover how they want to hook together by building them and letting them tell me.

Perhaps an XPR request would look like this:

Restrict("A","B")
Save("C")

I’m not sure I love that: it’s going to build up a stack of results. Another alternative will be to say that every operation saves its result in a named set (we might provide names internally if needed):

Restrict A,B Into C

This would mean that an XPR operation would have an operation code, some number of input names, and an output name.

Let’s run with that idea a bit.

The Interpreter

Given a program in XPR, there are two phases, optimize, and do. Optimize rewrites the program into a better program (we hope), and do actually does the operations.

In our spike, for the “do” part, the interpreter, I think we’re going to want something that I rarely want: we’re going to want some mock objects that we can interrogate to be sure that the right thing happened.

Let’s just spike something, in the form of a test:

        _:test("Restrict", function()
            local operation = XPR{into="C", op="Restrict", arg1="A", arg2="B"}
        end)

I hope that’s somewhat clear. I’m just imagining that XPR creates its instances from a table of named parameters. I thought briefly about just a list but that seemed too error prone. Here we can do some checking if we want to.

Now we want to “do” this operation and then we want to know that what it did was send restrict to the set named “A” in the symbol table, passing the set named “B” as a parameter, and that it stored the result into “C”.

I’m not sure how to write a test for all that yet, so I’m going to code up a sample interpreter, to see what it might want to do.

        _:test("Restrict", function()
            local operation = XPR{into="C", op="Restrict", arg1="A", arg2="B"}
            Interpret{operation}
        end)

Here, I’m thinking there’s a class Interpret and … no, I don’t like that. Recast:

        _:test("Restrict", function()
            local operation = XPR{into="C", op="Restrict", arg1="A", arg2="B"}
            Interpreter{operation}:execute()
        end)

There’s a class Interpreter that takes a list of operations (in this case just one), and builds an instance that can respond to execute.

Now some code:

Interpreter = class()

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

function Interpreter:execute()
    error("I don't know how")
end

I expect the I don’t know how error. However, I am ahead of myself. I should have run the test sooner:

2: Restrict -- Tests:18: attempt to call a nil value (global 'XPR')

Right. Sure. Build that class too.

XPR = class()

function XPR:init(tab)
    local result = tab.into
    local op = tab.op
    local arg1 = tab.arg1
    local arg2 = tab.arg2
end

Test.

2: Restrict -- Tests:41: I don't know how

Right. Should I check the XPR instance for containing the right values? I don’t think so.

Now to implement the interpreter, just now it looks like a big switch statement somewhere. Let’s have XPR do the work.

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

I expect an error from xpr not knowing how to execute.

2: Restrict -- Tests:42: attempt to call a nil value (method 'execute')

Now we are nearly to the point of doing some work. I’ll write a sketch of what execute should do:

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

I intentionally misspelled “restrict” to check the error branch. I expect “no operation named restrict”. I don’t get that

1: Restrict -- Tests:34: attempt to concatenate a nil value (field 'op')

Hahaha. Someone said no need to test the creation method. I don’t see the error. Add some checks.

LOL. What a fool. I stored all the values into locals~

function XPR:init(tab)
    local result = tab.into
    local op = tab.op
    local arg1 = tab.arg1
    local arg2 = tab.arg2
end

Brilliant. Maybe I better have a sip of chai.

function XPR:init(tab)
    self.result = tab.into
    self.op = tab.op
    self.arg1 = tab.arg1
    self.arg2 = tab.arg2
end

I’m glad I never developed the habit of banging my forehead when I make a stupid error, I’d be dead of concussion by now.

Now can I have my error about not knowing “restrict”?

1: Restrict -- Tests:35: no operation named Restrict

Fix the bug:

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

Now the error will tell me that we don’t have a method named restrict. I run the test to keep my steps small.

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

We’re getting down to it. Here’s roughly what I’d expect that method to do in the interpreter:

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

Here I’ve imagined an object, Symbols, that contains all the named sets. Let’s gin one up.

SymTab = class()

function SymTab:init()
    self.symbols = {}
end

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

function SymTab:save(key,value)
    self.symbols[key] = value
end

And in Main, I’ll create the instance:

function setup()
    CodeaUnit_Detailed = false
    --CodeaUnit_Lock = false
    Symbols = SymTab()
    if CodeaUnit then 
        _.execute()
    end
end

I expect to fail looking for A.

1: Restrict -- SymTab:8: no symbol A

We need to populate the symbol table with something. In the real system, they’ll be XSets. Here, they are some kind of fake object that we’ll be able to interrogate based on what has happened to them.

We’ll call them XSet.

        _: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()
        end)

I figure they’ll know their names. Now I’ll get an error on unknown XSet:

1: Restrict -- Tests:14: attempt to call a nil value (global 'XSet')

Create the class.

XSet = class()

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

Error should be XSet not knowing restrict.

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

Know it.

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

Back to the operation:

        _: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("please restrict A with B")
        end)

I don’t really expect that result I do expect something a lot like it, but I wanted to see the test fail.

1: Restrict  -- Actual: restrict A with B, Expected: please restrict A with B

Remove the politeness.

        _: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)

Test should run and does. Commit: XPR restrict uses fake XSet to return identifiable restrict result.

Let’s go heads-up and look at what we have. We might like some of it.

Where Are We?

We have four little objects, Interpreter, XPR, Symbols, and XSet.

The intention with XSet is that it will have the exact calling sequences of the real extended set XSet, but that it is a fake object that records information in the sets it processes. (It may wind up recording information elsewhere. We’ll see.)

Symbols is the sole instance of SymTab class, and it is nothing but a mapping from a string name to an XSet.

Interpreter is a trivial object that takes an array of XPR instances and asks them to execute themselves.

XPR is an object that knows an operation, the name of a result set, and the names of its parameters, assumed to be sets. (But we’ll probably need to provide other possibilities, since we do have some set operations that take non-set parameters.)

XPR dispatches to a method for each operation and in the fullness of time, XPR will know how to execute any set operation (or any operation, really) and will generally do nothing more than fetch the relevant parameters (XSets) and run the XSet operation.

I believe that if I were to plug these objects (without the fake XSet) into the XSet2 project, the test would nearly run. It would have to be changed to provide real XSets as input, but the interpreter should run and do an actual restrict.

Yes But Where Are We?

I think we have a sketch of how our next level up in extended set theory might work. This code can run on top of XSet, and use it to do its work. And it can, in principle. run underneath a user interface that could accept commands from keyboard or file, as does, say, SQL.

The user interface will create lists of XPR, which all refer to names to be found in the Symbols, and which if executed will store new sets into Symbols. Presumably some of the commands from the user interface would display results for us, lest we just burn computer time to no purpose. We have NFTs for that.

Next Steps

I think this is a decent start. As the next step, we’ll probably build up the same optimizable query for which we have a test in XSet2, and start building up the additional information structures we need to represent indexes and other hints for optimization. I foresee some interesting decisions needing to be made.

For example, how much optimization should the XSet level perform? Should it be mostly data structures with suitable access, or should it make global changes such as discovery and use of indexes? Or should that level of optimization be left to the XPR level? I’m inclined to the latter, with the only XSet-level optimizations limited to rapid hasAt access and such.

Longer Term …

I don’t think we’ll try to turn this thing into a complete Extended Set system with command language and optimization and all that. Codea isn’t the right platform for such a thing. If I were really interested in a complete or nearly complete system, I’d be looking at Python, Ruby, or Swift … or some other even more modern language.

But we’re here to experiment, have fun, and learn.

I hope you’ll follow along. And, please, if you’d like me to write about other things, let me know. I often take requests.

See you next time!