← 返回 PaperDaily 大模型与智能体

Lean立功！死分支证明携带值，编舞编程彻底告别运行时崩溃

先说说什么是编舞编程（Choreographic Programming）。想象几个分布式角色要协同完成复杂协议，传统做法是给每个角色分别写代码，然后祈祷它们能正确对上。

龙哥读论文 阅读 3 查看原文
#人工智能
Lean立功！死分支证明携带值，编舞编程彻底告别运行时崩溃
原论文信息如下：
论文标题:
On Eliminating the Impossible with Dependent Types: Choreographic Libraries with Proof-Carrying Located Values 发表日期:
2026年08月 发表单位:
TU Darmstadt, University of St. Gallen, hessian.AI, National Research Center for Applied Cybersecurity ATHENE 原文链接:
https://arxiv.org/pdf/2608.23237v1.pdf

编舞编程的"不可能"困境：现有库的隐藏缺陷

先说说什么是编舞编程（Choreographic Programming）。想象几个分布式角色要协同完成复杂协议，传统做法是给每个角色分别写代码，然后祈祷它们能正确对上。编舞编程的思路完全不同：程序员只需从全局视角写一个总谱（Choreography），描述整个协议的完整流程，然后由编译器或库自动将这个总谱投影（Project）成每个角色各自执行的分谱（Endpoint）。
这个过程叫端点投影（Endpoint Projection，简称EPP）。下图展示了核心思想：左边是包含多个角色（A、B、C）的全局编舞，经过EPP后，右边变成每个角色各自的进程代码，原本统一的一对通信指令被拆分成匹配的发送（Send）和接收（Receive）操作。
图1：将编舞投影为进程。
这个"投影"听起来很美好，但真正实现起来有一个令人头疼的问题：部分性（Partiality）。啥叫部分性？简单说，就是一个函数并不是对所有可能的输入都能给出有效输出，在某些分支上它会直接"罢工"——抛异常、返回空值或者干脆陷入未定义行为。
论文犀利地指出，目前主流的库式编舞编程实现，比如用Haskell写的HasChor、MultiChor，以及用Rust写的ChoRus，它们的EPP实现都是部分函数。这些库在遇到某些"理论上不可达"的分支时，只能直接调用Haskell里的error函数抛出一个运行时错误。表面上看，库的设计者可以通过巧妙的API设计让用户不容易触发这些错误，但这种"让错误难以发生"的做法，本质上还是靠人工纪律来保证正确性，而不是靠类型系统。编译器只能眼睁睁看着这些隐患存在，却无法在编译期就把它们揪出来。
我们来看论文中展示的HasChor库的EPP核心代码（经过简化）。这段代码里有三处（第9行、第20行、第31行）直接使用了Haskell的error函数来处理"不应该发生"的情况。比如当目标角色没有某个值时，unwrap函数直接报错；当发送一个空值时，直接报错；当广播一个空值时，也直接报错。
    1  epp :: Choreo m a -> LocTm -> Network m a
2  epp c l' = interpFreer handler c
3  where
4  handler :: ChoreoSig m a -> Network m a
5  handler (Local l m)
6    | toLocTm l == l' =
7      wrap <　∥>∥ ∥r∥u∥n∥ ∥(∥m∥ ∥(∥∥x∥ ∥-∥>∥ ∥c∥a∥s∥e∥ ∥x∥ ∥o∥f∥8∥ ∥ ∥ ∥ ∥ ∥ ∥ ∥ ∥W∥r∥a∥p∥ ∥v∥ ∥-∥>∥ ∥v∥9∥ ∥ ∥ ∥ ∥ ∥ ∥ ∥ ∥E∥m∥p∥t∥y∥ ∥-∥>∥ ∥e∥r∥r∥o∥r∥ ∥"∥u∥n∥w∥r∥a∥p∥:∥ ∥E∥m∥p∥t∥y∥"∥1∥0∥ ∥ ∥ ∥|∥ ∥o∥t∥h∥e∥r∥w∥i∥s∥e∥ ∥=∥ ∥r∥e∥t∥u∥r∥n∥ ∥E∥m∥p∥t∥y∥1∥1∥1∥2∥ ∥h∥a∥n∥d∥l∥e∥r∥ ∥(∥C∥o∥m∥m∥ ∥s∥ ∥a∥ ∥r∥)∥1∥3∥ ∥ ∥ ∥|∥ ∥t∥o∥L∥o∥c∥T∥m∥ ∥s∥ ∥=∥=∥ ∥t∥o∥L∥o∥c∥T∥m∥ ∥r∥ ∥=∥1∥4∥ ∥ ∥ ∥ ∥ ∥c∥a∥s∥e∥ ∥a∥ ∥o∥f∥1∥5∥ ∥ ∥ ∥ ∥ ∥ ∥ ∥W∥r∥a∥p∥ ∥v∥ ∥-∥>∥ ∥r∥e∥t∥u∥r∥n∥ ∥(∥W∥r∥a∥p∥ ∥v∥)∥1∥6∥ ∥ ∥ ∥ ∥ ∥ ∥ ∥E∥m∥p∥t∥y∥ ∥-∥>∥ ∥r∥e∥t∥u∥r∥n∥ ∥E∥m∥p∥t∥y∥1∥7∥ ∥ ∥ ∥|∥ ∥t∥o∥L∥o∥c∥T∥m∥ ∥s∥ ∥=∥=∥ ∥l∥'∥ ∥=∥1∥8∥ ∥ ∥ ∥ ∥ ∥c∥a∥s∥e∥ ∥a∥ ∥o∥f∥1∥9∥ ∥ ∥ ∥ ∥ ∥ ∥ ∥W∥r∥a∥p∥ ∥v∥ ∥-∥>∥ ∥s∥e∥n∥d∥ ∥v∥ ∥(∥t∥o∥L∥o∥c∥T∥m∥ ∥r∥)∥ ∥>∥>∥ ∥r∥e∥t∥u∥r∥n∥ ∥E∥m∥p∥t∥y∥2∥0∥ ∥ ∥ ∥ ∥ ∥ ∥ ∥E∥m∥p∥t∥y∥ ∥-∥>∥ ∥e∥r∥r∥o∥r∥ ∥"∥s∥e∥n∥d∥:∥ ∥E∥m∥p∥t∥y∥ ∥p∥a∥y∥l∥o∥a∥d∥"∥2∥1∥ ∥ ∥ ∥|∥ ∥t∥o∥L∥o∥c∥T∥m∥ ∥r∥ ∥=∥=∥ ∥l∥'∥ ∥=∥2∥2∥ ∥ ∥ ∥ ∥ ∥w∥r∥a∥p∥ ∥<∥　> recv (toLocTm s)
23   | otherwise = return Empty
24
25 handler (Cond l a c)
26   | toLocTm l == l' =
27     case a of
28       Wrap v -> do
29         broadcast v
30         epp (c v) l'
31       Empty -> error "cond: Empty at broadcaster"
32   | otherwise =
33     recv (toLocTm l) >>= \x -> epp (c x) l'
    这段代码的问题在于，这些error分支虽然在实际使用中可能不会被触发，但类型系统无法证明这一点。这就好比一个电梯的说明书上写着"在正常情况下不会坠落"，但电梯里却没有安装任何防坠落的物理装置。正常情况当然不会掉，可一旦出了异常，你就只能听天由命。
    除了EPP本身的部分性，用户自己写的代码中也存在类似的问题。论文引用了一个MultiChor中的典型例子：当程序需要在一个和类型（Sum Type）上做分支时，比如一个值要么是LongList要么是LargeMatrix，用户必须写一些永远不该被执行的"死分支"（dead branches），用undefined来填充。这些死分支的存在，同样是类型系统不够强大导致的。
    这些问题的根源在于，现有的库式编舞编程都是把EPP当作一个运行时的解释器——在程序运行过程中动态地解释每一个编舞指令并生成对应的网络操作。这种动态解释的方式，让库无法像编译器那样在编译期对整体协议做静态检查。一般来说，解决这个问题需要宿主语言（Host Language）拥有足够强大的类型系统，把更多检查工作从运行时提前到编译期。Haskell的类型系统虽然强，但还不够强到可以表达和消除这些"不可能"的分支。

    破局思路：用更强的类型系统兜底

    那有没有一种语言，它的类型系统强大到可以直接把"部分性"从根源上消灭掉？有，那就是依赖类型（Dependent Types）。论文选择了一个以定理证明闻名，但同时也是一个完备的依赖类型编程语言——Lean。
    R-C
    依赖类型是一种允许类型依赖于值的类型系统。普通语言里，[Int]是一个类型（整数列表），但依赖类型语言里，你可以表达类似"长度为n的整数列表"这样的类型，其中n是一个值。这听起来很抽象，但它的威力在于：你可以把程序的不变量直接编码到类型里，让编译器在编译期就帮你证明这些不变量一定成立。

    依赖类型如何让端点投影成为全函数

    ChorLean要解决的第一大问题，就是让定位值（Located Value）的访问变得安全。什么是定位值？在编舞编程里，一个变量的值通常只存在于某些角色的本地（这些角色叫做该变量的"拥有者"即owners）。其他角色对这个变量是一无所知的。比如一个变量只在Alice的机器上存在，Bob的机器上根本没有这个变量的存储空间。
    在现有的库（HasChor, MultiChor, ChoRus）中，定位值通常被建模为一个类似Option的类型：有值就是Some v，没值（即该角色不是拥有者）就是None。这种建模方式带来的后果就是，当你需要"解开"（unwrap）这个定位值以获取内部的实际值时，你必须同时处理Some和None两种情况。对于None这种情况，代码就不知道该怎么办了，只能报错——这就是部分性的来源。
    ChorLean的设计则完全颠覆了这个思路。它把定位值定义为一个函数：一个从"目标角色是拥有者"这个证明，到实际值的函数。换句话说，你只有在持有"你确实是这个值的拥有者"的证明时，才能访问到这个值。如果你没有这个证明，编译器根本不会让你通过类型检查。
      def Located
  (O: List (Fin N)) (t: Hidden (Fin N)) (α: Type) :=
  t.v ∈ O -> α
notation α "@" O "#" t => Located O t α
      这里，Fin N表示小于N的自然数类型，用来给N个角色编号。Hidden类型包装了目标角色t，并且它的构造和析构函数是private的，用户无法直接查看t的具体值——这样就不会有人写出"如果我是Alice就干A，是Bob就干B"这种破坏同步性的代码了。
      这个定义妙在哪里？你会发现，unwrap操作变成了一个恒等函数（identity function）：
        def unwrap: Located O t α -> t.v ∈ O -> α := id
        函数变成了id，问题的关键转移到了如何构造出t.v ∈ O这个证明。而Lean的自动化证明工具（比如grind策略）可以自动构造大部分证明。只有真正拥有该值的角色才能得到这些证明，于是访问定位值这件事，就变成了一个类型检查问题——你无法在类型层面构造出不该有的证明。
        这种设计称为证明携带的定位值（Proof-Carrying Located Values）。论文作者特别指出，仅在这个核心机制上，ChorLean就把其他库有安全隐患的unwrap操作，变成了一个完全安全、不可能出错的操作。
        那EPP呢？在ChorLean中，EPP函数被设计为总函数（Total Function），也就是说，它对所有合法的编舞输入，都能给出一个对应的进程输出，不存在"报错"的分支。这得益于Lean的完全性检查器（Totality Checker）。在EPP的实现中，凡是遇到"不可能"的分支，代码都是用False.elim来处理的——它接收一个逻辑矛盾（False）的证明，然后从矛盾中推导出任何命题。关键在于，这个矛盾证明不是瞎编的，而是由Lean的证明策略自动构造出来的——它证明了这些分支真的不可能发生。
        fine
        我们用论文中的列表10来具体看看。在EPP处理Enclave和Share这两个构造器时，有几行代码是绿色的（在论文中高亮显示），代表"不可能"的情况。比如当处理Enclave时，如果子编舞的census不包含目标角色t，那就说明这个子编舞在当前投影下根本不应该执行。此时代码构造了一个矛盾证明h: t.v ∈ c'（实际上c'不包含t），然后用False.elim把这个矛盾转换为我们需要的任意值。Lean的完全性检查器看到这里就满意了——因为这里不是抛异常，而是给出了一个逻辑上严密的证明，证明这条路走不通。

        证明携带的定位值：消除死分支的关键机制

        前面提到，即便EPP本身做到了全函数，用户写的编舞代码里依然可能存在"死分支"。这个问题的根源在于：当一个值通过通信从一个角色传递到另一个角色时，接收方无法自动得知这个值的构造信息。
        我们来看论文中的MultiChor例子。场景是这样的：frida角色有一个值val，它要么是LongList要么是LargeMatrix（在Haskell中用Either类型表示）。协议需要根据val的实际构造来决定后续走handleList还是handleMatrix分支。但关键是，决定权在frida这里，emil需要被通知这个选择。你可以传一个布尔标志位给emil，告诉他"是Left还是Right"。问题在于，当emil收到这个标志位后，在本地做模式匹配时，Haskell的类型系统依然要求他提供完整的两个分支的代码。即使emil知道这个值是Left，类型系统也不相信他，他仍然必须写一条处理Right的代码，而这个分支永远不会被执行。代码被迫写成了下面这样：
          -- 来自MultiChor的例子
case (un frida val) of
  Left is  -> is
  Right _  -> undefined  -- 永远不可达，但必须写
          而ChorLean则利用依赖类型的表达能力，提供了一种"证明携带的广播"（Proof-Carrying Broadcast）机制。核心思想是：当我们广播一个消息msg时，我们不仅发送这个消息的内容v，还能附带一个证明，证明v与原始消息msg对所有拥有者来说都是等价的。这个证明在类型层面被编码为：
            {v: µ // ∀ x, msg x = v}
            这个类型读作"存在一个值v，并且对于所有的证明x（即对于所有能拿到这个消息的角色），msg x 都等于 v"。利用这个证明，在后续的模式匹配中，ChorLean就可以自动推导出哪些分支是"不可能的"，并且可以在类型层面直接排除这些分支！
            于是，同样的逻辑，在ChorLean中写起来就是这样的（论文中的列表6）：我们看到，在第4行，bcast'返回了一个带有证明的布尔值（true或false），这个证明在h和h'中被携带。在第6-7行，当我们从val中提取List时，只需要用到h: (val x).isLeft = true，就能安全地调用getLeft。整个代码中，不存在任何"死分支"，因为类型系统已经替我们证明：这些分支不需要存在。
            这个机制巧妙在哪里？它利用了编舞编程的一个特性：在EPP过程中，当一个值被共享（Share）时，它对于所有拥有它的角色来说，值是不变的。虽然网络传输本身会"丢失"值的信息（接收方无法证明收到的值就是发送方发送的那个值），但我们可以证明"如果一个角色已经拥有某个值，那么通过广播并不会改变这个值"。

            从理论到实践：ChorLean的案例验证

            理论说得再好，不如动手写个例子。论文提供了一个经典的"图书销售员"（Bookseller）案例，这个案例在之前的编舞编程文献中经常被用作基准测试。我们来看看ChorLean怎么搞定它的。
            图3：图书销售员时序图。
            这个协议有三个角色：买家B、卖家S。流程是这样的：买家输入书名，传给卖家；卖家根据书名查价格，然后把价格分享给买家；最后，如果买家预算充足，双方打印"购买成功"。这个流程可以用下面的代码来写：
              def books {t p} (budget:Nat): Choreo 2 t [B, S] p Unit := do
  let title: String @ [B] ← enclave [B] fun _ => run do
    IO.println "enter your title"
    Input.readString
  let title': String @ [S] ← com S title
  let price: Nat @ [S] ← enclave [S] fun h => run do
    lookup_price (title' h)
  let price' : Nat @ [B, S] ← share B price
  let price'': Nat := price' p
  if budget >= price'' then
    parallel fun _ _ => IO.println "purchase successful"
              代码看起来很简洁，但每个细节都值得品味。比如enclave [B]这个调用，它限定了子编舞只在B这个角色上执行，其他角色看不见。返回值title的类型是String @ [B]，表示只有B拥有这个字符串。当S需要这个title时，用com S title来把它发送给S。而share B price则是把price共享给B，注意共享和通信的区别：共享之后的price'类型是Nat @ [B, S]，表示B和S都拥有价格了。
              然后，price' p这一行，就是一次性使用证明p来解包定位值。这里p是编译期自动生成的证明，用户无需关心它是怎么构建的，只需要知道p证明了当前目标角色确实拥有price'，所以可以安全地读取它的值。
              论文还对比了ChorLean和MultiChor的实现。作者指出，ChorLean不仅在定位值访问这个层面做到了静态类型安全，还支持了MultiChor所有的核心特性，包括enclave（飞地）、run（本地IO执行）、share（共享）、com（通信）、bcast（广播）、locally（本地执行）、parallel（并行执行）等。
              论文附带的开源工件（artifact）中，还包含了其他几个非平凡的案例分析，比如分布式排序、两阶段提交等，都来自已有的编舞编程文献。这表明ChorLean的表达能力足够覆盖真实世界中的典型分布式协议，而不仅仅是玩具示例。
              值得一提的是，ChorLean在实现核心EPP函数和定位值定义时，完全没有使用sorry或panic。sorry是Lean中的"我不证明了，你信我"（实际上会留下一个编译警告），panic则是运行时错误。整个库的核心代码通过了Lean的完全性检查，这意味着没有任何未定义行为。
              但论文也坦诚地指出了当前实现的局限和未来方向。首先，通信仍然无法传递消息值的语义信息——接收方无法在类型层面证明收到的值就是发送方发出的同一个值，因为网络传输本身是外部不可控的事实。因此，对于那些依赖于"消息确实被正确传递"的性质（比如分布式排序算法的终止性）就无法在类型层面被证明了。其次，编舞编程库方法的一个固有不足是必须用一个private的Hidden类型包装目标角色，以防止用户代码查看目标值，从而破坏不同投影之间的同步性。这个限制在之前的HasChor、MultiChor等库中同样存在。

              局限与展望：编舞编程的未来方向

              这就要说到ChorLean的边界了。正如论文所说，编舞编程库这个路线的关键假设是"每个角色上的进程在到达通信原语时保持同步（lockstep）"。这个同步性在纯函数语言里是靠确定性来保证的：同样的输入必然产生同样的分支选择，所以所有投影都会沿着相同的控制流走到同一条通信指令上。
              前面提到的那个MultiChor死分支的例子，恰恰说明了这种同步性的脆弱性：虽然通信中的"值"可以被传递，但"关于值的知识"（比如这个值是Left还是Right）往往会丢失。ChorLean通过proof-carrying机制，在不需要发出额外消息的前提下，把这些"知识"在类型层面保持下来，消除了死分支。但对于跨网络的值本身，这种知识就无法携带了，例如分布式排序的终止性验证即不在其能力范围内。
              如果把眼光放长远一点，ChorLean的工作其实是朝着"可验证的分布式系统"这个方向迈出的一步。传统的分布式系统验证方法是先写代码，再写形式化证明，证明这个代码满足某个规范。而ChorLean的思路是直接在语言层面把"不可能的状态"变成"不可表达的代码"。这有点像是安全带和防护栏的区别——一个是在出事后减轻伤害，另一个是从物理上不让出事。
              对于未来工作，作者提到可以探索的方向包括：验证更丰富的协议性质（比如活性liveness）、支持动态角色集合、以及把ChorLean的proof-carrying想法应用到其他现有编舞库中去。尤其是最后一点，如果能把MultiChor或者HasChor的定位值改成proof-carrying风格，那么它们也能在不切换到Lean的情况下，提升自身的类型安全性。
              一个值得思考的问题是，为什么选择Lean而不是其他依赖类型语言比如Agda或Coq？论文提到，之前的Agda方案在理论上证明了可行性，但Agda的编译性能和代码效率不太适合实际运行。Lean之所以能胜出，在于它既拥有强大的证明能力，又会被编译成高效的C代码和JavaScript，更贴近"真正的编程"。

              龙迷三问

              下面是龙哥对于大家可能的一些问题的解答：
              这篇论文到底在解决什么问题？编舞库的端点投影与定位值访问长期靠运行时错误兜底。ChorLean用Lean依赖类型把端点投影变为全函数，以证明携带的定位值消除死分支，既通过全函数检查又不牺牲表达能力，还删掉了sum type上的假死代码。
              这篇工作最值得看的点是什么？论文通过多个案例研究（认证协议、GMW协议、Karatsuba乘法）验证了ChorLean的实用性，展示了其能够实现与MultiChor等库相同的功能集，同时消除部分性。
              这篇工作的边界或风险在哪里？优点：(1) 利用依赖类型实现了全函数的端点投影和定位值访问，消除了运行时错误；(2) 通过证明携带的定位值，避免了用户代码中的死分支；(3) 保持了与现有库相同的功能集和表达力。缺点：(1) 通信仍会丢失消息值的语义信息，无法证明跨角色传输的值不变性；(2) 依赖Hidden类型包装目标角色，依赖可见性修饰符，存在理论上的局限性；(3) 部分递归算法（如Karatsuba）仍需标记为partial定义。
              如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~

              龙哥点评

              论文创新性分数：★★★★☆

              利用Lean依赖类型系统，通过证明携带的定位值（proof-carrying located values）将端点投影（EPP）和定位值访问从部分函数转变为全函数，消除运行时错误和未定义行为。

              实验合理度：★★★☆☆

              现有材料未完整覆盖数据划分、基线公平性和统计显著性，因此按中性评价处理。

              学术研究价值：★★★★☆

              利用Lean依赖类型系统，通过证明携带的定位值（proof-carrying located values）将端点投影（EPP）和定位值访问从部分函数转变为全函数，消除运行时错误和未定义行为；更关键的是问题定义是否可复用到同类任务。

              稳定性：★★★☆☆

              现有材料未提供充分的极端条件、重复运行或扰动测试，稳定性暂按中性评价。

              适应性以及泛化能力：★★★☆☆

              现有材料未完整展示跨数据集、跨场景或分布外实验，泛化能力仍需进一步验证。

              硬件需求及成本：★★★☆☆

              现有材料缺少完整训练资源、参数量、显存和推理时延信息，成本暂按中性评价。

              复现难度：★★★☆☆

              现有材料未确认完整代码、配置、数据处理脚本和权重是否齐备，复现难度暂按中性评价。

              产品化成熟度：★★★☆☆

              论文验证以研究实验为主，真实部署中的时延、成本、维护和异常场景仍需补充验证。

              可能的问题：(1) 通信仍会丢失消息值的语义信息，无法证明跨角色传输的值不变性；(2) 依赖Hidden类型包装目标角色，依赖可见性修饰符，存在理论上的局限性；

              主要参考文献

              [1] Simon Daniel, Timon Böhler, Pascal Weisenburger, David Richter, Mira Mezini. On Eliminating the Impossible with Dependent Types: Choreographic Libraries with Proof-Carrying Located Values. TU Darmstadt, University of St. Gallen, 2026.
              [2] 原论文链接: https://arxiv.org/pdf/2608.23237v1.pdf
              [3] 论文中提到的ChorLean开源工件: 可于作者发布的artifact中获取，详细地址见原论文。

              *本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击"阅读原文"，查看更多原论文细节哦！       

              end
              想让bug在出现前就被"不可能"三个字挡在门外？欢迎加入龙哥读论文粉丝群，扫描下方二维码或者添加龙哥助手微信号加群：kangjinlonghelper。一定要备注：研究方向+地点+学校/公司+昵称，根据格式备注可更快被通过并邀请进群。『龙哥读论文』微信群目前包含：图像处理、大模型及智能体、自动驾驶及机器人、AI医疗及AI金融5个群，一起把正确性焊死在编译期！

              转发文章 微博 X LinkedIn Facebook
              龙哥读论文 · PaperDaily

              本文基于龙哥读论文 PaperDaily 数据库整理，结合论文原文与工程视角进行解读。