方法分派（method dispatch）的几个例子

昨天发的帖只是提到了单一分派（single-dispatch）和多分派（multiple-dispatch），没有说明它们到底是什么。这里简单解释一下方法分派的概念。

追加：请留意后续帖C# 4的方法动态分派逻辑变了……中的内容。本帖所描述的C# 4.0的行为只适用于VS2010CTP的版本，将不适用于C# 4.0正式版。

在程序设计语言中，许多时候同一个概念的操作或运算可能需要针对不同数量、不同类型的数据而做不同的处理。既然是“同一概念”，如果能用同样的名字来命名这个操作或运算的函数，会有助于程序代码清晰的表达出语义。但是函数的名字一样了，程序该如何判断应该选用同名函数的哪个版本就成了个问题，这里就需要在编译时由编译器来选择，或在运行时进行方法分派。
参数的数量、类型等信息组成了函数的signature。在不同语言中，函数的signature不仅可以包含参数的数量、类型，也可能包含参数的结构/模式，甚至可能包括返回类型的数量和类型；这超出了本文的范围，下面将简单的认为signature只是针对指参数的数量和类型而言。

在过程式语言中，使用同一个名字来命名signature不同的函数，称为函数重载（function overloading）。可惜C语言并不支持函数重载，这里就用只使用了过程式程序设计的语法结构的C++代码来说明：

#include <cstdio>

void foo( int i ) {
    printf( "foo( int )\n" );
}

void foo( int i, int j ) {
    printf( "foo( int, int )\n" );
}

void foo( double d ) {
    printf( "foo( double )\n" );
}

int main( ) {
    int i, j;
    foo( i );    // foo( int )
    foo( i, j ); // foo( int, int )

    double d;
    foo( d );    // foo( double )

    return 0;
}

函数重载是编译时概念。参数类型是由变量声明的类型所决定的。上面的代码中虽然没有给局部变量i、j和d赋值，编译器已经有足够信息来判断应该采用哪个版本的foo()。

在面向对象程序设计语言中，同一个继承链上的不同类型可以拥有signature相同的虚方法，表现出多态。观察以下Java代码：

class A {
    public void foo( int i ) {
        System.out.println( "A.foo( int )" );
    }
}

class B extends A {
    @Override
    public void foo( int i ) {
        System.out.println( "B.foo( int )" );
    }
}

public class Program {
    public static void main( String[ ] args ) {
        A b = new B( );
        b.foo( 0 ); // B.foo( int )
    }
}

Java中的成员方法（非静态方法）都是虚方法。这里的A.foo(int)与B.foo(int)就是同一继承链上signature相同的两个虚方法，B.foo(int)覆盖（override）A.foo(int)。从语义上说，在编译时无法判断一个虚方法调用到底应该采用继承链上signature相同的哪个版本，所以要留待运行时进行分派（dispatch）。上面的例子中，可以看到虽然局部变量b的类型是A，但b.foo(0)调用的是b所指向的对象的实际类型B上的foo(int)方法。
当然，在静态类型的面向对象程序设计语言中，函数仍然是可以重载的。所以上面的例子也可以有：

class B extends A {
    @Override
    public void foo( int i ) { }

    public void foo( int i, int j ) { }

    public void foo( double d ) { }
}

这里，只有B.foo(int)对A.foo(int)表现出运行时多态，B.foo(int,int)与B.foo(double)只是对B.foo(int)的重载。
注意到在单一分派静态类型的面向对象语言中，重载仍然是编译时概念：编译器只会根据静态变量的类型来判断选择哪个版本的重载，而不像运行时多态那样根据值的实际类型来判断。

那么单一分派（single-dispatch）是什么意思？
假如把上面的Java例子的类型声明用伪C来展开，可以变成类似这样：
（假设B*能隐式转换到A*。
下面代码无法表示B*到A*的隐式转换，也不支持重载，所以只能是伪C了，凑合看看吧）

typedef struct {
    FOOPTR foo;
} A;

typedef struct {
    FOOPTR foo;
} B;

void foo( A* this, int i ) { }
void foo( B* this, int i ) { }

那么在调用的时候可以看作：

A* b = ( A* ) malloc( sizeof( B ) );
foo( b, 0 );

这里想表达的是，面向对象语言中经常会对函数调用的第一个参数做特殊处理，包括语法和语义都很特别。语法的特别之处在于实际上的第一个参数不用写在参数列表里，而是写在某种特殊符号之前（b.foo(0)的“.”），也就是所谓的隐含参数。语义的特别之处在于这第一个参数的称为方法调用的接收者（reciever）；它的实际类型会参与到方法分派的判断中，而其余的参数要么只参与静态类型判断（单一分派+方法重载），要么也以实际类型参与到方法分派的判断（多分派）。

再看看昨天的帖里我举的例子。假设有下面的类型声明：

public class A { }
public class B : A { }

public class Foo {
    public virtual void Bar( A a ) { }
    public virtual void Bar( B b ) { }
}

public class Goo : Foo {
    public override void Bar( A a ) { }
    public override void Bar( B b ) { }
}

那么Bar(A)与Bar(B)之间的关系就是方法重载，而Foo.Bar(A)与Goo.Bar(A)之间的关系就是继承关系中的虚方法覆盖。然后在这样的代码中：

Foo goo = new Goo( );
A b = new B( );

变量goo与b的静态类型都与它们实际所指向的值的实际类型不同：

C#的方法分派是单一分派的，所以在以下调用中：

goo.Bar( b ); // Goo.Bar( A )

这里goo就是隐含的第一个参数，而b是第二个参数。
虽然变量goo的静态类型是Foo，但因为它指向的值得实际类型是Goo而且Bar()是虚函数，所以选用Goo上的Bar()。
对参数b的处理则不同。编译器只看到它的静态类型是A，所以在编译时就决定选用Bar(A)而不是Bar(B)。

在C# 4增加了“动态类型”之后，如果一个虚方法调用的接收者或者任意的参数的类型是dynamic，那么整个方法调用都无法在编译时判定到底应该选用哪个具体版本。所以，底层的运行时库会根据运行时接收者和每个参数的实际类型来进行方法分派。这个语义就与多分派的语义一样了。因此：

Foo goo = new Goo( );
dynamic b = new B( );
goo.Bar( b ); // Goo.Bar( B )

在这个goo.Bar(b)中，虽然只有b是dynamic类型的，但这会让编译器认为整个方法调用的分派都需要留到运行时来做。到运行时，首先知道goo的静态类型是Foo，再看b的实际类型——是B，然后看Foo上有没有名为Bar的方法是接受B类型的参数的，找到Foo.Bar(B)；接着由于Foo.Bar(B)是虚方法，要再看goo的实际类型——是Goo，结果找到Goo.Bar(B)，于是就对这个版本进行调用。这个判断过程是由所谓的C# runtime binder（Microsoft.CSharp.RuntimeBinder.RuntimeBinder）来完成的，是C# 4基于DLR实现的一个组件。

using System;

public class A { }
public class B : A { }

public class Foo {
    public virtual void Bar( A a1, A a2 ) {
        Console.WriteLine( "Foo.Bar( A, A )" );
    }

    public virtual void Bar( A a, B b ) {
        Console.WriteLine( "Foo.Bar( A, B )" );
    }

    public virtual void Bar( B b, A a ) {
        Console.WriteLine( "Foo.Bar( B, A )" );
    }

    public virtual void Bar( B b1, B b2 ) {
        Console.WriteLine( "Foo.Bar( B, B )" );
    }

    public void Baz( A a ) {
        Console.WriteLine( "Foo.Baz( A )" );
    }
}

public class Goo : Foo {
    public override void Bar( A a1, A a2 ) {
        Console.WriteLine( "Goo.Bar( A, A )" );
    }

    public override void Bar( A a, B b ) {
        Console.WriteLine( "Goo.Bar( A, B )" );
    }

    public override void Bar( B b, A a ) {
        Console.WriteLine( "Goo.Bar( B, A )" );
    }

    public override void Bar( B b1, B b2 ) {
        Console.WriteLine( "Goo.Bar( B, B )" );
    }

    public new void Baz( A a ) {
        Console.WriteLine( "Goo.Baz( A )" );
    }
}


static class Program {
    static void Main( string[ ] args ) {
        A a = new A( );
        A b = new B( );
        Foo goo = new Goo( );

        dynamic da = a;
        dynamic db = b;
        dynamic dgoo = goo;

        goo.Bar( a, b );  // Goo.Bar( A, A ), single-dispatch

        goo.Bar( da, b ); // Goo.Bar( A, B ), multi-dispatch
        goo.Bar( a, db ); // Goo.Bar( A, B ), multi-dispatch
        goo.Bar( b, db ); // Goo.Bar( B, B ), multi-dispatch
        dgoo.Bar( a, b ); // Goo.Bar( A, B ), multi-dispatch

        goo.Baz( b );  // Foo.Baz( A )
        dgoo.Baz( b ); // Goo.Baz( A )
    }
}

很明显，C# 4的虚方法调用中任意一个或多个参数是dynamic类型时，所有参数的实际类型都会参与到方法分派的判定中。
但留意一下最后的两个方法调用，goo.Baz(b)和dgoo.Baz(b)：Foo.Baz(A)和Goo.Baz(A)不是虚方法。在C# 4中如果一个非虚方法的方法调用的接收者不是dynamic，那么到运行时选择方法重载仍然会使用接收者的静态类型来考虑。goo.Baz(b)选用的是Foo.Baz(A)就是这个情况。

在Python或者Ruby等变量没有类型，只有值有类型的动态类型语言中，由于无法指定参数的静态类型，也就无从说起“根据参数的静态类型选择方法的版本”。在这样的语言里，要根据参数类型做方法分派基本上只能在一个分派用方法里手工判断，然后再调用具体的版本：

class A
end

def foo(a)
  # declare the differnet specialized versions of the method
  foo_Fixnum = proc { puts 'Fixnum defaults to 0' }
  foo_A = proc { puts 'A defaults to nil' }
  foo_other = proc { puts 'whatever...' }

  # manually dispatch according to type
  # NOT something I would recommend doing in Ruby, though
  case
  when a.instance_of?(Fixnum)
    foo_Fixnum[]
  when a.instance_of?(A)
    foo_A[]
  else
    foo_other[]
  end
end

foo 1     # Fixnum defaults to 0
foo A.new # A defaults to nil
foo 'me'  # whatever...

这种手工的方法分派在Python和Ruby都有些第三方库封装起来了可以直接用，但关键是脚本引擎本身并不直接提供根据类型做方法分派的支持。这些语言里通常也没必要对类型来分派就是了……

虽然上面一直是在讨论以参数的数量和类型为signature的考虑，许多语言实际上还可以对参数的模式进行判断来做函数分派。看看这段OCaml/F#代码的函数定义：

let rec length = function
    []    -> 0
  | x::xs -> 1 + length xs;;

然后调用：

length [0;2;4;6];;

就得到了结果4。这里就是对参数做了模式匹配然后决定采用哪个版本的表达式来计算。当看到参数是空的表时，返回0；当看到参数是一个非空的表时，把表头元素称为x，余下的元素所构成的表称为xs，那么对xs递归调用length之后把结果加上1然后返回。很简单很方便。

评论

2 楼 RednaxelaFX 2008-10-30  

cajon 写道

吼吼，明白了。这个就是你说的那个“一个表达式中任何一个值的类型是dynamic的时候整个表达式的类型都是dynamic……”就是这个意思吗？还是有更多的影响。75G实在太夸张了，就不自己尝试了，厚着脸皮问了

其实没那么大啦。FAQ说最小需要40G，我在虚拟机里看这个虚拟硬盘也才56G而已。还好我的新笔记本是250G的硬盘不然也吃不消……

所谓一个表达式中任意一个变量的类型是dynamic导致整个表达式的类型都是dynamic是这个意思：

dynamic i = 1; // i is dynamic
var j = 2;     // j is int
var k = i + j; // k is dynamic
int l = k;     // l is implicitly converted into int

注意到var跟dynamic有着本质的区别：var是在编译时根据声明语句中赋值符右侧的表达式类型来静态判定类型，而dynamic在编译时不关心类型是什么，等到运行的时候再判断。

问题是dynamic到底是什么？在编译的时候，其实dynamic就是打上了[Dynamic]标签的object而已。任何能赋值给object的东西都能赋值给声明为dynamic类型的变量。但到运行的时候，这些dynamic会先被替换会到变量所指向的值的实际类型，然后再执行。换句话说到运行的时候经过处理，上面的代码近似等价于：

int i = 1;
int j = 2;
int k = i + j;
int l = k;

这个“处理”就是DLR CallSite配合C# runtime binder完成的了。以后肯定有机会再说说这方面的内容的。

1 楼 cajon 2008-10-30  

吼吼，明白了。
这个就是你说的那个“一个表达式中任何一个值的类型是dynamic的时候整个表达式的类型都是dynamic……”就是这个意思吗？还是有更多的影响。

75G实在太夸张了，就不自己尝试了，厚着脸皮问了