Just Enough Type Information [blog/lti/enough]

在放弃了对「完全类型推断」的追求之后,一个至关重要的问题便浮现出来:一个「部分」类型推断算法,其推断能力需要达到何种程度,才算是「足够」?一个极具实践智慧的回答:一个好的部分类型推断算法,其核心使命在于消除那些既普遍又愚蠢的类型标注。

此处的「愚蠢」与「合理」相对。「合理的」标注,如顶级函数定义中对其参数的类型声明,通常能作为有价值的、且经由编译器检查的文档,帮助人们理解代码。「愚蠢的」标注则恰恰相反,它们徒增代码的冗余,却几乎不提供任何有用的信息。可以想见,在一个完全显式类型的语言中,任何人都不会愿意去书写或阅读 cons[Int](3, nil[Int]) 中那两个多余的 Int 标注。

Pierce 对十几万行 ML 代码的调研,揭示了三种最主要的「愚蠢标注」来源:

  • 多态实例化:在所测量的代码中,类型应用(即对多态函数的实例化)的现象无处不在,平均来看,每三行代码中就至少出现一次。这些在多态函数调用点插入的类型参数,几乎没有任何文档价值,纯属语法上的累赘。
  • 匿名函数定义:在类似 map(list, fun(x) x+1) 这样的上下文中,为匿名函数的参数 x 补上类型标注,只会掩盖其核心逻辑,实为一种不必要的干扰。
  • 局部变量绑定 (Let): 为这些生命周期短暂的中间变量一一标注类型,显然是繁琐且意义不大的。

基于上述的定量观察,我们可以勾画出一个「足够」的部分类型推断算法的轮廓:

  1. 它必须能够推断出多态函数应用中的类型参数。与此同时,要求程序员为顶级函数或相对稀少的局部函数提供显式标注,则是完全可以接受的,因为这些标注本身就是有益的文档。
  2. 为了使高阶编程更加便捷,算法应当能够推断匿名函数参数的类型,尽管这并非绝对必要。
  3. 局部变量绑定通常不应要求显式的类型标注。

1. Strategies [blog/lti/strategies]

为了实现我们的目标,我们需要设计一套高效的策略来处理上述三种类型推断的场景。 下面的是两种本文将要介绍的主要策略:

  • 局部类型参数合成 (Local Synthesis of Type Arguments):此策略旨在自动推断多态函数应用中被省略的类型参数。其基本思路是,通过比较函数参数的期望类型与实际参数的类型,生成一组关于待定类型参数的局部子类型约束。随后,算法会求解这组约束,并选取一组能使整个应用表达式获得「最佳」(即最精确、最小)结果类型的解。
  • 双向类型信息传播 (Bidirectional Propagation of Type Information):此策略主要用于推断匿名函数中绑定变量的类型标注。它通过将类型信息从外围的表达式(如函数应用节点)向下传播至其子表达式,从而为子表达式提供一个「期望类型」,以指导其类型检查过程。

这两项技术均恪守「局部性」原则,即所有推断所需的信息都只在语法树的相邻节点间传递,不涉及长距离的依赖或全局性的合一变量。