Proofs¶
Causal ordering¶
Formal model for diff and apply¶
This is similar to, but not exactly the same as, darcs’ theory of patches. Their theory is more developed with more “useful” results, but is also places more constraints on what valid patches are.
We try to be more general (less constrained), to demonstrate that the rest of our work depends on fewer assumptions than their model. For example, we don’t need a notion of “compose two patches into another patch”, and we only have partial notions of “applying n patches is equivalent to <n other patches”.
Objects of our investigation:
- S
- set of all possible states
- D
- set of all possible patches
- ▵ :: S x S → D
- binary operation: diff an earlier state with a later state; always succeeds
- · :: S x D → S ∪ {⊥}
- binary operation: apply a patch to a state; may fail, represented by ⊥
Axioms:
Zero diff
∀ s ∈ S: s ▵ s = 0
Diff-apply conversion
∀ s, t ∈ S; d ∈ D: s · d = t ⇔ d = s ▵ t
Apply cancellation
∀ s ∈ S; d, e ∈ D: s · d = s · e ≠ ⊥ ⇒ d = e
Note the converse is already true due to how = works.
Diff inverse
∀ s, t ∈ S: s ▵ t = -(t ▵ s)
Diff cancellation
∀ s ∈ S; d ∈ D: s · d ≠ ⊥ ⇒ s · d · -d = s
Note the converse is already true due to the definition of ·.
Weak commutativity (optional)
∀ o, a, b ∈ S: o · (o ▵ a) · (o ▵ b) = o · (o ▵ b) · (o ▵ a)
Lemmas: (TODO)
Zero apply (by A2, A1)
∀ s ∈ S: s · 0 = s
Diff collapse (by A2, A3)
∀ s ∈ S; d ∈ D: s ▵ (s · d) = d
Apply collapse (by A2, A3)
∀ s, t ∈ S: s · (s ▵ t) = t
Theorems:
Let 3-way-merge(o, a, b) = b · (o ▵ a)
First argument defines the identity element.
3-way-merge(o, a, o) = a (by L3)3-way-merge(o, o, a) = a (by A1, L1)If A6, then 3-way-merge is commutative under fixed o (by L3, A6)
∀ o, a, b ∈ S: b · (o ▵ a) = a · (o ▵ b)