type dispatching

我们知道某些问题存在若干个互相有继承关系的类,比如类 A,有子类 B 和 C,如果拿到 A 的对象希望有一些 polymorphism 的动作,常见的策略莫过于使用 virtual function,但是这个策略往往会有一定的局限性,提供 A 的人未必知道这些动作是什么,这意味着一般通过继承获得的多态是“封闭”的,不可扩展的。常常会被人“觉得”能够解决这个问题的策略是函数重载。

从某个角度来说这两种“polymorphism”是截然不同的,虚函数获得的是 dynamic 的而函数重载是 static 的,即前者是运行时决定的,后者是编译时决定的。这个区别导致一些人觉得能 work 的实现其实都不 work。

public class WrongDispatching {
    public static class A {}
    public static class B extends A {}
    public static class C extends A {}

    public static class Printer {
        public static void print (A a) {
            System.out.println ("A") ;
        }

        public static void print (B b) {
            System.out.println ("B") ;
        }

        public static void print (C c) {
            System.out.println ("C") ;
        }

    }

    public static void main (String[] args) {
        A a = new A () ;
        B b = new B () ;
        C c = new C () ;
        Printer.print (a) ;
        Printer.print (b) ;
        Printer.print (c) ;
    }
}

一般人认为以上代码能 work,那么我们拿个 List<A> 遍历一下估计也会 work,

public static void print (List<A> l) {
    for (A a : l)
        Printer.print (a) ;
}
    List<A> ar = new ArrayList<A> () ;
    ar.add (a) ;
    ar.add (b) ;
    ar.add (c) ;
    print (ar) ;

结果却不对,其实理由很简单,这里 print 函数里面拿到的是 A,自然编译时就 bind 到 Printer.print (A) 这个函数上啦。当然总有人会想办法,希望能将编译时的多态成功的弄成运行时的:

public static void print (List<A> l) {
    for (A a : l)
        Printer.print (cast (a, a.getClass ())) ;
}

public static <T> T cast (Object o, Class<T> c) {
    return c.cast (o) ;
}

看样子通过 a.getClass 应该是获得对应的类对象了,那 cast 返回的应该分别是 A、B、C 的对象了,可是结果仍然是三个 A。这个问题出现在哪里呢,其实 cast 的确完成了你所要的转换,但是在确定 Printer.print 是哪个 print 的时候编译器只选择了 print (A) 这个,如果我们在 l 里面混入一些别的类的对象就会出现一些诡异的事情。

public static class D {}
    D d = new D () ;
    List arr = ar ;
    arr.add (d) ;
    print (ar) ;

这就会导致运行时错误,这也是引入 generic 之后 java 就不希望大家用不带 generic type 的类型的原因:不能通过类型检查防止程序员干蠢事。事实上 print (D) 是不能被编译的,但是运行时居然碰到了,抛出的异常也很有意思,说是类型不能转换。Okay 我想你大概明白了,因为 cast 的结果可以隐式转换到 A 类型,所以前面的三个 A 就很清楚了。那么为什么编译器选择的却是 print (A) 而不是另外两个呢?其实这应该是从这个 print (List<A>) 推断出来的。

那么是不是原来的问题就无解了?我们回想一下 C++ 里面的一些对应的概念,其实 C++ 对应 generic 是模板,实际调用这个模板的时候参数是已知的,这样 forward 到一组重载函数上也是编译时决定的了。如果你非要通过指针数组传入非 A 的指针(reinterpret_cast 一下)那结果是仍然执行对应的函数,请款如果简单(如我们这里并没有访问 A 的成员)可能不会 crash,但是稍微复杂一点可以想像后果更加严重,因为和 Java 不同 C++ 并不做运行时类型检查。可能跟标题有点类似的一个 meta programming 技巧 tag dispatching 是不是会有点帮助呢?tag dispatching 是在这些类 A、B、C 里面 typedef 一个 tag,tag 类之间有继承关系表达这些类是否满足某些特性,那么提供的 print 方法通过这个 tag 将其 forward 到不同的实现上,这依赖于编译时多态,以及编译时的 type inference。

all right… 看起来 C++ 的那些技巧用不上了,祭出 design pattern 中的 visitor pattern。其实这是应用 virtual function 本身来做 dispatching,仍然要求我们能修改 A、B、C 的实现。其实这个想法就是既然 virtual function 能够产生多态,那么我们从这个函数里面调用 visitor 的对应实现就行了!

import java.util.List ;
import java.util.ArrayList ;

public class VisitorDispatching {
    public static interface Visitor {
        public void visit (A a) ;
        public void visit (B b) ;
        public void visit (C c) ;
    }

    public static class A {
        public void accept (Visitor v) {
            v.visit (this) ;
        }
    }
    public static class B extends A {
        public void accept (Visitor v) {
            v.visit (this) ;
        }
    }
    public static class C extends A {
        public void accept (Visitor v) {
            v.visit (this) ;
        }
    }

    public static class Printer implements Visitor {
        public void visit (A a) {
            System.out.println ("A") ;
        }

        public void visit (B b) {
            System.out.println ("B") ;
        }

        public void visit (C c) {
            System.out.println ("C") ;
        }

    }

    public static void print (List<A> l) {
        Printer p = new Printer () ;
        for (A a : l) {
            a.accept (p) ;
        }
    }

    public static void main (String[] args) {
        A a = new A () ;
        B b = new B () ;
        C c = new C () ;

        List<A> ar = new ArrayList<A> () ;
        ar.add (a) ;
        ar.add (b) ;
        ar.add (c) ;
        print (ar) ;
    }
}

其实这段 Java 看起来还是很傻,同样一段 accept 函数必须放在三个类里面(否则还是三个 A),Visitor 自己的接口函数跟 A 的所有子类必须对应,这导致实现这个接口的人任务巨大。哎,还是土方法的好?

public static void print (List<?> l) {
    for (Object o : l) {
        if (o.getClass () == A.class)
            Printer.print ((A) o) ;
        else if (o.getClass () == B.class)
            Printer.print ((B) o) ;
        else if (o.getClass () == C.class)
            Printer.print ((C) o) ;
        else
            Printer.print (o) ;
    }
}

比较头疼的是这个 pattern 你弄不成 generic 的,除非… reflection?也许你会想是不是 scala 就 okay 了,我感觉也没法做,写出来跟上面 if then else 一样,兴许看起来好看点?有更好的解决方案吗?

——————
So that I come again to my father’s house in peace; then shall the LORD be my God:

Advertisements
type dispatching

发表评论

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