Skip to main content

logicaffeine_proof/
trace_determinism.rs

1//! The concurrency tie made **literal**: *determinism = contractibility*, on a real machine.
2//!
3//! `proof_rewrite` showed that a refutation's independent steps commute, and that the space of
4//! reorderings is a contractible `CAT(0)` cube complex. That is not an analogy to concurrency — it is
5//! the *same* object. Here we run an actual tiny shared-memory machine and prove the identification on
6//! the nose:
7//!
8//! - Two operations' **commutation 2-cell** exists (the square commutes in the cube complex) **iff**
9//!   running them in both orders yields the same state — and the structural test for that is exactly
10//!   **Bernstein's conditions** (neither writes what the other reads or writes), the independence
11//!   relation of the trace monoid.
12//! - A set of pairwise-independent operations is **deterministic** — every one of the `n!` schedules
13//!   produces byte-identical state (we run them all) — and that is **exactly the contractibility**
14//!   (`χ = 1`, the cube condition) of the same [`ProofPoset`] the proof tower uses.
15//! - **Cooperative ≡ work-stealing**: two schedulers over independent tasks agree byte-for-byte because
16//!   both are linear extensions of one contractible trace complex, joined by commutation 2-cells. This
17//!   is the repo's `diff_cooperative_eq_workstealing` as a homotopy — the certificate of agreement *is*
18//!   the 2-cell path.
19//! - A **data race** is a *missing* 2-cell: a write-write conflict makes the ops dependent (no square),
20//!   and the two orders genuinely diverge. Race detection falls out of the homotopy.
21//!
22//! So the homotopy theory of proofs and the determinism theory of concurrency are one theory, and this
23//! module is the bridge with the machine actually running underneath it.
24
25use crate::proof_rewrite::{permutations, ProofPoset};
26
27/// A shared-memory operation: read some cells, then write one cell with a pure function of the reads
28/// (in `reads` order). The minimal unit that can race.
29#[derive(Clone)]
30pub struct Op {
31    pub reads: Vec<usize>,
32    pub write: usize,
33    pub f: fn(&[i64]) -> i64,
34}
35
36impl Op {
37    /// Apply the operation to mutable shared state.
38    pub fn apply(&self, state: &mut [i64]) {
39        let args: Vec<i64> = self.reads.iter().map(|&r| state[r]).collect();
40        state[self.write] = (self.f)(&args);
41    }
42}
43
44/// **Bernstein's conditions** — `a` and `b` commute (are independent) iff neither writes a cell the
45/// other reads or writes. This is the independence relation of the trace monoid: precisely the pairs
46/// whose commutation square is a 2-cell in [`ProofPoset`]. (Read–read sharing is fine; reads commute.)
47pub fn bernstein_independent(a: &Op, b: &Op) -> bool {
48    a.write != b.write && !b.reads.contains(&a.write) && !a.reads.contains(&b.write)
49}
50
51/// Run a schedule (a sequence of op indices) from an initial state, returning the final state.
52pub fn run(ops: &[Op], schedule: &[usize], init: &[i64]) -> Vec<i64> {
53    let mut state = init.to_vec();
54    for &i in schedule {
55        ops[i].apply(&mut state);
56    }
57    state
58}
59
60/// The commutation poset of a set of concurrent operations: independent pairs (Bernstein) are left
61/// unordered — their commutation is a 2-cell — and conflicting pairs get a program-order edge (lower
62/// index first), which is the only way to keep a deterministic execution. The trace's cube complex.
63pub fn trace_poset(ops: &[Op]) -> ProofPoset {
64    let mut edges = Vec::new();
65    for i in 0..ops.len() {
66        for j in (i + 1)..ops.len() {
67            if !bernstein_independent(&ops[i], &ops[j]) {
68                edges.push((i, j));
69            }
70        }
71    }
72    ProofPoset::new(ops.len(), &edges)
73}
74
75#[cfg(test)]
76#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/trace_determinism/tests.rs"]
77mod tests;