A tale of four theorem provers, or: A (reasonably) opinionated comparison of Isabelle/HOL, Lean, HOL4, and Agda

本文为原文前 6,000 字符的节选翻译，完整内容请查看原文。

A tale of four theorem provers, or: A (reasonably) opinionated comparison of Isabelle/HOL, Lean, HOL4, and Agda.

四位定理证明者的故事，或者：对 Isabelle/HOL、Lean、HOL4 和 Agda 的（相当）主观的比较。

The above (wow, long title) In which I compare Lean, Isabelle/HOL, Agda, and HOL4 with only mild regard for “fairness”.

以上（哇，好长的标题）在文中，我比较了 Lean、Isabelle/HOL、Agda 和 HOL4，且仅对“公平性”给予了轻微的关注。

What are we comparing, anyway? All four of the above are theorem proving applications; that is, their purpose is to computer-formalize mathematics. Broadly speaking, both Lean and Agda are dependent-types based systems, utilizing the Curry-Howard correspondence to prove theorems via a complex type system, whereas Isabelle/HOL and HOL4 are LCF-style systems, with a small “proof kernel” containing base rules (e.g. forall x, x = x) that all proofs must be constructed via. Both foundations have advantages and disadvantages, and some will be discussed.

我们到底在比较什么？上述四者均为定理证明应用程序；也就是说，它们的目的是将数学计算机形式化。广义上讲，Lean 和 Agda 都是基于依赖类型的系统，利用 Curry-Howard 同构通过复杂的类型系统来证明定理；而 Isabelle/HOL 和 HOL4 是 LCF 风格的系统，具有一个包含基本规则（例如 forall x, x = x）的小型“证明内核”，所有证明都必须通过这些规则构建。这两种基础各有利弊，文中将讨论其中一些。

And on what? I have formalized in all four a proof of the infinitude of primes; that is, the statement “For any number n, there is a prime larger than n”. The exact proof formalized is the “usual” construction by Euclid, which you can find on Wikipedia if you want; see here. All of the proofs structurally look similar (mostly, we’ll get to that), and hence it was the user experience that made the difference. For transparency, before this experiment, I was most familiar with Isabelle/HOL and Agda, and to some extent learnt HOL4 and Lean as part of this review.

比较什么内容？我在所有四个系统中都形式化了一个关于素数无穷性的证明；即“对于任何数字 n，都存在一个大于 n 的素数”这一陈述。所形式化的确切证明是欧几里得的“常规”构造，如果你愿意，可以在维基百科上找到它；见此处。所有证明在结构上看起来都很相似（大部分如此，我们稍后会谈到），因此用户体验才是造成差异的原因。为了透明起见，在本次实验之前，我最熟悉 Isabelle/HOL 和 Agda，并在本次评估中在一定程度上学习了 HOL4 和 Lean。

Comparison time! What follows is a bunch of opinions and somewhat arbitrary categories. Don’t expect an unbiased review, please. If you only want proof comparisons, skip to Proof Comparisons, and if you only want more opinions, read the below and then skip to Arbitrary Rankings. The opinions go first. I do not claim any of the following proofs are perfect! They’re probably quite mediocre, really.

比较时间！接下来是一堆观点和一些相当随意的分类。请不要期待一篇公正的评论。如果你只想看证明比较，请跳至“证明比较”；如果你只想看更多观点，请阅读下文，然后跳至“随意排名”。观点先行。我不认为以下任何证明是完美的！它们实际上可能相当平庸。

Overarching similarities/differences There are a few categories by which we can group these theorem provers. We have the above mentioned: LCF-style: Isabelle/HOL, HOL4 Dependent-style: Lean, Agda But there’s also: Interactivity High-interactivity: Isabelle/HOL, Lean Low-interactivity: HOL4, Agda.

总体相似点/差异点：我们可以通过几个类别对这些定理证明器进行分组。我们有上述提到的：LCF 风格：Isabelle/HOL、HOL4；依赖类型风格：Lean、Agda。但还有：交互性：高交互性：Isabelle/HOL、Lean；低交互性：HOL4、Agda。

Reasoning: Both Isabelle/HOL and Lean provide “live updates” as you type, and their structured proofs can be “down-arrow“‘d through, to see intermediate steps. In contrast, both completed HOL4 and Agda proofs exist as fully-put-together terms that must be manually taken apart if you wish to inspect their internals. Both HOL4 and Agda can show you your current state and related information at any time, of course.

推理：Isabelle/HOL 和 Lean 都能在你输入时提供“实时更新”，并且可以通过“向下箭头”浏览它们的结构化证明，以查看中间步骤。相比之下，完成的 HOL4 和 Agda 证明都以完整组合项的形式存在，如果你想检查其内部结构，必须手动将其拆解。当然，HOL4 和 Agda 都可以随时向你显示当前状态及相关信息。

Automation High-automation: Isabelle/HOL, HOL4 Medium-automation: Lean Low-automation: Agda Isabelle/HOL has sledgehammer, which calls out to a number of external proof generation methods (SAT/SMT solvers, various FOL solvers, etc). For any goal that looks doable-but-annoying, there’s a solid chance sledgehammer can solve it - this is nice because it saves you work, but the proofs it generates are also indecipherable, which is perhaps less than ideal.

自动化：高自动化：Isabelle/HOL、HOL4；中自动化：Lean；低自动化：Agda。Isabelle/HOL 拥有 sledgehammer，它会调用多种外部证明生成方法（SAT/SMT 求解器、各种 FOL 求解器等）。对于任何看起来可行但令人烦恼的目标，sledgehammer 很有可能解决它——这很好，因为它节省了你的工作量，但它生成的证明也难以解读，这可能不太理想。

There also exists an equivalent for HOL4 called HolyHammer, but I didn’t realize it existed until after I was writing this. Oh well. Isabelle/HOL and HOL4 both have very good support for many automated simplification and proof methods, which come in quite handy when trying to work with complex assumptions, for example. It may not be obvious how to proceed without simplification kicking in to chunk everything down.

HOL4 也有一个名为 HolyHammer 的等效工具，但我直到写完这篇文章才意识到它的存在。好吧。Isabelle/HOL 和 HOL4 对许多自动化简化和证明方法都有很好的支持，例如在处理复杂假设时非常方便。如果没有简化介入将一切拆解，可能很难看出如何继续。

Lean has decent automation, but not to the same level as Isabelle/HOL or HOL4. Its simp is not nearly as productive, and while grind is a very neat approach that can sometimes rival sledgehammer, a lot of the time it’s quite useless for reasons beyond me. Both sledgehammer and grind are all-or-nothing; if they don’t solve the goal, they make no progress. This is in contrast to simp (in all three), or more specialized tools like auto (Isabelle/HOL) or gvs (HOL4), which can make some progress and then leave the context in (ideally) a better place.

Lean 的自动化水平尚可，但未达到 Isabelle/HOL 或 HOL4 的水平。它的 simp 效率远不如前者，虽然 grind 是一种非常巧妙的方法，有时可以媲美 sledgehammer，但很多时候它因我不理解的原因而毫无用处。sledgehammer 和 grind 都是“全有或全无”的；如果它们不能解决目标，就不会有任何进展。这与 simp（在所有三个系统中）或更专业的工具（如 Isabelle/HOL 中的 auto 或 HOL4 中的 gvs）形成对比，后者可以取得一些进展，然后（理想情况下）将上下文留在更好的状态。

The fact Lean doesn’t have nearly as good partial-automation is a bit of a shame, because in my experience that’s what actually matters more. Notably, both Lean and Isabelle/HOL have a try (In Isabelle/HOL, try/try0 for with/without sledgehammer; in Lean, try?/exact?/rw?) that “have a go” at your goal with various automated methods and direct solve attempts. HOL4 doesn’t have an equivalent, as far as I can tell, which is unfortunate, as it’s quite handy.

Lean 没有同样优秀的局部自动化功能确实有点遗憾，因为根据我的经验，这才是真正重要的地方。值得注意的是，Lean 和 Isabelle/HOL 都有一个 try 功能（在 Isabelle/HOL 中是 try/try0，用于配合或不配合 sledgehammer；在 Lean 中是 try?/exact?/rw?），它们会用各种自动化方法和直接求解尝试来“尝试”你的目标。据我所知，HOL4 没有等效功能，这很不幸，因为它非常方便。

Agda has essentially no automation. The only simplification you get is what can be computed based on inputs to functions. This, to be a bit frank, sort of sucks. It’s quite hard to get things done because there’s so much manual fiddling that must be taken into account. I am personally not a fan.

Agda 基本没有自动化。你得到的唯一简化是基于函数输入所能计算的内容。坦率地说，这有点糟糕。因为必须考虑太多的手动调整，所以很难完成工作。我个人不太喜欢。

Foundations Isabelle/HOL and HOL4 are both extremely classical in their foundations, which means that they accept the Law of Excluded Middle (∀ P. ¬P ∨ P), and both also axiomatize Hilbert’s epsilon, which leads also to the Axiom of Choice. This seems to have a very positive effect on automated solvers, which quite often rely on laws such as double-negation elimination (¬¬P —> P), which is equivalent to the LEM. Lean is theoretically constructive (and hence does not have the LEM by default), but some of the “good” proof automation requires the LEM, and it seems the norm to use Lean classically, so that’s what I did. grind for example just assumes you’re using it. This does have the disadvantage that Lean isn’t as good at dealing with e.g. existentials, for example. Agda is constructive by default, and it seems the

基础：Isabelle/HOL 和 HOL4 在其基础上都是极其经典的，这意味着它们接受排中律（∀ P. ¬P ∨ P），并且两者都公理化了希尔伯特 epsilon，这也导致了选择公理。这对自动化求解器似乎有非常积极的影响，它们经常依赖于双重否定消除（¬¬P —> P）等定律，这与排中律等价。Lean 在理论上是构造性的（因此默认没有排中律），但一些“好的”证明自动化需要排中律，而且经典地使用 Lean 似乎是常态，所以我也是这样做的。例如，grind 就假设你在使用它。这确实有一个缺点，即 Lean 在处理例如存在量词时不如前者。Agda 默认是构造性的，似乎……