Lean 语言参考手册

1. 简介🔗

这是Lean语言参考手册。 它旨在对Lean进行全面而精确的描述,是Lean用户查找详细信息的参考资料,而不是给新用户的入门教程。 如需其他文档,请参阅Lean文档总览(英文)lean中文文档。 本手册涵盖Lean 4.21.0-rc3版本。

1.1. 历史🔗

Leonardo de Moura于2013年在微软研究院发起了Lean项目,Lean 0.1于2014年6月16日正式发布。 Lean项目的目标是结合由小型、可独立实现的逻辑内核所提供的高度信任度与类似SMT求解器等工具的便利性和自动化能力,同时能够扩展到大型问题。 这一愿景仍然引领着Lean的发展,我们不断致力于改进自动化、提升性能和增强用户友好性;受信任的核心证明检查器依然极为精简,并且存在独立实现。

Lean的初始版本主要是以C++库的形式配置,客户端代码能够在其中执行可被独立检查的可靠证明。 在早期,这些Lean版本的设计迅速向传统的交互式证明器演进,最初使用Lua编写策略,后来又引入了专用前端语法。 2017年1月20日,Lean 3.0系列首次发布。Lean 3被数学家广泛采纳,并首创自我可扩展性:策略、符号和顶层命令都可以用Lean本身来定义。 数学界创建了Mathlib,在Lean 3末期,Mathlib已拥有超过一百万行形式化数学,所有证明均由计算机机械化验证。 然而,该系统本身依然由C++实现,这对Lean的灵活性构成了限制,由于开发需要具备多种技能,导致了开发变得困难。

Lean 4的开发始于2018年,并于2023年9月8日发布了4.0版本。 Lean 4代表着一个重要的里程碑:自4.0版本起,Lean实现了自托管(self-hosted)——大约90%的Lean实现代码本身就以Lean编写。 Lean 4丰富的扩展API使用户能够根据自己的需求对其进行适配,而不必依赖核心开发团队来添加所需功能。 此外,自托管大大加快了开发进程,因此功能与性能都能更快地交付 Lean 4比Lean 3速度更快,并且能够处理更大规模的问题。 在Lean开发者的支持下,社区于2023年成功将Mathlib迁移到Lean 4,目前其规模已超过150万行。 即便Mathlib增长了50%,Lean 4对它的检查速度比Lean 3对较小库的检查还要快。 Lean 4的开发周期几乎与所有先前版本加总的开发周期持平,如今我们对其设计非常满意——不再计划进行重写。

Leonardo de Moura及其联合创始人Sebastian Ullrich于2023年7月在Convergent Research旗下发起了Lean Focused Research Organization (FRO)非盈利机构,得到了Simons Foundation International、Alfred P. Sloan基金会和Richard Merkin的慈善支持。 该FRO目前拥有十余名员工,致力于支持Lean及更广泛Lean社区的发展与可扩展性。

1.2. 排版方式🔗

本文档采用了多种排版和布局方式,来表示不同方面的信息。

1.2.1. Lean代码🔗

本文档包含许多Lean代码示例。其格式如下:

def hello : IO Unit := IO.println "Hello, world!"

编译器输出(可能是错误、警告,或仅是信息)既在代码中显示,也会单独列出:

"The answer is 4"#eval s!"The answer is {2 + 2}" theorem declaration uses 'sorry'bogus : False := False All goals completed! 🐙 example := Nat.succ Application type mismatch: In the application Nat.succ "two" the argument "two" has type String : Type but is expected to have type Nat : Type"two"

信息性输出,例如Lean.Parser.Command.eval : command`#eval e` evaluates the expression `e` by compiling and evaluating it. * The command attempts to use `ToExpr`, `Repr`, or `ToString` instances to print the result. * If `e` is a monadic value of type `m ty`, then the command tries to adapt the monad `m` to one of the monads that `#eval` supports, which include `IO`, `CoreM`, `MetaM`, `TermElabM`, and `CommandElabM`. Users can define `MonadEval` instances to extend the list of supported monads. The `#eval` command gracefully degrades in capability depending on what is imported. Importing the `Lean.Elab.Command` module provides full capabilities. Due to unsoundness, `#eval` refuses to evaluate expressions that depend on `sorry`, even indirectly, since the presence of `sorry` can lead to runtime instability and crashes. This check can be overridden with the `#eval! e` command. Options: * If `eval.pp` is true (default: true) then tries to use `ToExpr` instances to make use of the usual pretty printer. Otherwise, only tries using `Repr` and `ToString` instances. * If `eval.type` is true (default: false) then pretty prints the type of the evaluated value. * If `eval.derive.repr` is true (default: true) then attempts to auto-derive a `Repr` instance when there is no other way to print the result. See also: `#reduce e` for evaluation by term reduction. #eval的结果,呈现如下:

"The answer is 4"

警告如下显示:

declaration uses 'sorry'

错误消息如下显示:

Application type mismatch: In the application
  Nat.succ "two"
the argument
  "two"
has type
  String : Type
but is expected to have type
  Nat : Type

策略证明的状态通常通过可点击的小按钮指示,例如在rfl之后:

(译者注: 注意by和rfl之后有一个很小的长条状按钮,或者当鼠标移动到by或rfl上时会弹出一个气泡框显式当前的证明状态)

example : 2 + 2 = 4 := 2 + 2 = 4 All goals completed! 🐙

证明状态有时会单独展示。 在尝试证明2 + 2 = 4时,初始证明状态为:

2 + 2 = 4

使用All goals completed! 🐙后,得到的状态是:

All goals completed! 🐙

代码示例中的标识符会链接到其文档页面。

带有语法错误的代码示例会在出错位置给出指示,并附带错误信息:

def f : Option Nat → Type  | some 0 => Unit  |unexpected token '=>'; expected term => Option (f t)  | none => Empty
<example>:3:3-3:6: unexpected token '=>'; expected term

1.2.2. 示例🔗

说明性示例会折叠在如下所示的提示框中:

偶数

这是一个示例的样例

一种定义偶数的方法是使用归纳谓词:

inductive Even : Nat Prop where | zero : Even 0 | plusTwo : Even n Even (n + 2)

1.2.3. 技术术语🔗

技术术语是指在撰写技术资料时以非常特定的含义使用的术语,例如本参考资料中的术语。 技术术语通常会通过类似这样的链接超链接到其定义页面。

(译者注: 由于翻译进度的原因, 部分技术术语会以 中文(英文) 或 英文(中文) 的方式展示, 括号内的部分是超链接)

1.2.4. 常量、语法和策略参考🔗

定义、归纳类型、语法生成器和战术有特定的描述。这些描述标记如下:

/-- 偶数:如果一个数字能被二整除,则该数字是偶数。 -/ inductive Even : Nat Prop where | /-- 0是偶数 -/ zero : Even 0 | /-- 如果 n 是偶数,那么 n + 2 也是偶数。 -/ plusTwo : Even n Even (n + 2)
🔗inductive predicate
Even : Nat Prop
Even : Nat Prop

偶数:如果一个数字能被二整除,则该数字是偶数。

Constructors

zero : Even 0

0是偶数

plusTwo {n : Nat} : Even n  Even (n + 2)

如果 n 是偶数,那么 n + 2 也是偶数。

开源协议 (译者注: 此处不翻译)🔗

Editable Combobox With Both List and Inline Autocomplete Example, from the W3C's ARIA Authoring Practices Guide (APG)

https://www.w3.org/WAI/ARIA/apg/patterns/combobox/examples/combobox-autocomplete-both/

The search box component includes code derived from the example code in the linked article from the W3C's ARIA Authoring Practices Guide (APG).

W3C-20150513

Software and Document License - 2023 Version

Permission to copy, modify, and distribute this work, with or without modification, for any purpose and without fee or royalty is hereby granted, provided that you include the following on ALL copies of the work or portions thereof, including modifications:

* The full text of this NOTICE in a location viewable to users of the redistributed or derivative work.

* Any pre-existing intellectual property disclaimers, notices, or terms and conditions. If none exist, the W3C software and document short notice should be included.

* Notice of any changes or modifications, through a copyright statement on the new code or document such as "This software or document includes material copied from or derived from "Editable Combobox With Both List and Inline Autocomplete Example" at https://www.w3.org/WAI/ARIA/apg/patterns/combobox/examples/combobox-autocomplete-both/. Copyright © 2024 World Wide Web Consortium. https://www.w3.org/copyright/software-license-2023/"

fuzzysort v3.1.0

https://github.com/farzher/fuzzysort

The fuzzysort library is used in the search box to quickly filter results.

MIT

The MIT License

Copyright (c) 2018 Stephen Kamenar

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

KaTeX

https://katex.org/

KaTeX is used to render mathematical notation.

MIT

The MIT License

Copyright (c) 2013-2020 Khan Academy and other contributors

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Popper.js

https://popper.js.org/docs/v2/

Popper.js is used (as a dependency of Tippy.js) to show information (primarily in Lean code) when hovering the mouse over an item of interest.

MIT

The MIT License

Copyright (c) 2019 Federico Zivolo

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Tippy.js

https://atomiks.github.io/tippyjs/

Tippy.js is used together with Popper.js to show information (primarily in Lean code) when hovering the mouse over an item of interest.

MIT

The MIT License

Copyright (c) 2017-present atomiks

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.