14.6 Context relations and transformation variants

Causality and concurrency

• O1 --> O2 means that O1 had already been executed when O2 was generated.
• O1 || O2 means that neither O1 --> O2 nor O2 --> O1; the operations are concurrent.

Input and output states

Let in(O) be the state on which operation O is executed, and let out(O) be the state obtained after its execution. If S=in(O), then S+O denotes out(O).

Two operations may have the following context relations:

• context equivalent, written O1 <> O2, when in(O1)=in(O2);
• context convergent, written O1 >< O2, when out(O1)=out(O2);
• context serialised, written O1 >> O2, when out(O1)=in(O2);
• equivalent, written O1 ~ O2, when both O1 <> O2 and O1 >< O2.

These relations are contracts on the caller. The algorithms do not store states or test the relations at run time.

IT, IT2, ET and ET2

The four transformation variants move an operation between the edges of one transformation diamond. Start with concurrent, context-equivalent operations O1 and O2. Inclusion transformation produces O1'=IT(O1,O2) and O2'=IT(O2,O1):

IT

Transforms one of two context-equivalent operations forward past the other.

IT2

Transforms the first operation of a context-serialised pair forward so that it converges with the second.

ET

Transforms the second operation of a context-serialised pair backward so that it becomes context equivalent to the first.

ET2

Transforms one of two context-convergent operations backward so that it precedes the other.

The eight directions around the diamond

Information-preserving merge

An information-preserving merge is compatible with IT and ET. It is not sufficient for the merged operation merely to have the same immediate effect as the original sequence; it must behave as that sequence in later transformations.

Given context-serialised operations [O1,O2], define O1 ⊕ O2 as the merge of O1 and O2 into a single composite operation.

We require the following properties:

MP1

(O₁ ⊕ O₂) ⊕ O₃ = O₁ ⊕ (O₂ ⊕ O₃)   (associativity)

MP2

S + [O₁ O₂] = S + (O₁ ⊕ O₂)

MP3

IT(O₁, O₂ ⊕ O₃) = IT(O₁, [O₂, O₃])

MP4

IT(O₁ ⊕ O₂, O₃) = IT(O₁,O₃) ⊕ IT(O₂, IT(O₃, O₁))

In-place functions

DualIT, Transpose and Merge are in-place functions.

DualIT(O1,O2)

Given O1 <> O2, mutate both arguments so that O1'=IT(O1,O2) and O2'=IT(O2,O1), for which O1 >> O2', O2 >> O1' and O2' >< O1'.

Transpose(O1,O2)

Given O1 >> O2, mutate both arguments to replace the sequence [O1,O2] by [O2',O1'], such that O2' >> O1' and applying either sequence has the same result.

Merge(O1,O2)

Given O1 >> O2, compute O1 ⊕ O2 in place, replacing O1 by the composite operation and consuming O2.

The first two functions could instead be implemented using pure IT and ET functions that construct and return new operations:

void DualIT(Operation& O1, Operation& O2)
{
    Operation newO1 = IT(O1, O2);
    Operation newO2 = IT(O2, O1);
    O1 = newO1;
    O2 = newO2;
}

void Transpose(Operation& O1, Operation& O2)
{
    Operation newO2 = ET(O2, O1);
    Operation newO1 = IT(O1, newO2);
    O1 = newO1;
    O2 = newO2;
}

Direct implementations of DualIT and Transpose can also use a more efficient decomposition than separate calls to IT and ET. They can process a corresponding pair of components once and update both operations from the result. Transpose can likewise update both sides during one coordinated decomposition instead of materialising the ET result and traversing it again for IT. For example, when IT shifts text insertion positions to the right, DualIT needs to compare the insertion positions only once. If the positions are equal, it needs to compare the site identifiers only once. Two separate IT calls would repeat those comparisons while computing the two sides of the same transformation diamond.

The definitions above preserve the void, in-place interfaces of DualIT and Transpose, but the pure transformations construct complete result operations before assigning them back to the arguments. For substantial operation data structures, constructing those results can require considerable copying and cause excessive heap allocations. Direct in-place implementations can share work and reuse existing storage, which can provide better performance.