泛型爪哇（Generic Java）

核心提示：java 可能即将有一场大变革Dr. Dobb′s Journal February 2000GJ : A Generic Java. Java may be in for some changesBy Philip WadlerPhilip is a researcher at Bell Labs, LUCent T

　　java 可能即将有一场大变革

--------------------------------------------------------------------------------

Dr. Dobb′s Journal February 2000

GJ : A Generic Java. Java may be in for some changes

By Philip Wadler
Philip is a researcher at Bell Labs, LUCent Technologies. He can be reached at wadler@research.bell-labs.com.

--------------------------------------------------------------------------------

Java 语言可能即将要有一番大变革。虽然 Java 系统不断地以猛烈的速度增加并改变各式各样的程式库，但是 Java 语言自从数年前导入 inner classes 之後便几乎冻结了起来。现在，Sun 加入了 Java Community PRocess（译注：一个有正式组织的开放计划，用来开发并修订 Java 技术规格），考虑为 Java 语言加上泛型（generics）特性。

下面就是「泛型」能够解决的问题。假设你希望运用 lists，有些人希望拥有 list of bytes，有些人希望拥有 list of strings，还有一些人希望拥有 lists of lists of strings。在 Java 语言中，这很简单。你可以使用相同的 class 表达上述三个你所想要的东西，它们都拥有型别为 class Object 的元素，见表一(a)。

表一/ lists的使用 (a) Java (b) Generic Java

List 的型态 使用的 Class
(a)
list of bytes
list of strings
list of list of strings
-
List
List
List

(b)
list of bytes
list of strings
list of list of strings
-
List<Byte>
List<String>
List<List<String>>

为了保持语言的简单，你被迫自己动手做一些事情：是的，你必须记住一个事实，那就是你所拥有的是个 list of bytes（或 strings 或 lists），而後当你从中萃取出一个元素时，在更进一步处理之前，你必须将它转型，从 class Object 转为 class Byte（或 String 或 List）。Java2 的 collection class framework 就是以此方式对待各种容器类别（其中涵盖 lists）。

爱因斯坦说过，每件事情都应该尽量简化，但不要过度简介（everything should be as simple as possible, but no simpler）。可能有人会说以上太过简化了。假如我们以泛型型别（generic types）来扩充 Java 语言，就有可能以一种更直接的方法来表现 lists 的相关资讯；见表一(b)。於是，编译器可以追踪记录你是否拥有一个 list of bytes（或 strings 或 lists），而你也就不再需要将型别转回 class Byte（或 String 或 List<String>）。某种情况下，这很类似 Ada 语言的 generics 或 C++ 语言的 templates。它也很类似所谓的 functional languages（如 ML 和 Haskell）中的 parametric polymorphism。

Sun 的工作受到一些前人努力的影响，我指的是令人测目的 Generic Java (GJ)。GJ 最初由三组人马设计，分别是 Sun 的 Gilad Bracha 和 David Stoutamire，瑞士联邦科技学会的 Martin Odersky，和我本人。Bracha 如今带领 Sun 的一个部门，正在为Java加入泛型特性而冲锋陷阵。Odersky 和我则是在相关的专家委员会里头。在这篇文章中，我要以一种前瞻的态度描述 GJ，看看 Sun 的努力可能浮现出什麽成果。GJ 的进一步细节，可自以下网站获得：http://www.cs.bell-labs.com/~wadler/gj/。GJ 编译器由 Odersky 撰写，目前可由上述站点下载。这个 GJ 编译器同时也是 Sun 目前服役的 Java 编译器的基础 ─ 虽然後者尚未支援泛型。GJ 和 GJ 编译器并不是 Sun 的产品。

GJ 的几个要害特性包括：

相容於 Java。GJ 是 Java 的超集。每一个 Java 程式在GJ 中都仍然合法而且有着与过去相同的意义。
相容於 Java 虚拟机器（JVM）。GJ 被编译为 JVM 码。JVM 不需任何改变。因此 Java 所能执行之处，GJ 都能执行，包括在你的浏览器上。
相容於既有的程式库。既有的程式库都能够和 GJ 共同运作，即使是编译後的 class 二进位型式。有时候我们也可以将一个旧有的程式库翻新，加上新的型别，而不需更动其源代码。例如 Java collection class library 就可以被这样翻新，加上泛型特性。
高效（Efficiency）。与泛型型别（generic types）相关的资讯，只有在编译期（而非执行期）才被维护着。这意味编译後的 GJ 代码几乎完全和相同目的、相同效率的 Java 代码一致。
GJ 编译器的工作是把 GJ 代码翻译回一般的 Java 代码。这个翻译程序仅仅只是消除型别叁数（type parameters）并加上转型动作。例如它把 GJ class List<Byte> 翻译回 Java class List，并加上转型，在必要的地方从 Object 转为 Byte。获得的结果就像你在不支援泛型的情况下所写的 Java 代码一样。这就是为什麽我们能够轻易为 GJ 和既存的 Java 程式库建立起介面的原因，这也是为什麽 GJ 能够和 Java 拥有相同效率的原因。此外，GJ 带有所谓的转型铁律，保证任何一个被编译器加入的转型动作都不会导致错误。在功效上，型别系统是一个简单的逻辑，足以让编译器证实某个转型动作是否安全。在这些保证之下，由於 GJ 将程式码翻译为 JVM byte codes，所以 Java 平台原本拥有的安全性（safety）和防护性（security）也都获得了保留。

GJ 如何运作
让我们看两个例子，实际了解 GJ 的运作方式。第一个例子涵盖 GJ 的最基本性质，用以建立并验证 generic lists。第二个例子涵盖一些比较进阶的性质，为你展示如何撰写一个 generic method，以便找出某个 list 所含的最大元素。无论哪一个例子，我都会先以 Java 代码完成，然後再示范如何以 GJ 重写。我也会说明如何将传统的 Java 程式库翻新，使它相容於 GJ，最後并对 C++ templates 和 GJ generics 做一个比较。

例一显示 list interface 和 iterator interface（两者都是根据 Java collections library 而做的高度简化），以及一个将 list interface实作出来的 linked list class，和一个测试用的 class。这里的 list interface 提供了一个 add method，用来为 list 添加新元素，还有一个 iterator method，用来传回 list 的一个迭代器。至於 iterator interface 则是提供了一个 hasNext method，用来决定迭代是否已经完成，以及一个 next method，用来取得下一个元素，并将迭代器推进一个位置。linked list class 实作出 list interface，但我略而不述其中细节。add method 接受一个物件，next method 则是传回一个物件。由於每一个 class 都是Object 的 subclass，所以你可以以 Byte, String, List 自己，或任何其他 class 元素来组成 lists。

例一：List interface 和 iterator interface
interface List {
public void add (Object x);
public Iterator iterator ();
}
interface Iterator {
public Object next ();
public boolean hasNext ();
}
class LinkedList implements List { ... }
class Test {
public static void main (String[] args) {
// byte list
List xs = new LinkedList();
xs.add(new Byte(0));
xs.add(new Byte(1));
Byte x = (Byte)xs.iterator().next();
// string list
List ys = new LinkedList();
ys.add("zero");
ys.add("one");
String y = (String)ys.iterator().next();
// string list list
List zss = new LinkedList();
zss.add(ys);
String z = (String)((List)zss.iterator().next()).iterator().next();
// string list treated as byte list
Byte w = (Byte)ys.iterator().next(); // run-time exception
}
}

测试用的那个 class 建造出一些 lists，然後从中萃取元素。使用者必须记住储存於 list 之中的元素是什麽型别，然後在萃取元素的同时，将它转为适当的型别。最後一次萃取行动需要两个转型动作。假如使用者出人意表地打算从一个 list of strings 中萃取出一个 byte，便会在执行时期发生异常（exception）。

例二所显示的是以 GJ 完成的 lists, iterators, linked lists，以及一个测试用的 class。现在，每个 interfaces 和 class 都有一个型别叁数 A，写在角括号内，用来表述元素的型别。先前Object 所出现的每一个地方，现在都以 A 取代。先前 List, Iterator, 或 LinkedList 所出现的每一个地方，现在都分别以 List<A>, Iterator<A>, 或 LinkedList<A> 取代。再也不需要仰赖使用者的记忆了，这些叁数便足以说明每一个 list 的元素型别，而且再也不需要转型动作了。从一个 list of lists 身上萃取元素，现在变得比较明白。假如企图从一个 list of strings 身上萃取 byte，编译器会指出错误。

例二：Lists, iterators, linked lists, 以及测试用的 class
rewritten in GJ
interface List<A> {
public void add(A x);
public Iterator<A> iterator();
}
interface Iterator<A> {
public A next();
public boolean hasNext();
}
class LinkedList<A> implements List<A> { ... }
class Test {
public static void main (String[] args) {
// byte list
List<Byte> xs = new LinkedList<Byte>();
xs.add(new Byte(0));
xs.add(new Byte(1));
Byte x = xs.iterator().next();
// string list
List<String> ys = new LinkedList<String>();
ys.add("zero");
ys.add("one");
String y = ys.iterator().next();
// string list list
List<List<String>> zss = new LinkedList<List<String>>();
zss.add(ys);
String z = zss.iterator().next().iterator().next();
// string list treated as byte list
Byte w = ys.iterator().next(); // compile-time error
}
}

在 Java 语言中，lists 是异质性的（heterogenous）-- 它们可以拥有任何型别的元素，没有任何办法可以强迫它们拥有相同型别。然而在 GJ 中，lists 却是同质性的（homogenous） -- 它们必须拥有相同型别的元素，编译器会厉行这一点。假如你真的需要一个 list，拥有不同型别的元素，你应该使用 List<Object>。

为了将 GJ 翻译为 Java 语言，必须为每一个型别做一种非凡的擦拭（erasure）动作。一个被叁数化的型别，经过擦拭後，应该除去叁数（於是 List<A> 被擦拭为 List），一个未被叁数化的型别，经过擦拭後应该获得型别本身（於是 Byte 被擦拭为 Byte），而一个型别叁数经过擦拭後，结果为 Object（於是 A 被擦拭後变成 Object）。假如某个 method call 的传回型别是个型别叁数，编译器会为它安插适当的转型动作。将表二的 lists 的 GJ 代码转译为 Java 代码，会得到表一（引起错误的那行除外）。因此，一个「根据 GJ 代码完成的新程式」，可以和一个「根据 Java 代码完成的旧程式库」放在一起编译。

GJ 以角括号标示型别叁数，原因是 C++ 使用者对它们比较熟悉，而且其他型式的括号可能会带来混淆。是的，假如使用小括号，型别叁数和数值叁数就很难区分。假如使用中括号，型别叁数和阵列尺度（array dimension）就很难区分。假如使用大括号，型别叁数和类别主体（class body）就很难区分。

或许像 LinkedList<LinkedList<String>> 这样复杂的形式会给文句解析器（parser）带来一些难题。因为 >> 被视为单一语汇（ >>> 也一样）。C++ 要求使用者必须在两个右角括号之间加上额外空白，以回避这个问题。GJ 使用者不必担心同样的问题，这个问题已经透过一个稍微有点复杂的文法解决掉了。

Bridges, Generic Methods, Bounds
下一个例子示范进阶的泛型特性，包括 bridges，generic methods，以及 bounds。我打算写一段 Java 代码，搜寻某个 list 所含的最大元素，然後再示范如何以 GJ 重写一遍。

在 Java 之中，假如要让物件得以一较长短（大小），应该令它们实作出 Comparable interface。喔，是的，每一个基本型别（例如 byte 或 boolean）都有一个相应的物件型别（例如 Byte 或 Boolean）。

例三显示了 Comparable interface 的宣告，以及一个实作出该介面的 Byte class。两者都简化自 Java 程式库。compareTo method 接受一个叁数物件并传回一个整数。假如受者本身小於、等於、或大於叁数物件，传回的就分别是负值、零值、或正值。Byte class 定义了两个 methods，一个是 compareTo(Byte)，此式重载（overloads）了 compareTo，另一个是 compareTo(Object)，此式改写（overrides）了Comparable interface 中相应的 method。第一个 method 仅仅只是将两个 bytes 相减，以此做为它们的比较方式。第二个 method 将物件转型为 byte，然後呼叫第一式。要知道，假如第一式收到的是个物件而不是个 byte，会造成执行时期错误。因此第二个 method 的存在是有必要的，它会造成第一式的被呼叫一定发生於型别完全吻合的时候。我们把第二个 method 称为 "bridge"，因为它将第一个 method（专属於 bytes）和 interface method（对所有物件都适用）连接了起来。

例三还展示了一个 Lists class 和一个测试用的 class。前者带有一个 static method，用来找出 list 中的最大元素。max method 接受一个非空的 list，其内都是可比较的元素，传回的则是所有元素中最大的一个。Test class 示范了两个呼叫动作。和先前情况一样，使用者必须记住他使用的是什麽型别，并做适当转型。Booleans 并未实作出 comparable interface，所以假如企图找出一个「以 Booleans 为元素」的 list 中的最大值，执行时期会发生异常（exception）。

例三：以下是 Comparable interface 的宣告，以及实作出该介面的 Byte class 的宣告。
interface Comparable {
public int compareTo (Object that);
}
class Byte implements Comparable {
private byte value;
public Byte (byte value) { this.value = value; }
public byte byteValue () { return value; }
public int compareTo (Byte that) {
return this.value - that.value;
}
// bridge
public int compareTo (Object that) {
return this.compareTo((Byte)that);
}
}
class Lists {
public static Comparable max (List xs) {
Iterator xi = xs.iterator();
Comparable w = (Comparable)xi.next();
while (xi.hasNext()) {
Comparable x = (Comparable)xi.next();
if (w.compareTo(x) < 0) w = x;
}
return w;
}
}
class Test {
public static void main (String[] args) {
// byte list
List xs = new LinkedList();
xs.add(new Byte(0));
xs.add(new Byte(1));
Byte x = (Byte)Lists.max(xs);
// boolean list
List ys = new LinkedList();
ys.add(new Boolean(false));
ys.add(new Boolean(true));
Boolean y = (Boolean)Lists.max(ys); // run-time exception
}
}

例四是以 GJ 重新写过的代码。Comparable interface 现在接受一个型别叁数 A， 表示将被拿来比较的型别。举个例子，class Byte 实作出 Comparable<Byte> interface，那就表示一个 byte 可以被拿来和另一个 byte 比较。Comparable interface 需要一个 method，型式为 compareTo(A)，所以你可以预期，它被实作於某个 class 之内时，一定拥有诸如 compareTo(Byte) 这样的标记形式（signature）。使用者不再需要撰写 bridge method，因为它已经自动由 GJ 编译器完成了。

例四：Code rewritten in GJ
interface Comparable<A> {
public int compareTo (A that);
}
class Byte implements Comparable<Byte> {
private byte value;
public Byte (byte value) { this.value = value; }
public byte byteValue () { return value; }
public int compareTo (Byte that) {
return this.value - that.value;
}
}
class Lists {
public static <A implements Comparable<A>> A max (List<A> xs) {
Iterator<A> xi = xs.iterator();
A w = xi.next();
while (xi.hasNext()) {
A x = xi.next();
if (w.compareTo(x) < 0) w = x;
}
return w;
}
}
class Test {
public static void main (String[] args) {
// byte collection
LinkedList<Byte> xs = new LinkedList<Byte>();
xs.add(new Byte(0));
xs.add(new Byte(1));
Byte x = Collections.max(xs);
// boolean collection
LinkedList<Boolean> ys = new LinkedList<Boolean>();
ys.add(new Boolean(false));
ys.add(new Boolean(true));
Boolean y = Collections.max(ys); // compile-time error
}
}
// 译注：这里改用Collections.max()，而非前例的Lists.max()。
// 两者实作手法几乎完全相同，前者可见 srcjavautilcollections.java
max method 的标记式（signature）说明了 GJ 的两个有趣性质 -- generic methods 和 bounds。下面是 max 的标记全貌：

public static <A implements Comparable<A>> A max (List<A> xs)

这个长长的句子告诉我们， max method 接受一个 list，其内的元素型别都是 A，传回一个元素，型别亦为 A。最前面的角括号内宣告了型别叁数 A，并指出这个 method 可以被任意型别 A 具现化（instantiated），只要 A 实作出 Comparable<A> 介面。一个 method 假如拥有自己的型别叁数，我们称它为一个 "generic method"，而一个型别叁数假如必须实作出某个已知介面（或者必须是某个已知 class 的 subclass），我们称之为 "bounded"（被限制）。

Test class 示范了两个实际呼叫动作。在第一个呼叫动作中，编译器自动推导出 max method 标记式中的型别叁数 A 必须被具现化为 Byte，并且检查 class Byte 确实实作了 bound Comparable<Byte>。第二次呼叫推导出来的型别叁数是 Boolean，但它并未实作出 bound Comparable<Boolean>。也因此，Java 执行期原本会发出异常（exception）之处，GJ 在编译期就把它们指出来了。

一般而言，导入一个 bound 的方式是，在型别叁数之後写上 "implements" 然後再加上一个 interface 名称，或者是在型别叁数之後写上 "extends" 然後再加上一个 class 名称。不论是在 class head 或是 generic method 标记式中，凡型别叁数可以出现之处，bounds 都可以出现。bounding interface 或 class 本身可能又被叁数化，甚至可能形成递回（recursive），例如上述例子中的 bound Comparable<A> 就内含了 bounded 型别叁数 A。

现在，擦拭（erasure）的定义需要再扩充：一个型别变数经过擦拭，相当於其 bound 的擦拭结果（这麽一来 max method 中的 A 便被擦拭为 Comparable）。一如先前所说，转译会导致适当的转型，也会带来必要的 bridge methods。和先前所说一样，例四的 GJ 代码经过转译之後，会导致例三的 Java 代码（犯错的那行除外）。

如你所见，GJ 代码被编译为 Java 之後，其结果就像你在无泛型性质的情况下所写的代码。所以，只要使用GJ编译器的一个非凡翻新模式（retrofitting mode），你总是可以为旧式的传统代码加上型别资讯，甚至即使你手上只有二进位的 class files。

举个例子，假设你有一个 class file，其内有先前所描述的 Java 版的 LinkedList class，但你希望以 GJ 形式来使用它。例五显示必要的翻新档。

例五：翻新档（retrofitting file）
class LinkedList<A> implements Collection<A> {
public LinkedList ();
public void add (A elt);
public Iterator<A> iterator ();
}

为了支援独立编译，GJ 编译器将额外的型别标记（type-signature）储存於 JVM class files 中。class file 档案格式答应如此的扩充，并於执行时期被 JVM 忽略。翻新器（retrofitter）会取出原有的 Java class file，检查其型别标记是否如同「GJ 标记被擦拭後」的结果，然後产生一个带有 GJ 标记的崭新 class file。

Java2 的整个 collection class library已经以此方式翻新。程式库中的每一个 public interface, class, 和 method 都有一个适当对应的 GJ 型别，绝无漏网之鱼。由於翻新後的 class files 与原先不同之处只在於新增加的那些 GJ 型别标记（它会於执行时期被 JVM 忽略），所以你可以将其结果在一个与 Java 2 相容的浏览器中执行，不需重新载入 collection class library。

大部份情况下，你可能最终会想要将原始程式库以「叁数化型别」重新写过（rewriting）。翻修（retrofitting）的优点则是，你可以按自己兴奋或方便的时程来进行，因为，是的，在新的代码可以运用泛型型别之前，你并不需要重新撰写所有的旧式代码。

结论
Java 程式员经常使用一种泛型手法（generic idiom）：让某个资料结构的元素型别为 Object。这种作法很简易，但你被迫追踪元素的实际型别，并需要自行加上额外的转型动作。相反的，为 Java 语言加上泛型型别（generic types）虽然会增加一点复杂度，但「追踪元素型别」和「加上转型动作」的责任，却落在编译器而非你的身上。

更非凡的一点是，泛型型别还具有一个优点，可以把执行时期的异常转化为编译时期的错误，即早发现，即早治疗。下面是 Bill Joy，Java 语言规格的作者之一，对泛型爪哇的看法（发表於 Java One Conference，June 1999）：

我们继续致力於在软体开发阶段找出各种错误，并放置一个叁数化型别系统於 Java 语言之中。对我而言，这麽做的价值倒不在於使这个语言更具表达能力，而是得以摆脱各种该做而未做（或做错）的转型，使出货之後才发现的错误得以大量减少。

出货之後修正一个臭虫，其成本大约要比出货前提升 10,000 倍。而且对程序员而言，那是很令人厌烦的一个过程。假如臭虫在编译时期就被抓出来，你可以从容把握状况，因为整个代码概念完全在你心中。假如臭虫报告来自客户，就需要烦人的臭虫追踪，最终会回到你的桌上，或某人的桌上，而原先的设计思绪早就飞到九霄云外去了。你得在你的脑袋瓜中重新载入你的快取记忆体（"cache" memory）。所以，尽早抓出臭虫，是非常好而且非常有价值的观念。

假如你看到有哪个 Java 程式使用 class Object，通常那就是一个记号，表示那个程式可以因为使用泛型型别而受益。你可以说这个 class 的名称取得真好 -- 当你看到它，你就应该 "object" 并以泛型型别取而代之。（译注：美式幽默，"object" 作动词解，有「反对」之意）

GJ 是一种用来为 Java 加上泛型特性的语言。它的出现告诉我们，我们有可能以一个十分简单而有用的作法，为 Java 加上泛型能力。已有数个大型程式以 GJ 实作出来，包括 GJ 编译器本身。一如稍早所说，其他语言也以其他方式支援泛型，非凡是 C++ 以 templates 支援泛型。虽然两者有着类似的语法和类似的用途，C++ templates 和 GJ generics 的实作方式却完全不同。

C++ templates 是以膨胀法（eXPansion）实作出来，编译器针对被运用的每一个型别，为泛型代码产生一份对应副本。例如在我们的第一个例子中，会产生三份副本，一个用於 bytes, 一个用於 strings，一个用於 lists of strings。这往往导致程式码的体积膨胀。犹有进者，由於 template 可能被定义於一个档案之中而被另一个档案使用，膨胀法所引起的错误往往无法被侦测出来，直到联结时期才会记录，而且往往难以回溯。我的同事 Brian Kernighan 和 Rob Pike 曾经写过一个小型的 C++ 程式，其 templates 产生出一个名称长达 1594 字元的变数（见 The Practice of Programming, Addison-Wesley, 1999.）

GJ generics 就不一样，它以拭去法（erasure）实作出来，所以没有程式码膨胀的问题。型别变数必须满足的所有条件，都已经在其 bounds 中清楚指定了，因此所有错误都会在编译期就被侦测出来，不会等到联结期。这真是好呀，尤其因为 Java 有所谓动态联结，联结期和执行期是一致的。但从另一个角度说，为了让工作顺利，型别叁数必须总是一个指引型别（例如Byte）而不是一个基本型别（例如 byte）。因此，除非 Java 编译技术改善，否则 GJ generics 的效率比不上 C++ templates。但或许这没什麽大不了，因为就算编译器技术改善了，Java 的效率无论如何还是不可能高过 C++。

虽然 GJ 的目标明显是为了实用，但它也有理论依据。对 GJ 的设计有贡献的观念包括 Church 的 lambda calculus（1930s），Curry 和 Hindley 的 type inference system（型别推论系统，1950s），以及 Girard 和 Reynold 的 polymorphic calculus（1970s）。GJ 程式员并不需要了解这些观念，但是这些观念帮助 GJ 设计者做出更好的产品。上一个世纪的数学会对下一个千僖年的程式语言设计显现出影响。