Skip to main content

qualia_core_db/modalities/
linear.rs

1use crate::NQuin;
2
3// Marks a Quin as consumed by setting metadata bit 59 (CONSUMED_BIT).
4// Canonical bit position lives in the FrameLayout ABI (single source of truth).
5pub use crate::frame_layout::CONSUMED_BIT;
6
7/// Mark a Quin as linearly consumed by setting `CONSUMED_BIT` in its
8/// metadata — the premise of a linear (`-o`) rule is spent on firing.
9pub fn consume_quin(q: &mut NQuin) {
10    q.metadata |= CONSUMED_BIT;
11}
12
13/// True when `CONSUMED_BIT` is set — the quin's resource has been spent.
14pub fn is_consumed(q: &NQuin) -> bool {
15    (q.metadata & CONSUMED_BIT) != 0
16}
17
18// ─── Girard's linear-logic connectives ──────────────────────────────────────────────
19//
20// Linear logic treats propositions as RESOURCES: each is used exactly once unless explicitly
21// marked reusable with the `!` exponential. The connectives split into multiplicatives
22// (⊗ tensor, ⅋ par), additives (⊕ plus, & with), their units, and the exponentials (! ?).
23
24#[derive(Debug, Clone, Copy, PartialEq, Eq)]
25pub enum Connective {
26    /// A positive literal.
27    Atom,
28    /// A literal's linear negation `a⊥`.
29    AtomDual,
30    /// `A ⊗ B` — multiplicative conjunction ("both, together").
31    Tensor,
32    /// `A ⅋ B` — multiplicative disjunction.
33    Par,
34    /// `A ⊕ B` — additive disjunction (internal choice).
35    Plus,
36    /// `A & B` — additive conjunction (external choice).
37    With,
38    /// `1` — unit of `⊗`.
39    One,
40    /// `⊥` — unit of `⅋`.
41    Bottom,
42    /// `0` — unit of `⊕`.
43    Zero,
44    /// `⊤` — unit of `&`.
45    Top,
46    /// `!A` — exponential "of course" (reusable: weakening + contraction apply).
47    OfCourse,
48    /// `?A` — exponential "why not" (dual of `!`).
49    WhyNot,
50}
51
52impl Connective {
53    /// Linear negation `(·)⊥` — the involutive De Morgan dual (`A⊥⊥ = A`).
54    pub fn dual(self) -> Connective {
55        use Connective::*;
56        match self {
57            Atom => AtomDual,
58            AtomDual => Atom,
59            Tensor => Par,
60            Par => Tensor,
61            Plus => With,
62            With => Plus,
63            One => Bottom,
64            Bottom => One,
65            Zero => Top,
66            Top => Zero,
67            OfCourse => WhyNot,
68            WhyNot => OfCourse,
69        }
70    }
71
72    /// Multiplicative connectives/units (`⊗ ⅋ 1 ⊥`).
73    pub fn is_multiplicative(self) -> bool {
74        use Connective::*;
75        matches!(self, Tensor | Par | One | Bottom)
76    }
77
78    /// Additive connectives/units (`⊕ & 0 ⊤`).
79    pub fn is_additive(self) -> bool {
80        use Connective::*;
81        matches!(self, Plus | With | Zero | Top)
82    }
83
84    /// Exponential connectives (`! ?`).
85    pub fn is_exponential(self) -> bool {
86        matches!(self, Connective::OfCourse | Connective::WhyNot)
87    }
88
89    /// A resource under `!` ("of course") is **reusable** — structural weakening and contraction
90    /// are licensed. Everything else is linear (consume-once).
91    pub fn is_reusable(self) -> bool {
92        matches!(self, Connective::OfCourse)
93    }
94}
95
96/// Whether a resource quin `q` may be consumed to satisfy a demand: a reusable (`!`-marked)
97/// resource always can; a linear resource only if not already consumed.
98pub fn can_consume(q: &NQuin, reusable: bool) -> bool {
99    reusable || !is_consumed(q)
100}
101
102/// `A ⊗ B` consumption: a tensor demand needs **both** operands available *together*. Consumes
103/// each linear operand (leaves reusable ones); returns `false` without mutating if either is
104/// already exhausted.
105pub fn tensor_consume(a: &mut NQuin, a_reusable: bool, b: &mut NQuin, b_reusable: bool) -> bool {
106    if !can_consume(a, a_reusable) || !can_consume(b, b_reusable) {
107        return false;
108    }
109    if !a_reusable {
110        consume_quin(a);
111    }
112    if !b_reusable {
113        consume_quin(b);
114    }
115    true
116}
117
118// ─── Structural-rule discipline (weakening & contraction strictly controlled) ───────
119//
120// Linear logic's defining feature: the structural rules WEAKENING (discard a resource) and
121// CONTRACTION (duplicate a resource) are NOT freely available — they are licensed only on
122// reusable `!`-marked formulas. Exchange (reorder) is always fine.
123
124#[derive(Debug, Clone, Copy, PartialEq, Eq)]
125pub enum StructuralRule {
126    /// Discard a formula from the sequent.
127    Weakening,
128    /// Duplicate a formula in the sequent.
129    Contraction,
130    /// Reorder formulas.
131    Exchange,
132}
133
134/// Is applying `rule` to a formula with the given reusability licensed? Exchange always; Weakening
135/// and Contraction **only** on a reusable (`!`-marked) formula — applying either to a linear
136/// resource is an illegal proof step (resources must be used exactly once).
137pub fn structural_rule_licensed(rule: StructuralRule, reusable: bool) -> bool {
138    match rule {
139        StructuralRule::Exchange => true,
140        StructuralRule::Weakening | StructuralRule::Contraction => reusable,
141    }
142}
143
144/// Validate a whole sequence of structural-rule applications `(rule, reusable)`; every step must
145/// be licensed for the derivation to be well-formed.
146pub fn structural_derivation_valid(steps: &[(StructuralRule, bool)]) -> bool {
147    steps
148        .iter()
149        .all(|&(rule, reusable)| structural_rule_licensed(rule, reusable))
150}
151
152// ─── Proof-net validation (Danos-Regnier correctness, multiplicative fragment) ──────
153//
154// A multiplicative proof structure is a genuine PROOF NET iff every Danos-Regnier *switching*
155// (each `⅋` node keeps exactly one of its two premise edges) yields a tree — acyclic AND
156// connected. We enumerate the 2^(#par) switchings and check each with union-find. Bounded and
157// zero-heap (fixed-size stack arrays).
158
159/// Max nodes / par-links for the bounded DR check.
160pub const MAX_PN_NODES: usize = 32;
161/// Max `⅋` links (2^MAX_PN_PARS switchings enumerated).
162pub const MAX_PN_PARS: usize = 12;
163
164/// Union-find root of `x` with path halving — the connectivity check
165/// behind the bounded Danos–Regnier correctness criterion.
166#[inline]
167fn pn_find(parent: &mut [usize; MAX_PN_NODES], mut x: usize) -> usize {
168    while parent[x] != x {
169        parent[x] = parent[parent[x]]; // path halving
170        x = parent[x];
171    }
172    x
173}
174
175/// Union `a`,`b`; returns `false` if they were already connected (i.e. this edge closes a cycle).
176#[inline]
177fn pn_union(parent: &mut [usize; MAX_PN_NODES], a: usize, b: usize) -> bool {
178    let ra = pn_find(parent, a);
179    let rb = pn_find(parent, b);
180    if ra == rb {
181        return false;
182    }
183    parent[ra] = rb;
184    true
185}
186
187/// Danos-Regnier check: is the proof structure a **proof net**? `n_nodes` formula occurrences,
188/// the always-present `fixed_edges` (axiom / cut / `⊗` links), and the `par_switches` (each a
189/// pair of candidate edges for one `⅋`, one chosen per switching). Returns true iff EVERY
190/// switching graph is a tree. Bounded by [`MAX_PN_NODES`] / [`MAX_PN_PARS`].
191pub fn is_proof_net(
192    n_nodes: usize,
193    fixed_edges: &[(usize, usize)],
194    par_switches: &[((usize, usize), (usize, usize))],
195) -> bool {
196    if n_nodes == 0 || n_nodes > MAX_PN_NODES || par_switches.len() > MAX_PN_PARS {
197        return false;
198    }
199    let k = par_switches.len();
200    for mask in 0u32..(1u32 << k) {
201        let mut parent = [0usize; MAX_PN_NODES];
202        for (i, p) in parent.iter_mut().enumerate().take(n_nodes) {
203            *p = i;
204        }
205        let mut acyclic = true;
206        let mut edge_count = 0usize;
207
208        for &(a, b) in fixed_edges {
209            if a >= n_nodes || b >= n_nodes {
210                return false;
211            }
212            if !pn_union(&mut parent, a, b) {
213                acyclic = false;
214            }
215            edge_count += 1;
216        }
217        for (j, &(ea, eb)) in par_switches.iter().enumerate() {
218            let (a, b) = if (mask >> j) & 1 == 0 { ea } else { eb };
219            if a >= n_nodes || b >= n_nodes {
220                return false;
221            }
222            if !pn_union(&mut parent, a, b) {
223                acyclic = false;
224            }
225            edge_count += 1;
226        }
227
228        // Tree ⟺ acyclic ∧ connected ⟺ acyclic ∧ edge_count == n-1 ∧ single component.
229        if !acyclic || edge_count != n_nodes - 1 {
230            return false;
231        }
232        let root = pn_find(&mut parent, 0);
233        for i in 1..n_nodes {
234            if pn_find(&mut parent, i) != root {
235                return false; // disconnected switching → not a proof net
236            }
237        }
238    }
239    true
240}
241
242// ─── Zero-knowledge–gated resource exhaustion ───────────────────────────────────────
243
244/// ZK-gated consumption: a linear resource may be exhausted **only** if a zero-knowledge proof of
245/// entitlement verifies (the witness stays private). Composes the verification boolean — produced
246/// by `zk_proofs` / `legal_compose::zk_eligibility` — with the linear consume-once discipline.
247/// Consumes (and returns `true`) iff the proof holds AND the resource is available. The webizen-VM
248/// opcode dispatch that *invokes* this gate is a separate, out-of-(this-crate-scope) wiring step.
249pub fn zk_gated_consume(q: &mut NQuin, reusable: bool, proof_verified: bool) -> bool {
250    if !proof_verified || !can_consume(q, reusable) {
251        return false;
252    }
253    if !reusable {
254        consume_quin(q);
255    }
256    true
257}
258
259#[cfg(test)]
260mod tests {
261    use super::*;
262
263    #[test]
264    fn test_consume_quin() {
265        let mut q = NQuin {
266            subject: 0,
267            predicate: 0,
268            object: 0,
269            context: 0,
270            metadata: 0,
271            parity: 0,
272        };
273        assert!(!is_consumed(&q));
274        consume_quin(&mut q);
275        assert!(is_consumed(&q));
276    }
277
278    #[test]
279    fn linear_negation_is_involutive_and_dualises_connectives() {
280        use Connective::*;
281        for c in [
282            Atom, AtomDual, Tensor, Par, Plus, With, One, Bottom, Zero, Top, OfCourse, WhyNot,
283        ] {
284            assert_eq!(c.dual().dual(), c, "(A⊥)⊥ = A for {:?}", c);
285            assert_ne!(c.dual(), c, "no connective is its own dual: {:?}", c);
286        }
287        // The characteristic De Morgan dualities.
288        assert_eq!(Tensor.dual(), Par);
289        assert_eq!(Plus.dual(), With);
290        assert_eq!(One.dual(), Bottom);
291        assert_eq!(Zero.dual(), Top);
292        assert_eq!(OfCourse.dual(), WhyNot);
293    }
294
295    #[test]
296    fn connective_classification_and_reuse() {
297        use Connective::*;
298        assert!(Tensor.is_multiplicative() && !Tensor.is_additive());
299        assert!(With.is_additive() && !With.is_multiplicative());
300        assert!(OfCourse.is_exponential() && WhyNot.is_exponential());
301        // Only `!A` is reusable; linear atoms are consume-once.
302        assert!(OfCourse.is_reusable());
303        assert!(!Atom.is_reusable());
304    }
305
306    #[test]
307    fn tensor_consumes_both_and_respects_reuse() {
308        let mk = || NQuin {
309            subject: 1,
310            predicate: 2,
311            object: 3,
312            context: 0,
313            metadata: 0,
314            parity: 0,
315        };
316        // Two linear resources: tensor consumes both; a second demand fails.
317        let mut a = mk();
318        let mut b = mk();
319        assert!(tensor_consume(&mut a, false, &mut b, false));
320        assert!(is_consumed(&a) && is_consumed(&b));
321        assert!(
322            !tensor_consume(&mut a, false, &mut b, false),
323            "linear resources are exhausted"
324        );
325
326        // A reusable (!-marked) resource is never exhausted.
327        let mut r = mk();
328        let mut s = mk();
329        assert!(tensor_consume(&mut r, true, &mut s, false));
330        assert!(!is_consumed(&r), "reusable resource is not consumed");
331        assert!(is_consumed(&s));
332        assert!(
333            tensor_consume(&mut r, true, &mut s, true),
334            "reusable can satisfy again"
335        );
336    }
337
338    #[test]
339    fn structural_rules_are_controlled() {
340        // Weakening / contraction only on reusable (!) formulas; never on linear ones.
341        assert!(!structural_rule_licensed(StructuralRule::Weakening, false));
342        assert!(!structural_rule_licensed(
343            StructuralRule::Contraction,
344            false
345        ));
346        assert!(structural_rule_licensed(StructuralRule::Weakening, true));
347        assert!(structural_rule_licensed(StructuralRule::Contraction, true));
348        // Exchange is always fine.
349        assert!(structural_rule_licensed(StructuralRule::Exchange, false));
350        // A whole derivation: contraction on a reusable + exchange on a linear → valid.
351        assert!(structural_derivation_valid(&[
352            (StructuralRule::Contraction, true),
353            (StructuralRule::Exchange, false),
354        ]));
355        // …but contraction on a linear resource invalidates it.
356        assert!(!structural_derivation_valid(&[(
357            StructuralRule::Contraction,
358            false
359        )]));
360    }
361
362    #[test]
363    fn danos_regnier_distinguishes_nets_from_non_nets() {
364        // A single edge over 2 nodes, no pars → tree → net.
365        assert!(is_proof_net(2, &[(0, 1)], &[]));
366        // Disconnected: 3 nodes, 1 edge → not connected → not a net.
367        assert!(!is_proof_net(3, &[(0, 1)], &[]));
368        // Cyclic: 3 nodes, edges forming a triangle → cycle → not a net.
369        assert!(!is_proof_net(3, &[(0, 1), (1, 2), (0, 2)], &[]));
370
371        // A par link: 3 nodes, fixed edge (0,1), the ⅋ switches between (0,2) and (1,2).
372        // BOTH switchings give a 3-node/2-edge connected acyclic tree → net.
373        assert!(is_proof_net(3, &[(0, 1)], &[((0, 2), (1, 2))]));
374
375        // A par whose both candidate edges duplicate the fixed edge → every switching makes a
376        // cycle on {0,1} and leaves node 2 isolated → not a net.
377        assert!(!is_proof_net(3, &[(0, 1)], &[((0, 1), (0, 1))]));
378
379        // Bounds are enforced.
380        assert!(!is_proof_net(0, &[], &[]));
381        assert!(
382            !is_proof_net(2, &[(0, 5)], &[]),
383            "edge to out-of-range node rejected"
384        );
385    }
386
387    #[test]
388    fn zk_gate_controls_resource_exhaustion() {
389        let mk = || NQuin {
390            subject: 1,
391            predicate: 2,
392            object: 3,
393            context: 0,
394            metadata: 0,
395            parity: 0,
396        };
397        // No proof → no consumption, resource untouched.
398        let mut q = mk();
399        assert!(!zk_gated_consume(&mut q, false, false));
400        assert!(!is_consumed(&q));
401        // Valid proof → linear resource consumed once, then exhausted.
402        assert!(zk_gated_consume(&mut q, false, true));
403        assert!(is_consumed(&q));
404        assert!(!zk_gated_consume(&mut q, false, true), "already exhausted");
405        // Reusable resource with a valid proof is never exhausted.
406        let mut r = mk();
407        assert!(zk_gated_consume(&mut r, true, true));
408        assert!(!is_consumed(&r));
409    }
410}