← Back
Home › Systems › Numerical and mathematical computing

proof-assistant

proof assistant

Lean, Coq

SystemTechniques · 9Primitives · 15 proof-assistant Bidirectional type checkingcompilers · medium: Split checking into two mutually recursive modes, check against a known type and synthesize an unknown one, so annotations are needed only at a few points.›Congruence closurecompilers · medium: Union-find over terms with congruence propagation; decides equality with uninterpreted functionsDependent type theorycompilers · medium: Pi and Sigma types, universes, inductive families, definitional equality: core of Lean and CoqLanguage server protocolcompilers · medium: One JSON-RPC conversation over a pipe lets any editor drive any language's analysis server; the cost is keeping a live, edited document in sync and answering before it changes.›Normalization by evaluationcompilers · medium: Normalize lambda terms by evaluating into a semantic domain and reading back; used for type equalityTactic proof searchcompilers · medium: Tactic frameworks: goals, metavariables, backtracking, simp-style rewriting and automationCDCL SAT solvingoptimization · medium: Search for a satisfying assignment, learn a new constraint from every dead end, and jump back past irrelevant choices; handles industrial formulas with millions of clauses.›De bruijn indicescompilers · low: Nameless variable representation for binders: shifting, substitution, de Bruijn levelsUnificationcompilers · low: First-order unification with union-find and occurs check; basis of type inference and logic programmingHash consingdata-structures · low: Intern structurally equal immutable terms so equality is pointer comparison and sharing is maximalPratt parsingcompilers · low: Table-driven expression parsing with one loop and a numeric binding power per operator; the compact core of precedence handling in hand-written parsers.›Reference countingcompilers · low: Keep a count of owners in each object, free it when the count hits zero; deterministic and local, but pays on every copy and leaks cycles.›Name resolutioncompilers · low: Bind every use of a name to its declaration with a scope stack, handling shadowing, hoisting and closure capture in one AST walk.›Union-findgraphs · low: Disjoint-set forest with union by size and path compression; merges sets and answers same-set queries in effectively constant time.›Closures and upvaluescompilers · low: How interpreters and compilers let a function keep using its enclosing variables after they return: flat closures, open and closed upvalues, closure conversion, capture by value or reference.›d-ary heapdata-structures · low: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.›Drat proof certificatesoptimization · low: DRAT and LRAT proofs emitted by SAT solvers and checked independentlyTwo watched literalsoptimization · low: Unit propagation for SAT that watches just two literals per clause, so backtracking costs nothing and long clauses are rarely touched.›Arena allocatorsystems · low: Allocate by bumping a pointer through big chunks and free everything at once: a few instructions per allocation for objects sharing a lifetime.›String interningdata-structures · low: Store each distinct string once and refer to it by idSwiss tabledata-structures · low: Open-addressing hash table that filters 8-16 slots at once with 1-byte hash tags and SIMD, giving fast lookups at 87.5 % load.›Tree pattern matchingcompilers · low: Matching AST patterns with metavariables+ 2 more techniques

Similar systems

Share the most building blocks with this one.

type-checker 29 %ai-for-math 17 %