Ward’s wiki explains that a ‘three-star programmer’ is ‘someone whose programs contain three consecutive dereference stars’. The implication, I believe, is that such code is too clever for its own good. I’m not sure whether three stars in a declarator count, but I’m hoping so.
This is a subject which has been on my mind for a while. It turns out to be much simpler than one might expect.
Firstly, let’s be clear about what the problem actually is. We want to be able to find out whether two objects are structurally equivalent. To have a clear idea of what this means, we’ll divide objects into atomic values and containers. An atomic value is just a thing with no interesting (for our purposes) internal structure. We can suppose that we’re given a predicate for determining whether two atomic objects are equal, and we’ll say that atomic objects are structurally equivalent if and only if they’re equal. A container, on the other hand, contains pointers to other objects. We’ll need to understand the structure of containers. In abstract, we can think of a container as being a partial function from atomic values to objects. Two containers are then structurally equivalent if and only if their domains are equal (so they have the same ‘shape’) and they map equal keys to structurally equivalent objects.
This is a recursive definition. If you translate it directly into code then you end up with a function which doesn’t always work. In particular, it won’t work on circular structures (e.g., $A$ points to itself).
Over the weekend I wrote a surprisingly simple function which solves this problem. I’ll present it in bits. It’s in Common Lisp, but hopefully that won’t be too scary.
