Generics v.s. Subtyping.

Generics v.s. Subtyping

关于 generics (parametric polymorphism) 与 subtyping polymorphism 的比较也是一个很重要的话题。

What are generics good for?

先来看看 generics (parametric polymorphism) 的两种最常见的应用。

  1. higher-order function 的复合。

    1
    val compose : ('b -> 'c) * ('a -> 'b) -> ('a -> 'c)

  2. functions that operate over collections/containers where different collections/containers can hold values of different types.

    1
    2
    3
    val length : 'a list -> int
    val map : ('a -> 'b) * 'a list -> 'b list
    val swap : ('a * 'b) -> ('b * 'a)

generic types 放松了对函数参数类型的限制，从而提高了代码的复用性。举例来说，如果没有 generics，那么对于每一对不同类型的 pair 都需要编写一个 swap 函数。

Subtyping is bad substitute for generics

在不支持 generics 的语言中，程序员有时会用 subtyping 实现 generics，但是：

  • Somewhat lame generics.
  • Doing so is like painting with a hammer instead of a paintbrush.
1
2
3
4
5
6
7
8
9
class LamePair {
    Object x;
    Object y;
    LamePair(Object _x, Object _y) { x=_x; y=_y; }
    LamePair swap() { return new LamePair(y,x); }
    ...
}

String s = (String)(new LamePair("hi", 4).y); // error caught only at run-time

这是用 subtyping 实现 generics 的一个例子：由于 Object 类型是所有类型的 supertype，任何类型的数据都能传入 LamePair 的域中。问题出在从 LamePair 中提取数据：我们只能获得一个 Object 类型的数据，因此必须使用强制类型转换 downcast 来将其转换为“原本”的类型。

downcast 将对被转换的数据类型执行 run-time checks，因此上述程序中的类型错误只有在运行时才能被侦测到；这一方面增加了动态检查的时空成本，一方面潜在降低了程序的安全性。

When you use Object and downcasts, you are essentially taking a dynamic typing approach: any object could be stored in an Object field, so it is up to programmers, without help from the type system, to keep straight what kind of data is where.

What is subtyping good for?

subtyping 的优势区间在于 allowing code to be reused with data that has extra information.

1
2
3
fun distToOrigin {x=x, y=y} =
    Math.sqrt(x*x + y*y)
val five = distToOrigin {x=3.0, y=4.0, color="red"}

该代码在不支持 subtyping 的语言如 ML 中将不会 type check。而在支持 subtyping 的语言中，distToOrigin 函数既能作用于 Point 类的对象，又能作用于 ColorPoint 类的对象：其中 ColorPoint is data that has extra information for Point.

Bounded Polymorphism

既然 generics 与 subtyping 都有着各自的优势区间，许多 statically typed 语言 (例如 Java 与 C#) 选择同时实现这 generics 与 subtyping。同时拥有这两种 polymorphism 机制带来了：

  • Some complications. (e.g. static overloading & subtyping are more difficult to define)
  • Merits brought by generics and subtyping separately.
  • More code reuse and expressiveness with the combination of the two ideas.

generics 与 subtyping 的结合带来了 bounded polymorphism, 具体体现为 bounded generic types。

Bounded generic types allow us to say, for all types 'a that are subtype of T.

  • (generics) We use 'a multiple times to indicate where two things must have the same type.
  • (subtyping) We can treat 'a as a subtype of T, accessing whatever fields and methods we know a T has.

见下例，Point 类中定义了 distance 方法。

1
2
3
4
5
class Pt {
    double x, y;
    double distance(Pt pt) { return Math.sqrt((x-pt.x)*(x-pt.x)+(y-pt.y)*(y-pt.y)); }
    Pt(double _x, double _y) { x = _x; y = _y; }
}

接下来是一个静态函数，输入一个 point 类 list 与一个圆，返回 list 中所有在该圆内的 point。

1
2
3
4
5
6
7
static List<Pt> inCircle(List<Pt> pts, Pt center, double radius) {
    List<Pt> result = new ArrayList<Pt>();
    for (Pt pt : pts)
        if (pt.distance(center) <= radious)
            result.add(pt)
    return result;
}

对于一个 ColorPt 类型的 list，我们能否将其传入 inCircle 方法实现代码的复用？该问题我们已经讨论过。

  • 一方面，list 中的各个 entry 是 mutable 的，这意味着 depth subtyping 不成立，List<ColorPt> 并非 List<Pt> 的 subtype。
  • 另一方面，即使 List<ColorPt> 传入了 inCircle 方法，其返回的 list 类型是 List<Pt> 而不是 List<ColorPt>，我们必须用到丑陋的 downcast。

好消息是，Java 的 bounded polymorphism 使得我们能够结合 generics 与 subtyping，实现该功能：

1
2
3
4
5
6
7
static <T extends Pt> List<T> inCircle(List<T> pts, Pt center, double radius) {
    List<T> result = new ArrayList<T>();
    for (T pt : pts)
        if (pt.distance(center) <= radius)
            result.add(pt);
    return result;
}

利用 generics，我们将 T 声明为一个 generic type；利用 subtyping，我们规定该 generic type T 必须是 Pt 的 subtype。当传入 List<ColorPt> 时，T 将被指定为 ColorPt，且 ColorPt 的确是 Pt 的 subtype。

这样，我们不仅能够传入 List<ColorPt> 类型的 list，该方法也将返回相同类型的 list 而无需用到 downcast。

Reference

Supplementry notes:

My notes in CnBlogs.

Inheritance 与 subtyping 到底有什么区别 -知乎.

Course info:

Programming Languages, Part C, University of Washington, Lecturer: Professor Dan Grossman.

そして、次の曲が始まるのです。