About This Site
> Concepts for Persistent Objects
Language Design Principles
Instances and Copies
Branches and Growth Points
> Synchronization and Merging
Relation to Commutative DiagramsIt's clear that synchronization and merging have some relation to commutative diagrams, but what is it? Let's start by looking at the following figure.
The natural thing to do, here, is to ask whether A commutes with B. To even ask the question, though, we have to think of A and B as functions acting on some space—the space of potential object versions—and then we're forced to realize that we don't even know what the functions are, that we only know their values at a single point, the original version.
In general, it's impossible to determine a function from its value at a single point. However, if the space the function acts on has some structure, and the function is known to be natural (in some sense), then it's often possible to make a good guess by pattern recognition. For example, knowing that the string abc maps to abd, we might reasonably guess that pqrs would map to pqrt, i.e., that the function is “increment the last letter of the string”. On the other hand, as discussed in Analogies and Roles in Human and Machine Thinking, there are other more or less plausible choices.
Although it's interesting to think about determining the functions A and B, we don't actually need to do so. For example, for unidirectional synchronization into the left-hand branch, all we need to do is determine how B acts on a single point, the left-hand version. In other words, we need to complete a single analogy: the original version is to the right-hand branch as the left-hand branch is to … what? For bidirectional synchronization we need to complete two analogies, and for merging we need the two completed analogies to agree.
So far I've been talking as if we can't even think about synchronization or merging unless the functions A and B commute, and of course that's not quite right. For one thing, in synchronization it's not strictly necessary that the synchronized versions should be the same. It may be a good idea, but it's not absolutely necessary. For another thing, the synchronization or merging of versions doesn't have to be mathematically exact, it can involve judgement on the part of the person doing it. I don't have much to say about how to exercise judgement, though, so I'll stick to mathematically exact things.
Another interesting fact is that even when A and B commute, the merged version may not make sense. Suppose, for example, we have an original code fragment
String a, b;
along with two branched versions.
String a, b;
It's clear what the merged version should be, but unfortunately it won't even compile.
int a, b;
I'm not sure what to make of this. My best guess right now is that it means I'm making a mistake by thinking of the space of potential object versions as being simply the space of all text files.
Synchronization and Merging
@ September (2000)