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}