Episteme

New to logic programming? This README assumes some familiarity with Prolog-style terminology (facts, rules, unification, backtracking...) since it's written for evaluating Episteme as a dependency. TUTORIAL.md explains every one of those terms from scratch, with plain-English walkthroughs and no assumed background at all — start there instead if any of the paragraph below is unfamiliar.

A standalone Prolog-like resolution engine and clause database for Elixir: you store facts and rules (statements, and statements that hold whenever some other statement does), ask goals (questions) against them, and get back every answer the engine can find by searching through what it knows and automatically trying alternatives (backtracking) when one path doesn't work out. Concretely, that's terms, unification (the core "make these two things match, filling in any blanks as needed" operation), backtracking search, a genuine clause-scoped cut (a real "commit to this choice" control construct, not an approximation of one), a dynamic database (assert/retract), solution aggregation (findall/forall), and a small builtin-predicate set, on top of Ichor's search substrate. No parser, no concrete surface syntax, no dependency on one: build a database and goal terms directly, or put a reader on top (real Prolog syntax is exactly what Aletheia — the sibling project this split out of — puts on top of Episteme).

alias Episteme.{Database, Term}

alias Episteme.Term.Compound



tom = :tom

{x, y, z} = {Term.new_var("X"), Term.new_var("Y"), Term.new_var("Z")}



db =

  Database.new()

  |> Database.add_fact(%Compound{name: :parent, args: [tom, :bob]})

  |> Database.add_fact(%Compound{name: :parent, args: [:bob, :ann]})

  |> Database.add_clause(

    {%Compound{name: :grandparent, args: [x, z]},

     %Compound{name: :and, args: [

       %Compound{name: :parent, args: [x, y]},

       %Compound{name: :parent, args: [y, z]}

     ]}}

  )



Episteme.query(%Compound{name: :grandparent, args: [tom, Term.new_var("Who")]}, db)

#=> {:ok, [%{"Who" => :ann}]}

Documentation

Why a separate package from Aletheia

Aletheia is the embedded-Prolog-syntax half — :-, ,/;, =, the standard operator table, a reader built on Ichor.Toolkit.Pratt. Episteme is everything underneath that a concrete syntax never actually needed: the term representation, unification and backtracking, clause storage, SLD-resolution, cut, and the builtin-predicate set. Splitting them means anyone who wants a Prolog-like rule engine/query layer in Elixir — without buying into Aletheia's .alp syntax at all — can depend on Episteme alone.

Installation

Not yet published to Hex. For now, add it as a path or git dependency alongside a checkout of this repository:

def deps do

  [

    {:episteme, path: "../episteme"}

  ]

end

How it fits together

   Database.t()  ──── clause storage: {name, arity} -> [{head, body}, ...],

         │              indexed + mutated via a pluggable Database.Backend

         │              (Backends.Ets by default, Backends.Dets for

         │              on-disk persistence); built directly, via

         │              consult_forms/2, or at runtime via assert/retract

         ▼

   Episteme.query/2 (or query_once/2, query_lazy/2 + next_solution/2)

         │

         ▼

   Episteme.Engine  ──── SLD-resolution over Ichor.Backtrack.Tree/

         │                Bindings, cut-barrier mechanism, builtin

         │                predicate dispatch (Episteme.Builtins.*)

         ▼

      solutions

Episteme depends on ichor_runtime as its one real dependency (Ichor.Backtrack, Ichor.Toolkit.TermWalk). It has no reader or grammar of its own, so — unlike Aletheia — ichor (the Aether front-end, codegen) never appears here at all.

Dynamic database and solution aggregation

assertz/1/asserta/1 (assert/1 is an alias for assertz/1) add a clause at runtime — a bare term is a fact, Head :- Body a rule — retract/1 removes the first stored clause whose head and body unify with its argument, and retractall/1 removes every clause whose head unifies with its argument (always succeeds, even against an undefined predicate). Effects are immediately visible to every subsequent call against the same Database.t(), including from separate Episteme.query/2 calls — not undone by backtracking, exactly like real Prolog:

db = Database.new()

Episteme.query(%Compound{name: :assertz, args: [%Compound{name: :fact, args: [1]}]}, db)

Episteme.query(%Compound{name: :fact, args: [Term.new_var("X")]}, db)

#=> {:ok, [%{"X" => 1}]}

findall/3 collects every solution's template into a list ([] if there are none); forall/2 succeeds iff every solution of its first goal has at least one solution of its second. Both are cut-opaque and bind nothing outside themselves, same as not/1.

Storage backends

Database.new/1 takes a :backend option — Episteme.Database.Backends.Ets (the default: in-memory, indexed by {name, arity}) or Episteme.Database.Backends.Dets (the same shape, persisted to a file, so a database survives past the process or the VM that built it):

db = Database.new(backend: Episteme.Database.Backends.Dets, file: "facts.dets")

# ... assert/consult as usual ...

Database.sync(db)   # flush to disk now, rather than whenever :dets gets to it

Database.close(db)  # release the file handle

Because a Database.t() now wraps a mutable resource rather than being a plain immutable value, call Database.close/1 when you're done with one you don't want to leak (an ETS-backed database is cleaned up automatically if its owning process exits; a DETS-backed one holds an open file handle until closed). Any other storage strategy — an Agent, a remote store, whatever a given deployment needs — is a matter of implementing Episteme.Database.Backend's five callbacks and passing that module as :backend.

Development

mix deps.get

mix test

mix format --check-formatted

mix compile --warnings-as-errors

mix docs

See CONTRIBUTING.md for the full workflow (git flow branching, commit style, what mix precommit runs, and what to update when adding a new predicate).