Episteme.Engine (Episteme v0.1.0)

Copy Markdown View Source

SLD-resolution over Ichor.Backtrack.Tree + Ichor.Backtrack.Bindings plus Episteme.Database -- clause selection is disjunction/2 folded over a predicate's clauses in declared order, subgoal sequencing is conjunction/2, both reused unmodified from Ichor. Control constructs (and, or, if_then/if_then_else, cut, not/1, call/N, once/1) live directly here rather than in a separate builtins module: they turned out, once actually implemented, to be inseparable from the cut-barrier machinery below, not independent predicates dispatchable through a generic table. Every one of these is a plain English name, not the traditional Prolog operator (,/;/->/!/ \+) it corresponds to -- Episteme has no reader of its own (see Episteme's moduledoc), so there's no textual syntax for any of this to look "conventional" against; a word you can actually remember beat matching ISO Prolog's punctuation.

Cut

Ichor.Backtrack.Tree's once/1 is not cut -- cut commits to every choice made since entering the current clause specifically, including pruning alternatives for goals that already SUCCEEDED earlier in the same body, which a bindings-borne "cut fired" marker can't express. The textbook illustration, in real Prolog's own textual syntax: p :- !, fail. with a second clause p :- true. must fail p outright (cut commits to clause 1 before fail ever runs), but a clause body that never produces a solution never gives a marker-on-solutions scheme anything to inspect.

So cut succeeds once normally, but its "give me another solution" continuation throw({:episteme_cut, barrier})s instead of returning :empty. Every predicate call (and call/N, once/1, not/1 -- each cut-opaque per ISO) mints a fresh barrier = make_ref() and wraps its own clause-disjunction's lazy solution stream in guard_cut/2, which re-wraps every successive rest thunk so the guard is active no matter how many times -- or how much later -- a caller pulls another solution, catching only throws tagged with its own barrier (catch {:episteme_cut, ^barrier} -> :empty) and re-throwing (letting Elixir's own catch semantics do it for free) any other tag, so a cut inside a called predicate never escapes past its own frame to affect the caller.

Because Ichor.Backtrack.Tree's combinators are plain function calls with no try anywhere inside them, a throw passes through conjunction/disjunction/once completely untouched -- this needs zero changes to Ichor itself.

Summary

Functions

A goal (bindings -> solutions) for term, resolved under whatever barrier is currently in scope.

Solves goal_term against db from empty bindings -- the top-level query entry point. Genuinely lazy even in the very first dispatch step: a goal function call is itself eager (only the rest of a search tree is deferred by Ichor.Backtrack.Tree's own combinators), so a builtin that throws immediately on its first attempt (calling an undefined predicate, say) would otherwise escape before a caller pulling solutions one at a time (Episteme.next_solution/2) ever gets a chance to guard it -- wrapping everything in one more thunk here defers that first dispatch until whoever holds this value actually calls Ichor.Backtrack.Tree's next/1 on it.

Types

barrier()

@type barrier() :: reference()

Functions

goal(term, db, barrier)

A goal (bindings -> solutions) for term, resolved under whatever barrier is currently in scope.

solve_query(goal_term, db)

@spec solve_query(term(), Episteme.Database.t()) :: Ichor.Backtrack.Tree.t()

Solves goal_term against db from empty bindings -- the top-level query entry point. Genuinely lazy even in the very first dispatch step: a goal function call is itself eager (only the rest of a search tree is deferred by Ichor.Backtrack.Tree's own combinators), so a builtin that throws immediately on its first attempt (calling an undefined predicate, say) would otherwise escape before a caller pulling solutions one at a time (Episteme.next_solution/2) ever gets a chance to guard it -- wrapping everything in one more thunk here defers that first dispatch until whoever holds this value actually calls Ichor.Backtrack.Tree's next/1 on it.