[译] ES6中的尾调用优化

原文:http://exploringjs.com/es6/ch_tail-calls.html

ECMAScript 6 提供了尾调用优化(tail call optimization)功能,以使得对某些函数的调用不会造成调用栈(call stack)的增长。本文解释了这项功能,以及其带来的好处。

  • 1. 什么是尾调用优化
    • 1.1. 正常的执行
    • 1.2. 尾调用优化
  • 2. 检查函数调用是否在尾部发生
    • 2.1. 表达式中的尾调用
    • 2.2. 声明语句中的尾调用
    • 2.3. 尾调用优化只在严格模式下有效
    • 2.4. 单独的函数调用不算在尾部
  • 3. 尾递归函数
    • 3.1. 尾递归循环

1. 什么是尾调用优化?

粗略的来说,如果当一个函数所做的最后一件事是调用了另一个函数,而后者不需要返回调用者函数中再去做任何动作时;以及由此可知,在这种情况下没有调用者的额外信息需要被储存在调用栈(call stack)上,函数间的调用更像一种goto跳转的时候 -- 这种调用就被成为尾调用(tail call),此时使得内存栈不再增长的行为就称为尾调用优化(TCO - tail call optimization)。

举个例子来更好的理解下TCO。首先说明一下是否用TCO的区别:

function id(x) {
    return x; // (A)
}
function f(a) {
    const b = a + 1;
    return id(b); // (B)
}
console.log(f(2)); // (C)

1.1 正常的执行

假设有一个JS引擎通过 存储本地变量并返回栈上的地址 来管理方法调用。该引擎会如何执行上述代码呢?

Step 1. 最初,栈上只有全局变量idf

栈会对当前作用域的状态(包括本地变量、参数等)进行编码,形成被称为“调用帧”(frame)的一块。

Step 2. 在代码中的C行,f()被调用:首先,将要return到的位置被记录在栈中;然后f的参数a被分配并执行。

栈现在看起来是这样的:共有两个调用帧,一个是位于底部的全局作用域,另一个是其上方 的f()

Step 3. id() 在B行中被调用。再次形成了一个调用帧,包含了id将要返回到的地址及其参数x被分配和调用的值。

Step 4. 在行A,结果x被返回。id的调用栈被移除,执行过程跳转到其调用帧中存储的要return的位置,也就是行B。(处理返回值有多种途径,最常见的两种是将结果留在栈中和在寄存器中处理之,此处按下不表)

栈现在是这副模样的了:

Step 5. 在行B中,从id中返回的值将继续返回给f的调用者。照旧,最上面的调用帧被移除,执行过程跳转到要return的位置 -- 行C。

Step 6. 行C接收到返回值3并完成打印工作。

1.2 尾调用优化

function id(x) {
    return x; // (A)
}
function f(a) {
    const b = a + 1;
    return id(b); // (B)
}
console.log(f(2)); // (C)

回顾上个章节的过程,其实 step 5 是多余的。行B中发生的全部事情其实只不过是把id()中返回的值传递给行C罢了。理想情况是,id()可以自行完成这一步,而跳过二传手 step 5。

可以通过对行B的函数调用采取不一样的实现方式来达成以上目的。栈在调用发生前是这样的:

检查这次调用就会发现,它是f()的最后一个行为。一旦id()完成,f()剩余执行的唯一行为就是把前者的结果返回给自身的调用者。因此,f中的变量就不需要了,其调用帧也就可以在这次调用之前被移除了。赋给id()的将要return地址直接可以是f的return地址,也就是行C了。在id()执行期间,栈看起来就是这样的:

id()返回了数值3,或者可以说它为f()返回了这个值;因为通过行C,该值被传递给了f的调用者。

不难发现,行B的函数调用就是一个尾调用。这样的调用可以在栈0增长的情况下完成。要判断函数调用是否是尾调用,必须检查其是否处于尾部(比如最后一个行为)。下一章节将讲述如何做到。

2. 检查函数调用是否在尾部发生

我们已经了解到尾调用可以被更有效率的执行,那么如何认定一个尾调用呢?

首先,调用函数的方式是无所谓的。下列调用如果出现在尾部,就都可以被优化:

  • 函数调用: func(···)
  • 方法调用: obj.method(···)
  • 通过 call(): func.call(···)
  • 通过 apply(): func.apply(···)

2.1 表达式中的尾调用

箭头函数可以用表达式作为方法体。对于尾调用优化,因此必须找出表达式中函数调用的尾部。只有下列表达式会包含尾调用:

  • 条件操作符 (? :)
  • 逻辑或 (||)
  • 逻辑与 (&&)
  • 逗号 (,)

分别来举例看一下:

2.1.1 条件操作符 (? :)
const a = x => x ? f() : g();

f() 和 g() 都在尾部。

2.1.2 逻辑或 (||)
const a = () => f() || g();

f() 不在尾部,g() 在尾部。至于为什么,看看下面的等价代码就知道了:

const a = () => {
    const fResult = f(); // not a tail call
    if (fResult) {
        return fResult;
    } else {
        return g(); // tail call
    }
};

逻辑或操作符的结果依赖于f()的结果,所以是g(),而非f()的方法调用(调用者在其返回后又做了些什么)处于尾部。

2.1.3 逻辑与 (&&)
const a = () => f() && g();

同样,f() 不在尾部,g() 在尾部:

const a = () => {
    const fResult = f(); // not a tail call
    if (!fResult) {
        return fResult;
    } else {
        return g(); // tail call
    }
};

理由和逻辑或相同。

2.1.4 逗号 (,)
const a = () => (f() , g());

依然是,f() 不在尾部,g() 在尾部:

const a = () => {
    f();
    return g();
}

2.2 声明语句中的尾调用

对于声明语句,下列规则适用,只有这些混合声明语句会包含尾调用:

  • 块 (用 {}界定,有时会有一个label)
  • if: 包括逻辑上的 “then” 和 “else” 子句
  • do-while, while, for: 在其循环体中
  • switch: 在其判断体中
  • try-catch: 只在 catch 子句中,try 子句将 catch 子句作为上下文,导致无法被优化
  • try-finally, try-catch-finally: 只在 finally 子句中,它会成为其他子句的上下文

对于所有原子(非混合)声明语句,只有return会包含尾调用。其他此类声明语句都有无法被优化的上下文。如下所示,当expr部分包含尾调用时,下列声明语句就包含尾调用。

return «expr»;

2.3 尾调用优化只在严格模式下有效

在非严格模式下,大多数引擎会包含下面两个属性,以便开发者检查调用栈:

  • func.arguments: 表示对 func最近一次调用所包含的参数
  • func.caller: 引用对 func最近一次调用的那个函数

在尾调用优化中,这些属性不再有用,因为相关的信息可能以及被移除了。因此,严格模式(strict mode)禁止这些属性,并且尾调用优化只在严格模式下有效。

2.4 单独的函数调用不算在尾部

下面的代码中,对bar() 的函数调用不算在尾部:

function foo() {
    bar(); // this is not a tail call in JS
}

原因在于foo()的最后一个动作不是对bar() 的函数调用,而是隐式的返回了undefined。换句话说,foo()的行为如下:

function foo() {
    bar();
    return undefined;
}

调用者可以依赖一个总是返回undefinedfoo();但如果对bar()做了尾调用优化,那么其返回值就有可能改变了foo的行为。

因此,如果想要bar()成为一个尾调用,就得改成这样:

function foo() {
    return bar(); // tail call
}

3. 尾递归函数

如果一个函数的主递归调用发生在尾部,那这个函数就是尾递归。

譬如,下面的阶乘函数不是尾递归,因为行A中的主递归调用不在尾部:

function factorial(x) {
    if (x <= 0) {
        return 1;
    } else {
        return x * factorial(x-1); // (A)
    }
}

可以用一个辅助方法facRec()来使factorial()成为尾递归。行A中的主递归调用处于尾部了:

function factorial(n) {
    return facRec(n, 1);
}
function facRec(x, acc) {
    if (x <= 1) {
        return acc;
    } else {
        return facRec(x-1, x*acc); // (A)
    }
}

这样,一些非尾递归的函数就可以转化成尾递归了。

3.1 尾递归循环

尾调用优化使得在递归循环中不增长调用栈成为可能。下面举两个例子。

3.1.1 forEach()
function forEach(arr, callback, start = 0) {
    if (0 <= start && start < arr.length) {
        callback(arr[start], start, arr);
        return forEach(arr, callback, start+1); // tail call
    }
}
forEach(['a', 'b'], (elem, i) => console.log(`${i}. ${elem}`));

// Output:
// 0. a
// 1. b
3.1.2 findIndex()
function findIndex(arr, predicate, start = 0) {
    if (0 <= start && start < arr.length) {
        if (predicate(arr[start])) {
            return start;
        }
        return findIndex(arr, predicate, start+1); // tail call
    }
}
findIndex(['a', 'b'], x => x === 'b'); // 1



(end)

----------------------------------------

长按二维码或搜索 fewelife 关注我们哦



评论
说说你的看法