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

• TUTORIAL.md — a from-scratch, step-by-step walkthrough. Start here if you're new to Episteme.
• REFERENCE.md — every control construct, comparison, type check, arithmetic feature, and exception/database/ list/I/O predicate, in full detail with a verified example each.
• EXAMPLES.md — complete, verified-runnable programs (a family tree, graph reachability, a key-value store, FizzBuzz, and more).
• CHEATSHEET.md — every predicate and Elixir-side function, one page, for once you know your way around (REFERENCE.md is the page behind each row of it).
• CHANGELOG.md — release history.
• CONTRIBUTING.md — workflow, commit style, what has to pass before a change lands.
• LICENSE — MIT.

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.Term — the term representation: atoms/numbers are plain Elixir atoms/integers/floats, lists are native Elixir lists (decomposing as ISO's own '.'/2 cons functor so unification can recurse into them), variables and compounds get dedicated structs.
• Episteme.Database — clause storage, indexed by {name, arity}, storage strategy pluggable via Episteme.Database.Backend (in-memory ETS by default, on-disk DETS built in, bring your own by implementing the behaviour).
• Episteme.Engine — the resolution engine: clause selection, subgoal sequencing, control constructs (and/or/if_then/ if_then_else/cut/not/call/N/once/1 — plain English names, not real Prolog's ,/;/->/!/\+, since there's no reader here for that punctuation to be conventional syntax against) over Ichor.Backtrack, plus a real clause-scoped cut (not a once/1 stand-in — see the moduledoc on Episteme.Engine for why that distinction is load-bearing), a dynamic database (assert/1, asserta/1, assertz/1, retract/1, retractall/1), and solution aggregation (findall/3, forall/2).
• Episteme.Builtins.* — arithmetic (plus between/3), exceptions, the list predicate family, and minimal I/O.

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).