ProofCloud: A Proof Retrieval Engine for Verified Proofs in Higher Order Logic
Shuai Wang · 2024
Read ProofCloud: A Proof Retrieval Engine for Verified Proofs in Higher Order Logic by Shuai Wang (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-20947.txt.
Description
Abstract This paper introduces ProofCloud, a proof retrieval engine for verified proofs in higher order logic. It provides a fast proof searching service for mathematicians and computer scientists for the reuse of proofs and proof packages. In addition, it includes the first complete proof-checking results and benchmarks of the OpenTheory repository.
Catalog record
| CREATOR | Shuai Wang |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 16 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-20947
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ProofCloud: A Proof Retrieval Engine for Verified Proofs in Higher Order Logic Shuai Wang Abstract This paper introduces ProofCloud, a proof retrieval engine for verified proofs in higher order logic. It provides a fast proof searching service for mathematicians and computer scientists for the reuse of proofs and proof packages. In addition, it includes the first complete proof-checking results and benchmarks of the OpenTheory repository. 1 1 1 The paper has been presented at the International Workshop on User Interfaces for Theorem Provers (UITP) in 2016. August 24, 2026 1 Introduction \justify Interactive Theorem Provers (ITPs) have been playing an important role in formal mathematics, software verification and hardware verification. In recent years, there has been dramatic progress in the usability and power of ITPs. Among them, theorem provers in the HOL family are among the most widely used in this domain. The HOL family consists of HOL Light [ 1 ] , HOL4 [ 2 ] and ProofPower [ 3 ] , to name a few. These ITPs implement the same higher order logic, namely Church’s simple type theory [ 4 ] . However, they each contain significant theory formalisations that are not accessible to each other. HOL Light [ 1 ] has a formalisation of complex analysis while HOL4 has a formalisation of probability theory [ 2 ] . In contrast, ProofPower has a formalization of the Z specification language [ 3 ] . These ITPs were developed without considering proof sharing and reuse to avoid repeated work proving large theorems. Moreover, ITPs may not be bug-free and may lead to errors in generated proofs which are not necessarily apparent within the proof systems themselves. Additionally, proofs can be huge, making them difficult or even impossible to be checked by hand (e.g. the Kepler Conjecture [ 5 ] ). The demand of reliability of such systems leads to the necessity of proof checking, especially methods and tools independent from the ITPs involved. All this requires theorem provers to export proofs in a certain format. OpenTheory is a format and a proof repository for the HOL family with this purpose. Taking advantage of the similarity of the logic and design between these systems, OpenTheory [ 4 ] has developed a standard format for serializing proofs and sharing proofs [ 4 ] . ITPs in the HOL family can export proofs to the OpenTheory format as article files (packages of proofs and relevant information). These files are then converted to Dedukti [ 6 ] format by a proof translator, namely Holide [ 7 ] , for the sake of proof checking. HOL Light [ 1 ] is an open source interactive theorem prover for higher order logic. Its logic is an extension of Church’s simple type theory with polymorphic type [ 1 ] . Higher order logic is also known as simple type theory. It is a logic on top of simply typed \lambda -calculus with additional axioms and inference rules [ 1 ] . The type of a term is either an individual, a boolean type or a function type. A term is either a constant, a variable (e.g. x ), an abstraction (e.g. \lambda x.x ) or a well-typed application (e.g. (\lambda x.x)y) . The notation x:\iota means that the term x is of type \iota . Types are sometimes omitted for simplicity of representation. The equality is of polymorphic type and plays three roles in HOL Light: definition, equivalence and bi-implication. type variables \alpha,\beta type operators p types A,B::=\alpha\,|\,p(A_{1},\ldots,A_{n}) term variables x,y term constants c terms M,N::=x\,|\,\lambda x:A.M\,|\,MN\,|\,c This paper presents ProofCloud, a proof retrieval engine for retrieval of verified higher order logic proofs and some related proof checking results. This paper is organised as follows: we first introduce OpenTheory and explain its kernel and the recent updates in Section 2 . Following that is ProofCloud (Section 3 ) and the implementation (Section 4 ). Finally, the evaluation and benchmarks of proof checking are included. 2 OpenTheory OpenTheory [ 4 ] is a cross-platform proof package manager for proofs in ITPs of the HOL family. The standard library of OpenTheory groups theorems into packages, including theorems of booleans, sets, lists, etc. Moreover, it contains a repository of proof packages allowing sharing and reuse of proofs between theorem provers in the HOL family. OpenTheory has inspired further exploration of proof management between HOL families [ 8 ] as well as the development of several projects (e.g. [ 7 ] and [ 9 ] ) taking advantage of these packages. Table 1: OpenTheory version 5 Logic Kernel \text{refl}\,t \vdash t=t \text{assume}\,\varphi \left\{{\varphi}\right\}\vdash\varphi \Delta\vdash\varphi \Gamma\vdash\varphi=\psi eqMp \Gamma\cup\Delta\vdash\psi \Gamma\vdash t=u \text{absThm}\,v \Gamma\vdash(\lambda v.t)=(\lambda v.u) \Gamma\vdash f=g \Delta\vdash x=y appThm \Gamma\cup\Delta\vdash fx=gy \Gamma\vdash\varphi \Delta\vdash\psi deductAntisym (\Gamma\setminus\left\{{\psi}\right\})\cup(\Delta\setminus\left\{{\varphi}\right\})\vdash\varphi=\psi \Gamma\vdash\varphi \text{subst}\sigma \Gamma[\sigma]\vdash\varphi[\sigma] \text{betaConv}((\lambda v.t)u) \vdash(\lambda v.t)u=t[u/v] \text{defineConst}ct c=t \vdash\varphi\,t \text{defineTypeOp}\kern 5.0ptn\kern 5.0ptabs\kern 5.0ptrep\kern 5.0ptvs \vdash abs(rep\,a)=a\kern 5.0pt\kern 5.0pt\kern 5.0pt\kern 5.0pt\vdash(rep(abs\,r)=r)=\varphi\,r Table 1 illustrates the primitive inference rules of the OpenTheory logic kernel which has some small differences compared with the HOL Light kernel 2 2 2 Note that appThm Corresponds to MK_COMB in HOL Light. . Different from other proof libraries, OpenTheory was not designed to be a general purpose proof repository. It is a specialised library and format for proof sharing between the ITPs in the HOL family. 3 ProofCloud We introduce ProofCloud 3 3 3 http://airobert.github.io/proofcloud/ , a proof retrieval engine, for easy searching of verified higher order logic proofs. It consists of a presentation of proofs and proof packages, the results of some statistical and structural analyses, together with their proof checking results. So far it has been populated with 1687 proofs from 6 packages of OpenTheory. Information of each proof and package is presented on seperate webpages. Taking classical proofs as those using the axiom of choice, ProofCloud can distinguish between classical proofs and constructive proofs. Furthermore, it tracks the origin of classicism, in other words, which classical lemmas 4 4 4 To avoid confusion, all theorems used to prove the conclusion are referred to as lemmas when referring to a specific theorem. were used within the proof. With this ability, the amount as well as the percentage of classical proofs of a certain package is calculated and displayed on its (package) page. Users will also find a statistical analysis on the size of proofs and links to proof checking results. As far as the author knows, this is the only online proof retrieval engine of its kind. The specifications of ProofCloud is presented in Appendix A . Figure 1: The Interface of ProofCloud 4 Implementation ProofCloud is a customised search engine from Swiftype 5 5 5 Swiftype ( https://swiftype.com/ ) is a customisable search engine with simple APIs and real-time indexing. . It was implemented to provide fast searching service of proofs for mathematicians and computer scientists using ITPs in the HOL family. It has an elegant and user-friendly interface with the search results clearly displayed. It has been on service since July 2015 and just been upgraded to version 2. It contains more than 1700 pages of information about theorems and packages of higher order logic. These pages were generated by extending a modified version of HOL Light 6 6 6 http://src.gilith.com/hol-light.html with functions to import and export proof