diff options
Diffstat (limited to 'crates/elfmind/src/knowledge.rs')
| -rw-r--r-- | crates/elfmind/src/knowledge.rs | 154 |
1 files changed, 139 insertions, 15 deletions
diff --git a/crates/elfmind/src/knowledge.rs b/crates/elfmind/src/knowledge.rs index cbcce28..a610328 100644 --- a/crates/elfmind/src/knowledge.rs +++ b/crates/elfmind/src/knowledge.rs @@ -112,8 +112,8 @@ impl Rule { pub fn unify_body(&self, facts: &[&Relation]) -> Option<Unification> { if self.body.len() != facts.len() { return None; } let mut u = Unification::default(); - for (r1, r2) in self.body.iter().zip(facts) { - u = r1.unify(r2, u)?; + for (r, f) in self.body.iter().zip(facts) { + u = r.unify(f, u)?; } Some(u) } @@ -130,6 +130,17 @@ impl Facts { pub fn with_sort(&self, s: RelationDiscriminants) -> &HashSet<Relation> { &self.facts[s] } + pub fn with_sort_mut(&mut self, s: RelationDiscriminants) -> &mut HashSet<Relation> { + &mut self.facts[s] + } + pub fn contains(&self, f: &Relation) -> bool { + self.facts[f.discriminant()].contains(f) + } + pub fn absorb(&mut self, other: &mut Facts) { + for (rd, fs) in self.facts.iter_mut() { + fs.extend(other.with_sort_mut(rd).drain()); + } + } } #[derive(Debug, Default, Clone)] @@ -138,28 +149,141 @@ pub struct Database { rules: Vec<Rule>, } impl Database { - pub fn add_fact(&mut self, r: Relation) { self.facts.add(r); } - pub fn add_rule(&mut self, r: Rule) { self.rules.push(r) } - fn apply_rule(r: &Rule, facts: &mut Facts) -> bool { - let found: Vec<Unification> = r.body.iter() - .map(|r| facts.with_sort(r.discriminant())).multi_cartesian_product() - .filter_map(|fs| r.unify_body(&fs)) - .collect(); + pub fn is_known(&self, r: &Relation) -> bool { self.facts.contains(r) } + pub fn query<'a>(&'a mut self) -> Query<'a> { + Query { + db: self, + facts: Facts::default(), + rules: Vec::new(), + } + } +} + +#[must_use] +#[derive(Debug)] +pub struct Query<'a> { + db: &'a mut Database, + facts: Facts, + rules: Vec<Rule>, +} +#[derive(Debug, Clone, Copy)] +enum QueryFactsToConsider<'a> { + LastIteration(&'a Facts), + Query, + DB, +} +impl<'a> Query<'a> { + fn apply_rule(&self, r: &Rule, new_facts: &mut Facts, required_facts: QueryFactsToConsider) -> bool { + // we don't need to consider every possible fact against each body term (naive evaluation) + // instead, we can limit ourselves to the subset where at least one of the facts is new (semi-naive) + // let found: Vec<Unification> = r.body.iter() + // .map(|r| { + // let d = r.discriminant(); + // new_facts.with_sort(d).iter() + // .chain(self.facts.with_sort(d).iter()) + // .chain(self.db.facts.with_sort(d).iter()) + // }) + // .multi_cartesian_product() + // .filter_map(|fs| r.unify_body(&fs)) + // .collect(); + let mut found = Vec::new(); + // identify which slots of this rule body possibly have new facts to consider + let changed_slots = r.body.iter() + .enumerate() + .filter_map(|(i, r)| { + match required_facts { + // if we are only considering facts from the provided set + QueryFactsToConsider::LastIteration(rf) => + if rf.with_sort(r.discriminant()).is_empty() { None } else { Some(i) }, + // if we are only considering facts added by this query + QueryFactsToConsider::Query => + if self.facts.with_sort(r.discriminant()).is_empty() { None } else { Some(i) }, + // if we are considering all facts, simply consider every index + QueryFactsToConsider::DB => Some(i), + } + }); + let empty = HashSet::new(); + for cs in changed_slots { + let attempts = r.body.iter() + .enumerate() + .map(|(i, r)| { + let d = r.discriminant(); + match required_facts { + // if this is an index that changed, limit it to only the provided set of facts + QueryFactsToConsider::LastIteration(rf) if i == cs => + rf.with_sort(d).iter().chain(empty.iter()), + // (or the set of facts from this query) + QueryFactsToConsider::Query if i == cs => + self.facts.with_sort(d).iter().chain(empty.iter()), + // otherwise, consider all facts - a new fact might be used alongside an unchanged fact! + _ => + self.facts.with_sort(d).iter().chain(self.db.facts.with_sort(d).iter()), + } + }) + .multi_cartesian_product(); + for fs in attempts { + if let Some(u) = r.unify_body(&fs) { + found.push(u); + } + } + } let mut changed = false; for u in found { - if facts.add(r.head.substitute(&u)) { changed = true; } + let new = r.head.substitute(&u); + if new.is_concrete() && !self.facts.contains(&new) && !self.db.facts.contains(&new) { + if new_facts.add(new) { changed = true; } + } } changed } - pub fn apply_rules_once(&mut self) -> bool { + fn apply_new_once(&mut self, new_facts: &mut Facts, required_facts: QueryFactsToConsider) -> bool { let mut changed = false; - for r in self.rules.iter() { - if Self::apply_rule(r, &mut self.facts) { changed = true } + match &required_facts { + QueryFactsToConsider::DB => { + // if we are considering only DB facts, we only need to consider new rules + for r in self.rules.iter() { + if self.apply_rule(r, new_facts, required_facts) { changed = true } + } + }, + _ => { // otherwise, we should consider all rules + for r in self.rules.iter().chain(self.db.rules.iter()) { + if self.apply_rule(r, new_facts, required_facts) { changed = true } + } + } } changed } - pub fn apply_rules(&mut self) { - while self.apply_rules_once() {} + pub fn fact(mut self, r: Relation) -> Self { + if !self.db.is_known(&r) { + self.facts.add(r); + } + self + } + pub fn rule(mut self, r: Rule) -> Self { + self.rules.push(r); + self + } + fn run(&mut self) { + let mut new_facts = Facts::default(); + // compare the new rules with the old facts + self.apply_new_once(&mut new_facts, QueryFactsToConsider::DB); + // compare the new+old rules with the new facts + self.apply_new_once(&mut new_facts, QueryFactsToConsider::Query); + let mut prev_facts = new_facts.clone(); + self.facts.absorb(&mut new_facts); + while self.apply_new_once(&mut new_facts, QueryFactsToConsider::LastIteration(&prev_facts)) { + prev_facts = new_facts.clone(); + self.facts.absorb(&mut new_facts); + } + } + pub fn ask(mut self) -> Facts { + self.run(); + self.facts + } + pub fn learn(mut self) { + self.run(); + self.db.facts.absorb(&mut self.facts); + self.db.rules.extend_from_slice(&mut self.rules); } } |