qualia_core_db/modalities/abductive/
mod.rs

1//! Abductive inference — Peirce's "inference to the best explanation".
2//!
3//! Given observed effects, find the hypotheses that would account for them. This library
4//! (split per CLAUDE.md §10) covers the full abductive cycle:
5//!   * **chain explanation** ([`abductive_explanation`]) — walk explanatory edges back to a root;
6//!   * **minimal explanation** ([`minimal_explanation`]) — the parsimonious set of roots covering
7//!     a set of observations (Peirce's economy of hypotheses);
8//!   * **counter-abduction** ([`counter_abduction`]) — aggressively prune refuted hypotheses;
9//!   * **probabilistic abduction** ([`probabilistic`]) — Bayesian scoring / ranking of hypotheses;
10//!   * **ATMS** ([`atms`]) — assumption-based truth maintenance: minimal environments + nogoods.
11//!
12//! Zero-heap throughout (bounded chains, caller-supplied `out` buffers, bitset environments).
13
14use crate::NQuin;
15
16pub mod atms;
17pub mod probabilistic;
18
19pub use atms::{env_subset, holds_in, is_nogood, label_add, label_holds, Environment};
20pub use probabilistic::{bayesian_posteriors, best_hypothesis, Hypothesis};
21
22/// Max backward-chaining depth for abductive explanation (bounded, zero-heap).
23pub const MAX_ABDUCTION_DEPTH: usize = 64;
24
25/// Abductive inference — walk BACKWARD along explanatory edges (`hypothesis →explains→ effect`,
26/// predicate == `explains`) from an observed effect to the root hypothesis that accounts for it.
27/// Returns that root, or `None` if the observation has no explanation in the rule set. Zero-heap.
28pub fn abductive_explanation(rules: &[NQuin], observation: u64, explains: u64) -> Option<u64> {
29    let mut current = observation;
30    for _ in 0..MAX_ABDUCTION_DEPTH {
31        let mut next = None;
32        for q in rules {
33            if q.predicate == explains && q.object == current {
34                next = Some(q.subject);
35                break;
36            }
37        }
38        match next {
39            Some(h) => current = h,
40            None => break,
41        }
42    }
43    if current != observation {
44        Some(current)
45    } else {
46        None // no explanatory hypothesis for the observation
47    }
48}
49
50/// **Minimal explanation generation** (Peirce's parsimony): the DISTINCT root hypotheses that
51/// together explain every observation in `observations`, written into `out`. A single hypothesis
52/// accounting for several observations appears once (the smallest covering set under the chain
53/// model). Observations with no explanation are skipped. Returns the count. Zero-heap.
54pub fn minimal_explanation(
55    rules: &[NQuin],
56    observations: &[u64],
57    explains: u64,
58    out: &mut [u64],
59) -> usize {
60    let mut n = 0usize;
61    for &obs in observations {
62        if let Some(root) = abductive_explanation(rules, obs, explains) {
63            if !out[..n].contains(&root) && n < out.len() {
64                out[n] = root;
65                n += 1;
66            }
67        }
68    }
69    n
70}
71
72/// **Counter-abduction:** from `candidates`, drop every hypothesis that has been `refuted` (ruled
73/// out by an observation, or contradicted by an established fact), writing the survivors into
74/// `out`. Returns the surviving count — aggressive pruning of contradictory hypotheses. Zero-heap.
75pub fn counter_abduction(candidates: &[u64], refuted: &[u64], out: &mut [u64]) -> usize {
76    let mut n = 0usize;
77    for &c in candidates {
78        if !refuted.contains(&c) && n < out.len() {
79            out[n] = c;
80            n += 1;
81        }
82    }
83    n
84}
85
86#[cfg(test)]
87mod tests {
88    use super::*;
89
90    fn edge(hypothesis: u64, effect: u64) -> NQuin {
91        let mut q = NQuin {
92            subject: hypothesis,
93            predicate: crate::q_hash("abduces:explains"),
94            object: effect,
95            context: 0,
96            metadata: 0,
97            parity: 0,
98        };
99        q.parity = q.subject ^ q.predicate ^ q.object ^ q.context;
100        q
101    }
102
103    #[test]
104    fn finds_root_explanation() {
105        let explains = crate::q_hash("abduces:explains");
106        // disease(1) → symptom-fever(2) → observed-temp(3). Root hypothesis = 1.
107        let rules = [edge(1, 2), edge(2, 3)];
108        assert_eq!(
109            abductive_explanation(&rules, 3, explains),
110            Some(1),
111            "root hypothesis explains the observation"
112        );
113        assert_eq!(abductive_explanation(&rules, 2, explains), Some(1));
114        // An unexplained observation.
115        assert_eq!(abductive_explanation(&rules, 99, explains), None);
116    }
117
118    #[test]
119    fn minimal_explanation_collapses_shared_roots() {
120        let explains = crate::q_hash("abduces:explains");
121        // Root 1 → 2 → 3 and 1 → 4 (one disease explains two symptoms 3 and 4); root 5 → 6.
122        let rules = [edge(1, 2), edge(2, 3), edge(1, 4), edge(5, 6)];
123        let mut out = [0u64; 8];
124        // Observations {3, 4, 6}: minimal explanation is {1, 5} (1 covers both 3 and 4).
125        let n = minimal_explanation(&rules, &[3, 4, 6], explains, &mut out);
126        assert_eq!(n, 2, "shared root collapses → parsimonious set");
127        assert!(out[..n].contains(&1) && out[..n].contains(&5));
128        // An unexplained observation contributes nothing.
129        let m = minimal_explanation(&rules, &[3, 99], explains, &mut out);
130        assert_eq!(m, 1);
131        assert_eq!(out[0], 1);
132    }
133
134    #[test]
135    fn counter_abduction_prunes_refuted() {
136        let mut out = [0u64; 8];
137        let n = counter_abduction(&[1, 2, 3, 4], &[2, 4], &mut out);
138        assert_eq!(n, 2);
139        assert_eq!(&out[..n], &[1, 3]);
140        // Nothing refuted → all survive.
141        assert_eq!(counter_abduction(&[1, 2], &[], &mut out), 2);
142        // All refuted → none survive.
143        assert_eq!(counter_abduction(&[1, 2], &[1, 2], &mut out), 0);
144    }
145}
qualia_core_db/modalities/abductive/mod.rs

qualia_core_db/modalities/abductive/
mod.rs
