编程语言是如何实现泛型的 · 构建我的被动收入

[utterances-bot]

编程语言是如何实现泛型的 · 构建我的被动收入

本文介绍Go/Java/C/C++/Swift等编程语言是如何实现泛型的。

https://www.bmpi.dev/dev/deep-in-program-language/how-to-implement-generics/

[wey-gu]

👍 感谢

[weigram]

写的很好，第一次见到很多底层的名词！

[lxdlam]

文章里面有很多描述是存在问题的。我提出几点：

1. 强弱类型的区别并不是所谓的严格检查。虽然强弱类型没有严格定义，但是普遍认为强弱类型的核心区别在于，语言能否在某一个时刻能检查出来类型导出的错误，而不是扔出来一个 RuntimeError 一类 unchecked 的错误。

   举个例子的话，当你使用 1.0+1 的时候，一门强类型语言可以：

   • 接受这种行为，因为存在 fun +(float, integer)；
   • 拒绝这种行为，因为两个类型不同，且不存在上述的 + 函数。

   而弱类型语言会接受这种表达式，并且做出下面的某种或者多种类似行为：

   • 尝试将两种类型隐式转换成同一类型处理；
   • 尝试直接将二者加起来，并报错。

   可以发现，区别就是强类型语言会事先进行类型级别的操作，而弱类型语言会尝试去调整类型，甚至无视类型进行操作。将这二者区分出来的核心现象就是，弱类型语言往往无法信赖变量的值，需要写很多额外的代码做额外的类型验证操作。

2. 语言理论多态包含三个主要类型：Ad-hoc，parametric 和 subtyping。而通常语义下的泛型编程特指 Parametric Polymorphism，和 OOP 的多态（Subtyping）没有直接关系，动静态分发的语义是 Subtyping Polymorphism 下面的。这两个概念在文章中完全混淆了。

   泛型最大的特点在于有类型检查，可以检查你的参数和具体类之间是不是确实可以调用的。在检查上，泛型和另外两种多态类型有如下关系：

   • Ad-hoc：通过指定某种方法集合，让具体类型可以实现这个方法集合，进而满足泛型限制要求。（重载、接口等）
   • Subtyping：通过限制类的范围，让某一些具体的类能满足这个限制要求。（Java 和 Scala 等的 Covariance/Contravariance）

3. 实现泛型的方法目前普遍只有两种：

   • Monomorphization/Stenciling：根据不同类型生成不同的代码。现代编译器已经支持了只针对使用到的类型进行代码生成了，C++ 的模板跟 Rust 的静态 Trait 都是此类。

   • Type Erasure/Dictionary：调用方法统一，运行时对代码进行检查。在这种场景下，要么方法表会被传入对应的泛型参数，要么在调用时编译器去 Resolve。

     • Rust dyn traits，Java：编译时插入检查函数和 Resolve 代码，运行时针对对应 obj 去访问 metadata，确认是否可以 cast 到对应类型（Java）或者能否找到对应 stub 代码进行调用（Rust dyn traits）。
     • Haskell/Swift：编译时将泛型函数改写，并将对象的原信息当做参数传入，运行时从这个参数检查。

     这两种方法的具体区别只有这个 metadata 是跟着参数走，还是跟着对象走。跟着对象走会有 fat pointer 的问题，跟着参数走可能需要多个 pass 全局 Resolve。

   Go 的实现方法并没有什么巧妙的地方，它只是把上述两种方法结合了起来：

   • 代码生成不针对具体的类型，只针对 GC Shape 相同的类型。（区别于 Monomorphization：需要针对生成的类型减少）。
   • 具体类型的方法通过 Dictionary 传入。（区别于 Dictionary：通常的 Dictionary 只会生成一个 stub，所有检查都在 runtime）。

4. C 没有泛型。泛型被认为发生在编译期，而宏替换是 Preprocessor 的事情，不是 C 编译的事情。你同样可以在其他语言使用 Preprocessor。

[madawei2699]

@lxdlam 感谢这么详细而专业的反馈，我会尽快根据你的意见重新修改文章，谢谢！

[madawei2699]

原评论来自：https://www.v2ex.com/t/843140#r_11548105

1.先把词输入对。
范型(paradigm)
泛型(generics)
2.讨论泛型，C 放进来是用来嘲讽用的么。
这还是因为现在 C 有_Generic ，够当作底线了（但是 OP 一点没提）。
手工复制和旧式 C 宏连当作范型的底线都不配，因为和类型系统完全没有交互。
（原文评论区说无关是因为预处理器原因，这是错的，因为 pp phase 也是语言规范钦定的一部分，不应作为是否算是泛型实现的准则。否则 multi-stage programming 之类的就尬了。）
3.不要参考什么强类型弱类型之流只会让概念更加含混的伪劣资料来源。
所谓的强类型对立的就是“无”类型或者单一类型(unityped)。
更原则性上的错误在于这根本不属于类型检查，而是确保存在能被检查的类型的前提。
（ cf.github.com/FrankHB/pl-docs/blob/master/zh-CN/typing-vs-typechecking.md ）
4.装箱本质上和类型系统无关。
把装箱的外延缩小为几种 manifest typing 的语言的应用实例是一个常见理解偏差。
(cf.stackoverflow.com/a/69991369 ）
利用装箱实现泛型只是用了箱和被装的对象的非同一性；技术上，这里拿来装出来的是不是箱并不重要。
对象布局根本上需要通过 ABI 约定，箱不是描述 ABI 的抽象。
5.类型擦除和装箱无关。（为什么是 ed 不是 ing ？）
没有箱的类型擦除一样可以实现某种意义上的泛型。
6.vtable 不一定是虚“函数”表（就 Java 来说，一般叫虚方法表）。
虚表这里只是用来替代 RTTI ，跟装箱也无关。
7.同上，图中的字典传递跟装箱也无关。
而且跟虚表并列的应该是字典（虽然这个词太滥了），同样是用来实现某种 RTTI 替代品。
文章和目录里倒是正常了一点。
原文评论区有说 Type Erasure/Dictionary ，这个也不确切，更准确地，应该是+。两者都算不上是完整的实现技术。
但是前者是任意 manifest typing 意义上必要的，后者只是针对静态语言静态区分数据和所谓泛型函数的可选优化。
8.文章里说的 type parameter 暗示实现的说法是错的。
type parameter 本来就是 parameteric polymorphism 的核心，没 type parameter 的系统根本不会叫做泛型。
原文的评论区也指出了这一点。
要有区别，就是 typing 意义上的强度，例如类型系统是否允许支持所谓的 non-type parameter （根本地，形式上还是 type ，比如 dependent type ）。
9.文章链接的《透过 Rust 探索系统的本原：泛型》里把泛型函数从参数化类型中独立出来的做法在概念上是错的。
泛型函数的区别无非是类型参数和→这个类型构造器的交互，所以是参数化类型的一部分。
如果类型系统允许一个值同时居留于不带有→和带有→的类型（如类型擦除可以把→这个 kind 擦回*），那么单独考虑泛型函数差不多完全就是实现细节。
当然，考虑到带有→的 STLC （λ→）是 lambda cube 往其它类型系统（典型地，System F(λ2)）扩展的原点，基本上会涉及泛型函数的语言都不允许这样做，即便类型擦除有能力实现；所以这点很容易被一般的作者忽视掉。

[fatFire]

文章里面有很多描述是存在问题的。我提出几点：

1. 强弱类型的区别并不是所谓的严格检查。虽然强弱类型没有严格定义，但是普遍认为强弱类型的核心区别在于，语言能否在某一个时刻能检查出来类型导出的错误，而不是扔出来一个 RuntimeError 一类 unchecked 的错误。
   举个例子的话，当你使用 1.0+1 的时候，一门强类型语言可以：

   • 接受这种行为，因为存在 fun +(float, integer)；
   • 拒绝这种行为，因为两个类型不同，且不存在上述的 + 函数。

   而弱类型语言会接受这种表达式，并且做出下面的某种或者多种类似行为：

   • 尝试将两种类型隐式转换成同一类型处理；
   • 尝试直接将二者加起来，并报错。

   可以发现，区别就是强类型语言会事先进行类型级别的操作，而弱类型语言会尝试去调整类型，甚至无视类型进行操作。将这二者区分出来的核心现象就是，弱类型语言往往无法信赖变量的值，需要写很多额外的代码做额外的类型验证操作。

2. 语言理论多态包含三个主要类型：Ad-hoc，parametric 和 subtyping。而通常语义下的泛型编程特指 Parametric Polymorphism，和 OOP 的多态（Subtyping）没有直接关系，动静态分发的语义是 Subtyping Polymorphism 下面的。这两个概念在文章中完全混淆了。
   泛型最大的特点在于有类型检查，可以检查你的参数和具体类之间是不是确实可以调用的。在检查上，泛型和另外两种多态类型有如下关系：

   • Ad-hoc：通过指定某种方法集合，让具体类型可以实现这个方法集合，进而满足泛型限制要求。（重载、接口等）
   • Subtyping：通过限制类的范围，让某一些具体的类能满足这个限制要求。（Java 和 Scala 等的 Covariance/Contravariance）

3. 实现泛型的方法目前普遍只有两种：

   • Monomorphization/Stenciling：根据不同类型生成不同的代码。现代编译器已经支持了只针对使用到的类型进行代码生成了，C++ 的模板跟 Rust 的静态 Trait 都是此类。

   • Type Erasure/Dictionary：调用方法统一，运行时对代码进行检查。在这种场景下，要么方法表会被传入对应的泛型参数，要么在调用时编译器去 Resolve。

     • Rust dyn traits，Java：编译时插入检查函数和 Resolve 代码，运行时针对对应 obj 去访问 metadata，确认是否可以 cast 到对应类型（Java）或者能否找到对应 stub 代码进行调用（Rust dyn traits）。
     • Haskell/Swift：编译时将泛型函数改写，并将对象的原信息当做参数传入，运行时从这个参数检查。

     这两种方法的具体区别只有这个 metadata 是跟着参数走，还是跟着对象走。跟着对象走会有 fat pointer 的问题，跟着参数走可能需要多个 pass 全局 Resolve。

   Go 的实现方法并没有什么巧妙的地方，它只是把上述两种方法结合了起来：

   • 代码生成不针对具体的类型，只针对 GC Shape 相同的类型。（区别于 Monomorphization：需要针对生成的类型减少）。
   • 具体类型的方法通过 Dictionary 传入。（区别于 Dictionary：通常的 Dictionary 只会生成一个 stub，所有检查都在 runtime）。

4. C 没有泛型。泛型被认为发生在编译期，而宏替换是 Preprocessor 的事情，不是 C 编译的事情。你同样可以在其他语言使用 Preprocessor。

大佬是从哪里学习这些知识的？有什么书或者课程推荐吗

[madawei2699]

一些有价值的关于泛型的讨论：

https://twitter.com/haoel/status/1549721534876397568?s=21&t=gziu6e4kN3GCYat6-k-lFQ

https://twitter.com/haoel/status/1549716684566450181?s=21&t=gziu6e4kN3GCYat6-k-lFQ

[lxdlam]

https://www.bmpi.dev/dev/deep-in-program-language/how-to-implement-generics/

sry 刚看到，这个去看一些比较老派的语言社区都会有提到相关概念，比如 Racket（现在应该是用的人最多的 Scheme 实现），Haskell 等

[lxdlam]

一些有价值的关于泛型的讨论：

https://twitter.com/haoel/status/1549721534876397568?s=21&t=gziu6e4kN3GCYat6-k-lFQ

https://twitter.com/haoel/status/1549716684566450181?s=21&t=gziu6e4kN3GCYat6-k-lFQ

我不得不说，非常浮于表面的探讨。

实际上如何选择某一个类型，这个是类型系统的工作，和是否是泛型没有直接联系。Go 的 type assertion 跟 C++ 的 if constexpr 唯一区别只是一个发生在 Runtime 一个发生在 Compile time。一些注重性能的语言通常把 type 维度的计算放在 Compile time，比如 Zig、Rust、C++，而其他语言则倾向于放到 Runtime，比如 Java 等等。

实际上来说，在 Parametric Polymorphism 这一层，我们的目的是提出 contract：可以对某些类型 T 做这样的操作，比如 fun Sort(arr []T) where T: Comparable，而在 Ad-hoc Polymorphism 这一层，我们的目的是满足 constraint：如果我的类型不支持 Comparable，我提供一个实现，让其可以满足 constraint。你会发现，这个里面对于检查这个过程并没有提及：无论是在运行时还是编译期，我们其实无所谓，这不破坏语言理论上的要求，而更多是性能方面的需求。

换句话说，type assertion 和 if constexpr 是直接把 pattern matching 的过程手动做了，而 interface 和 template 上的 type traits 则是让编译器去做 pattern matching。无非是谁做的事儿而已。

[madawei2699]

感谢 @lxdlam 的评论，虽然这篇文章错误百出，估计是我写过错误最多的一篇文章了，但能得到这样好的评论让我觉得这一切都很值得，这也是写作的意义，写的对帮助了别人，写的错提高了自己😂

从我遇到很多对类型及泛型的讨论看，这是一个非常复杂的概念，因为不同的编程语言实现方式不同，而这又很容易与其它一些多态（Polymorphism）的概念混淆，导致产生了很多不在一条线上的讨论。这可能源于不少概念的模糊定义，从你的评论我大概才算了解了一些泛型的概念：

泛型的支持让编程语言能做安全的类型检查，只不过在实现类型检查的过程中，不同的编程语言有不同的方案，这个在你的评论有详细的介绍。于开发者使用的角度看，有些泛型实现是自动化的，无需开发者手动去做，有些做的比较稀烂的就需要开发者手动去做 type assets 或者一些不安全的强制类型转换与处理。但从那个 tweet thread 的讨论看，就算编程语言有泛型的支持，不少开发者也会不自觉的手动去实现类型判断，从而失去了编译器或运行时的一些安全保护，这到底是语言设计的缺陷还是其它原因？从实现的角度看，那种语言的泛型是最佳的？

[lxdlam]

感谢 @lxdlam 的评论，虽然这篇文章错误百出，估计是我写过错误最多的一篇文章了，但能得到这样好的评论让我觉得这一切都很值得，这也是写作的意义，写的对帮助了别人，写的错提高了自己😂

从我遇到很多对类型及泛型的讨论看，这是一个非常复杂的概念，因为不同的编程语言实现方式不同，而这又很容易与其它一些多态（Polymorphism）的概念混淆，导致产生了很多不在一条线上的讨论。这可能源于不少概念的模糊定义，从你的评论我大概才算了解了一些泛型的概念：

泛型的支持让编程语言能做安全的类型检查，只不过在实现类型检查的过程中，不同的编程语言有不同的方案，这个在你的评论有详细的介绍。于开发者使用的角度看，有些泛型实现是自动化的，无需开发者手动去做，有些做的比较稀烂的就需要开发者手动去做 type assets 或者一些不安全的强制类型转换与处理。但从那个 tweet thread 的讨论看，就算编程语言有泛型的支持，不少开发者也会不自觉的手动去实现类型判断，从而失去了编译器或运行时的一些安全保护，这到底是语言设计的缺陷还是其它原因？从实现的角度看，那种语言的泛型是最佳的？

我两个问题分开回答。

1. 为什么很多语言有成熟的泛型机制，但是开发者还是可能手动来做这种事情呢？

   习惯、需求和语言设计问题。

   • 从习惯角度来说，根据学习到的风格、自己的思维方式等，很多人可能会有潜意识的偏好，使用其中某一种。
   • 从需求的角度来说，当我们只有两种类型，甚至只需要特判某种类型的时候，我也会优先选择 type assertion。
   • 从语言设计角度来说，历史包袱和社区习惯不得不提：C++ 的 if constexpr 是 C++17 才写入标准的，而在此之前使用 template pattern matching 做类型选择的诸多“奇技淫巧”（如 SFINAE）等已经深入人心、遍布社区了。同样，Go 为了实现 C void * 类似的基于 Top Type Cast 的类泛型机制引入了 interface{}，而 1.18 泛型的部分功能才开始进入预览状态。

   而反过来看，编译器也是程序。对于有能力的开发者，我们同样可以通过各种方式 hack 掉一些安全保护，或者也饱受这些神秘的编译错误的煎熬（Rust 的 GADT preview）。一段极其优秀的泛型代码，可能会因为累赘的 http api 而让整个系统毁于一旦。换句话说，泛型是锦上添花，而不是银弹，在泛型之外，我们还有更多其它的设计和抽象需要探讨。精进工具的最终目的，还是解决问题。

2. 从实现角度看，哪种语言的泛型是最佳的？

   没有最佳的泛型设计。或者，没有给定问题之前，没有最佳的泛型设计。

   这个问题其实十分有趣。对于拥有现代最强的类型系统的几门语言之一的 Haskell，部分类型的构造和检查工作同样发生在运行时，并不是总发生在编译期；而同样地，大家津津乐道 Java 的类型擦除，其实现代 JDK 就能做不少工作，只把必要的工作推迟到运行时了。

   语言如何实现泛型，最终看的还是语言设计的目的和解决的问题。现行的实现方案都有各自的缺点，很难说谁更好。不过，就我个人而言，我比较喜欢下面几个语言的泛型实现：

   • .NET family，比如 C#：对于 value type 和特定已知类型，.NET 使用 code generation 的方式生成泛型代码，除此之外的 reference type，都使用运行时的泛型实现。加上 .NET family 各种语言自己的出色互操作能力，.NET 其实在自己的语言生态里是非常易用的。（https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/generics/generics-in-the-run-time）
   • Haskell 和其他 typed 函数式语言：这些语言是研究类型系统的精华，他们会从根本上解释什么是类型系统，为何类型重要，而泛型作为其中的一个其实比较小的领域，这些语言同样能正确解释，无非就是一种能接受某种类型，产出新类型的构造类型而已（用 Haskell 的概念，就是 kind 为 * -> * type。）
   • C++：C++ 的 template 是这门语言中最魔法、最复杂、也是最出色的功能之一。某种意义上，模板就是一门出色的纯函数语言，前人在这里留下的无数优秀资料能让我们学到非常多的东西，进一步转移到其他领域。

---

最后还是感谢作者，这个话题其实我之前也打算写文章讨论一下，但是因为各种原因始终未能成文，这次探讨也是极其宝贵的机会，我也重新复习和梳理了一遍这里面的各种玄机与奥妙。希望未来还有机会能够在其他领域展开交流，未来的计算机还是需要科学的力量，不再是应用为王了。

[madawei2699]

感谢 @lxdlam 的评论，虽然这篇文章错误百出，估计是我写过错误最多的一篇文章了，但能得到这样好的评论让我觉得这一切都很值得，这也是写作的意义，写的对帮助了别人，写的错提高了自己😂

从我遇到很多对类型及泛型的讨论看，这是一个非常复杂的概念，因为不同的编程语言实现方式不同，而这又很容易与其它一些多态（Polymorphism）的概念混淆，导致产生了很多不在一条线上的讨论。这可能源于不少概念的模糊定义，从你的评论我大概才算了解了一些泛型的概念：

泛型的支持让编程语言能做安全的类型检查，只不过在实现类型检查的过程中，不同的编程语言有不同的方案，这个在你的评论有详细的介绍。于开发者使用的角度看，有些泛型实现是自动化的，无需开发者手动去做，有些做的比较稀烂的就需要开发者手动去做 type assets 或者一些不安全的强制类型转换与处理。但从那个 tweet thread 的讨论看，就算编程语言有泛型的支持，不少开发者也会不自觉的手动去实现类型判断，从而失去了编译器或运行时的一些安全保护，这到底是语言设计的缺陷还是其它原因？从实现的角度看，那种语言的泛型是最佳的？

我两个问题分开回答。

1. 为什么很多语言有成熟的泛型机制，但是开发者还是可能手动来做这种事情呢？

   习惯、需求和语言设计问题。

   • 从习惯角度来说，根据学习到的风格、自己的思维方式等，很多人可能会有潜意识的偏好，使用其中某一种。

   • 从需求的角度来说，当我们只有两种类型，甚至只需要特判某种类型的时候，我也会优先选择 type assertion。

   • 从语言设计角度来说，历史包袱和社区习惯不得不提：C++ 的 if constexpr 是 C++17 才写入标准的，而在此之前使用 template pattern matching 做类型选择的诸多“奇技淫巧”（如 SFINAE）等已经深入人心、遍布社区了。同样，Go 为了实现 C void * 类似的基于 Top Type Cast 的类泛型机制引入了 interface{}，而 1.18 泛型的部分功能才开始进入预览状态。

   而反过来看，编译器也是程序。对于有能力的开发者，我们同样可以通过各种方式 hack 掉一些安全保护，或者也饱受这些神秘的编译错误的煎熬（Rust 的 GADT preview）。一段极其优秀的泛型代码，可能会因为累赘的 http api 而让整个系统毁于一旦。换句话说，泛型是锦上添花，而不是银弹，在泛型之外，我们还有更多其它的设计和抽象需要探讨。精进工具的最终目的，还是解决问题。

2. 从实现角度看，哪种语言的泛型是最佳的？

   没有最佳的泛型设计。或者，没有给定问题之前，没有最佳的泛型设计。

   这个问题其实十分有趣。对于拥有现代最强的类型系统的几门语言之一的 Haskell，部分类型的构造和检查工作同样发生在运行时，并不是总发生在编译期；而同样地，大家津津乐道 Java 的类型擦除，其实现代 JDK 就能做不少工作，只把必要的工作推迟到运行时了。

   语言如何实现泛型，最终看的还是语言设计的目的和解决的问题。现行的实现方案都有各自的缺点，很难说谁更好。不过，就我个人而言，我比较喜欢下面几个语言的泛型实现：

   • .NET family，比如 C#：对于 value type 和特定已知类型，.NET 使用 code generation 的方式生成泛型代码，除此之外的 reference type，都使用运行时的泛型实现。加上 .NET family 各种语言自己的出色互操作能力，.NET 其实在自己的语言生态里是非常易用的。（https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/generics/generics-in-the-run-time）

   • Haskell 和其他 typed 函数式语言：这些语言是研究类型系统的精华，他们会从根本上解释什么是类型系统，为何类型重要，而泛型作为其中的一个其实比较小的领域，这些语言同样能正确解释，无非就是一种能接受某种类型，产出新类型的构造类型而已（用 Haskell 的概念，就是 kind 为 * -> * type。）

   • C++：C++ 的 template 是这门语言中最魔法、最复杂、也是最出色的功能之一。某种意义上，模板就是一门出色的纯函数语言，前人在这里留下的无数优秀资料能让我们学到非常多的东西，进一步转移到其他领域。

---

最后还是感谢作者，这个话题其实我之前也打算写文章讨论一下，但是因为各种原因始终未能成文，这次探讨也是极其宝贵的机会，我也重新复习和梳理了一遍这里面的各种玄机与奥妙。希望未来还有机会能够在其他领域展开交流，未来的计算机还是需要科学的力量，不再是应用为王了。

感谢解答🙏我在写之前没料到泛型竟然如此复杂，甚至资料也很少，可能都存在各种古老的函数式语言社区里（如Haskell），像其他一些PLT的概念如并发都很容易找到资料，这个领域看来比较小众。

之前在写的过程中发现.net的泛型实现挺不错，不过由于用.net很少，就没怎么写.net相关的实现。

如果评价一个最差的，Java应该榜上有名。还有人说Golang花了十年时间实现了如此拉垮的泛型，但我感觉Golang的实现并不算差，甚至做了不少优化，可能设计是一方面，使用体验也是一方面，Golang的使用体验从上面 tweet 那个帖子看是有些难用😅