Skip to main content

qualia_core_db/modalities/
asp.rs

1use crate::NQuin;
2
3pub const MAX_STABLE_MODELS: usize = 8;
4
5/// Returns number of stable models found (max MAX_STABLE_MODELS = 8)
6/// Worlds are encoded as context-hash variants: world_i_context = base_context ^ (i as u64)
7pub fn enumerate_stable_models(
8    base: &NQuin,
9    rules: &[NQuin],
10    out_worlds: &mut [u64; MAX_STABLE_MODELS],
11) -> usize {
12    if rules.is_empty() {
13        out_worlds[0] = base.context;
14        return 1;
15    }
16
17    let mut num_worlds = 1;
18    out_worlds[0] = base.context;
19
20    // For each rule, we bifurcate the context simulating applying vs not applying the rule,
21    // up to the maximum number of supported stable models.
22    for rule in rules.iter().take(3) {
23        // 2^3 = 8
24        let current_worlds = num_worlds;
25        for w in 0..current_worlds {
26            if num_worlds < MAX_STABLE_MODELS {
27                // Bifurcate by XORing the rule's hash components into the context
28                out_worlds[num_worlds] = out_worlds[w] ^ rule.subject ^ rule.object;
29                num_worlds += 1;
30            }
31        }
32    }
33
34    num_worlds
35}
36
37// ─── True stable-model (answer-set) semantics — Gelfond-Lifschitz ───────────────
38//
39// The function above is a legacy context-bifurcation heuristic kept for its callers.
40// `compute_answer_sets` is the REAL thing: stable models of a normal logic program
41// (`head :- p1..pk, not n1..nm`, plus integrity constraints `:- body`) under the
42// Gelfond-Lifschitz reduct. Bounded + zero-heap: atoms are indexed into a u64 bitmask,
43// candidate models are brute-forced over 2^|atoms|, each reduced + least-fixpoint'd +
44// checked for stability. Correct (not heuristic): an under-determined norm
45// ("permitted :- not forbidden; forbidden :- not permitted") yields its TWO consistent
46// answer sets; a constraint prunes them.
47
48pub const ASP_MAX_ATOMS: usize = 12; // 2^12 = 4096 candidate interpretations
49pub const ASP_MAX_BODY: usize = 6;
50
51/// A normal ASP rule `head :- pos.., not neg..`. `head == 0` encodes an integrity
52/// constraint `:- pos.., not neg..` (admits no atom; prunes models satisfying the body).
53#[derive(Clone, Copy)]
54pub struct AspRule {
55    pub head: u64,
56    pub pos: [u64; ASP_MAX_BODY],
57    pub pos_len: usize,
58    pub neg: [u64; ASP_MAX_BODY],
59    pub neg_len: usize,
60}
61
62impl AspRule {
63    /// Build a rule `head :- pos, not neg` into the fixed-size body
64    /// arrays; literals beyond `ASP_MAX_BODY` are silently truncated.
65    pub fn new(head: u64, pos: &[u64], neg: &[u64]) -> Self {
66        let mut r = AspRule {
67            head,
68            pos: [0; ASP_MAX_BODY],
69            pos_len: 0,
70            neg: [0; ASP_MAX_BODY],
71            neg_len: 0,
72        };
73        for &a in pos.iter().take(ASP_MAX_BODY) {
74            r.pos[r.pos_len] = a;
75            r.pos_len += 1;
76        }
77        for &a in neg.iter().take(ASP_MAX_BODY) {
78            r.neg[r.neg_len] = a;
79            r.neg_len += 1;
80        }
81        r
82    }
83    /// A fact: a rule with `head` and no body.
84    pub fn fact(head: u64) -> Self {
85        Self::new(head, &[], &[])
86    }
87    /// An integrity constraint: `head` 0, so a model where the body
88    /// holds is disallowed.
89    pub fn constraint(pos: &[u64], neg: &[u64]) -> Self {
90        Self::new(0, pos, neg)
91    }
92}
93
94/// Compute the stable models (answer sets) of `rules` over `atoms`. Each answer set is
95/// written to `out` as a bitmask over atom indices (bit i ⇔ `atoms[i]` is in the set).
96/// Returns the number found. Zero-heap; bounded to `ASP_MAX_ATOMS` atoms.
97pub fn compute_answer_sets(atoms: &[u64], rules: &[AspRule], out: &mut [u64]) -> usize {
98    let n = atoms.len().min(ASP_MAX_ATOMS);
99    let idx = |a: u64| -> Option<usize> { atoms[..n].iter().position(|&x| x == a) };
100    let removed_by_reduct = |r: &AspRule, cand: u64| -> bool {
101        // GL reduct: a rule is removed iff some negative-body atom is IN the candidate.
102        for &na in &r.neg[..r.neg_len] {
103            if let Some(ni) = idx(na) {
104                if cand & (1u64 << ni) != 0 {
105                    return true;
106                }
107            }
108        }
109        false
110    };
111    let body_pos_in = |r: &AspRule, m: u64| -> bool {
112        for &pa in &r.pos[..r.pos_len] {
113            match idx(pa) {
114                Some(pi) if m & (1u64 << pi) != 0 => {}
115                _ => return false,
116            }
117        }
118        true
119    };
120
121    let mut found = 0usize;
122    let total: u64 = 1u64 << n;
123    for cand in 0..total {
124        // Least model of the reduct (positive Horn) by fixpoint iteration.
125        let mut m: u64 = 0;
126        loop {
127            let mut changed = false;
128            for r in rules {
129                if r.head == 0 || removed_by_reduct(r, cand) {
130                    continue;
131                }
132                if body_pos_in(r, m) {
133                    if let Some(hi) = idx(r.head) {
134                        if m & (1u64 << hi) == 0 {
135                            m |= 1u64 << hi;
136                            changed = true;
137                        }
138                    }
139                }
140            }
141            if !changed {
142                break;
143            }
144        }
145        // Stability: the least model of the reduct must equal the candidate …
146        if m != cand {
147            continue;
148        }
149        // … and no integrity constraint may be violated by it.
150        let mut ok = true;
151        for r in rules {
152            if r.head != 0 || removed_by_reduct(r, cand) {
153                continue;
154            }
155            if body_pos_in(r, m) {
156                ok = false;
157                break;
158            }
159        }
160        if ok {
161            if found >= out.len() {
162                break;
163            }
164            out[found] = m;
165            found += 1;
166        }
167    }
168    found
169}
170
171// ─── Index helper ───────────────────────────────────────────────────────────────────
172
173/// Index of atom `a` in `atoms` (bit position), if present.
174#[inline]
175pub fn atom_index(atoms: &[u64], a: u64) -> Option<usize> {
176    atoms.iter().take(ASP_MAX_ATOMS).position(|&x| x == a)
177}
178
179/// Rule-body satisfaction under a candidate model bitmask: every
180/// `pos` atom's bit set, no `neg` atom's bit set (atoms outside
181/// `atoms` fail `pos` but vacuously satisfy `neg`).
182#[inline]
183fn body_holds(atoms: &[u64], model: u64, pos: &[u64], neg: &[u64]) -> bool {
184    for &p in pos {
185        match atom_index(atoms, p) {
186            Some(i) if model & (1u64 << i) != 0 => {}
187            _ => return false,
188        }
189    }
190    for &nn in neg {
191        if let Some(i) = atom_index(atoms, nn) {
192            if model & (1u64 << i) != 0 {
193                return false;
194            }
195        }
196    }
197    true
198}
199
200// ─── Grounding: zero-heap instantiation of a non-ground rule template ───────────────
201
202/// Ground a rule TEMPLATE by substituting variable `var` with each element of `domain`, writing
203/// the ground instances into `out`. Returns the count. Apply repeatedly (over the partially-ground
204/// output) for multiple variables. Zero-heap — bounded by `out.len()` (the "millions of
205/// constraints" ceiling is the caller's buffer, not a heap allocation here).
206pub fn ground_rule(template: &AspRule, var: u64, domain: &[u64], out: &mut [AspRule]) -> usize {
207    let subst = |a: u64, d: u64| if a == var { d } else { a };
208    let mut n = 0usize;
209    for &d in domain {
210        if n >= out.len() {
211            break;
212        }
213        let mut g = *template;
214        g.head = subst(g.head, d);
215        for i in 0..g.pos_len {
216            g.pos[i] = subst(g.pos[i], d);
217        }
218        for i in 0..g.neg_len {
219            g.neg[i] = subst(g.neg[i], d);
220        }
221        out[n] = g;
222        n += 1;
223    }
224    n
225}
226
227// ─── Weak constraints & optimization (the "best" stable model) ──────────────────────
228
229/// A weak constraint `:~ pos.., not neg.. [weight]` — incurs `weight` when its body holds in a
230/// model. Optimal answer sets MINIMISE total incurred weight.
231#[derive(Clone, Copy)]
232pub struct WeakConstraint {
233    pub pos: [u64; ASP_MAX_BODY],
234    pub pos_len: usize,
235    pub neg: [u64; ASP_MAX_BODY],
236    pub neg_len: usize,
237    pub weight: i64,
238}
239
240impl WeakConstraint {
241    /// Build a `:~ pos, not neg [weight]` weak constraint into the
242    /// fixed-size body arrays; literals beyond `ASP_MAX_BODY`
243    /// truncate.
244    pub fn new(pos: &[u64], neg: &[u64], weight: i64) -> Self {
245        let mut w = WeakConstraint {
246            pos: [0; ASP_MAX_BODY],
247            pos_len: 0,
248            neg: [0; ASP_MAX_BODY],
249            neg_len: 0,
250            weight,
251        };
252        for &a in pos.iter().take(ASP_MAX_BODY) {
253            w.pos[w.pos_len] = a;
254            w.pos_len += 1;
255        }
256        for &a in neg.iter().take(ASP_MAX_BODY) {
257            w.neg[w.neg_len] = a;
258            w.neg_len += 1;
259        }
260        w
261    }
262}
263
264/// Total penalty of `model` under `weak`: the sum of weights of the weak constraints whose body
265/// holds in the model.
266pub fn model_penalty(atoms: &[u64], model: u64, weak: &[WeakConstraint]) -> i64 {
267    let mut total = 0i64;
268    for w in weak {
269        if body_holds(atoms, model, &w.pos[..w.pos_len], &w.neg[..w.neg_len]) {
270            total += w.weight;
271        }
272    }
273    total
274}
275
276/// The **optimal** answer set: the stable model minimising total weak-constraint penalty. Returns
277/// `(model_bitmask, penalty)`, or `None` if the program has no stable model. `buf` is scratch for
278/// the enumerated answer sets.
279pub fn optimal_answer_set(
280    atoms: &[u64],
281    rules: &[AspRule],
282    weak: &[WeakConstraint],
283    buf: &mut [u64],
284) -> Option<(u64, i64)> {
285    let k = compute_answer_sets(atoms, rules, buf);
286    if k == 0 {
287        return None;
288    }
289    let mut best = (buf[0], model_penalty(atoms, buf[0], weak));
290    for &m in &buf[1..k] {
291        let p = model_penalty(atoms, m, weak);
292        if p < best.1 {
293            best = (m, p);
294        }
295    }
296    Some(best)
297}
298
299// ─── Cautious / brave reasoning ─────────────────────────────────────────────────────
300
301/// **Cautious** (skeptical) consequences: the atoms in EVERY answer set (bit-AND of all models).
302/// `0` if there are no models.
303pub fn cautious_consequences(models: &[u64]) -> u64 {
304    match models.split_first() {
305        Some((&first, rest)) => rest.iter().fold(first, |acc, &m| acc & m),
306        None => 0,
307    }
308}
309
310/// **Brave** (credulous) consequences: the atoms in SOME answer set (bit-OR of all models).
311pub fn brave_consequences(models: &[u64]) -> u64 {
312    models.iter().fold(0u64, |acc, &m| acc | m)
313}
314
315// ─── Paraconsistent routing: no-stable-model handling ───────────────────────────────
316
317/// Outcome of an answer-set computation — distinguishes "no model" (an over-constrained /
318/// inconsistent program) from genuine results, so the caller can route the former to
319/// paraconsistent reasoning instead of treating absence-of-model as plain falsity.
320#[derive(Debug, Clone, Copy, PartialEq, Eq)]
321pub enum AspOutcome {
322    /// `n` stable models were written to the output buffer.
323    Stable(usize),
324    /// No stable model exists — the program is inconsistent; route to `paraconsistent`.
325    NoStableModel,
326}
327
328/// Compute answer sets; if NONE exist, return [`AspOutcome::NoStableModel`] so the caller routes
329/// the (inconsistent) program to `modalities::paraconsistent::route_paraconsistent` rather than
330/// silently concluding falsity. This is the tight integration with paraconsistent routing.
331pub fn answer_sets_or_paraconsistent(
332    atoms: &[u64],
333    rules: &[AspRule],
334    out: &mut [u64],
335) -> AspOutcome {
336    let k = compute_answer_sets(atoms, rules, out);
337    if k == 0 {
338        AspOutcome::NoStableModel
339    } else {
340        AspOutcome::Stable(k)
341    }
342}
343
344#[cfg(test)]
345mod tests {
346    use super::*;
347
348    /// Real stable-model semantics: an even loop has exactly TWO answer sets; a constraint prunes.
349    #[test]
350    fn answer_sets_even_loop_and_constraint() {
351        let (p, q) = (101u64, 202u64);
352        let atoms = [p, q];
353        // p :- not q.   q :- not p.   → answer sets {p} and {q}.
354        let prog = [AspRule::new(p, &[], &[q]), AspRule::new(q, &[], &[p])];
355        let mut out = [0u64; 8];
356        let k = compute_answer_sets(&atoms, &prog, &mut out);
357        assert_eq!(k, 2, "even loop has exactly two stable models");
358        let bp = 1u64 << 0; // p is atoms[0]
359        let bq = 1u64 << 1; // q is atoms[1]
360        assert!(
361            out[..k].contains(&bp) && out[..k].contains(&bq),
362            "the two answer sets are {{p}} and {{q}}"
363        );
364
365        // Add `:- q` (forbid q) → only {p} survives.
366        let prog2 = [
367            AspRule::new(p, &[], &[q]),
368            AspRule::new(q, &[], &[p]),
369            AspRule::constraint(&[q], &[]),
370        ];
371        let mut out2 = [0u64; 8];
372        let k2 = compute_answer_sets(&atoms, &prog2, &mut out2);
373        assert_eq!(k2, 1, "the constraint prunes {{q}}");
374        assert_eq!(out2[0], bp, "only {{p}} remains");
375    }
376
377    #[test]
378    fn test_enumerate_stable_models() {
379        let base = NQuin {
380            subject: 0,
381            predicate: 0,
382            object: 0,
383            context: 42,
384            metadata: 0,
385            parity: 0,
386        };
387        let mut out_worlds = [0; MAX_STABLE_MODELS];
388
389        // Empty rules -> 1 world
390        let count = enumerate_stable_models(&base, &[], &mut out_worlds);
391        assert_eq!(count, 1);
392        assert_eq!(out_worlds[0], 42);
393
394        // One rule -> 2 worlds
395        let rule = NQuin {
396            subject: 10,
397            predicate: 0,
398            object: 20,
399            context: 0,
400            metadata: 0,
401            parity: 0,
402        };
403        let count2 = enumerate_stable_models(&base, &[rule], &mut out_worlds);
404        assert_eq!(count2, 2);
405        assert_eq!(out_worlds[0], 42);
406        assert_eq!(out_worlds[1], 42 ^ 10 ^ 20);
407    }
408
409    #[test]
410    fn grounder_instantiates_a_template_over_a_domain() {
411        // Template:  node(X).   with X a variable, domain {a,b,c} → three ground facts.
412        let var = crate::q_hash("var:X");
413        let node = |x: u64| x; // identity: the head IS the (variable) atom node(X)≡X here
414        let template = AspRule::fact(var);
415        let (a, b, c) = (node(11), node(22), node(33));
416        let mut out = [AspRule::fact(0); 8];
417        let n = ground_rule(&template, var, &[a, b, c], &mut out);
418        assert_eq!(n, 3);
419        assert_eq!(out[0].head, a);
420        assert_eq!(out[1].head, b);
421        assert_eq!(out[2].head, c);
422    }
423
424    #[test]
425    fn weak_constraints_select_the_optimal_model() {
426        let (p, q) = (101u64, 202u64);
427        let atoms = [p, q];
428        // Even loop → {p} and {q}. Weak constraint `:~ q [1]` penalises q.
429        let prog = [AspRule::new(p, &[], &[q]), AspRule::new(q, &[], &[p])];
430        let weak = [WeakConstraint::new(&[q], &[], 1)];
431        let mut buf = [0u64; 8];
432        let (best, penalty) = optimal_answer_set(&atoms, &prog, &weak, &mut buf).unwrap();
433        assert_eq!(best, 1u64 << 0, "optimal model is {{p}} (no penalty)");
434        assert_eq!(penalty, 0);
435        // {q} would have incurred penalty 1.
436        assert_eq!(model_penalty(&atoms, 1u64 << 1, &weak), 1);
437    }
438
439    #[test]
440    fn cautious_and_brave_consequences() {
441        let (p, q) = (101u64, 202u64);
442        let atoms = [p, q];
443        let prog = [AspRule::new(p, &[], &[q]), AspRule::new(q, &[], &[p])];
444        let mut buf = [0u64; 8];
445        let k = compute_answer_sets(&atoms, &prog, &mut buf);
446        assert_eq!(k, 2);
447        // Cautious: in BOTH {p} and {q} → neither p nor q → 0. Brave: in SOME → both bits set.
448        assert_eq!(cautious_consequences(&buf[..k]), 0);
449        assert_eq!(brave_consequences(&buf[..k]), (1u64 << 0) | (1u64 << 1));
450    }
451
452    #[test]
453    fn no_stable_model_routes_to_paraconsistent() {
454        let p = 101u64;
455        let atoms = [p];
456        // `p :- not p` has NO stable model — an inconsistent program.
457        let prog = [AspRule::new(p, &[], &[p])];
458        let mut out = [0u64; 8];
459        assert_eq!(
460            answer_sets_or_paraconsistent(&atoms, &prog, &mut out),
461            AspOutcome::NoStableModel
462        );
463        // A consistent program reports its model count.
464        let prog2 = [AspRule::fact(p)];
465        assert_eq!(
466            answer_sets_or_paraconsistent(&atoms, &prog2, &mut out),
467            AspOutcome::Stable(1)
468        );
469    }
470}