返回资讯中心
外部精选
软件工程
#开发者实时流

用 TypeScript 讲解 Lean:LLM 时代的形式化验证语言

来源标题:Lean Explained with TypeScript

Lean 是一种可证明数学命题的编程语言,其验证器自动检查证明的正确性,但手写证明极其繁琐。随着 LLM 兴起,Lean 人气大增:LLM 快速生成代码、Lean 自动验证,两者互补。Lean 的验证器本质是类型检查器,命题即类型、证明即值。

Hacker News 最新fagnerbrack2026/11/22 · 今天22 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

Lean 是一门能让你证明数学命题的编程语言。Lean 验证器会自动检查这些证明是否正确。这是数学中书写证明最形式化、最无懈可击的方式。但它也确实极其繁琐。像 a+b=b+a 这样的基本陈述,没有证明就不会被接受。

随着 LLM 的出现,Lean 的人气急剧上升。LLM 能快速写出大量代码,但验证过程十分费力。Lean 可以自动完成验证,但编写代码本身又很费劲。简直是天作之合!

这不仅对数学家有用。Lean 是一门通用编程语言。对于普通软件来说,如果能拥有更多、更强的保证,那也很不错,比如:

令人惊叹的是,Lean 验证器“只不过”是一个类型检查器。命题被表示为类型,证明被写成值(也就是项)。要证明一个类型/命题,就是写出该类型的一个值。类型检查器只是像往常一样检查:这个值/证明是否真的是那个类型/命题。如果是,证明就是正确的。

这听起来可能有点令人意外。通常要找到一个匹配某类型的值并不难。恰恰相反,可能的取值太多了,我们使用类型的唯一原因就是为了限制可选项。尽管如此,Lean 的类型系统与 TypeScript 中那种“普通”类型系统并没有太大区别。一些基础概念惊人地相似。事实上,我们甚至可以在 TypeScript 中直接证明简单的命题。

最简单的形式是这样的:

const proposition_name: PropositionAsType = proofAsValue

有了显式的类型标注,类型检查器就被迫去检查 proofAsValue 是否属于 PropositionAsType 类型。如果是,证明就是正确的。否则我们就会得到一个类型错误。

常量的一个问题是我们无法使用类型变量。而我们会需要类型变量。于是我们把所有证明都包在一个占位函数里:

function proposition_name<P,Q>(): PropositionAsType<P,Q> { return proofAsValue

注意:这样的函数并不是用来调用的。这只是纯粹的类型把戏,在运行时毫无用处。

费马大定理和黎曼猜想这类著名例子会浮现在脑海中。它们可以在 Lean 中表达,但无法在 TypeScript 中表达。我们得从更基础的地方开始:任何逻辑陈述都是一个命题。最基础的是 true 和 false,任何“返回”布尔值的表达式也可以被视为一个命题。所以用 &&、||、===、<=、isUpperCase(...) 等构建出来的东西都算。但这些是值层面的工具。命题是以类型的形式书写的。我们需要在类型层面拥有这一切。

false

命题 false 是错的!所以它绝不能有证明。在 TypeScript 中,对应的类型是 never。为什么?never 是空类型。根据定义,你在这里没有任何值/证明可以返回:

function false_is_true(): never { return ???

因此 never 没有证明。嗯,TypeScript 有一些逃生舱口。严格来说你可以这样写:

function false_is_true(): never { return "obviously not never" as never

但这是刻意绕过了类型系统。这就像假设 0=1。一旦你这么做了,一切就都不作数了。所以 never 是 false 在类型层面的版本。为了明确这一点,我们从现在起使用一个类型别名:

type False = never

true

true 必须有一个证明。所以必须存在该类型的一个值。这个值具体是什么并不重要。我们可以把它定义为一个带单个占位值的类型:

function true_is_true(): True { return "dummy"

与 / 或

下面是如何在类型层面定义布尔与/或:

type And<P, Q> = { left: P, right: Q } type Or<P, Q> = { left: P } | { right: Q }

作为第一个例子,我们来证明 Or<True, False>。如你所知,true || false 为真,所以这个命题应该有一个证明:

function true_or_false(): Or<True, False> { return { left: "dummy" }

另一方面,true && false 为假,所以它不可能有证明。你可以试试,但会卡住:

function true_and_false(): And<True, False> { return { left: "dummy", right: ??? }

逐一分析下面的命题。想一想对应的值层面表达式。如果它为真,就会有一个证明。试着把它写出来。

And<True, True> And<False, True> And<False, False> Or<True, True> Or<False, True> Or<False, False>

附注:你也可以用交叉类型运算符(&)来写 And。得到的类型是相同的,但请注意其语法与值层面的与(p && q)和或(p || q)是多么相似:

type And<P, Q> = { left: P } & { right: Q } // p && q type Or<P, Q> = { left: P } | { right: Q } // p || q

蕴含

蕴含(如果 P 则 Q)无处不在。不只是在数学命题中:

在数学/逻辑中,标准符号是 =>。要在类型层面使用蕴含,我们可以使用箭头函数。语法又一次对上了!

(p: P) => Q // if P then Q

记住,每个值都是一个证明。这个蕴含以一个 P 的证明作为参数,并且必须返回一个 Q 的证明。要证明蕴含本身,就是要表明这样一个函数存在。下面是一个简单的例子:

function P_implies_P_or_Q<P,Q>(): (p: P) => Or<P, Q> { return proofOfP => ({ left: proofOfP })

下面这点有点反直觉。我想每个人都会相信 false 蕴含 false。证明是成立的,但等一下……

function false_implies_false(): (p: False) => False { return proofOfFalse => proofOfFalse

我们不是说过不存在 False 类型的值吗?这个证明接收一个 False 类型的值作为输入,然后把它返回。为什么这居然是被允许的?这有点像在说:如果你给我一只独角兽,我就还你一只独角兽。独角兽并不存在,所以我知道第一步永远不会发生,但第一步蕴含第二步本身并没有任何问题。

下面是第一个有众所周知名字的命题:

type ModusPonens<P, Q> = (p_pq: And<P, (p: P) => Q>) => Q

用英语说就是:如果 P 为真,并且 P 蕴含 Q,那么 Q 也为真。

这一点起初让我非常困惑。尤其是嵌套的蕴含。一个蕴含去蕴含某个东西,到底是什么意思?但一旦你写下证明并选定具体的类型,

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →