java 参数多态性与 Ad-hoc 多态性

Parametric polymorphism vs Ad-hoc polymorphism

提问by Ilya Lakhin

I would like to understand the key difference between parametric polymorphism such as polymorphism of generic classes/functions in the Java/Scala/C++ languages and "ad-hoc" polymorphism in the Haskell type system. I'm familiar with the first kind of languages, but I have never worked with the Haskell.

我想了解参数多态性（例如 Java/Scala/C++ 语言中的泛型类/函数的多态性）与 Haskell 类型系统中的“临时”多态性之间的主要区别。我熟悉第一种语言，但我从未使用过 Haskell。

More precisely:

更确切地说：

1. How is type inference algorithm e.g. in Java different from the type inference in Haskell?
2. Please, give me an example of the situation where something can be written in Java/Scala but can not be written in Haskell(according to the modular features of these platforms too), and vice-versa.

1. Java 中的类型推断算法与 Haskell 中的类型推断有何不同？
2. 请举一个例子，说明可以用 Java/Scala 编写但不能用 Haskell 编写的内容（根据这些平台的模块化特性），反之亦然。

Thanks in advance.

提前致谢。

回答by Francois G

As per the TAPL, §23.2:

根据TAPL§23.2：

Parametric polymorphism (...), allows a single piece of code to be typed “generically,” using variables in place of actual types, and then instantiated with particular types as needed. Parametric definitions are uniform: all of their instances behave the same. (...)

Ad-hoc polymorphism, by contrast, allows a polymorphic value to exhibit different behaviors when “viewed” at different types. The most common example of ad-hoc polymorphism is overloading, which associates a single function symbol with many implementations; the compiler (or the runtime system, depending on whether overloading resolution is static or dynamic) chooses an appropriate implementation for each application of the function, based on the types of the arguments.

参数多态性 (...)，允许使用变量代替实际类型来“通用”输入一段代码，然后根据需要使用特定类型进行实例化。参数定义是统一的：它们的所有实例的行为都相同。(...)

相比之下，临时多态性允许多态值在以不同类型“查看”时表现出不同的行为。Ad-hoc 多态性的最常见示例是重载，它将单个函数符号与许多实现相关联；编译器（或运行时系统，取决于重载解析是静态的还是动态的）根据参数的类型为函数的每个应用程序选择合适的实现。

So, if you consider successive stages of history, non-generic official Java (a.k.a pre-J2SE 5.0, bef. sept. 2004) had ad-hoc polymorphism - so you could overload a method- but not parametric polymorphism, so you couldn't write a generic method. Afterwards you could do both, of course.

因此，如果您考虑历史的连续阶段，非通用官方 Java（又名前J2SE5.0，2004 年 9 月之前）具有临时多态性 - 因此您可以重载方法- 但不是参数多态性，因此您不能' t写一个泛型方法。之后你当然可以两者都做。

By comparison, since its very beginning in 1990, Haskell was parametrically polymorphic, meaning you could write:

相比之下，自1990 年一开始，Haskell 就具有参数多态性，这意味着您可以编写：

swap :: (A; B) -> (B; A)
swap (x; y) = (y; x)

where A and B are type variables can be instantiated to alltypes, without assumptions.

其中 A 和 B 是类型变量，可以实例化为所有类型，无需假设。

But there was no preexisting construct giving ad-hocpolymorphism, which intends to let you write functions that apply to several, but not alltypes. Type classes were implemented as a way of achieving this goal.

但是没有预先存在的构造提供临时多态性，它旨在让您编写适用于多种类型的函数，但不是所有类型。类型类被实现为实现这一目标的一种方式。

They let you describe a class(something akin to a Java interface), giving the type signatureof the functions you want implemented for your generic type. Then you can register some (and hopefully, several) instancesmatching this class. In the meantime, you can write a generic method such as :

它们让您描述一个类（类似于 Java 接口的东西），给出要为泛型类型实现的函数的类型签名。然后，您可以注册一些（希望有几个）与此类匹配的实例。同时，您可以编写一个通用方法，例如：

between :: (Ord a)  a -> a -> a -> Bool
between x y z = x ≤ y ^ y ≤ z

where the Ordis the class that defines the function (_ ≤ _). When used, (between "abc" "d" "ghi")is resolved staticallyto select the right instancefor strings (rather than e.g. integers) - exactly at the moment when (Java's) method overloading would.

其中Ord是定义函数的类(_ ≤ _)。在使用时，(between "abc" "d" "ghi")被静态解析选择正确的实例字符串（而不是如整数） -也就是在那一刻（Java的）方法重载会。

You can do something similar in Java with bounded wildcards. But the key difference between Haskell and Java on that front is that only Haskell can do dictionary passing automatically: in both languages, given two instances of Ord T, say b0and b1, you can build a function fthat takes those as arguments and produces the instance for the pair type (b0, b1), using, say, the lexicographic order. Say now that you are given (("hello", 2), ((3, "hi"), 5)). In Java you have to remember the instances for stringand int, and pass the correct instance (made of four applications of f!) in order to apply betweento that object. Haskell can apply compositionality, and figure out how to build the correct instance given just the ground instances and the fconstructor (this extends to other constructors, of course) .

您可以使用有界通配符在 Java 中执行类似操作。但是在这方面 Haskell 和 Java 之间的主要区别在于，只有 Haskell 可以自动进行字典传递：在两种语言中，给定两个实例Ord T，比如说b0和b1，您可以构建一个函数f，将它们作为参数并为该对生成实例type (b0, b1)，例如使用字典顺序。现在说你得到了(("hello", 2), ((3, "hi"), 5))。在 Java 中，您必须记住stringand的实例int，并传递正确的实例（由f!的四个应用程序组成）才能应用于between该对象。Haskell 可以应用组合性，并找出如何构建正确的实例，只给定地面实例和f构造函数（当然，这扩展到其他构造函数）。

---

---

Now, as far as type inferencegoes (and this should probably be a distinct question), for both languages it is incomplete, in the sense that you can always write an un-annotatedprogram for which the compiler won't be able to determine the type.

现在，就类型推断而言（这应该是一个不同的问题），对于这两种语言，它都是不完整的，从某种意义上说，您始终可以编写编译器无法确定的未注释程序方式。

1. for Haskell, this is because it has impredicative(a.k.a. first-class) polymorphism, for which type inference is undecidable. Note that on that point, Java is limited to first-order polymorphism (something on which Scala expands).

2. for Java, this is because it supports contravariant subtyping.

1. 对于 Haskell，这是因为它具有不可预测的（又名一流的）多态性，因此类型推断是不可判定的。请注意，在这一点上，Java 仅限于一阶多态（Scala 对此进行了扩展）。

2. 对于 Java，这是因为它支持逆变子类型。

But those languages mainly differ in the range of program statements to which type inference appliesin practice, and in the importance given to the correctnessof the type inference results.

但是这些语言的主要区别在于类型推断在实践中适用的程序语句的范围，以及对类型推断结果正确性的重视程度。

1. For Haskell, inference applies to all "non-highly polymorphic" terms, and make a serious effort to return sound results based on published extensions of a well-known algorithm:

   • At its core, Haskell's inference is based on Hindley-Milner, which gives you complete results as soon as when infering the type of an application, type variables(e.g. the Aand Bin the example above) can be only instantiated with non-polymorphictypes (I'm simplifying, but this is essentially the ML-style polymorphism you can find in e.g. Ocaml.).
   • a recent GHC will make sure that a type annotation may be required only for a let-binding or λ-abstraction that has a non-Damas-Milner type.
   • Haskell has tried to stay relatively close to this inferrable core across even its most hairy extensions (e.g. GADTs). At any rate, proposed extensions nearly always come in a paper with a proof of the correctnessof the extended type inference .

2. For Java, type inference applies in a much more limited fashionanyway :

   Prior to the release of Java 5, there was no type inference in Java. According to the Java language culture, the type of every variable, method, and dynamically allocated object must be explicitly declared by the programmer. When generics (classes and methods parameterized by type) were introduced in Java 5, the language retained this requirement for variables, methods, and allocations. But the introduction of polymorphic methods (parameterized by type) dictated that either (i) the programmer provide the method type arguments at every polymorphic method call site or (ii) the language support the inference of method type arguments. To avoid creating an additional clerical burden for programmers, the designers of Java 5 elected to perform type inference to determine the type arguments for polymorphic method calls. (source, emphasis mine)

   The inference algorithmis essentially that of GJ, but with a somewhatkludgyaddition of wildcards as an afterthought (Note that I am not up to date on the possible corrections made in J2SE 6.0, though). The large conceptual difference in approach is that Java's inference is local, in the sense that the inferred type of an expression depends only on constraints generated from the type system and on the types of its sub-expressions, but not on the context.

   Note that the party line regarding the incomplete & sometimes incorrect type inference is relatively laid back. As per the spec:

   Note also that type inference does not affect soundness in any way. If the types inferred are nonsensical, the invocation will yield a type error. The type inference algorithm should be viewed as a heuristic, designed to perfdorm well in practice. If it fails to infer the desired result, explicit type paramneters may be used instead.

1. 对于 Haskell，推理适用于所有“非高度多态性”术语，并认真努力返回基于知名算法的已发布扩展的合理结果：

   • 在其核心，Haskell 的推断是基于Hindley-Milner 的，它在推断应用程序的类型时立即为您提供完整的结果，类型变量（例如A和B在上面的示例中）只能使用非多态类型（我正在简化，但这本质上是您可以在例如 Ocaml 中找到的 ML 风格的多态性。）。
   • 最近的 GHC 将确保仅对具有非 Damas-Milner 类型的 let-binding 或 λ-abstraction 才需要类型注释。
   • Haskell 试图在其最毛茸茸的扩展（例如GADTs）中与这个可推断的核心保持相对接近。无论如何，提议的扩展几乎总是出现在一篇论文中，并证明了扩展类型推断的正确性。

2. 对于 Java，类型推断无论如何都适用于更有限的方式：

   在 Java 5 发布之前，Java 中没有类型推断。根据 Java 语言文化，每个变量、方法和动态分配的对象的类型必须由程序员显式声明。在 Java 5 中引入泛型（按类型参数化的类和方法）时，该语言保留了对变量、方法和分配的这一要求。但是多态方法（按类型参数化）的引入要求要么（i）程序员在每个多态方法调用站点提供方法类型参数，要么（ii）语言支持方法类型参数的推断。为了避免给程序员带来额外的文书负担，Java 5 的设计者选择执行类型推断来确定类型参数对于多态方法调用。（来源，强调我的）

   该推理算法基本上是GJ的，但有几分缺憾此外通配符作为一种事后（请注意，我不是最新的在J2SE 6.0所做的可能修正，虽然）。方法上的巨大概念差异在于 Java 的推理是 局部的，从某种意义上说，表达式的推断类型仅取决于从类型系统及其子表达式的类型生成的约束，而不取决于上下文。

   请注意，有关不完整且有时不正确的类型推断的派对路线相对宽松。根据规范：

   另请注意，类型推断不会以任何方式影响健全性。如果推断的类型是无意义的，则调用将产生类型错误。类型推断算法应被视为一种启发式算法，旨在在实践中表现良好。如果它无法推断出所需的结果，则可以使用显式类型参数代替。

回答by Rose Perrone

Parametric polymorphismmeans, we don't care about the type, we'll implement the function the same for any type. For example, in Haskell:

参数多态意味着，我们不关心类型，我们将为任何类型实现相同的功能。例如，在 Haskell 中：

length :: [a] -> Int
length [] = 0          
length (x:xs) = 1 + length xs

We don't care what the type of the elements of the list are, we just care how many there are.

我们不关心列表元素的类型是什么，我们只关心有多少。

Ad-hoc polymorphism (aka method overloading), however, means that we'll use a different implementation depending on the type of the parameter.

然而，临时多态性（又名方法重载）意味着我们将根据参数的类型使用不同的实现。

Here's an example in Haskell. Let's say we want to define a function called makeBreakfast.

这是 Haskell 中的一个示例。假设我们要定义一个名为 的函数makeBreakfast。

If the input parameter is Eggs, I want makeBreakfastto return a message on how to make eggs.

如果输入参数是Eggs，我想makeBreakfast返回一个关于如何制作鸡蛋的消息。

If the input parameter is Pancakes, I want makeBreakfastto return a message on how to make pancakes.

如果输入参数是Pancakes，我想makeBreakfast返回一个关于如何制作煎饼的消息。

We'll create a typeclass called BreakfastFoodthat implements the makeBreakfastfunction. The implementation of makeBreakfastwill be different depending on the type of the input to makeBreakfast.

我们将创建一个称为BreakfastFood实现该makeBreakfast函数的类型类。的实现makeBreakfast将因 的输入类型而异makeBreakfast。

class BreakfastFood food where
  makeBreakfast :: food -> String

instance BreakfastFood Eggs where
  makeBreakfast = "First crack 'em, then fry 'em"

instance BreakfastFood Toast where
  makeBreakfast = "Put bread in the toaster until brown"

According to John Mitchell's Concepts in Programming Languages,

根据 John Mitchell 的编程语言概念，

The key difference between parametric polymorphism and overloading (aka ad-hoc polymorphism) is that parameteric polymorphic functions use one algorithm to operate on arguments of many different types, whereas overloaded functions may use a different algorithm for each type of argument.

参数多态性和重载（又名即席多态性）之间的主要区别在于，参数多态函数使用一种算法对许多不同类型的参数进行操作，而重载函数可能对每种类型的参数使用不同的算法。

回答by Daniel Wagner

A complete discussion of what parametric polymorphism and ad-hoc polymorphism mean and to what extent they're available in Haskell and in Java is longish; however, your concrete questions can be tackled much more simply:

关于参数多态性和临时多态性的含义以及它们在 Haskell 和 Java 中的可用程度的完整讨论是冗长的；但是，您的具体问题可以更简单地解决：

How algorithm of type inference e.g. in Java difference from the type inference in Haskell?

Java 中的类型推断算法与 Haskell 中的类型推断有何不同？

As far as I know, Java does not do type inference. So the difference is that Haskell does it.

据我所知，Java 不进行类型推断。所以区别在于 Haskell 做到了。

Please, give me an example of the situation where something can be written in Java/Scala but can not be written in Haskell(according to the modular features of these platforms too), and vice-versa.

请举一个例子，说明可以用 Java/Scala 编写但不能用 Haskell 编写的内容（根据这些平台的模块化特性），反之亦然。

One very simple example of something Haskell can do that Java can't is to define maxBound :: Bounded a => a. I don't know enough Java to point out something it can do that Haskell can't.

Haskell 可以做而 Java 不能做的事情的一个非常简单的例子是定义maxBound :: Bounded a => a. 我对 Java 的了解不够多，无法指出它可以做而 Haskell 不能做的事情。