静态类型推导

前面说泛型的时候，提到了C++模板的实现方式是动态特性静态化，在实际情况中，这是一个提高效率的好办法。动态性的好处是灵活，开发简便，静态性的特性是效率高，编译期检查较好，因此很自然地就有一个问题，能不能各取所长，达到两全其美？应该说，在一定程度上是可以的，比如这篇即将讨论的静态类型推导，简称类型推导，因为动态类型无所谓什么推导。个人认为类型推导是编译原理最复杂的东西之一，其他复杂的有垃圾回收，代码优化等，后面会简单提到

类型推导，是指一个静态类型语言，在代码中可以不显式声明变量的类型，由编译器根据代码分析来判断出正确的类型，例如：

i = 1   
j = i * 2   
k = i + 1.234   
print i, j, k

强调一点，这个代码和本篇下面的代码都是静态类型语言（伪代码形式，能看懂就行了），虽然写起来像是动态类型。对于上面的代码，编译器推导结果如下：

int i = 1   
int j = i * 2   
double k = i + 1.234;   
print "%d %d %f" % (i, j, k)

这个过程在go和C++中已经有了，一个是:=赋值符号，一个是auto关键字，在定义变量时候不指定类型，由初值表达式的类型得出，在使用上增加了很多方便，不过，这个只是最初级的类型推导 注：auto关键字在很早的C标准就有了，后面C++修改了它的语义，这是一个不太兼容的地方，不过原本C中auto语义基本用不到

go和C++这种机制只是在赋初值时候使用，也就是说声明的位置还是确定的，而像上面的伪代码例子则不是，这有一点差别，就是在编译期做类型检查的时候查错机制不同，前者是先确定类型，后者则是检查使用的一致性，比如：

i = 1   
i = "abc"   
i = 1.234

编译器如果三次赋值是在三个文件中（假设i是extern变量这类），则编译器并不清楚程序员的真实意图是什么，因此只能报一个类型不一致的错误，当然这是假定了go和C++的这个语法的初值符合程序员意图，否则也可能报一个莫名其妙的错

由于调用函数时，参数传递可看做是一个给函数的局部变量赋初值过程，所以C++的函数模板的调用，也是上面说的这种类型推导，所不同的是，由于函数只是一段处理代码，所以用不同类型的参数调用，会产生不同的函数实例，只要每个实例都能编译通过即可

这是通过表达式的值来推导变量类型，顺便讲反过来推导的例子，通过变量类型也可以推导表达式中的某些类型，不过这个很少见，主要是在java的泛型中：

static <T> Vector<T> f()   
{   
    return new Vector<T>();   
}   
Vector<String> v = f();

这个f函数的泛型类型T，没有办法通过传入参数来决定，因为就没有参数，同时java好像也不能用f()这样的语法，所以只能通过被其返回值赋值的变量的类型来决定，由于前面讲过的java的泛型实现原理，可以改成这样：

static Vector f()   
{   
    return new Vector();   
}   
Vector<String> v = f();

不过之前也说了，java的泛型是为了编译器做更多安全检查，所以这样写会有告警，如果写成这样则会报错，尽管不影响实现原理：

static <Object> Vector<Object> f()   
{   
    return new Vector<Object>();   
}   
Vector<String> v = f();

这种推导主要原因大概是java不支持f()这种方式，编译上做一个补充罢了。但它是属于后续补充推导的，也就是说，编译器在编译赋值语句的右值的时候，信息是不完全的，只能知道f大概是返回了一个Vector，而只有在看到左值的时候，才对f的返回值做一个补充。当然，编译器在编译赋值语句的时候，一般应该还是先编译左值，这只是从执行的顺序来看

假如所有的变量都没有显式声明类型，根据初值来确定类型（go和C++这种），似乎也没什么问题，如果有多个赋值语句，搞不清哪个是所谓“初值”，至少也可以检查不一致性。这个结论对于基本类型还算没错，但一旦引入对象等就有问题了，例如下面的代码：

i = null   
...   
i = new vector()   
...   
i.add(123)

编译器看到第一句，只知道i是个对象，还不知道具体是什么，看到第二句，才知道i是个vector，但不知道元素是什么， 再看到第三句，才知道i是vector。也就是说，表达式的值是模糊的，不一定有精确的类型能立即推导出变量的类型，可能需要在这个变量所有被赋值或被改变（比如上面的add方法调用）的地方做检查，收集各种信息然后汇总，拼凑出一个完整的轮廓，当然具体这个例子，如果在一个函数的上下文中，似乎还不难推导。一个细节问题是，如果信息缺失怎么办，比如代码里就一个i=null，其他啥都没有，这种情况下可以warning，或者随便给安一个Object类型，反正也没用到

如果考虑到函数或类，这个问题就更复杂了，首先明确一点的是，一个函数或类应当是一个模板，而不是一个确定类型的，比如说定义一个f(i)，则这并不是f(SomeType i)的简写，如果是的话，我们只要找到它的一个调用的地方，就能很容易根据参数确定了，但是实际情况中一个函数应该是能接受各种类型的处理流程，例如：

func f(a, b):   
    return a + b   
f(1, 2)   
f("hello", "world")

在编译阶段会将f视作一个模板，根据传入类型的不同将其转换成各种实例，如果和变量做同样处理，上面代码报f的类型不一致（int(int,int)和str(str,str)），则要求在每个确定的程序中，f确定，这是不现实的，最简单的，定义一个func sort(a)，就只能一种类型来用，这反而还不如显式指定类型然后重载

考虑如下代码：

func f(a):   
    print a   
func g(a, b):   
    a.add(b)   
i = new vector();   
f(i)   
g(i, "hello")   
f(i)   
j = new vector();   
j.add("world")   
f(j)   
k = new set();   
g(k, 123)   
f(k)

这个代码中，当编译器看到f(i)的时候，i的类型是vector<?>，第一个f的类型是void(vector<?>)，然后在看到g(i, "hello")的时候，分析g的代码发现b是字符串，而传入的i会被用来add(b)，于是i就是vector，然后返回去第一个f就是void(vector)，接下来看到第二个f(i)，这个f的类型跟上面一样，于是合并，再下来两句可以推导出j也是vector，第三个f和前面也一样，然后下一句k是set<?>，分析g(k, 123)的代码发现k是set，最后一个f就是void(set)，于是最后的代码会成为：

void f(vector<str> a):   
    print a.to_str()   
void f(set<int> a):   
    print a.to_str()   
void g(vector<str> a, str b):   
    a.add(b)   
void g(set<int> a, int b):   
    a.add(b)   
vector<str> i, j   
set<int> k   
...//下面的代码略

上面这个例子用了重载来扩展函数，但是有时候还需要考虑返回值，比如：

func f():   
    return new vector()   
i = f()   
i.add(123)   
j = f()   
j.add("hello")

于是经过推导，展开的时候，就得成f_ret_vector_int和f_ret_vector_str这种形式，由于返回值不在重载控制范围。这种情况就是上面那个java的例子的扩展版本，只不过java那个是必须赋值时候推导，这里需要后续根据add行为来推导，更复杂一些

这里只举了函数的例子，类的情况也类似，考虑到类的方法也是模板，可以说更复杂，大家自己想象

于是我们看到，如果自动推导跨了类和函数，会比较麻烦，不过也是能做到的，在一个程序编译的时候，我们强制规定main函数只有一个实例，这是合理的，然后从main开始，画出所有函数的调用树，对于未确定的类型，用一个待定号码来表示（例如上面的“?”），等确定了再回填，最后再合并类型相同的函数即可，问题在于，如果只是一棵树还好办，但如果加上递归调用，树就变成了图，例如：

func f(a, b):   
    ...   
    f(new vector(), b + 1.0)   
    ...   
    f(new vector(), (int)b)   
    ...   
    a.add(b)   
f(new vector(), 1)

这里编译到f的调用的时候，参数是vector<?>和int，然后可以推出传入的a是vector，然后再第一个递归调用的时候，需要新建一个参数为vector<?>和double的f，第二个递归的时候可以复用之前的第一个f的实例，这个推导还是很麻烦的

实际上，针对f的静态分析本身可以总结出一些特点，比如看到a.add(b)这句，虽然不知道传入的a和b具体类型，但是知道它们的约束，即a必须有一个add(typeof(b) b)的方法，用静态分析先总结约束，然后每次调用时候就能直接检查和推导实例，不用每次分析代码，但我觉得算法和数据结构表示可能太复杂了 说到这里再提醒一句，vector这个类也是模板，new的时候是不知道它具体类型的，根据后续add来决定，因此上面说的“a必须有一个add(typeof(b) b)的方法”的约束应该是说f的类型是void(vector,T)这样比较合适，这还没完，如果a.add(b)下面再加一个b.add(a)，那这个约束该怎么写呢，泛型表示都是无限递归了，还有，假如这个add不是f里面，而是在更深的调用，甚至是回调函数，那写个编译器分析这个我只能呵呵呵了，有心无力啊，还是交给专家来研究吧

考虑到递归，有时候很简单一句话也不一定容易处理，比如：

class A:   
    A(i):   
        this.i=i   
i = A(i)

i是一个类A的对象（实际表示形式是无限递归的，用一个单独的A表示自身），但是这个推导就可能需要把这句赋值分解成：

i = A()   
i.i = i

这样可能会好点，但如果是A的两个实例互相引用：

class A:   
    A(i):   
        this.i = i   
        this.j = null   
i = A(123)   
j = A("hello")   
i.j = j   
j.j = i

这种代码生成的类型系统就很复杂了

虽然类型推导很复杂，但还是有很多语言实现了，或部分实现了，函数式编程比较多，据说Haskell就做的很好，但是命令式编程里面貌似比较少，或者就是只支持C++和go这种“半吊子”推导，究其原因，我觉得除了上面说的实现的复杂性以外，代码可读性是一个很重要的原因，毕竟一个变量的类型如果要读完代码（甚至要跨越几个库）才能知道，这是非常难以维护的，相对来说多敲几个声明成本是很低的，如果是大项目，打这点字死不了人，如果是小程序，那直接上动态类型语言一般也能接受了，因此，没有必要做很完整的类型推导，不过在理论方面，这仍然是编译原理中一直被深入研究的一个话题