FAFO on GitHub

If I’m going to get serious about this Extended Set Theory thing, a tiny bit of design thinking seems to be in order.

Hello, friends!

After re-retiring to bed at oh-dark-thirty, I thought a bit about pushing the XST stuff forward, and what it means for the design. I recall Dave Childs saying, repeatedly, “it all comes down to ordered pairs”, which I don’t think I ever understood or found useful, but along those lines, I do think that in my understanding it all comes down to element-scope, which can be seen as an ordered pair, and is in fact implemented as an 2-tuple, which is Python for “ordered pair”. What it really all comes down to, I think, are two things:

Membership
We need, for any set A, element a and scope s, to be able to answer whether element a is a member of A under scope s:

Is a ∈s A?

Iteration
We need, I believe, to be able to produce all the elements and scopes of any set, so that we can apply our various set-theoretic functions to the set. There could be exceptions to this rule. For example, we could, in principle, support an “infinite” set, which could produce elements forever but we wouldn’t have time to wait. I plan not to concern myself with that now, or possibly ever. Still, you never know.

Generally speaking, we need to be able to produce the elements and scopes.

Every other set operation, project, restrict, select, union, intersection, whatever, can be and should be expressed in terms of membership and iteration. That said, certain sets might implement those operations differently based on things that the specific kind of set knows. For example, the null set might answer includes directly with False.

So we are facing a design issue, or issues, regarding how we are going to structure things so that set operations will run correctly regardless of the specific implementation of a given set’s data structure.

As things stand now, key issues are delegated to the XSet’s contents member:

class XSet:
    def __init__(self, a_list):
        def is_2_tuple(a):
            return isinstance(a, tuple) and len(a) == 2

        self.contents = frozenset(a_list)
        if not all(is_2_tuple(a) for a in self.contents):
            raise AttributeError

    def __eq__(self, other):
        if isinstance(other, self.__class__):
            return self.contents == other.contents
        else:
            return NotImplemented

    def __repr__(self):
        if self == self.null:
            return "∅"
        else:
            return f"XSet({self.contents})"

    def __hash__(self):
        return hash(self.contents)

    def __iter__(self):
        return self.contents.__iter__()

    def __bool__(self):
        return bool(self.contents)

I believe that this means we could replace the contents with some other object instead of the frozenset we usually put there, and the tests would all still run. One question is how might we do that. Suppose we did have an alternative implementation of a set, even if it was a set with certain limitations. Perhaps it is known to be an n-tuple of elements, so its scopes are 1..n, and so its data structure could be a simple tuple of the element part, and we’d produce the scope part on the fly.

As things stand, there’s no way to create an XSet with anything other than the frozenset default structure. So we’ll need to devise some additional factory methods that produce the desired structure, and change __init__ to just tuck whatever it is away in contents. We might rename contents to implementation.

However, if we just do that, our set operations will still use the default iterative behavior. In the case of the n-tuple set, the question of whether an element is in the set becomes an array lookup, which is nice, but what if we had a structure that could do select operations more quickly, or intersections or something?

We’ll want, somehow, for our set operations to defer down to the implementation, if it can do the thing, and to use the default operation if the implementation doesn’t know a better way. Maybe we pass the default object down so that the implementation object can call back?

I don’t know. I’ll have to think about that and surely try a couple of ways to see what seems right. We could always just look in the implementation’s attributes, but it seems rude to go rummaging through other objects’ stuff, looking for things. Anyway, there will surely be a way. I’ll ask my friends for ideas, and if you have any, please do toot me up.

Interrupted

The above was written around 3 PM Friday, at which point I was interrupted for a conversation and never came back. Well, never came back until now. In the meantime, I asked my peers on a code Slack for ideas and my old nemesis Bill Caputo suggested an approach that is worthy of note:

Off the top of my head: pass message and give receiver a way to reject it (eg via return value, exception, some sort of state flag in the message, etc) and only handle it if that happens. Main benefit: the message and recipient remain ignorant of xset’s existence.

This is, it seems to me, a clear and simple way to deal with my concern. What is striking about it is that I did not think of it myself. Why? Well, one possibility is that I’m not very bright. We must always keep that in mind. But I think in this case, I was thinking so deeply about how weird objects might be wired in, how they might work, what they might be good for … that a simple idea would not fit in my mind at the time.

What we see here is one of the biggest benefits of pair or ensemble programming: we get more good ideas, closer to when we need them. For any of us, there is an even larger benefit: it is more fun to work together than it is to work separately. I know that many people believe they would not like pairing or mobbing, and I also know that “science” has determined that a large percentage of people who try pairing do like it after all. Their image of it and the thing itself are quite different.

But I’m not here to tell you to pair or work in ensemble. I am here to show you what I do, tell you what I experience, and leave it to you to decide what you should do.

For now, I’ll wrap up this, yesterday’s article, and then start on today’s.

Summary

I plan to get serious about XST for a while. Might generate a new tag to avoid contamination with the earlier 40-odd odd articles. Things to work on include:

  1. Alternate internal storage structures that are optimized for some purpose;
  2. One or more “little languages” or other ways of controlling things without actual coding;
  3. Discovering useful ways of doing things with XST, and with Python;
  4. Observing my mistakes, and the occasional thing that I do well, and figuring out what I can learn from them.
  5. Entertaining myself, as my primary audience, and the rest of you to the extent that I can.
  6. You tell me …

See you next time!