Typeclass 与模块

# Typeclass 与模块 - sm2n.ca Source: https://sm2n.ca/articles/typeclasses-vs-modules/ 长久以来，我注意到一个挥之不去的困惑：模块系统（如 OCaml 中所见）与 typeclass（如 Haskell 或 Rust 中所见）之间到底有何异同。本文试图澄清这一困惑。 ## 简短回答 typeclass 作为一种语言构造，其主要目标是提供 *ad-hoc polymorphism*（特设多态）。这又被称为 *运算符重载* 或 *基于类型的派发*。特设多态的核心价值在于它是一种面向小规模编程的便利特性：它允许你跨类型复用相同的标识符。例如，我可能希望用 `+` 符号既表示整数的加法，也表示浮点向量的加法（重要的是，向量类型可能定义在某个随意的库中，因此我们无法将这种行为硬编码到语言本身）。 模块系统作为一种语言构造，其主要目标是提供 *模块化抽象*。这个特性的某些部分在更广泛的软件行业中有名字，比如 *依赖注入*、*封装* 和 *信息隐藏*。模块化抽象的核心价值在于让你能显式地表达程序的分解方式，从而更高效地进行大规模编程。它提供了一种组合式的方法，可以递归地将程序拆解为组成部分。 我认为导致困惑的主要因素有： - 历史上，编程语言往往只选择二者之一 - 它们共享一些底层机制： - 一种指定 *接口* 的方式 - 一种表明某段代码 *符合该接口* 的方式 - 你有时可以"将就着"用其中一个来模拟另一个（即用 typeclass 提供模块化抽象，或用模块提供特设多态）。不过，虽然模拟在很多情况下是可行的，但通常并非最优。 ## 为什么以及是什么：Typeclass Typeclass 背后的动机理念基本是：如果你要重载一个符号，它在"道德上"应当表示同样的含义。例如符号 `+` 表示加法这个抽象概念，我们可以为不同类型提供不同的实现。这与 C++ 形成对比，例如 `<<` 根据类型可以表示位移或流重定向，而这两者毫无共同之处。这里的目标是让程序的含义更易于理解（相对于无原则的 C++ 那套做法），同时通过减少符号数量来降低认知负担。我们可以学习少数几个适用于抽象结构的符号，比如 `+` 或 `>>=`，然后在各种不同的具体结构上使用它们。 如果我们想对此更认真一些，就需要考虑语义问题。如何确保 `+` 确实表示一个抽象的加法运算呢？我们可以给 typeclass 添加定律。例如，我们可以说加法必须满足 (a + b) + c = a + (b + c)（尽管这对浮点数不成立），然后用属性测试或证明见证（proof witness）来检验新的实现确实满足该定律。总体而言，每个 typeclass 都可以附带一些语义描述，理想情况下应以测试套件或证明义务的形式进行机器检验。 作为参考，下面是 Haskell 中 `Num` typeclass 的定义，取自 ghc (https://hackage.haskell.org/package/ghc-internal-9.1201.0/docs/src/GHC.Internal.Num.html#Num)。注意它给出了一些定律，但在这种情况下它们只是惯例性的。例如，浮点乘法不满足结合律，但它仍然有一个 `Num` 实例。 ``` -- | Basic numeric class. -- -- The Haskell Report defines no laws for 'Num'. However, @('+')@ and @('*')@ are -- customarily expected to define a ring and have the following properties: -- -- [__Associativity of @('+')@__]: @(x + y) + z@ = @x + (y + z)@ -- [__Commutativity of @('+')@__]: @x + y@ = @y + x@ -- [__@'fromInteger' 0@ is the additive identity__]: @x + fromInteger 0@ = @x@ -- [__'negate' gives the additive inverse__]: @x + negate x@ = @fromInteger 0@ -- [__Associativity of @('*')@__]: @(x * y) * z@ = @x * (y * z)@ -- [__@'fromInteger' 1@ is the multiplicative identity__]: -- @x * fromInteger 1@ = @x@ and @fromInteger 1 * x@ = @x@ -- [__Distributivity of @('*')@ with respect to @('+')@__]: -- @a * (b + c)@ = @(a * b) + (a * c)@ and @(b + c) * a@ = @(b * a) + (c * a)@ -- [__Coherence with 'toInteger'__]: if the type also implements 'GHC.Real.Integral', then -- 'fromInteger' is a left inverse for 'GHC.Internal.Real.toInteger', i.e. @fromInteger (toInteger i) == i@ class Num a where (+), (-), (*) :: a -> a -> a -- | Unary negation. negate :: a -> a -- | Absolute value. abs :: a -> a -- | Sign of a number. -- The functions 'abs' and 'signum' should satisfy the law: -- -- > abs x * signum x == x -- -- For real numbers, the 'signum' is either @-1@ (negative), @0@ (zero) -- or @1@ (positive). signum :: a -> a -- | Conversion from an 'Integer'. -- An integer literal represents the application of the function -- 'fromInteger' to the appropriate value of type 'Integer', -- so such literals have type @('Num' a) => a@. fromInteger :: Integer -> a x - y = x + negate y negate x = 0 - x ``` ## 为什么以及是什么：模块 模块的要点在于让你能符合人体工学地抽象程序的各个部分。为此，我们把程序拆分为各个部分（"模块"、"结构"），然后显式地指定它们如何组合在一起。重要的是，通过让每个模块对与之交互的其他模块隐藏自身的部分内容（封装！），我们可以减少推理整个程序所需的总精力。这对输出是有利的，但我们同样要考虑对输入进行抽象。为此，我们可以制作参数化模块（由于历史原因，这些通常被称为 *函子*，functors），它们本身不是模块，而是在用其他某个（些）模块实例化后产生一个模块。 我们被允许用哪些模块来实例化呢？所有符合某个特定接口的模块（在文献中这些接口通常被称为 *签名*，signatures）！同样，如果我们对此认真对待，可以给接口附加一些语义，例如惯例性的定律、测试套件或证明义务。毕竟，用模块化分解来组织程序最常见的原因之一，就是为了提高可测试性。识别重要的接口并针对接口进行测试，是一种以低成本获得大量覆盖的有效方式。 让我们看一个用到很多特性的例子。以下代码取自 unison 文件同步项目 (https://github.com/bcpierce00/unison/blob/master/src/fsmonitor/watchercommon.mli)，我为清晰起见做了轻微编辑。 首先，我们声明有一个 `StringMap` 类型，它符合标准库中的 `Map.S` 签名，但键类型特化为 String。这意味着任何依赖于 stdlib 暴露的接口的代码都可以使用我们的自定义 map，它甚至会检查所有调用点是否使用了正确的键类型。 接下来是一个参数化模块。高层的思路是：这是一个抽象了文件监视平台相关 API 的接口。 - 我们声明一个参数化模块 `Watcher`，它 - 接受一个模块 `WatchDescriptor`，该模块 - 定义了一个 `watch` 句柄类型 - 并返回一个支持后面声明的有限的、类似文件描述符的 API 的模块。 - 我们声明一个签名 `WatchBackend`，它暴露了一个用于操作 watcher 的 API - 还有一个参数化模块 `Run`， - 可用于运行 `Watcher`， - 使用一个实现了 `WatchBackend` 的模块（由于参数化模块返回的是一个签名为空的东西，它只能用于其副作用。） ``` module StringMap : Map.S with type key = string module Watcher (WatchDescriptor : sig type watch end) : sig type t val get_id : t -> int val get_watch : t -> WatchDescriptor.watch option val set_watch : t -> WatchDescriptor.watch option -> unit val get_subdirs : t -> t StringMap.t val is_root : t -> bool val file_by_id : (int, t) Hashtbl.t val dir_path : t -> string -> string val signal_change : float -> t -> string option -> [> `CREAT | `DEL ] -> unit val signal_overflow : unit -> unit end module type WatchBackend = sig val add_watch : string -> t -> bool -> unit val release_watch : t -> unit val watch : unit -> unit val clear_event_memory : unit -> unit end module Run (Backend : WatchBackend) : sig end ``` ## 如何：用 Typeclass 实现模块化 Typeclass 经常被用于抽象。例如，这里是我某个项目中的一些简单代码： ``` pub trait FileSystem { /// Check if a path exists fn exists(&self, path: &Path) -> bool; /// Get the file type of a path /// Returns an error if the path doesn't exist or can't be accessed /// Note: follows symlinks, so a symlink to a directory will return FileType::Dir fn file_type(&self, path: &Path) -> Result<FileType, Error>; /// List entries in a directory /// Returns an iterator of (name, file_type) pairs /// Note: follows symlinks, so a symlink to a directory will return FileType::Dir fn read_dir(&self, path: &Path) -> Result<Box<dyn Iterator<Item = (String, FileType)>>, Error>; /// Read the contents of a file as a string fn read_to_string(&self, path: &Path) -> Result<String, Error>; } ``` 由于我不需要很多文件系统操作，我只声明了需要的那些，这使得很容易在该接口上进行测试。那么，相对于使用模块，我们失去了什么？ - 我们分解事物的方式不是组合式的。例如，这里我说 `read_dir` 可能返回一个满足 `Iterator` trait 且 `Item` 类型被特化的东西。但我无法表达"这个方法返回一个符合我刚编造的这个特定签名的东西"（即内联接口不存在）。所有接口都必须绑定到某个类型（这些类型存在于某个作用域中），并且不能嵌套在其他接口中。 - 现在，每个想要针对这个接口编程的函数都要带上 trait 约束，这比具体版本更啰嗦。当函数签名变得极长时，这既烦人又嘈杂。用模块，你可以把约束放在模块层级，每个函数不必显式声明依赖（Rust 用 `impl` 块勉强有这一点，但它们同样不可组合）。 - 由于 typeclass 是为特设多态设计的，实例搜索通常是实现的一部分，这在编译时可能代价高昂。（例如，在 rust 中 `foo.bar()` 必须先推断 foo 的类型，然后查看所有可能传递性地 `impl foo` 的东西，再看有哪些 `bar` 的可能实现。） 总体而言，我认为这种做法推广了我所称的"函数集合"式的程序分解方法。Typeclass 的世界观是存在一个全局类型数据库，函数可能根据作用域看到该数据库的不同部分，但归根结底，程序只是一堆函数。每个函数独立存在，你必须在函数层面上进行推理。 模块为我们提供了一种更丰富的程序分解思考方式。我们不必把边界画在函数上。我们可以一次推理程序中更大的部分。用前面的类比来说，模块让我们一次思考程序中非平凡的子集。 好了，还有一件事，那就是反方向的情况。许多 ML 程序员会说"你不需要特设多态，实际上它可能还是有害的"。这个论点并不像听起来那么不合理：通过小心地使用词法作用域的导入，缺少特设多态只是稍显啰嗦，而且可能在机制上更容易理解。此外，由于一切都是显式的，编译器无需进行任何搜索来解析多态操作，这能加快编译速度。我认为，对许多 Zig 用户来说，Zig 相比 Rust 的吸引力有一部分就在于 Zig 程序员也倾向于站在这边。 以上这一大段归根结底是想说：至少在 OCaml 中，实现特设多态的方式就是干脆不要它。例如，下面是来自 Real World OCaml (https://dev.realworldocaml.org/files-modules-and-programs.html) 的一段代码，展示了几种使用 `Int64` 算术而不必给每个算术操作加命名空间的方法。 ``` let average x y = let open Int64 in (x + y) / of_int 2;; ``` ``` let average x y = Int64.((x + y) / of_int 2);; ``` 假设我们真的很想要特设多态。仔细想想，传统的 typeclass 可以用以下方式用模块来表达： - 我们有一个全局的签名数据库 - 我们有一个全局的类型数据库 - 我们有一个全局的模块数据库，每个模块都与一个类型关联（即每个模块有一个类型，但一个类型可以有多个模块） - 每个签名也知道所有符合它的模块，因而知道它们关联的类型 然后，每当我们使用来自某个签名的东西时，我们先推断类型，然后用它查找具体的模块。理论上，你可以几乎完全以与 typeclass 优先方式相同的方式实现特设多态，而在人体工学上没有真正的损失。这基本上就是 Modular Implicits (https://www.cl.cam.ac.uk/~jdy22/papers/modular-implicits.pdf) 提案为 OCaml 所建议的。Scala 3 也支持它所称的 "Contextual Abstraction" (https://docs.scala-lang.org/scala3/reference/contextual/index.html)，本质上就是上述做法的一种方式。与更传统的 typeclass 系统的主要区别在于，它不需要 *一致性*（coherence），而一致性超出了本文的讨论范围。 ## 模块和 Typeclass 都要？ 是的！Haskell 除了人人都在用的 typeclass 系统外，还有一个没人用的 Backpack 模块系统。理论上，它对模块化抽象和特设多态都有很好的支持。不幸的是，Bakpack 来到这个生态系统的时机有点晚，并没有获得太多采用。我相信 Rocq（原 Coq）也有独立的模块和 typeclass 系统。Rust 有一个与其 trait 系统分离的模块系统，但它太弱了，无法支持完整的模块化编程。该模块系统只支持封装，无法指定抽象的模块签名，因此不可能有参数化模块。Elixir 有一个模块系统，有它称之为 "behaviours" 的签名，还有通过它称之为 "protocols" 的 typeclass 式特设多态。此外，Elixir 具有渐进式类型，可以检查模块是否符合 behaviour。然而，目前还不可能声明"任何符合某个签名的模块都可以作为输入"。所以虽然你确实有参数化模块，但它们没有经过类型检查。 ## 结论 请记住 *模块化抽象* 与 *特设多态* 之间的区别。它们都可以是编程语言中有用的特性，并且关注点不同：一个面向大规模编程，另一个面向小规模编程。Typeclass 和模块只是实现这些目标的手段而已。 如果你在设计一门新语言，我认为很多人会优先选择 typeclass 和对特设多态的良好支持，而把模块化抽象当作事后才想到的事。我个人认为这本末倒置：我发现，在实践中，对模块化抽象的良好支持比特设多态对编写高质量程序更有价值。