summaryrefslogtreecommitdiff
path: root/crates/elfmind
diff options
context:
space:
mode:
Diffstat (limited to 'crates/elfmind')
-rw-r--r--crates/elfmind/Cargo.toml1
-rw-r--r--crates/elfmind/src/knowledge.rs154
-rw-r--r--crates/elfmind/src/knowledge/relation.rs80
-rw-r--r--crates/elfmind/src/main.rs24
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());
+
}
generated by cgit v1.3.1 (git 2.54.0) at 2026-10-31 06:48:56 +0000