几个基本概念

写程序果然有很多事情我是不晓得的,语言是会限制对这些问题的认识的。所以多了解一些别的语言从某种意义上是很有必要的。这次要说的就是 covariance/contravariance

很奇怪的是,尽管是跟写程序有关系,这两个概念的来源却是数学 category theory(范畴论),与此紧密相关的一个原理是 Liskov substitution principle(Liskov 替换原则),这个原则的数学表述比较抽象,大致的意思就是说如果你想把 B 当做 A 来用,那么 A 能做的事情 B 都能做。

这个在 OOP 里面直接相关的概念就是继承、实现导致的两个类/接口之间的关系。比如 B 继承了 A 那么我们需要满足 Liskov 替换原则的意思就是说原先使用 A 的地方,传递 B 的对象、引用、指针也应该是能用的;同时另一层意思却常常被人忽视。但是我们常见到 C++/Java 都会提到这么一点:那就是如果 A 有个函数 foo 返回了某个类 C 的话,B 实现的 foo 可以返回 C 的子类(不是仅仅写成返回 C 类,通过隐式转换将其子类转换到 C 类的问题,而是你可以直接将返回类型写成一个子类,而这不是编译错误!)这个看似放松了对覆盖函数的返回类型的要求,但实际上却满足 Liskov 替换原则,因为原先通过 A::foo 返回 C 类的东西,换成实际对象为 B 却依然满足这个条件。这常被人称为 covariant。

另外一个被人忽视的方面是,如果 A 的 foo 接受一个 D 类型的参数,那么 B 的 foo 应该可以接受任意 D 类型父类的参数。这一点也很显然,因为把 B 当作 A 来用的时候接受的是 D 类型(及其子类),自然也满足了 B 的参数类型的要求。

#include <iostream>

struct A {} ;

struct B : public A {} ;

struct C {
  virtual A
  foo (B b) {
    std::cout << "C::foo" << std::endl ;
    return A () ;
  }
} ;

struct D : public C {
  B foo (A b) {
    std::cout << "D::foo" << std::endl ;
    return B () ;
  }
} ;

int
main () {
  A a ; B b ;
  C c ; D d ;
  c.foo (b) ;
  d.foo (b) ;
  d.foo (a) ;

  C& dr = d ;
  dr.foo (b) ;
  //dr.foo (a) ;

  return 0 ;
}

如果这里输出如下

C::foo
D::foo
D::foo
C::foo

这说明 C++ 其实不支持这种意义上符合替换原则的扩展,这一般称为 contravariant。与这两个概念相关的第三个就是 invariant/nonvariant。从这里我们大概能看出来成员函数的输入与继承关系是 contravariant,而输出是 covariant 的(子类输出子类,子类输入父类)。

为什么说这个概念重要?其实从 C++/Java 的 container/collection 的设计就能略微看到一点。Java 传统上有 array,并且这个概念是 covariant 的,意味着如果你有一个类 A,类 B 继承了 A,那么 B[] 可以转换成为 A[],即这两者也是继承关系的。但这个扩展却存在严重的问题!这个问题居然和 mutability 有关系!为什么呢?比如 A[] a,这意味着我们可以拿个 B[] b 赋值给 a,如果我们有另外一個子类 C 也继承了 A,那意味着我们可以将其放在 a 里面,同时如果通过 b 将其取出来,C 就成功的“被转换”成了 B,我们知道这肯定是一个 runtime error 的。似乎有了这个教训之后,Java 的 collections 和 C++ 的 container 都表示我们是 invariant 的,比如 List<A> 和 List<B> 其实没有任何继承关系,std::vector<A> 和 std::vector<B> 也没有任何关系。不过这也带来一些问题,写了个 smart_ptr<A>、却发现 smart_ptr<B> 与之不能隐式转换,当然 C++ 通过 template method 解决了这类问题,但我们总觉得少了一些什么。

Okay 话说回来,为什么 mutability 跟这个有关系?很明显如果 A[] 是不能被修改的(并不是说不支持插入元素的操作,而是这些操作会返回新的对象),那么原先都是 A 的对象自然不能被其子类(C 的对象)覆盖,那么之前的引用(B 类型)就仍然是合法的了(不会指向 C 的对象)。也就是说 immutable collection 可以是 covariant 的!这也就是 scala 里面 immutable collection 与 Java collection 之类的最大的区别。那么我们再考虑一个更复杂的例子一个这种容器的 insert 会有什么结果?

class List[+T] {
  def insert (elem: T) : List[T] = ???
}

我们知道 List[A] 可以插入 B、C 的对象,但是 List[B] 是万万不能插入 C 的,可是这看起来有点怪,因为我们得手动将 List[B] 转到 List[A],然后插入。为了能够更加自动的完成这个事情,我们需要更加符合前面 Liskov 替换原则的方式来表达这里的概念(事实上以上代码无法通过 scala 的 variance checking),

class List[+T] {
  def insert [U >: T] (elem: U) : List[U] = ???
}

这样一来插入就能 work 了。也就是说 scala 里面如果希望产生 variance,我们就必须依照前面的原则来表示输入输出类型的上下界。看起来简单,做起来着实不是那么容易,特别对一个从没有这么严格的 variance checking 语言转到一个需要严格声明的语言下面的程序员来说。从某个角度来说,这只是增强了表述的准确性,获得了原先不具有的 type inference 能力。

——————
And she put the skins of the kids of the goats upon his hands, and upon the smooth of his neck:

Advertisements
几个基本概念

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s