Reproduce “Frex: dependently-typed algebraic simplification” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Guillaume Allais, Edwin Brady, Nathan Corbyn, Ohad Kammar, Jeremy Yallop

Frex introduces a dependently typed framework for algebraic simplification, leveraging concepts from universal algebra like free algebras and free extensions to build a principled, generic library. The system guarantees termination, soundness, and completeness of simplification modules by construction, allowing for the automatic extraction of printable and certifiable proofs. It provides interactive performance, simplifying terms with up to 30 leaves for commutative monoids within one second, and has been implemented in both Idris 2 and Agda.

Key insights

  • Dependent types can be effectively utilized to encode the meta-theory of universal algebra, enabling formal guarantees of correctness for algebraic simplifiers directly within the type system.
  • Setoid-based reasoning preserves intensional information, making it possible to automatically extract and certify human-readable proof terms from successful algebraic simplifications.
  • A modular "frexlet" architecture allows for the systematic construction and reuse of simplifiers for different algebraic theories, enhancing extensibility beyond ad-hoc solutions.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.