Lean 4 KnowledgeLean 4 Knowledge · 5 min read
Graph traversal answers useful questions, but knowledge engineering also encounters rules about rules, relations passed as arguments, and temporary assumptions. These are natural places to use higher-order representations. The goal is not to make every graph problem more abstract. It is to represent the structure your problem already has.
What “higher-order” changes
A first-order rule talks about individuals and applies named predicates to them. Higher-order logic can also quantify over predicates and functions. For an engineering example, a reusable reachability construction can take the edge relation as an argument: the same pattern can describe reporting lines, dependencies, or containment.
Binders introduce a second practical benefit. A formula such as “for every person, a policy holds” contains a variable with a scope. Encoding that syntax with raw strings creates opportunities for accidental capture and incorrect substitution. Higher-order abstract syntax uses the host language's binding structure to represent the object's binders, reducing the amount of substitution machinery you must implement yourself.
Where λProlog and ELPI fit
λProlog is a logic programming language designed around typed higher-order terms and scoped reasoning. ELPI extends that tradition. In the LeanElpi project, the engine is implemented in Lean, with higher-order pattern unification, backtracking, and facilities for hypothetical and universally quantified goals. The pattern restriction matters: general higher-order unification is not a simple decidable operation.
A fresh scoped variable and a temporary hypothesis let a program explore a local reasoning context. Think of checking a function body while temporarily assuming that its argument has a given type. When the local computation ends, the assumption should not leak into the surrounding knowledge base. This makes logic programming particularly useful for language tools and reasoning about structured syntax.
An answer is not yet a certificate
A successful search tells you what the search engine found. Certification is another step. LeanElpi exposes an optional LF certification layer that records derivations and translates their signatures into Lean definitions. The resulting proof is then checked by Lean. Ordinary interpreter results do not automatically gain this guarantee merely because the interpreter was written in Lean.
This separation lets you change heuristics, indexing, and search order without making those choices part of the logical justification. A buggy searcher can waste time, miss an answer, or supply an invalid certificate. It should not be able to make a correct checker accept a derivation that its rules do not justify.
Give failure the right meaning
Search exhaustion or a timeout is not generally a proof that a statement is false. The search may be incomplete, resource bounded, or operating in a fragment. Expose “not derived” separately from “refuted”, and return counterevidence only when your system really has it.
For a concrete application, LeanRDF uses Elpi to find semantic derivations and a verified checker to validate certificates. Start experimenting with the LeanElpi book and getting-started examples; then use Bulletproof Knowledge to connect scoped reasoning to agent memory.