擦除存在类型

# 擦除存在量词 来源：https://wolfgirl.dev/blog/2026-05-20-erasing-existentials/ 最近，我被 Alice (@welltypedwit.ch)（https://welltypedwit.ch/）在 Bluesky 上发布的一篇文章（https://bsky.app/profile/welltypedwit.ch/post/3mlpwmdubds2i）狠狠地"nerd-snipe"了。她在文章中问道： > 在 Rust 中，`dyn Trait` 表示 ∃s. Trait(s) ∧ s ，而 `fn f() -> impl Trait` 表示 f: ∃s. Trait(s) ∧ (() → s) 。但如果我想要一个存在量词作用于除 `Self` 参数之外的其他东西呢？比如，如果我有 `Trait`，并且我想要一个 ∃s, b. Trait(s, b) ∧ s 呢？ 这里面有很多花哨的数学符号，但我希望读完本文后，你既能理解它们的含义，也能明白我对这个问题的答案！ ## 什么是存在量词？ 从她问题的第一部分可以找到线索： > `dyn Trait` 表示 ∃s. Trait(s) ∧ s 我们来想想拥有一个 `dyn Trait`¹（https://doc.rust-lang.org/reference/types/trait-object.html）（https://wolfgirl.dev/blog/2026-05-20-erasing-existentials/#fn-sized）类型的值意味着什么。我们知道存在*某个*底层类型，但我们无法获取那个类型。我们所能做的就是调用 `Trait` 中的方法。这基本上就是那个公式所说的！"存在（∃）某个类型 `s`，使得（…）`s` 符合 `Trait`，并且（∧）你现在就可以使用 `s`"。那些吓人的数学符号只是简洁地表达了这一点。 数学还帮助我们形式化这样一个事实：仅仅给出这个 ∃ 陈述，我们无法事先知道 `s` 会是什么，因此在构建程序类型良好的"证明"时，我们只能假设关于 `s` 的那些来自它符合 `Trait`²（https://wolfgirl.dev/blog/2026-05-20-erasing-existentials/#fn-dyn）的信息。 Alice 还指出了 Rust 中另一个看起来像存在量词的地方： > `fn f() -> impl Trait` 表示 f: ∃s. Trait(s) ∧ (() → s) 这种"返回位置 impl trait"（https://doc.rust-lang.org/reference/types/impl-trait.html#r-type.impl-trait.return）语法确实是另一种指定类型的方式，使得 `f` 的调用者只知道返回类型符合 `Trait` 这一事实。与 `dyn Trait` 不同，这些是在编译时确定的，但从类型理论的角度来看，它们有些相似。 好了！现在我们有了初步理解，让我们开始真正的提问： > 如果我有 `Trait`，并且我想要一个 ∃s, b. Trait(s, b) ∧ s 呢？ 也就是说，是否可能拥有一个存在量化类型 `S`，它本身又有另一个存在量化类型变量 `B`，使得 `S: Trait`？ ## 尝试 1：For-Exists 转换 处理*任何*存在量词的一种经典方法是我称之为"for-exists 转换"的方法。基本上，它依赖于以下恒等式： ((∃x.P(x)) → Q) ⟺ (∀x.(P(x) → Q)) > 我的类型理论朋友说"这只是柯里化而已"，我当时非常困惑，因为我熟悉的柯里化定义是 ⟨a,b⟩ → c ⟺ a → b → c。也就是说，给定一个接受元组的函数，可以将其转换为一个返回函数的函数，乍一看这与上面提到的 exists/forall 定理毫无相似之处。 > > 然而！如果你有一个"依赖和" Σαβ(α)（第二个元素 β 的类型依赖于第一个元素 α 的值）和一个"依赖积" Παβ(α)（返回类型 β 依赖于输入 α 的值的函数），那么你会得到一个看起来非常相似的恒等式（https://ncatlab.org/nlab/show/existential+quantifier#in_dependent_type_theory）³（https://wolfgirl.dev/blog/2026-05-20-erasing-existentials/#fn-nlab）： > > ((Σαβ(α)) → C) ⟺ (Παβ(α) → C) > > 你可以从两个角度解释两边： > - 在"类型即命题"的解释中，Σ 有点类似于 ∃，因为要使其成立，你只需要一对 ⟨α, β(α)⟩；而 Π 有点类似于 ∀，因为要使其成立，你需要展示如何为每个可能的 α 得到一个 β(α)。 > - 将其解释为数据结构，Σ 就是一个元组，Π 就是一个函数，这正好是我们最初的柯里化。 > > 所以，我的类型理论朋友认为"应该称之为‘柯里化’而不是发明一个新名字"。但我不同意，因为这种联系并不明显，所以为了清晰起见，我将坚持使用我自己的名称 :) 知道得越多！在 Rust 中，这可以表述为： ```rust fn f_left(x: impl P) -> Q { x.foobar() } fn f_right<X: P>(x: X) -> Q { x.foobar() } ``` "但是 PolyWolf！"我听到你说，"你只是写了两次相同的函数？？"亲爱的读者，这正是这个恒等式的巧妙之处。它*看起来*显而易见，但实际上在说一些相当深刻的东西。`f_left` 确实在其参数中使用了存在量词（你对 `x` 的了解仅限于它有一个符合 `P` 的类型），而 `f_right` 首先对所有可能的类型 `X` 进行全称量化，然后限制为那些满足 trait `P` 的类型。在 Rust 中，你可能会认为前者只是后者的"语法糖"，但这并不能改变它们是*不同的数学陈述*这一事实。 为了更清楚地看到这一点，让我们考虑一下当我们把这些参数类型用作返回类型时会发生什么： ```rust fn g1() -> impl P { SpecificX::proof() } fn g2<X: P>() -> X { X::proof() } ``` 在这里，我们可以更清楚地看到 `impl P` 和 `X: P` 在说不同的事情。前者，像 ∃，只要求你展示一个满足 trait `P` 的 `SpecificX`；而后者，像 ∀，要求你为所有可能的 `X: P` 生成有效值。 那么！回到我们最初的问题，我们想要描述一个形式为： ∃s, b. Trait(s, b) ∧ s 在本篇文章的剩余部分，我们假设 Trait(s, b) 是某个 `S: Generic`（为了避免与后面引入的其他 trait 混淆而重命名），并且我们只能构建引用它的新类型/trait，绝不能修改它或以下实现： ```rust pub trait Generic { fn name(&self) -> &'static str; } impl Generic for i32 { fn name(&self) -> &'static str { "f32" } } impl Generic for i32 { fn name(&self) -> &'static str { "f64" } } ``` 首先将我们自己限制在接收这种类型的函数上，我们得到： (∃s, b. Trait(s, b) ∧ s) → () 然后，利用我们的恒等式，我们可以将其重写为： ∀s, b. (Trait(s, b) ∧ s) → () 这导致了以下函数（playground 链接（https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=5d4a408cb9e2b259c311f65fd8de2c6c））： ```rust fn use_generic<S: Generic>(s: &S) -> &'static str { s.name() } ``` 简单吧！这是处理该问题的一种非常标准的方法，在我看来也是最干净的。 然而，Alice 并不满意（https://bsky.app/profile/welltypedwit.ch/post/3mlqosj7his2o）： > 但你不能例如把这个放在一个数据结构（在 `Box` 后面）里，对吧？ 确实如此！由于我们以 ∀ 的方式重新描述了问题，一旦我们返回 `Box<dyn Generic>`，我们就必须在所有使用它的地方保留一个 ∀b 子句，这在一定程度上违背了最初拥有 ∃ 类型的目的（playground 链接（https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=7889714d44805f2f7f35a7a36a4f8e85））： ```rust fn put_in_box<S: Generic + 'static>(s: S) -> Box<dyn Generic> { Box::new(s) } fn use_box(s: &Box<dyn Generic>) -> &'static str { s.name() } ``` 这个解决方案可能对某些用例来说是令人满意的，但我们需要再努力一点，才能使事物只使用 ∃。 ## 尝试 2：关联类型 我的下一个想法是将 ∃s, b. 量词"偷偷"放在一个 Rust 在使用 trait 对象时给出的单个 ∃t. 量词后面。第一个尝试可能看起来像这样（playground 链接（https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=349cf08dc829d60b126b9f52b4f411ed））： ```rust trait SingleAssociated { type B; } impl<S: Generic, B> SingleAssociated for S { type B = B; } ``` 然而，我们很快就遇到了一个问题： ``` error[E0207]: the type parameter `B` is not constrained by the impl trait, self type, or predicates --> src/main.rs:15:6 | 15 | impl<S: Generic, B> SingleAssociated for S { | ^ unconstrained type parameter ``` E0207 文档（https://doc.rust-lang.org/error_codes/E0207.html）对此做了很好的解释（如果你还没试过，应该试试 `rustc --explain`！），但简而言之，每当实现 trait 时，Rust 希望对于每个具体类型*最多只有一种*具体的 trait 实现。这个限制被称为"连贯性（coherence）"，因为如果我们可以为单个类型选择多种可能的 trait 实现，那将是"不连贯的"⁴（https://wolfgirl.dev/blog/2026-05-20-erasing-existentials/#fn-specialization）。 当我们写 `impl<S: Generic, B> SingleAssociated for S` 时，Rust 会考虑所有符合条件可能的 `B` 和 `S`，然后才继续处理后续代码。然而，"所有可能的 `B`" 可能导致多于一个 `SingleAssociated for S` 的实现，所以我们不被允许这样做。 为了解决这个问题，我们必须将 `B` 放在 trait 或类型中，以"约束"它。我们不能将其放在 `SingleAssociated` trait 定义中（那样会使其与 `Generic` 相同！），也不能将其放在 `S` 中（它已经是泛型的），那么我们还能做什么呢？`PhantomData` :) `PhantomData`（https://doc.rust-lang.org/std/marker/struct.PhantomData.html）是一个零大小类型，允许我们为某个在运行时*基本上*与普通 `S` 相同的东西实现 `SingleAssociated` trait，只是多了额外的类型级别信息： ```rust use std::marker::PhantomData; impl<S: Generic, B> SingleAssociated for (S, PhantomData<B>) { type B = B; } fn mk_existential<S: Generic, B>(s: S) -> impl SingleAssociated { (s, PhantomData) } ``` 太好了，任务完成了，对吧？等等……我们实际上如何使用它呢？（playground 链接（https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=522b821400e55e934d0e64545c6ed571）） ```rust fn use_existential(_s: &impl SingleAssociated) -> &'static str { todo!() } ``` 我们存在量化类型的全部意义在于携带一个关于如何利用 `Generic` trait 做事情的证明。但就其本身而言，`SingleAssociated` trait 不允许我们访问任何实现 `Generic` 的东西。*我们*知道它只针对我们特殊的元组类型实现，但 Rust 不知道，所以我们不得不通过添加第二个关联类型和一个访问函数来帮助它： ```rust trait DoubleAssociated { type S: Generic; type B; fn as_ref(&self) -> &Self::S; } impl<S: Generic, B> DoubleAssociated for (S, PhantomData<B>) { type S = S; type B = B; fn as_ref(&self) -> &Self::S { &self.0 } } ``` 这让我们可以使用 `Generic` 中的函数⁵（https://wolfgirl.dev/blog/2026-05-20-erasing-existentials/#fn-self-types）（playground 链接（https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=a423fefa5b7e2d3963de3d99f6998912））： ```rust fn mk_existential<S: Generic, B>(s: S) -> impl DoubleAssociated { (s, PhantomData) } fn use_existential(s: &impl DoubleAssociated) -> &'static str { s.as_ref().name() } ``` 太棒了！如果我们满足于将 ∃ 类型用作函数的返回值，我们可以到此为止。 ……然而，为了满足 Alice 的要求，我们还希望能够通过将其放入 `Box` 中来"擦除"该类型，使其具有一致的表示；否则，两个都返回 `impl DoubleAssociated` 的函数实际上可能返回不同的类型，例如无法放在同一个 `Vec` 中。我们应该能够做到 `Box<dyn DoubleAssociated>`，所以让我们试试吧，好吗？（playground 链接（https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=7c335ebb94ff1628ef63e1ec483f6602）） ```rust fn mk_box<S: Generic, B: 'static>(s: S) -> Box<dyn DoubleAssociated> { Box::new((s, PhantomData)) } fn use_box(s: &Box<dyn DoubleAssociated>) -> &'static str { DoubleAssociated::as_ref(Box::as_ref(s)).name() } ``` 哎呀 ``` error[E0191]: the value of the associated types `S` and `B` in `DoubleAssociated` must be specified --> src/main.rs:44:24 | 14 | type S: Generic; | ------------------------ `S` defined here 15 | type B; | ------ `B` defined here ... 44 | fn use_box(s: &Box<dyn DoubleAssociated>) -> &'static str { | ^^^^^^^^^^^^^^^^^ | help: specify the associated types | 44 | fn use_box(s: &Box<dyn DoubleAssociated<S = , B = >>) -> &'static str { | ++++++++++++++++++++++++++++++++ ``` 它要求我们再次使用 ∀……说实话，我完全没有预料到这一点。我原以为 Rust 强制"每个具体类型最多一种具体 trait 实现"意味着关联类型可以以某种方式存储在 trait 对象 vtable 中，但我的直觉大错特错。再想想，我们返回类型为 `Associated::S` 的东西，这意味着在运行时，不同的 `DoubleAssociated` 实现必然有不同的 vtable，因为返回类型会有不同的内存布局，因此具有不同关联类型的 trait 对象*必须*是不同的。 Rust 1 – 我 0 那么，我们可以从中得到什么启示？在 Rust 中，完全自动地在同一类型中擦除多个存在量词边界是不可能的，因为它一次只支持一个（使用 `dyn Trait`）？不幸的是，是的，这是我得出的结论 :( 不过，如果我们愿意多花一点功夫，手动将多个存在量词边界合并成一个是有可能的。 ## 尝试 3：手动擦除 不要试图直接使用 `Generic` 中的函数，让我们创建一个 trait，对于每个我们关心的函数，手动将其透传到 trait 的函数： ```rust trait Erased { fn name(&self) -> &'static str; } impl<S: Generic, B> Erased for (S, PhantomData<B>) { fn name(&self) -> &'static str { self.0.name() } } ``` 这行得通！！我们甚至可以把它装箱，万岁（playground 链接（https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=67deae4b6f9b2145945b74b50418b89a））： ```rust fn mk_box<S: Generic, B: 'static>(s: S) -> Box<dyn Erased> { Box::new((s, PhantomData)) } fn use_box(b: &Box<dyn Erased>) -> &'static str { b.name() } ``` Alice 在这里对我们提出了最后一个要求（https://bsky.app/profile/welltypedwit.ch/post/3mlqu5urfjc2s）： > 嗯，但如果 trait 实际上使用了 `B` 参数，这个就行不通了，对吧？（因为你在 `Erased` 中无法使用它） 确实如此：`Erased` *故意*没有让它关心的类型发生变化，所有东西都需要是具体的，这样才能在 `dyn` 中没有问题地使用它。如果我们想要处理多种类型，我们将不得不使用 `std::any::Any`（https://doc.rust-lang.org/std/any/trait.Any.html）在运行时处理它们。这是一个例子（playground 链接（https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=8552501df3bcf4ae4d80aef60d3073b8））： ```rust use std::any::Any; use std::marker::PhantomData; trait Generic<B> { fn input(b: &B); fn output(&self) -> B; } impl Generic<f32> for i32 { fn input(b: &f32) { println!("f32: {b}") } fn output(&self) -> f32 { *self as f32 } } impl Generic<f64> for i32 { fn input(b: &f64) { println!("f64: {b}") } fn output(&self) -> f64 { *self as f64 } } trait Erased { fn input(&self, b: &Box<dyn Any>); fn output(&self) -> Box<dyn Any>; } impl<S: Generic<B>, B: 'static> Erased for (S, PhantomData<B>) { fn input(&self, b: &Box<dyn Any>) { S::input(b.downcast_ref::<B>().unwrap()) } fn output(&self) -> Box<dyn Any> { Box::new(self.0.output()) } } ``` 这编译并运行成功！不幸的是，如你所见，手动