参数多态

参数多态程序设计语言类型论中是指声明与定义函数、复合类型、变量时不指定其具体的类型,而把这部分类型作为参数使用,使得该定义对各种具体类型都适用。参数化多态使得语言更具表达力,同时保持了完全的静态类型安全[1] 这被称为泛型函数、泛型数据类型、泛型变量,形成了泛型编程的基础。

参数多态名字来源于其发明人克里斯托弗·斯特雷奇[2]特设多态(ad hoc polymorphism)相对。特设多态是指一个多态函数有多个不同的实现,依赖于其实参而调用相应版本的函数。因此,特设多态仅支持有限数量的不同类型。

历史

克里斯托弗·斯特雷奇于1967年8月在哥本哈根的计算机程序设计暑期学校发表了著名论文Fundamental Concepts in Programming Languages中首次提出了参数多态特设多态左值右值等概念。[2]1975年ML语言首次实现了参数多态。[3]

现在,Standard ML, OCaml, F#, Ada, Haskell, Mercury, Visual Prolog, Scala, Julia等。Java, C#, Visual Basic .NET and Delphi引入了泛型作为参数多态。

C++模板特化这样的类型多态(type polymorphism)表面上类似于参数多态并同时引入了特设多态。

直谓与非直谓

直谓多态

直谓参数多态(predicative parametric polymorphism)是指,类型包含类型变量不能用在被实例化为一个多态类形。直谓类型理论包括直觉类型论NuPRL

非直谓多态

非直谓多态(Impredicative polymorphism),也称“头等多态”(first-class polymorphism)是最强有力的参数多态形式。[4]非直谓是指自引用(self-referential),类型论中允许实例化类型的变量为任何类型,包括参数化类型,如自身。一个例子是系统F在类型变量X下,类型,其中X可以为T自身。

类型论中,最常被研究的非直谓有类型λ演算是基于λ立方体,特别是系统F[1]

限定的参数多态

1985年卢克·卡德利彼得·瓦格纳提出类型参数允许限定(bounds)的益处。[5]限定量化(bounded quantification)也称作“限定多态”(bounded polymorphism)或“约束泛型”(constrained genericity)。许多操作要求数据类型的某些知识,但仍可以把类型参数化。例如,判断一项是否出现在列表中,需要比较项的相等。在Standard ML中,类型参数’’a被限定有相等判断可用,因此具有如下类型的函数:’’a × ’’a list → bool且’’a可译为任何定义了任何定义了相等判断的类形。在Haskell中,限定是通过要求类型属于某个type class,因此同样的函数在Haskell中可写为:。大多数支持参数多态的面向对象语言可以把参数限定为给定类型的子类型。(见子类型多态)

下述Java例子中,类型参数T被限于I的子类:

class I {
}

class A <T extends I> {
    public T id(T x) {
        return x;
    }
}

参见

  • 多态递归
  • 类型类别

注释

  1. Pierce 2002.
  2. Strachey 1967.
  3. Milner, R., Morris, L., Newey, M. "A Logic for Computable Functions with reflexive and polymorphic types", Proc. Conference on Proving and Improving Programs, Arc-et-Senans (1975)
  4. Pierce 2002, p. 340.
  5. Cardelli & Wegner 1985.

参考文献

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.