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.

# October 2009 Archives

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.