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
@type barrier() :: reference()
Functions
@spec goal(term(), Episteme.Database.t(), barrier()) :: Ichor.Backtrack.goal()
A goal (bindings -> solutions) for term, resolved under whatever barrier is currently in scope.
@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.