NBEP 5: 类型推断
- 作者:
林思宽
- 日期:
2016年9月
- 状态:
草稿
本文档描述了numba中当前的类型推断实现。
介绍
Numba 使用类型信息来确保用户代码中的每个变量都能被正确地降低（翻译成低级表示）。变量的类型描述了有效操作集和可用属性。在编译期间解析此信息避免了在运行时进行类型检查和调度的开销。然而，Python 是动态类型的，用户不声明变量类型。由于缺少类型信息，我们使用类型推断来重建缺失的信息。
Numba 类型语义
类型推断在 Numba IR 上运行，这是Python字节码的静态单赋值（SSA）编码。从概念上讲，Python代码中的所有中间值都显式地分配给IR中的一个变量。Numba强制要求每个IR变量只能有一种类型。用户变量（来自Python源代码）可以映射到IR中的多个变量。它们是变量的*版本*。每次用户变量被赋值时，都会创建一个新版本。从那时起，所有后续引用都将使用新版本。用户变量*演化*为函数逻辑更新其类型。控制流中的合并点（例如if-else的后续块、循环体等）需要特别注意。在每个合并点，都会隐式创建一个新版本来合并来自传入路径的不同变量版本。变量版本的合并可能会转换为隐式类型转换。
Numba 使用函数重载来模拟 Python 的鸭子类型。函数的类型可以包含多个调用签名，这些签名接受不同的参数类型并产生不同的返回类型。决定重载函数最佳签名的过程称为 重载解析。Numba 部分实现了 C++ 重载解析方案（ISOCPP 13.3 重载解析）。该方案通过对称地对每个参数进行排名，使用“最佳匹配”算法。五个可能的排名按惩罚递增的顺序是：
精确：预期类型与实际类型相同。
提升：实际类型可以通过扩展精度而不改变行为来向上转换为预期类型。
安全转换：实际类型可以通过在不丢失信息的情况下改变类型来转换为预期类型。
不安全的转换：实际类型可以通过改变类型或即使不精确也向下转型为预期类型。
不匹配：没有有效的操作可以将实际类型转换为预期类型。
可能存在不明确的解析。例如，具有签名 (int16, int32) 和 (int32, int16) 的函数，如果遇到参数类型 (int32, int32)，可能会变得不明确，因为将任一参数降级为 int16 都是同样“合适”的。幸运的是，numba 通常可以通过编译具有精确签名 (int32, int32) 的新版本来解决这种不明确性。当编译被禁用且存在多个同样合适的签名时，会引发异常。
类型推断
numba 中的类型推断有三个重要组成部分——类型变量、约束网络和类型上下文。
*typing context* 提供了所有类型信息和与类型相关的操作，包括类型统一逻辑，以及全局和常量值的类型逻辑。它定义了可以由 numba 编译的语言语义。
一个 类型变量 保存每个变量的类型（在Numba IR中）。从概念上讲，它被初始化为通用类型，并且在重新赋值时，它通过将新类型与现有类型统一来存储一个公共类型。这个公共类型必须能够表示新类型和现有类型的值。根据需要应用类型转换，并且出于可用性考虑，接受精度损失。
约束网络 是从 IR 构建的依赖图。每个节点代表 Numba IR 中的一个操作，并至少更新一个类型变量。由于用户代码中的循环，可能存在循环。
类型推断过程从初始化参数类型开始。这些初始类型在约束网络中传播，最终填充所有类型变量。由于网络中存在循环，该过程会重复进行，直到所有类型变量收敛或因无法确定的类型而失败。
类型统一总是返回一个更“通用”（之所以加引号是因为允许不安全的转换）的类型。类型将收敛到能够表示变量可能持有的所有可能值的最“不通用”的类型。由于统一永远不会沿着类型层次结构向下移动，并且存在一个单一的顶级类型——object，因此类型推断保证会收敛。
类型推断失败可能由两个原因引起。第一个原因是由于类型使用不当导致的用户错误。这种类型的错误在常规的Python执行中也会触发异常。第二个原因是由于使用了不支持的功能，但代码在常规的Python执行中是有效的。发生错误时，类型推断会将所有类型设置为对象类型。因此，numba将回退到*对象模式*。
由于函数可以被重载，类型推断需要在每个调用点决定使用的类型签名。重载解析应用于 调用模板 中描述的所有已知重载版本的被调用函数。调用模板可以是具体的或抽象的。具体调用模板定义了所有可能签名的固定列表。抽象调用模板定义了计算接受签名的逻辑，并用于实现泛型函数。
由于能够编译新版本，Numba 编译的函数是泛型函数。当它看到一组新的参数类型时，它会触发类型推断以验证并确定返回类型。当存在对 Numba 编译函数的嵌套调用时，每个调用点都会触发类型推断。这对递归函数提出了一个问题，因为类型推断也会递归触发。目前，如果签名由用户注解，则支持简单的单次递归，这避免了类型推断中的无界递归，这种递归永远不会终止。