NBEP 6：类型推断递归

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

简介

本文档提出了一种增强类型推断算法的方法，以支持递归而无需显式标注函数签名。因此，该提议使 Numba 能够在某些限制下对自递归和互递归函数进行类型推断。在实践中，通过指定编译顺序可以轻松克服这些限制。

现状

Numba 中对递归的支持目前仅限于具有显式函数类型标注的自递归。此限制源于无法确定递归调用的返回类型。这是因为被调用者要么是当前函数（对于自递归），要么是父函数（对于互递归），并且其类型推断过程已暂停，等待其被调用者的函数类型。这导致形成了循环依赖。例如，给定一个调用 bar() 的函数 foo()，而 bar() 又调用 foo()

def foo(x):
    if x > 0:
        return bar(x)
    else:
        return 1

def bar(x):
    return foo(x - 1)

函数 foo() 的类型推断过程依赖于 bar() 的类型推断过程，而 bar() 又依赖于 foo()。因此，foo() 依赖于自身，类型推断算法无法终止。

解决方案

提议的解决方案包含两个组成部分

引入一个在编译时跟踪编译函数的调用栈。
通过利用非递归控制流路径上的返回类型，允许对函数进行部分类型推断。

编译时调用栈存储正在编译的函数的类型信息。像普通的调用栈一样，每当一个函数被“调用”时，它会推入一个新的记录。由于这发生在编译时，一次“调用”会触发被调用者的编译。

为了检测递归，编译时调用栈会从底部向上搜索（栈向下增长）以查找与被调用者匹配的记录。由于该记录包含对类型推断状态的引用，因此可以恢复类型推断过程以确定返回类型。

回想一下，由于返回类型的循环依赖性，类型推断过程无法正常恢复。在实践中，我们可以假设一个有用的程序必须有一个终止条件，即一条不递归的路径。因此，类型推断过程可以通过使用非递归路径确定的返回类型，在递归调用处对返回类型进行初步猜测。这使得类型信息可以在递归路径上传播以生成最终返回类型，该类型用于在类型推断过程的后续迭代中完善类型信息。

下图说明了当编译器从 bar() 遇到对 foo() 的递归调用时编译时调用栈的状态。

此时，foo() 的类型推断过程已暂停，而 bar() 的类型推断过程处于活动状态。编译器通过搜索调用栈可以发现被调用者正在编译。由于知道这是一个递归调用，编译器可以通过忽略包含递归调用的路径来恢复对 foo() 的类型推断。这意味着只考虑 else 分支，在这种情况下我们可以很容易地判断 foo() 返回一个 int。然后编译器将 foo() 和 bar() 的初始返回类型设置为 int。随后的类型传播可以利用此信息完成这两个函数的类型推断，统一所有返回路径的返回类型。

限制

为了使提议的类型推断算法终止，它假设至少有一条控制路径会引导到返回语句而不会进行递归调用。如果不是这种情况，算法将引发异常，指示可能存在失控递归。

例如

@jit
def first(x):
    # The recursing call must have a path that is non-recursing.
    if x > 0:
        return second(x)
    else:
        return 1

@jit
def second(x):
    return third(x)

@jit
def third(x):
    return first(x - 1)

为了使类型推断算法成功完成，必须首先编译 first() 函数。如果首先编译任何其他函数，将导致类型推断失败。由于递归被调用者中缺少非递归出口，类型推断算法会将其视为失控递归。

例如，如果首先编译 second()，递归调用将转移到 first()。当编译器尝试恢复 second() 的类型推断过程时，它将无法找到非递归路径。

这是一个小限制，可以通过代码重构或以特定顺序预编译来轻松克服。