FAFO 13: Hey!

FAFO on GitHub

In which, I show you what I’m dealing with, and mention an insight.

Source -> Insight

Just to give you a sense of what I’m dealing with, here’s an example of a paper about Extended Set Theory from Dave Childs. For your interest and delectation, take a look at Definition 7.2, Restriction, on page 4. It is the full-boat all-singing all-dancing definition that Childs was using at the time of that document’s writing, in 2018. I am pretty sure that he had a simpler less powerful one earlier on.

As you see, I have that marked for “STUDY”. Most recently, I worked out some simple examples last night, and finally came to some understanding of what the thing does, in particular the purpose of the sigma 𝞼 that appears there. “Q, restricted by A, under the influence of sigma”. Here’s what I think I understand:

If sigma is not present, all the scopes are treated “as is”, ignored by the comparison part. With sigma in effect, the elements of the restricting set A are renamed on the fly, according to the set 𝞼, as in Definition 6.3, Rescope by Element. Suppose the set Q had elements with scope “last”, and that the set A had elements with scope “lastname”, and we wanted to match on “last” vs “lastname”.

According to 6.3 and 7.2, if 𝞼 contains { …, “last”^{“lastname”}, … }, a rename will happen (on the fly) and the match will be made “last” vs “last” as we desire.

Whee, is about all I can say about that. Except that the notation there at the end made me think. The very last bit in 7.2, that says

s^\𝝈\ ⊆ w

If s is a subset of w, then s is a set, not a simple atomic value like 3 or “last”. And certainly, just as the element part can be a set, the scope can be a set as well. But I’ve never, to my recollection, considered making the scope a set, and I began to wonder why one might. And I got an idea. Consider this set, with an ordered pair as the scope:

{ …, “hendrickson^{<“last”, “string”>}, 10000^{<“salary”, “int”>}, … }

I don’t know what Childs had in mind¹ for Restrict, or for the general case of sets as scopes, but what we can see here is that we could, with some care, put symbolic information into the scope of an atom, in a record, such as the data type of that item, or, well, really anything.

The matching rule is one-sided, in that in A the scope set has to be a subclass of the scope in Q, which means that if the records all included their data type, as in the example sketched just above, the A set (which I would have called the query set, except that Childs called the other set Q), anyway the A set could just look for

{ …, “hendrickson^<“last”>, … }

and that would be OK. What would not be OK, if I read this correctly, would be to say just:

{ …, “hendrickson^“last”, … }

because “last” is not a subset of <“last”, “int”>. It’s almost an element (wrong scope) but since “last” is not a set, it is not a subset of any set.

So. Lots of head-scratching, and around 40 years after I started thinking about XST, I have a thought that either I’ve never had before, or that I had forgotten amid all the other things I remember and all the even more other things that I have forgotten.

Upshot

As a result of this insight / observation, I am even more focused om the notion of trying to implement this little XST thing “right”, so that, among all its other quirks and foibles, it can readily represent arbitrary “curliness”, with sets of sets of sets possible without technical limitation. (Except, possibly, for recursive stack overflow).

I am a bit concerned about the present implementation, as I mentioned this morning. If we think of how the theoretical definitions go, it’s all ∃ this ∀ that ∈_x other thing. As such, I think we probably need corresponding methods on our XSets, which means, among other things, that they have to be iterable (which, so far, as they are frozenset instances, they are).

We’ll see. Right now all this is taking place in a very experimental PyCharm project, and we can always move to a new one, or gut this one retaining only the good bits, as we may find desirable.

For now, let’s fix some issues. Those were:

• we need a null set constant
• Atom should be invisible to XSet users
• restrict code needs improvement
• duplicates can occur in restrict output

XSet.null = XSet([])

Stuffing this at the end of the XSet definition does the job. I have not been able to figure out how to define a class variable that refers to the set it is part of in any other way. I’ll change my tests to use it.

That works. Life is good. Commit: provide XSet.null.

Let’s improve this code next:

    def restrict(self, other):
        if not isinstance(other, self.__class__):
            return NotImplemented
        result_atoms = []
        for candidate_atom in self.contents:
            for check_atom in other.contents:
                if check_atom.element.is_subset(candidate_atom.element):
                    result_atoms.append(candidate_atom)
        return frozenset(result_atoms)

I replace that with this:

    def restrict(self, other):
        if not isinstance(other, self.__class__):
            return NotImplemented
        return frozenset([candidate_atom for candidate_atom in self.contents
                          if any([check_atom.element.is_subset(candidate_atom.element)
                                  for check_atom in other.contents])])

Is that better? Well, I think it is less likely to create real lists, more likely to just run as iterators. Does it really do that? I honestly do not understand enough about Python internals to be sure, but I’m sure that the previous implementation is creating a real list.

I change to this:

    def restrict(self, other):
        if not isinstance(other, self.__class__):
            return NotImplemented
        return frozenset((candidate_atom for candidate_atom in self.contents
                          if any((check_atom.element.is_subset(candidate_atom.element)
                                  for check_atom in other.contents))))

Now there are no square brackets, so I am sure these are all iterators. I think this is a good thing.

But wait. That’s still not right. It’s returning a frozenset, not an XSet.

I improve a test and make it work:

    def test_xset_restrict(self):
        ron = XSet([Atom("jeffries", "last"), Atom("ron", "first"), Atom("boss", "job")])
        chet = XSet([Atom("chet", "first"), Atom("hendrickson", "last"), Atom("boss", "job")])
        hill = XSet([Atom("hill", "last"), Atom("geepaw", "first"), Atom("serf", "job")])
        personnel = XSet.classical_set([ron, chet, hill])
        boss_record = XSet([Atom("boss", "job")])
        boss_set = XSet.classical_set([boss_record])
        bosses = personnel.restrict(boss_set)
        assert isinstance(bosses, XSet)
        assert Atom(ron, XSet.null) in bosses
        assert Atom(chet, XSet.null) in bosses
        assert Atom(hill, XSet.null) not in bosses

    def restrict(self, other):
        if not isinstance(other, self.__class__):
            return NotImplemented
        return XSet((candidate_atom for candidate_atom in self.contents
                          if any((check_atom.element.is_subset(candidate_atom.element)
                                  for check_atom in other.contents))))

I wonder if a type annotation would help here.

    def restrict(self, other) -> XSet:
        if not isinstance(other, self.__class__):
            return NotImplemented
        return XSet((candidate_atom for candidate_atom in self.contents
                          if any((check_atom.element.is_subset(candidate_atom.element)
                                  for check_atom in other.contents))))

I had to from __future__ import annotations for that to work, but in fact PyCharm now warns me if I am not returning an XSet. I think I like this idea. I’ll play with it further as time goes on.

Commit: improve restrict code, including expected XSet result annotation.

Now what?

• Atom should be invisible to XSet users
• we need a null set constant
• restrict code needs improvement
• duplicates can occur in restrict output

I think I’ll save that one for tomorrow. Let’s sum up.

Summary

We seem to have a restrict that will work on properly configured sets. We should check to see what it does with improper input. The tests for simple proper input are, I think, pretty solid.

We will likely not undertake the advanced Definition 7.2 version unless we really needed the scope mangling. We might want to implement the basic scope-mangling operations as independent operations.

Where am we going with this thing? How far will we push it? I honestly don’t know, and don’t remember why I stopped last time. What is it good for? Absolutely nothin! Probably. But I do enjoy it.

In other experiments with this we actually did implement for-every and there-exists, and that might be an interesting way to go. Python is somewhat opposed to lambdas, but it still might be useful.

And, we need some additional creation methods that hide the Atoms from “users”. We might try the cascade, return self addition method for creating records.

I wonder if there is anything actually useful that could be done with this thing.

Anyway, see you next time!