多态与泛型

多态性使得单一代码能够统一地作用于多种类型，其主要形式包括参数多态（泛型）、特定多态（重载和类型类）以及子类型多态。

Definition

多态性是指单一函数、类型或操作可以应用于多种类型值的属性；参数多态通过类型参数（泛型）统一实现，而特定多态则分派到特定类型的实现。

Scope

本主题涵盖了多态的主要类型：通过泛型和System F实现的参数多态，通过重载和类型类实现的特定多态，以及包含（子类型）多态。它探讨了参数化及其产生的强大推理原则，以及泛型抽象如何被编译和约束。

Core questions

• 泛型如何在不牺牲类型安全的情况下实现重用？
• 什么是参数化，它能提供哪些免费的保证？
• 类型类如何系统化特定重载？
• 泛型定义是如何编译的，以及哪些约束可以绑定类型参数？

Key theories

参数化（抽象定理）

Reynolds的抽象定理表明，参数多态函数在不同类型之间表现一致，这一特性独立于具体类型实例化，约束了其可能的行为。

免费定理

Wadler指出，参数多态函数的类型本身就蕴含了关于其行为的免费定理，这是参数化的直接且实际的推论。

用于有原则重载的类型类

Wadler和Blott引入了类型类，为特定多态提供了一个连贯的类型理论基础，其中重载操作通过传递方法实现的隐式字典来解析。

Clinical relevance

泛型和多态性是现代语言中可重用库设计和集合框架的核心。类型类及其类似物（trait、concept、protocol）提供了有原则的、类型安全的重载，而参数化则支持正确性推理和编译器优化。

History

System F捕捉了参数多态性，由Girard和Reynolds在20世纪70年代早期独立发现。ML将带有推断的多态性付诸实践。Cardelli和Wegner在1985年的调查中对多态形式进行了分类，Reynolds在1983年形式化了参数化，Wadler和Blott在1989年的类型类塑造了Haskell中的重载并影响了其他语言中的trait和concept。

Debates

擦除与具体化泛型

语言实现者争论通过类型擦除编译泛型，这种方法简单但会丢失运行时类型信息；或者在运行时具体化类型参数，这使得内省成为可能，但会增加复杂性和代码大小。

Key figures

• John Reynolds
• Jean-Yves Girard
• Philip Wadler
• Luca Cardelli
• Robin Milner

Seminal works

• reynolds1983
• wadler1989free
• wadler1989
• cardelli1985

Frequently asked questions

参数多态和特定多态有什么区别？

参数多态对所有类型参数应用一个统一的实现（如泛型），而特定多态则选择一个特定类型的实现，如重载或类型类。

参数化给我们带来了什么？

参数化保证泛型函数对所有类型实例一视同仁，这使得关于其行为的“免费定理”可以仅从其类型签名推导出来。