Theorem Proving in Lean 4

6. 与 Lean 交互

你现在已经熟悉了依值类型论(dependent type theory)的基础,它既可以作为定义数学对象的语言,也可以作为构造证明(proof)的语言。唯一缺少的是定义新数据类型(data type)的机制。我们将在下一章中填补这一空白,下一章将介绍归纳类型(inductive data type)的概念。但首先,在本章中,我们将暂离类型论机制,探索与 Lean 交互的一些实际方面。

这里的所有信息并不都会立即对你有用。我们建议先快速浏览本章以了解 Lean 的功能,然后在需要时再回来查阅。

6.1. 消息(Messages)🔗

Lean 产生三种消息:

Errors

当代码中存在不一致导致无法处理时,会产生错误(Error)。例如语法错误(如缺少 ))和类型错误(type error),如试图将自然数(natural number)与函数相加。

Warnings

警告(Warning)描述代码的潜在问题,例如存在 sorry。与错误不同,代码并非无意义;然而,警告需要仔细关注。

Information

信息(Information)不指示代码的任何问题,包括来自诸如 #check#eval 等命令的输出。

Lean 可以检查命令是否产生了预期的消息。如果消息匹配,则忽略任何错误;这可用于确保出现了正确的错误。如果不匹配,则会产生错误。你可以使用 #guard_msgs 命令来指定预期的消息。

以下是一个示例:

/-- error: Type mismatch "Not a number" has type String but is expected to have type Nat -/ #guard_msgs in def x : Nat := "Not a number"

#guard_msgs 后面的括号中包含消息类别,使其仅检查指定类别,而让其他类别通过。在此示例中,#eval 由于存在 sorry 而发出错误,但为 sorry 始终发出的警告照常显示:

/-- error: aborting evaluation since the expression depends on the 'sorry' axiom, which can lead to runtime instability and crashes. To attempt to evaluate anyway despite the risks, use the '#eval!' command. -/ #guard_msgs(error) in declaration uses 'sorry'#eval (sorry : Nat)
declaration uses 'sorry'

没有配置时,两条消息都会被捕获:

/-- error: aborting evaluation since the expression depends on the 'sorry' axiom, which can lead to runtime instability and crashes. To attempt to evaluate anyway despite the risks, use the '#eval!' command. --- warning: declaration uses 'sorry' -/ ❌️ Docstring on `#guard_msgs` does not match generated message: - error: aborting evaluation since the expression depends on the - 'sorry' axiom, which can lead to runtime instability and crashes. + warning: declaration uses 'sorry' + --- + error: aborting evaluation since the expression depends on the 'sorry' axiom, which can lead to runtime instability and crashes. - To attempt to evaluate anyway despite the risks, use the '#eval!' - command. - --- - warning: declaration uses 'sorry' + To attempt to evaluate anyway despite the risks, use the '#eval!' command. #guard_msgs in declaration uses 'sorry'aborting evaluation since the expression depends on the 'sorry' axiom, which can lead to runtime instability and crashes. To attempt to evaluate anyway despite the risks, use the '#eval!' command.#eval (sorry : Nat)
❌️ Docstring on `#guard_msgs` does not match generated message:

- error: aborting evaluation since the expression depends on the
- 'sorry' axiom, which can lead to runtime instability and crashes.
+ warning: declaration uses 'sorry'
+ ---
+ error: aborting evaluation since the expression depends on the 'sorry' axiom, which can lead to runtime instability and crashes.
 
- To attempt to evaluate anyway despite the risks, use the '#eval!'
- command.
- ---
- warning: declaration uses 'sorry'
+ To attempt to evaluate anyway despite the risks, use the '#eval!' command.

本书中的一些示例使用 #guard_msgs 来指示预期的错误。

6.2. 导入文件(Importing Files)🔗

Lean 前端的目的是解释用户输入,构造形式表达式(formal expression),并检查它们是否良构(well-formed)且类型正确(type-correct)。Lean 还支持使用多种编辑器,提供持续检查和反馈。更多信息可以在 Lean 文档页面上找到。

Lean 标准库中的定义(definition)和定理(theorem)分布在多个文件中。用户可能还需要使用额外的库,或在多个文件中开发自己的项目。Lean 启动时会自动导入 Init 文件夹的内容,其中包含许多基本定义和构造。因此,我们在此展示的大多数示例都可以“开箱即用”。

但是,如果你想使用额外的文件,则需要通过在文件开头的 import 语句手动导入。该命令

import Bar.Baz.Blah

导入文件 Bar/Baz/Blah.olean,其中描述相对于 Lean 搜索路径(search path)进行解释。关于搜索路径如何确定的信息可以在文档页面上找到。默认情况下,它包括标准库目录,以及(在某些情况下)用户本地项目的根目录。

导入是传递的(transitive)。换句话说,如果你导入 Foo,而 Foo 导入了 Bar,那么你也可以访问 Bar 的内容,无需显式导入它。

6.3. 更多关于章节(Sections)🔗

Lean 提供了多种章节机制来帮助组织理论。你在变量与章节(Variables and Sections)中看到,section 命令不仅可以将在逻辑上属于一起的理论元素分组,还可以声明变量(variable),这些变量会根据需要作为参数插入到定理和定义中。请记住,variable 命令的目的是声明用于定理的变量,如下例所示:

section variable (x y : Nat) def double := x + x double y : Nat#check double y
double y : Nat
double (2 * x) : Nat#check double (2 * x)
double (2 * x) : Nat
attribute [local simp] Nat.add_assoc Nat.add_comm Nat.add_left_comm theorem t1 : double (x + y) = double x + double y := x:Naty:Natdouble (x + y) = double x + double y All goals completed! 🐙 t1 y : (y_1 : Nat), double (y + y_1) = double y + double y_1#check t1 y
t1 y :  (y_1 : Nat), double (y + y_1) = double y + double y_1
t1 (2 * x) : (y : Nat), double (2 * x + y) = double (2 * x) + double y#check t1 (2 * x)
t1 (2 * x) :  (y : Nat), double (2 * x + y) = double (2 * x) + double y
theorem t2 : double (x * y) = double x * y := x:Naty:Natdouble (x * y) = double x * y All goals completed! 🐙 end

double 的定义不必将 x 声明为参数;Lean 会自动检测依赖关系并插入它。类似地,Lean 会检测 t1t2 中出现的 x,并自动将其插入。注意,double没有y 作为参数。变量只包含在实际使用它们的声明中。

6.4. 更多关于命名空间(Namespaces)🔗

在 Lean 中,标识符由分层名称(name)给出,例如 Foo.Bar.baz。我们在命名空间(Namespaces)中看到,Lean 提供了处理分层名称的机制。命令 namespace Foo 会导致 Foo 被添加到每个定义和定理的名称前,直到遇到 end Foo。命令 open Foo 会为以前缀 Foo 开头的定义和定理创建临时的别名(alias)

namespace Foo def bar : Nat := 1 end Foo open Foo Foo.bar : Nat#check bar
Foo.bar : Nat
Foo.bar : Nat#check Foo.bar
Foo.bar : Nat

以下定义

def Foo.bar : Nat := 1

被视为宏(macro),展开为

namespace Foo def bar : Nat := 1 end Foo

虽然定理和定义的名称必须是唯一的,但标识它们的别名不必如此。当我们打开一个命名空间时,标识符可能产生歧义。Lean 会尝试使用类型信息来根据上下文消歧义,但你始终可以通过给出完整名称来消歧义。为此,字符串 _root_ 是对空前缀的显式描述。

def String.add (a b : String) : String := a ++ b def Bool.add (a b : Bool) : Bool := a != b def add (α β : Type) : Type := Sum α β open Bool open String -- This reference is ambiguous: -- #check add String.add (a b : String) : String#check String.add
String.add (a b : String) : String
Bool.add (a b : Bool) : Bool#check Bool.add
Bool.add (a b : Bool) : Bool
_root_.add (α β : Type) : Type#check _root_.add
_root_.add (α β : Type) : Type
"hello".add "world" : String#check add "hello" "world"
"hello".add "world" : String
true.add false : Bool#check add true false
true.add false : Bool
_root_.add Nat Nat : Type#check add Nat Nat
_root_.add Nat Nat : Type

我们可以通过使用 protected 关键字来阻止创建较短的别名:

protected def Foo.bar : Nat := 1 open Foo /-- error: Unknown identifier `bar` -/ #guard_msgs in #check bar -- error Foo.bar : Nat#check Foo.bar
Foo.bar : Nat

这通常用于像 Nat.recNat.recOn 这样的名称,以防止常见名称的重载。

open 命令有多种变体。命令

仅为列出的标识符创建别名。命令

open Nat hiding succ gcd Nat.zero : Nat#check zero
Nat.zero : Nat
/-- error: Unknown identifier `gcd` -/ #guard_msgs in #eval gcd 15 6 -- error 3#eval Nat.gcd 15 6
3

Nat 命名空间中的列出的标识符之外的所有内容创建别名。

open Nat renaming mul times, add plus 7#eval plus (times 2 2) 3
7

创建将 Nat.mul 重命名为 timesNat.add 重命名为 plus 的别名。

有时将别名从一个命名空间export 到另一个命名空间或导出到顶层是很有用的。命令

export Nat (succ add sub)

在当前命名空间中为 succaddsub 创建别名,因此每当该命名空间被打开时,这些别名都可用。如果此命令在命名空间外部使用,则别名将被导出到顶层。

6.5. 属性(Attributes)🔗

Lean 的主要功能是将用户输入翻译为形式表达式(formal expression),由内核(kernel)检查其正确性,然后存储在环境(environment)中供以后使用。但有些命令对环境有其他影响,要么为环境中的对象分配属性(attribute),要么定义记号(notation),要么声明类型类(type class)的实例,如类型类(type classes)一章所述。这些命令大多具有全局效果,也就是说,它们不仅在当前文件中有效,在导入该文件的任何文件中也都有效。然而,此类命令通常支持 local 修饰符,指示它们仅在当前 sectionnamespace 关闭之前或当前文件结束之前有效。

使用化简器(Using the Simplifier)中,我们看到可以用 [simp] 属性注解定理,使其可供化简器(simplifier)使用。以下示例定义了列表上的前缀关系,证明了该关系是自反的(reflexive),并给该定理分配了 [simp] 属性。

def isPrefix (l₁ : List α) (l₂ : List α) : Prop := t, l₁ ++ t = l₂ @[simp] theorem List.isPrefix_self (as : List α) : isPrefix as as := [], α:Type u_1as:List αas ++ [] = as All goals completed! 🐙 example : isPrefix [1, 2, 3] [1, 2, 3] := isPrefix [1, 2, 3] [1, 2, 3] All goals completed! 🐙

然后化简器通过将其重写(rewrite)为 True 来证明 isPrefix [1, 2, 3] [1, 2, 3]

也可以在定义之后的任何时间分配属性:

theorem List.isPrefix_self (as : List α) : isPrefix as as := [], α:Type u_1as:List αas ++ [] = as All goals completed! 🐙 attribute [simp] List.isPrefix_self

在所有这些情况下,属性在导入声明所在文件的任何文件中都保持有效。添加 local 修饰符可以限制作用域(scope):

section theorem List.isPrefix_self (as : List α) : isPrefix as as := [], α:Type u_1as:List αas ++ [] = as All goals completed! 🐙 attribute [local simp] List.isPrefix_self example : isPrefix [1, 2, 3] [1, 2, 3] := isPrefix [1, 2, 3] [1, 2, 3] All goals completed! 🐙 end /-- error: `simp` made no progress -/ #guard_msgs in example : isPrefix [1, 2, 3] [1, 2, 3] := isPrefix [1, 2, 3] [1, 2, 3] isPrefix [1, 2, 3] [1, 2, 3]

另一个例子,我们可以使用 instance 命令将记号 分配给 isPrefix 关系。该命令将在类型类(type classes)一章中解释,其工作原理是将 [instance] 属性分配给相关联的定义。

def isPrefix (l₁ : List α) (l₂ : List α) : Prop := t, l₁ ++ t = l₂ instance : LE (List α) where le := isPrefix theorem List.isPrefix_self (as : List α) : as as := [], α:Type u_1as:List αas ++ [] = as All goals completed! 🐙

该分配也可以设为局部(local):

def instLe : LE (List α) := { le := isPrefix } section attribute [local instance] instLe example (as : List α) : as as := [], α:Type u_1as:List αas ++ [] = as All goals completed! 🐙 end /-- error: failed to synthesize LE (List α) Hint: Additional diagnostic information may be available using the `set_option diagnostics true` command. -/ #guard_msgs in example (as : List α) : as as := [], by simp

在下面的记号(Notation)中,我们将讨论 Lean 定义记号的机制,并看到它们也支持 local 修饰符。然而,在设置选项(Setting Options)中,我们将讨论 Lean 设置选项的机制,它遵循此模式:选项只能局部设置,也就是说,它们的作用域总是限于当前章节或当前文件。

6.6. 更多关于隐式参数(Implicit Arguments)🔗

隐式参数(Implicit Arguments)中,我们看到如果 Lean 将项(term)t 的类型显示为 {x : α} β x,那么花括号表示 x 已被标记为 t隐式参数(implicit argument)。这意味着每当你写 t 时,就会插入一个占位符,或“洞”,因此 t 被替换为 @t _。如果你不希望发生这种情况,则必须写 @t 代替。

注意,隐式参数是 eager 地插入的。假设我们定义一个函数 f : (x : Nat) {y : Nat} (z : Nat) (z + y)。那么,当我们写下表达式 f 7 而没有进一步的参数时,它被解析为 @f 7 _

Lean 提供了一种较弱的注解,指定占位符只应在《在》随后的显式参数《之前》添加。它可以写成双花括号形式,因此 f 的类型将是 f : (x : Nat) {{y : Nat}} (z : Nat) (z + y)。使用此注解,表达式 f 7 将被原样解析,而 f 7 3 将被解析为 @f 7 _ 3,与强注解一样。此注解也可以写为 ⦃y : Nat⦄,其中 Unicode 括号分别通过输入 \{{\}} 输入。

为了说明区别,请考虑以下示例,该示例表明一个自反的欧几里得关系(euclidean relation)既是对称的(symmetric)也是传递的(transitive)。

def reflexive {α : Type u} (r : α α Prop) : Prop := (a : α), r a a def symmetric {α : Type u} (r : α α Prop) : Prop := {a b : α}, r a b r b a def transitive {α : Type u} (r : α α Prop) : Prop := {a b c : α}, r a b r b c r a c def Euclidean {α : Type u} (r : α α Prop) : Prop := {a b c : α}, r a b r a c r b c theorem th1 {α : Type u} {r : α α Prop} (reflr : reflexive r) (euclr : Euclidean r) : symmetric r := fun {a b : α} => fun (h : r a b) => show r b a from euclr h (reflr _) theorem th2 {α : Type u} {r : α α Prop} (symmr : symmetric r) (euclr : Euclidean r) : transitive r := fun {a b c : α} => fun (rab : r a b) (rbc : r b c) => euclr (symmr rab) rbc theorem th3 {α : Type u} {r : α α Prop} (reflr : reflexive r) (euclr : Euclidean r) : transitive r := th2 (th1 reflr @euclr) @euclr variable (r : α α Prop) variable (euclr : Euclidean r) euclr : r ?m.3 ?m.4 r ?m.3 ?m.5 r ?m.4 ?m.5#check euclr
euclr : r ?m.3 ?m.4  r ?m.3 ?m.5  r ?m.4 ?m.5

结果被分解为小步骤:th1 表明自反且欧几里得的关系是对称的,th2 表明对称且欧几里得的关系是传递的。然后 th3 结合了这两个结果。但请注意,我们必须手动禁用 euclr 中的隐式参数,否则会插入过多的隐式参数。如果我们使用弱隐式参数,问题就会消失:

def reflexive {α : Type u} (r : α α Prop) : Prop := (a : α), r a a def symmetric {α : Type u} (r : α α Prop) : Prop := {{a b : α}}, r a b r b a def transitive {α : Type u} (r : α α Prop) : Prop := {{a b c : α}}, r a b r b c r a c def Euclidean {α : Type u} (r : α α Prop) : Prop := {{a b c : α}}, r a b r a c r b c theorem th1 {α : Type u} {r : α α Prop} (reflr : reflexive r) (euclr : Euclidean r) : symmetric r := fun {a b : α} => fun (h : r a b) => show r b a from euclr h (reflr _) theorem th2 {α : Type u} {r : α α Prop} (symmr : symmetric r) (euclr : Euclidean r) : transitive r := fun {a b c : α} => fun (rab : r a b) (rbc : r b c) => euclr (symmr rab) rbc theorem th3 {α : Type u} {r : α α Prop} (reflr : reflexive r) (euclr : Euclidean r) : transitive r := th2 (th1 reflr euclr) euclr variable (r : α α Prop) variable (euclr : Euclidean r) euclr : Euclidean r#check euclr
euclr : Euclidean r

还有第三种隐式参数,用方括号 [] 表示。它们用于类型类(type class),如类型类(type classes)一章所述。

6.7. 记号(Notation)🔗

Lean 中的标识符可以包含任何字母数字字符,包括希腊字符(除了 ∀、Σ 和 λ,正如我们所见,它们在依值类型论中有特殊含义)。它们还可以包含下标,可以通过输入 \_ 后跟所需下标字符来输入。

Lean 的解析器(parser)是可扩展的,也就是说,我们可以定义新的记号。

Lean 的语法可以在各个层次上由用户扩展和定制,从基本的“混合固定(mixfix)”记号到自定义的精化器(elaborator)。事实上,所有内置语法都使用与用户相同的机制和 API 进行解析和处理。在本节中,我们将描述和解释各种扩展点。

虽然在编程语言中引入新记号是一个相对罕见的特性,有时甚至因可能混淆代码而受到批评,但在形式化(formalization)工作中,它是在代码中简洁地表达各自领域既有约定和记号的宝贵工具。超越基本记号,Lean 将常见样板代码分解为(行为良好的)宏以及嵌入整个自定义领域特定语言(DSL)以高效且可读地编码子问题的能力,对程序员和证明工程师都大有裨益。

6.7.1. 记号与优先级(Notations and Precedence)🔗

最基本的语法扩展命令允许引入新的(或重载已有的)前缀(prefix)、中缀(infix)和后缀(postfix)运算符。

infixl:65 " + " => HAdd.hAdd -- left-associative infix:50 " = " => Eq -- non-associative infixr:80 " ^ " => HPow.hPow -- right-associative prefix:100 "-" => Neg.neg postfix:max "⁻¹" => Inv.inv

在描述运算符种类的初始命令名称(其“fixity(固结性)”)之后,我们给出运算符的解析优先级(parsing precedence),前面加冒号 :,然后用双引号括起一个或多个记号(空格用于美观打印(pretty printing)),再然后是在箭头 => 之后该运算符应转换成的函数。

优先级是一个自然数,描述运算符与其参数结合的“紧密程度”,编码了运算的顺序。我们可以通过查看上述命令展开的内容来更精确地理解这一点:

notation:65 lhs:65 " + " rhs:66 => HAdd.hAdd lhs rhs notation:50 lhs:51 " = " rhs:51 => Eq lhs rhs notation:80 lhs:81 " ^ " rhs:80 => HPow.hPow lhs rhs notation:100 "-" arg:100 => Neg.neg arg -- `max` is a shorthand for precedence 1024: notation:1024 arg:1024 "⁻¹" => Inv.inv arg

事实证明,第一个代码块中的所有命令实际上都是命令宏(macro),它们转换为更通用的 notation 命令。我们将在下面学习如何编写此类宏。notation 命令接受记号和带有优先级的命名项占位符的混合序列,可以在 => 的右侧引用,并将被替换为在该位置解析的相应项。优先级为 p 的占位符只接受优先级至少为 p 的记号。因此,字符串 a + b + c 无法被解析为 a + (b + c) 的等价形式,因为 infixl 记法的右侧操作数优先级比记法本身高一级。相比之下,infixr 对右侧操作数重用记法的优先级,因此 a ^ b ^ c可以被解析为 a ^ (b ^ c)。注意,如果我们直接使用 notation 来引入一个类似的中缀记法

notation:65 lhs:65 " ~ " rhs:65 => wobble lhs rhs

当优先级不足以确定结合性(associativity)时,Lean 的解析器将默认右结合。更准确地说,Lean 的解析器在存在歧义语法时遵循局部的最长解析(longest parse)规则:当解析 a ~ b ~ ca ~ 的右侧时,它会尽可能继续解析(在当前优先级允许的情况下),不会在 b 后停止,而是也解析 ~ c。因此该术语等价于 a ~ (b ~ c)

如上所述,notation 命令允许我们定义自由混合记号和占位符的任意混合固定(mixfix)语法。

notation:max "(" e ")" => e notation:10 Γ " ⊢ " e " : " τ => Typing Γ e τ

没有优先级的占位符默认为 0,即它们接受在其位置任何优先级的记号。如果两个记号重叠,我们再次应用最长解析规则:

notation:65 a " + " b:66 " + " c:66 => a + b - c 0#eval 1 + 2 + 3
0

新记号优先于二元记号,因为后者在链接之前会停止在 1 + 2 之后解析。如果存在多个接受相同最长解析的记号,选择将被延迟到精化(elaboration)阶段,除非恰好有一个重载类型正确,否则将失败。

6.8. 强制类型转换(Coercions)🔗

在 Lean 中,自然数类型 Nat 与整数类型 Int 不同。但有一个函数 Int.ofNat 将自然数嵌入到整数中,这意味着在需要时我们可以将任何自然数视为整数。Lean 有检测和插入这种强制类型转换(coercion)的机制。可以使用重载的 运算符显式请求强制类型转换。

variable (m n : Nat) variable (i j : Int) i + m : Int#check i + m
i + m : Int
i + m + j : Int#check i + m + j
i + m + j : Int
i + m + n : Int#check i + m + n
i + m + n : Int

6.9. 显示信息(Displaying Information)🔗

有多种方式可以向 Lean 查询关于其当前状态和当前上下文中可用的对象与定理的信息。你已经见过最常用的两种:#check#eval。请记住,#check 通常与 @ 运算符一起使用,该运算符使定理或定义的所有参数变为显式。此外,你可以使用 #print 命令获取关于任何标识符的信息。如果标识符表示一个定义或定理,Lean 会打印该符号的类型及其定义。如果它是一个常量或公理(axiom),Lean 会指示这一事实并显示其类型。

-- examples with equality Eq.{u_1} {α : Sort u_1} : α α Prop#check Eq
Eq.{u_1} {α : Sort u_1} : α  α  Prop
@Eq : {α : Sort u_1} α α Prop#check @Eq
@Eq : {α : Sort u_1}  α  α  Prop
Eq.symm.{u} {α : Sort u} {a b : α} (h : a = b) : b = a#check Eq.symm
Eq.symm.{u} {α : Sort u} {a b : α} (h : a = b) : b = a
@Eq.symm : {α : Sort u_1} {a b : α}, a = b b = a#check @Eq.symm
@Eq.symm :  {α : Sort u_1} {a b : α}, a = b  b = a
theorem Eq.symm.{u} : {α : Sort u} {a b : α}, a = b b = a := fun {α} {a b} h => h rfl#print Eq.symm
theorem Eq.symm.{u} :  {α : Sort u} {a b : α}, a = b  b = a :=
fun {α} {a b} h => h  rfl
-- examples with And And (a b : Prop) : Prop#check And
And (a b : Prop) : Prop
And.intro {a b : Prop} (left : a) (right : b) : a b#check And.intro
And.intro {a b : Prop} (left : a) (right : b) : a  b
@And.intro : {a b : Prop}, a b a b#check @And.intro
@And.intro :  {a b : Prop}, a  b  a  b
-- a user-defined function def foo {α : Type u} (x : α) : α := x foo.{u} {α : Type u} (x : α) : α#check foo
foo.{u} {α : Type u} (x : α) : α
@foo : {α : Type u_1} α α#check @foo
@foo : {α : Type u_1}  α  α
def foo.{u} : {α : Type u} α α := fun {α} x => x#print foo
def foo.{u} : {α : Type u}  α  α :=
fun {α} x => x

6.10. 设置选项(Setting Options)🔗

Lean 维护许多可以由用户设置以控制其行为的内部变量(internal variable)。设置语法的格式如下:

set_option <name> <value>

一个非常有用的选项系列控制着 Lean 的美观打印机(pretty printer)显示项的方式。以下选项接受 true 或 false 作为输入:

pp.explicit  : display implicit arguments
pp.universes : display hidden universe parameters
pp.notation  : display output using defined notations

例如,以下设置会产生长得多的输出:

set_option pp.explicit true set_option pp.universes true set_option pp.notation false @Eq.{1} Nat (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))) (@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))) : Prop#check 2 + 2 = 4
@Eq.{1} Nat
  (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
    (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
    (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
  (@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))) : Prop
@Eq.{1} (Nat Nat) (fun x => @HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) x (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))) fun x => @HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) x (@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))#reduce (fun x => x + 2) = (fun x => x + 3)
@Eq.{1} (Nat  Nat)
  (fun x =>
    @HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) x
      (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
  fun x =>
  @HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) x
    (@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(fun x => @HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) x (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))) (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) : Nat#check (fun x => x + 1) 1
(fun x =>
    @HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) x
      (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
  (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) : Nat

命令 set_option pp.all true 一次性完成所有这些设置,而 set_option pp.all false 恢复到以前的值。当你调试证明或试图理解晦涩的错误消息时,打印额外信息通常非常有用。不过,信息过多可能令人不知所措,Lean 的默认设置通常足以应对常规交互。

6.11. 使用库(Using the Library)🔗

要有效使用 Lean,你不可避免地需要使用库中的定义和定理。回想一下,文件开头的 import 命令会导入其他文件中先前编译的结果,且导入是传递的:如果导入 Foo,而 Foo 导入了 Bar,那么 Bar 中的定义和定理也对你可用了。但是,打开命名空间以提供较短名称的操作不会传递。在每个文件中,你需要打开希望使用的命名空间。

总的来说,熟悉库及其内容对你来说很重要,这样你才能知道有哪些定理、定义、记号和资源可供使用。下面我们将看到 Lean 的编辑器模式也可以帮助你找到需要的内容,但直接研究库的内容通常是不可避免的。Lean 的标准库可以在 GitHub 上在线找到:

你可以使用 GitHub 的浏览器界面查看这些目录和文件的内容。如果你在本地计算机上安装了 Lean,可以在 lean 文件夹中找到该库,并使用文件管理器浏览。每个文件顶部的注释标题提供了附加信息。

Lean 库的开发人员遵循一般的命名指南,使得更容易猜测所需定理的名称,或使用支持此功能的 Lean 模式编辑器中的 Tab 补全来查找它,这将在下一节讨论。标识符通常是 camelCase,类型是 CamelCase。对于定理名称,我们依赖描述性名称,其中不同的组成部分由 _ 分隔。通常,定理的名称仅描述其结论:

Nat.succ_ne_zero (n : Nat) : n.succ 0#check Nat.succ_ne_zero
Nat.succ_ne_zero (n : Nat) : n.succ  0
Nat.zero_add (n : Nat) : 0 + n = n#check Nat.zero_add
Nat.zero_add (n : Nat) : 0 + n = n
Nat.mul_one (n : Nat) : n * 1 = n#check Nat.mul_one
Nat.mul_one (n : Nat) : n * 1 = n
Nat.le_of_succ_le_succ {n m : Nat} : n.succ m.succ n m#check Nat.le_of_succ_le_succ
Nat.le_of_succ_le_succ {n m : Nat} : n.succ  m.succ  n  m

请记住,Lean 中的标识符可以组织成分层命名空间。例如,命名空间 Nat 中的定理 le_of_succ_le_succ 的全名是 Nat.le_of_succ_le_succ,但较短的名称可通过命令 open Nat 获得(对于未标记为 protected 的名称)。我们将在归纳类型(inductive types)结构与记录(structures and records)章节中看到,在 Lean 中定义结构和归纳数据类型会生成相关的操作,这些操作存储在与所定义类型同名的命名空间中。例如,积类型(product type)带有以下操作:

@Prod.mk : {α : Type u_1} {β : Type u_2} α β α × β#check @Prod.mk
@Prod.mk : {α : Type u_1}  {β : Type u_2}  α  β  α × β
@Prod.fst : {α : Type u_1} {β : Type u_2} α × β α#check @Prod.fst
@Prod.fst : {α : Type u_1}  {β : Type u_2}  α × β  α
@Prod.snd : {α : Type u_1} {β : Type u_2} α × β β#check @Prod.snd
@Prod.snd : {α : Type u_1}  {β : Type u_2}  α × β  β
@Prod.rec : {α : Type u_2} {β : Type u_3} {motive : α × β Sort u_1} ((fst : α) (snd : β) motive (fst, snd)) (t : α × β) motive t#check @Prod.rec
@Prod.rec : {α : Type u_2} 
  {β : Type u_3}  {motive : α × β  Sort u_1}  ((fst : α)  (snd : β)  motive (fst, snd))  (t : α × β)  motive t

第一个用于构造一对,而接下来的两个 Prod.fstProd.snd 投影出两个元素。最后一个 Prod.rec 提供了另一种基于两个分量上的函数来定义积上函数的机制。像 Prod.rec 这样的名称是受保护的(protected),这意味着即使在 Prod 命名空间打开的情况下,也必须使用全名。

根据命题即类型对应关系(propositions as types),逻辑连接词也是归纳类型的实例,因此我们也倾向于对它们使用点号记法(dot notation):

@And.intro : {a b : Prop}, a b a b#check @And.intro
@And.intro :  {a b : Prop}, a  b  a  b
@And.casesOn : {a b : Prop} {motive : a b Sort u_1} (t : a b) ((left : a) (right : b) motive ) motive t#check @And.casesOn
@And.casesOn : {a b : Prop} 
  {motive : a  b  Sort u_1}  (t : a  b)  ((left : a)  (right : b)  motive )  motive t
@And.left : {a b : Prop}, a b a#check @And.left
@And.left :  {a b : Prop}, a  b  a
@And.right : {a b : Prop}, a b b#check @And.right
@And.right :  {a b : Prop}, a  b  b
@Or.inl : {a b : Prop}, a a b#check @Or.inl
@Or.inl :  {a b : Prop}, a  a  b
@Or.inr : {a b : Prop}, b a b#check @Or.inr
@Or.inr :  {a b : Prop}, b  a  b
@Or.elim : {a b c : Prop}, a b (a c) (b c) c#check @Or.elim
@Or.elim :  {a b c : Prop}, a  b  (a  c)  (b  c)  c
@Exists.intro : {α : Sort u_1} {p : α Prop} (w : α), p w Exists p#check @Exists.intro
@Exists.intro :  {α : Sort u_1} {p : α  Prop} (w : α), p w  Exists p
@Exists.elim : {α : Sort u_1} {p : α Prop} {b : Prop}, ( x, p x) (∀ (a : α), p a b) b#check @Exists.elim
@Exists.elim :  {α : Sort u_1} {p : α  Prop} {b : Prop}, ( x, p x)  (∀ (a : α), p a  b)  b
@Eq.refl : {α : Sort u_1} (a : α), a = a#check @Eq.refl
@Eq.refl :  {α : Sort u_1} (a : α), a = a
@Eq.subst : {α : Sort u_1} {motive : α Prop} {a b : α}, a = b motive a motive b#check @Eq.subst
@Eq.subst :  {α : Sort u_1} {motive : α  Prop} {a b : α}, a = b  motive a  motive b

6.12. 自动绑定隐式参数(Auto Bound Implicit Arguments)🔗

在上一节中,我们展示了隐式参数如何使函数更方便使用。然而,像 compose 这样的函数定义起来仍然相当冗长。注意,宇宙多态(universe polymorphic)的 compose 比以前定义的更加冗长。

universe u v w def compose {α : Type u} {β : Type v} {γ : Type w} (g : β γ) (f : α β) (x : α) : γ := g (f x)

你可以通过在定义 compose 时提供宇宙参数来避免使用 universe 命令。

def compose.{u, v, w} {α : Type u} {β : Type v} {γ : Type w} (g : β γ) (f : α β) (x : α) : γ := g (f x)

Lean 4 支持一个称为自动绑定隐式参数(auto bound implicit arguments)的新特性。它使得像 compose 这样的函数编写起来方便得多。当 Lean 处理声明(declaration)的头部时,任何未绑定的标识符会自动作为隐式参数添加。使用此特性,我们可以将 compose 写为

def compose (g : β γ) (f : α β) (x : α) : γ := g (f x) @compose : {β : Sort u_1} {γ : Sort u_2} {α : Sort u_3} (β γ) (α β) α γ#check @compose
@compose : {β : Sort u_1}  {γ : Sort u_2}  {α : Sort u_3}  (β  γ)  (α  β)  α  γ

注意,Lean 使用 Sort 而不是 Type 推断出了更一般的类型。

尽管我们喜爱这个特性并在实现 Lean 时广泛使用它,但我们认识到一些用户可能对此感到不适应。因此,你可以使用命令 set_option autoImplicit false 禁用它。

set_option autoImplicit false /-- error: Unknown identifier `β` --- error: Unknown identifier `γ` --- error: Unknown identifier `α` --- error: Unknown identifier `β` --- error: Unknown identifier `α` --- error: Unknown identifier `γ` -/ #guard_msgs in def compose (g : β γ) (f : α β) (x : α) : γ := g (f x)

6.13. 隐式 λ(Implicit Lambdas)🔗

当表达式的期望类型是一个等待隐式参数的函数时,精化器(elaborator)会自动引入相应的 λ。例如,pure 的类型指出第一个参数是隐式类型 α,但 ReaderT.pure 的第一个参数是读取器单子(reader monad)的上下文类型 ρ。它会自动被 fun {α} => ... 包围,这允许精化器正确填充主体中的隐式参数。

instance : Monad (ReaderT ρ m) where pure := ReaderT.pure bind := ReaderT.bind

用户可以通过使用 @ 或编写带有 {}[] 绑定注解的 λ 表达式来禁用隐式 λ 特性。以下是一些示例

def id1 : {α : Type} α α := fun x => x def listId : List ({α : Type} α α) := (fun x => x) :: [] -- In this example, implicit lambda introduction has been disabled because -- we use `@` before {kw}`fun` def id2 : {α : Type} α α := @fun α (x : α) => id1 x def id3 : {α : Type} α α := @fun α x => id1 x def id4 : {α : Type} α α := fun x => id1 x -- In this example, implicit lambda introduction has been disabled -- because we used the binder annotation `{...}` def id5 : {α : Type} α α := fun {α} x => id1 x

6.14. 简单函数的语法糖(Sugar for Simple Functions)🔗

Lean 包含一种使用匿名占位符而非 fun 来描述简单函数的记号。当 · 作为项的一部分出现时,最接近的封闭括号将变成一个函数,其中 · 作为其参数。如果括号包含多个占位符且没有其他中间括号,则它们从左到右成为参数。以下是一些示例:

fun x => x + 1 : Nat Nat#check (· + 1)
fun x => x + 1 : Nat  Nat
fun x => 2 - x : Nat Nat#check (2 - ·)
fun x => 2 - x : Nat  Nat
120#eval [1, 2, 3, 4, 5].foldl (· * ·) 1
120
def f (x y z : Nat) := x + y + z fun x1 x2 => f x1 1 x2 : Nat Nat Nat#check (f · 1 ·)
fun x1 x2 => f x1 1 x2 : Nat  Nat  Nat
[1, 3, 5]#eval [(1, 2), (3, 4), (5, 6)].map (·.1)
[1, 3, 5]

嵌套括号会引入新的函数。在以下示例中,创建了两个不同的 λ 表达式:

fun x => (x, fun x => x + 1) : ?m.1 ?m.1 × (Nat Nat)#check (Prod.mk · (· + 1))
fun x => (x, fun x => x + 1) : ?m.1  ?m.1 × (Nat  Nat)

6.15. 命名参数(Named Arguments)🔗

命名参数使你能够通过将参数与其名称匹配而不是其在参数列表中的位置来为参数提供实参。如果你不记得参数的顺序但知道它们的名称,你可以按任意顺序发送实参。当 Lean 无法推断(infer)隐式参数时,你也可以为其提供值。命名参数还通过标识每个参数代表什么来提高代码的可读性。

def sum (xs : List Nat) := xs.foldl (init := 0) (·+·) 10#eval sum [1, 2, 3, 4]
10
-- 10 example {a b : Nat} {p : Nat Nat Nat Prop} (h₁ : p a b b) (h₂ : b = a) : p a a b := Eq.subst (motive := fun x => p a x b) h₂ h₁

在以下示例中,我们说明了命名参数和默认参数之间的交互。

def f (x : Nat) (y : Nat := 1) (w : Nat := 2) (z : Nat) := x + y + w - z example (x z : Nat) : f (z := z) x = x + 1 + 2 - z := rfl example (x z : Nat) : f x (z := z) = x + 1 + 2 - z := rfl example (x y : Nat) : f x y = fun z => x + y + 2 - z := rfl example : f = (fun x z => x + 1 + 2 - z) := rfl example (x : Nat) : f x = fun z => x + 1 + 2 - z := rfl example (unused variable `y` Note: This linter can be disabled with `set_option linter.unusedVariables false`y : Nat) : f (y := 5) = fun x z => x + 5 + 2 - z := rfl def g {α} [Add α] (a : α) (b? : Option α := none) (c : α) : α := match b? with | none => a + c | some b => a + b + c variable {α} [Add α] example : g = fun (a c : α) => a + c := rfl example (x : α) : g (c := x) = fun (a : α) => a + x := rfl example (x : α) : g (b? := some x) = fun (a c : α) => a + x + c := rfl example (x : α) : g x = fun (c : α) => x + c := rfl example (x y : α) : g x y = fun (c : α) => x + y + c := rfl

你可以使用 .. 将缺失的显式参数作为 _ 提供。此特性与命名参数结合使用时对于编写模式非常有用。以下是一个示例:

inductive Term where | var (name : String) | num (val : Nat) | app (fn : Term) (arg : Term) | lambda (name : String) (type : Term) (body : Term) def getBinderName : Term Option String | Term.lambda (name := n) .. => some n | _ => none def getBinderType : Term Option Term | Term.lambda (type := t) .. => some t | _ => none

当显式参数可以由 Lean 自动推断,而我们又想避免一串 _ 时,省略号也很有用。

example (f : Nat Nat) (a b c : Nat) : f (a + b + c) = f (a + (b + c)) := congrArg f (Nat.add_assoc ..)