NBEP 6: 类型递归

作者:: 林思宽
日期:: 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() 的类型推断过程时，它将无法找到非递归路径。

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