NBEP 5: 类型推断

作者: Siu Kwan Lam
日期: 2016年9月
状态: 草稿

本文档描述了 Numba 中当前的类型推断实现。

简介

Numba 使用类型信息来确保用户代码中的每个变量都能被正确地降级（翻译成低级表示）。变量的类型描述了有效的操作集和可用的属性。在编译期间解析这些信息可以避免运行时类型检查和分派的开销。然而，Python 是动态类型的，用户不声明变量类型。由于类型信息缺失，我们使用类型推断来重建缺失的信息。

Numba 类型语义

类型推断操作于 Numba IR，这是一种主要采用静态单赋值（SSA）方式编码的 Python 字节码。从概念上讲，Python 代码中的所有中间值都在 IR 中显式地赋值给一个变量。Numba 强制每个 IR 变量只能有一种类型。一个用户变量（来自 Python 源代码）可以映射到 IR 中的多个变量。它们是变量的版本。每次用户变量被赋值时，都会创建一个新版本。从那时起，所有后续引用都将使用新版本。用户变量随着函数逻辑更新其类型而演变。控制流中的合并点（例如，if-else 后的后续块、循环体等）需要额外处理。在每个合并点，会隐式创建一个新版本，以合并来自传入路径的不同变量版本。变量版本的合并可能会转换为隐式类型转换。

Numba 使用函数重载来模拟 Python 的鸭子类型（duck-typing）。函数的类型可以包含多个调用签名，这些签名接受不同的参数类型并产生不同的返回类型。决定重载函数最佳签名的过程称为重载解析。Numba 部分实现了 C++ 重载解析方案（ISOCPP 13.3 重载解析）。该方案使用“最佳匹配”算法，对称地对每个参数进行排名。惩罚递增的五种可能排名是：

精确匹配：预期类型与实际类型相同。
提升：实际类型可以通过扩展精度向上转换为预期类型，而不改变行为。
安全转换：实际类型可以通过改变类型转换为预期类型，而不会丢失信息。
不安全转换：实际类型可以通过改变类型或向下转换类型来转换为预期类型，即使它不精确。
不匹配：没有有效操作可以将实际类型转换为预期类型。

可能会出现歧义解析。例如，如果一个函数具有签名 (int16, int32) 和 (int32, int16)，当参数类型为 (int32, int32) 时，可能会变得模糊，因为将任一参数降级到 int16 都同样“适合”。幸运的是，Numba 通常可以通过编译一个具有精确签名 (int32, int32) 的新版本来解决这种歧义。当编译被禁用且存在多个同样匹配的签名时，会引发异常。

类型推断

Numba 中的类型推断有三个重要组成部分：类型变量、约束网络和类型上下文。

类型上下文提供所有类型信息和类型相关操作，包括类型统一的逻辑，以及全局和常量值类型化的逻辑。它定义了 Numba 可以编译的语言的语义。
一个类型变量保存每个变量（在 Numba IR 中）的类型。从概念上讲，它被初始化为通用类型，并且在重新赋值时，通过将新类型与现有类型统一来存储一个通用类型。通用类型必须能够表示新类型和现有类型的值。必要时应用类型转换，并出于可用性原因接受精度损失。
约束网络是一个从 IR 构建的依赖图。每个节点代表 Numba IR 中的一个操作，并更新至少一个类型变量。用户代码中的循环可能会导致循环。

类型推断过程从设置参数类型开始。这些初始类型在约束网络中传播，最终填充所有类型变量。由于网络中的循环，该过程会重复，直到所有类型变量收敛，或者因类型无法确定而失败。

类型统一总是返回一个更“通用”（加引号是因为允许不安全转换）的类型。类型将收敛到能够表示变量可以持有的所有可能值的最“通用”类型。由于统一永远不会在类型层次结构中向下移动，并且存在一个单一的顶级类型，即通用类型—object，因此类型推断保证会收敛。

类型推断失败可能由两个原因造成。第一个原因是用户错误，由于类型使用不正确。这种类型的错误在普通的 Python 执行中也会触发异常。第二个原因是使用了不支持的功能，但代码在普通的 Python 执行中是有效的。发生错误时，类型推断会将所有类型设置为对象类型。结果，Numba 将回退到对象模式（object-mode）。

由于函数可以重载，类型推断需要决定在每个调用点使用的类型签名。重载解析应用于调用模板（call-templates）中描述的被调用函数的所有已知重载版本。调用模板可以是具体的或抽象的。具体调用模板定义了所有可能签名的固定列表。抽象调用模板定义了计算接受签名的逻辑，并用于实现泛型函数。

Numba 编译的函数是泛型函数，因为它们能够编译新版本。当它看到一组新的参数类型时，会触发类型推断来验证并确定返回类型。当 Numba 编译的函数存在嵌套调用时，每个调用点都会触发类型推断。这对递归函数提出了一个问题，因为类型推断也会递归触发。目前，如果签名由用户注解，则支持简单的单一递归，这避免了类型推断中永远不会终止的无限递归。