The project ended on July 31, 2026. We keep the web site as an archive of the project and no longer update it.
TyDiForm focused on designing and implementing new techniques for formal verification of mathematics with the aim of improving the capabilities of proof assistants. In the project, we built on the synergy between formalized mathematics and databases of mathematical structures, and developed domain-specific type theories and type systems for programming languages. The sections below state the goals of the project and summarize the results by theme.
Project information:
Formalized mathematics is mathematical knowledge presented in a form that can be processed and verified by proof assistants, which check correctness of all the reasoning steps. Libraries of formalized mathematics collect and curate definitions, theorems, and proofs from various branches of mathematics.
Apart from proving theorems, mathematicians also curate large collections of mathematical structures, which are used for mathematical exploration, hypothesis testing, and discovery of new mathematical laws. These collections are generated with computers, but rarely formally verified by computers.
We set out to apply mathematical formalization methods to these collections, in order to give assurance of their correctness and to enable further exploration and analysis. A further aim was to facilitate the incorporation of such databases into proof assistants.
We developed Lean-HoG, a library for the Lean 4 proof assistant that incorporates and formally verifies the House of Graphs database, a collection of 20,000 small graphs with their invariants. For that purpose we developed a computationally efficient formalization of graph theory, and the infrastructure for the exchange of data between the database and the proof assistant.
We improved MathDataHub, a repository of mathematical data sets, and helped build MathBases, an index of mathematical databases. We built Mathswitch, which links records of mathematical concepts across Wikidata, Wikipedia, nLab, MathWorld, ProofWiki, the Encyclopedia of Mathematics and agda-unimath. We proposed maniplexes, a combinatorial framework that encompasses graphs, surface maps and polytopes, as a common foundation for cross-linking databases of symmetric objects.
We applied machine learning to formalized mathematics. We published MLFMF, a collection of data sets for training recommendation systems that help a user find the library entries relevant to a new theorem or construction. The collection comprises the Lean 4 library Mathlib, the Agda standard library, agda-unimath and TypeTopology. For premise selection in Lean 4, we combined the text of formalizations with the dependency structure of Mathlib, and the combination outperformed models that use the text alone.
Most formalized mathematics is written in one of many flavors of type theory. Ordinarily, a type theory is designed to be general and very expressive, so that it can incorporate most, if not all mathematics. However, databases of mathematical structures are almost always narrowly specialized, e.g., they contain just graphs, or just finite groups. To make formal processing of such databases efficient, we set out to design domain-specific type theories that are small and tailored for representation and verification of large databases of mathematical structures. In addition, we planned to design and implement transformations between type theories that allow the databases to be interfaced with proof assistants and other tools for formal reasoning.
Domain-specific type theories have other uses in formalized mathematics as well. They can be used to express auxiliary notions of type theory, such as universe levels and induction schemata, and to give modular and reusable implementations of automated reasoning algorithms.
We gave a general account of finitary type theories and proved that they satisfy the standard meta-theorems. We developed an extensible equality checking algorithm for standard type theories, proved that it is sound, and implemented it in the Andromeda 2 proof assistant. We defined a general notion of elaboration and proved that every finitary type theory can be elaborated to a standard type theory. Philipp Haselwarter and Anja Petković Komel wrote their doctoral dissertations on these results.
We gave a category-theoretic account of higher-rank syntax as a relative monad on a category of presheaves. Higher-rank syntax unifies the levels of syntax found in dependent type theories, namely variables, meta-variables and primitive symbols, each with a notion of substitution.
We developed a domain-specific type theory for finite discrete structures, based on the groupoid model of type theory, and formalized it in Lean. From the definition of a type, the formalization extracts a program that enumerates the elements of the type. The program is written in Enumix, a domain-specific language that we designed for compilation to efficient code running on multiple processors or on GPUs.
A second goal of the project was the development of novel type systems for programming languages with low-level real-world computational effects that exhibit asynchronous, stochastic, or even quantum-mechanical behavior. We set out to adapt and extend algebraic effect systems, which had until then been used successfully to describe computational effects as a programming technique for implementation of effects within a language. The results improve our ability to design and verify the interaction of programs with their external environments.
We extended our work on asynchronous algebraic effects to higher-order asynchronous effects, which cover pre-emptive multi-tasking, remote function calls and multi-party web applications. We designed a modal type system for temporal resources, such as external devices that need a certain amount of time to complete an action. The type system guarantees that programs using temporal resources work correctly.
We worked on an optimizing compiler for algebraic effects and handlers. We developed a simplification algorithm for polymorphic subtyping constraints, and proved the correctness of the translation and of the optimization phases of the compiler. We took part in the development of WasmFX, which introduces effect handlers into WebAssembly, and of SpecTec, a domain-specific language for writing the specification of WebAssembly.
We designed Clerical, an imperative language for exact real-number computation, together with a specification logic for proving the correctness of programs, and formalized large parts of the work in the Rocq proof assistant. We laid the mathematical foundations of symmetric programming, a style of programming that exploits the symmetries present in data and in proofs.
Homotopy type theory interprets types as spaces and equalities as paths. Univalent mathematics is the mathematics developed in homotopy type theory.
Egbert Rijke started agda-unimath, a library of formalized univalent mathematics for the Agda proof assistant. The library became the largest body of formalized mathematics in Agda, and a community of contributors develops it. Egbert Rijke’s textbook Introduction to Homotopy Type Theory appeared with Cambridge University Press in 2025.
We developed univalent combinatorics, including a univalent type of hydrocarbons that captures the symmetries of isomers. With coauthors we proved that C-systems and B-systems, two algebraic presentations of dependent type theories, are equivalent, as Vladimir Voevodsky had conjectured. We characterized the epimorphisms in homotopy type theory as the fiberwise acyclic maps.
We studied cubical assemblies, which are realizability models of homotopy type theory, in order to connect homotopy theory with computability. We defined computable 2-groups, showed that cubical assemblies have no subobject classifier, and used cohomology to measure the failure of the axiom of countable choice.
We discovered parameterized realizability, a new model of computation, and used it to construct a model of intuitionistic mathematics in which the Dedekind real numbers are countable. The construction shows that Cantor’s diagonal argument requires excluded middle or countable choice.
We developed a theory of oracle modalities, which express computation relative to an oracle in type theory and allow the study of Turing degrees independently of any particular model of computation. We showed that every modality is an oracle modality, and formalized the theory in Rocq.
We developed comodule representations of second-order functionals, which subsume the classic representations of continuous functionals by well-founded trees.