mengine

MEngine is a dependently typed kernel with explicit context management, a proof engine, a tactic language, and a theorem prover, optimized for highly automated proof scripts.

The original ideas and design of MEngine were detailed in my master's thesis¹, but have since been refined.

How it works

MEngine represents proof terms as λ-DAGs ²: directed acyclic graphs where subterms are shared by reference rather than duplicated. Variable nodes are pointer-unique: one heap allocation per variable, so every reference to x is literally the same pointer. Applications, abstractions, and other compound nodes hold references to their children, and every node keeps pointers its type, minimal context, and incoming references. All terms manipulated by a tactic live in the same DAG. Holes (e-vars/metavariables) are also first-class nodes.

The intended workflow: write proofs in MEngine's scripting language (.me files) using built-in tactics (exact, rewrite, induction, match_goal, apply, etc.) or define new tactics directly in the language.

Quick Start

# Install dependencies (if on macOS)
make install-tools
# Build CLI `mengine` and library `libmengine.a`
make
# Run examples
make examples

For development, it is helpful to generate a .clangd:

make clangd

Usage:

./mengine
./mengine path/to/script.me
./mengine --help  # for options

Check out examples/ for scripts showing the syntax.

Status

This is a prototype! My goals include:

• examples of verifying large imperative programs
• all proofs continue to generate Coq-checkable proof terms
• a tactic scripting language for writing new tactics

Benchmark Results

Benchmark	Description	Plot
addr0_let_in	Rewriting add_r_O inside nested let-bindings	overview
context_order_validity	Deep-context valid_in_context queries for order-backend comparison	overview
evar_free_filling	Hole filling with a large evar-free proof term	overview
repeat_mod	Rewriting nested modulo chains (mod (mod ... b p) p) = (mod b p)	overview
rewrite_fa	Rewriting f(f(...f(a))) = a with n nested applications	overview
rewrite_nm	Rewriting f(x,...,x)=x in let x1:=f x0..x0 in ... let xm:=f x(m-1)..x(m-1) in xm=x0	m1 m6 m10 7 more plot(s) omitted
separation_logic	Separation logic predicate cancellation (reordering sep predicates)	overview
substitution_sharing	Substitution through a dependent type with repeated references to one shared let-bound subtree	overview
symbolic_execution	Symbolic execution of imperative programs with partial maps	overview

Footnotes

1. https://dspace.mit.edu/handle/1721.1/162908 ↩

2. https://link.springer.com/chapter/10.1007/978-3-540-31987-0_16 ↩