Add semi-naive Datalog evaluation

4 files changed, 232 insertions, 27 deletions

diff --git a/crates/elfmind/Cargo.toml b/crates/elfmind/Cargo.toml
index fc8d9e0..982623d 100644
--- a/crates/elfmind/Cargo.toml
+++ b/crates/elfmind/Cargo.toml
@@ -24,6 +24,7 @@ enum-map = { workspace = true }
 serde = { workspace = true }
 bincode = { workspace = true }
 itertools = { workspace = true }
+smallbox = { workspace = true }
 
 [target.'cfg(target_arch = "wasm32")'.dependencies]
 wasm-bindgen = { workspace = true }
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);
     }
 }
 
diff --git a/crates/elfmind/src/knowledge/relation.rs b/crates/elfmind/src/knowledge/relation.rs
index 754bf0f..b738aa1 100644
--- a/crates/elfmind/src/knowledge/relation.rs
+++ b/crates/elfmind/src/knowledge/relation.rs
@@ -7,6 +7,76 @@ use crate::character::*;
 use enum_map::Enum;
 use strum::EnumDiscriminants;
 
+pub trait Concretizable {
+    type Concrete;
+    fn concretize(&self) -> Option<Self::Concrete>;
+}
+impl<A: Clone> Concretizable for Hole<A> {
+    type Concrete = A;
+    fn concretize(&self) -> Option<Self::Concrete> {
+        match self {
+            Self::Val(x) => Some(x.clone()),
+            _ => None,
+        }
+    }
+}
+impl<
+    A: Clone,
+    B: Clone,
+    > Concretizable for (Hole<A>, Hole<B>) {
+    type Concrete = (A, B);
+    fn concretize(&self) -> Option<Self::Concrete> {
+        let a = self.0.concretize()?;
+        let b = self.1.concretize()?;
+        Some((a, b))
+    }
+}
+impl<
+    A: Clone,
+    B: Clone,
+    C: Clone,
+    > Concretizable for (Hole<A>, Hole<B>, Hole<C>) {
+        type Concrete = (A, B, C);
+    fn concretize(&self) -> Option<Self::Concrete> {
+        let a = self.0.concretize()?;
+        let b = self.1.concretize()?;
+        let c = self.2.concretize()?;
+        Some((a, b, c))
+    }
+}
+impl<
+    A: Clone,
+    B: Clone,
+    C: Clone,
+    D: Clone,
+    > Concretizable for (Hole<A>, Hole<B>, Hole<C>, Hole<D>) {
+        type Concrete = (A, B, C, D);
+    fn concretize(&self) -> Option<Self::Concrete> {
+        let a = self.0.concretize()?;
+        let b = self.1.concretize()?;
+        let c = self.2.concretize()?;
+        let d = self.3.concretize()?;
+        Some((a, b, c, d))
+    }
+}
+impl<
+    A: Clone,
+    B: Clone,
+    C: Clone,
+    D: Clone,
+    E: Clone,
+    > Concretizable for (Hole<A>, Hole<B>, Hole<C>, Hole<D>, Hole<E>) {
+        type Concrete = (A, B, C, D, E);
+    fn concretize(&self) -> Option<Self::Concrete> {
+        let a = self.0.concretize()?;
+        let b = self.1.concretize()?;
+        let c = self.2.concretize()?;
+        let d = self.3.concretize()?;
+        let e = self.4.concretize()?;
+        Some((a, b, c, d, e))
+    }
+}
+
 pub trait Substitutable {
     fn substitute(&self, u: &Unification) -> Self;
 }
@@ -140,6 +210,16 @@ pub enum Relation {
     TimeIs(Hole<Time>),
     FriendOf((Hole<Character>, Hole<Character>)),
 }
+impl Relation {
+    pub fn is_concrete(&self) -> bool {
+        match self {
+            Self::HasItem(x) => x.concretize().is_some(),
+            Self::UsedItemAt(x) => x.concretize().is_some(),
+            Self::TimeIs(x) => x.concretize().is_some(),
+            Self::FriendOf(x) => x.concretize().is_some(),
+        }
+    }
+}
 impl Substitutable for Relation {
     fn substitute(&self, u: &Unification) -> Self {
         match self {
diff --git a/crates/elfmind/src/main.rs b/crates/elfmind/src/main.rs
index cd811f7..19b8a03 100644
--- a/crates/elfmind/src/main.rs
+++ b/crates/elfmind/src/main.rs
@@ -4,13 +4,13 @@ use knowledge::*;
 fn main() {
     let mut ctx = Context::default();
     let mut db = Database::default();
-    db.add_fact(Relation::TimeIs(Hole::Val(6)));
-    db.add_fact(Relation::TimeIs(Hole::Val(7)));
-    db.add_fact(Relation::HasItem((Hole::Val(character::Character::Tyumici), Hole::Val(item::Item::Apple))));
-    db.add_fact(Relation::FriendOf((Hole::Val(character::Character::Bobo), Hole::Val(character::Character::Naesten))));
+    db.query()
+        .fact(Relation::HasItem((Hole::Val(character::Character::Tyumici), Hole::Val(item::Item::Apple))))
+        .fact(Relation::FriendOf((Hole::Val(character::Character::Bobo), Hole::Val(character::Character::Naesten))))
+        .learn();
     let vt = ctx.var("time");
     let vi = ctx.var("item");
-    db.add_rule(Rule {
+    db.query().rule(Rule {
         head: Relation::UsedItemAt((
             Hole::Val(character::Character::Tyumici),
             Hole::Var(vi),
@@ -20,10 +20,10 @@ fn main() {
             Relation::TimeIs(Hole::Var(vt)),
             Relation::HasItem((Hole::Val(character::Character::Tyumici), Hole::Var(vi))),
         ],
-    });
+    }).learn();
     let vt = ctx.var("time");
     let vc = ctx.var("char");
-    db.add_rule(Rule {
+    db.query().rule(Rule {
         head: Relation::FriendOf((
             Hole::Val(character::Character::Naesten),
             Hole::Var(vc),
@@ -32,11 +32,11 @@ fn main() {
             Relation::TimeIs(Hole::Var(vt)),
             Relation::UsedItemAt((Hole::Var(vc), Hole::Val(item::Item::Apple), Hole::Var(vt))),
         ],
-    });
+    }).learn();
     let vc1 = ctx.var("char");
     let vc2 = ctx.var("char");
     let vc3 = ctx.var("char");
-    db.add_rule(Rule {
+    db.query().rule(Rule {
         head: Relation::FriendOf((
             Hole::Var(vc1),
             Hole::Var(vc3),
@@ -45,7 +45,7 @@ fn main() {
             Relation::FriendOf((Hole::Var(vc1), Hole::Var(vc2))),
             Relation::FriendOf((Hole::Var(vc2), Hole::Var(vc3))),
         ],
-    });
-    db.apply_rules();
-    println!("{:#?}", db);
+    }).learn();
+    println!("{:#?}", db.query().fact(Relation::TimeIs(Hole::Val(8))).ask());
+        
 }