27. 末尾呼び出し最適化

ECMAScript 6 は、コールスタックを増やすことなく関数呼び出しを行える末尾呼び出し最適化を提供しています。この章では、その仕組みと利点について説明します。

警告: 末尾呼び出し最適化は言語仕様の一部ですが、多くのエンジンでサポートされておらず、今後も変わらない可能性があります。

27.1. 末尾呼び出し最適化とは何か？
- 27.1.1. 通常の実行
- 27.1.2. 末尾呼び出し最適化
27.2. 関数呼び出しが末尾位置にあるかどうかの確認
- 27.2.1. 式中の末尾呼び出し
- 27.2.2. 文中の末尾呼び出し
- 27.2.3. 末尾呼び出し最適化は厳格モードでのみ可能
- 27.2.4. 落とし穴: 単独の関数呼び出しは決して末尾位置にない
27.3. 末尾再帰関数
- 27.3.1. 末尾再帰ループ

27.1 末尾呼び出し最適化とは何か？

大まかに言うと、関数が最後に行うことが別の関数を呼び出すことである場合、後者の関数は呼び出し元に戻る必要はありません。その結果、コールスタックに情報を保存する必要がなくなり、関数呼び出しは goto (ジャンプ) に近いものになります。この種の呼び出しを末尾呼び出しと呼びます。スタックを増やさないことを末尾呼び出し最適化 (TCO) と呼びます。

TCO をより深く理解するために、例を見てみましょう。最初に TCO なしで実行する方法を説明し、次に TCO ありで実行する方法を説明します。

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

27.1.1 通常の実行

ローカル変数と戻りアドレスをスタックに保存することで関数呼び出しを管理する JavaScript エンジンがあると仮定します。そのようなエンジンはどのようにコードを実行するでしょうか？

ステップ 1. 最初は、グローバル変数 id と f だけがスタック上にあります。

スタックエントリのブロックは、現在のスコープの状態 (パラメータを含むローカル変数) をエンコードし、スタックフレームと呼ばれます。

ステップ 2. C行で f() が呼び出されます。まず、戻る場所がスタックに保存されます。次に、f のパラメータが割り当てられ、実行がその本体にジャンプします。スタックは次のようになります。

現在、スタックには 2 つのフレームがあります。1 つはグローバルスコープ用 (下部) で、もう 1 つは f() 用 (上部) です。f のスタックフレームには、戻りアドレス、C行が含まれます。

ステップ 3. B行で id() が呼び出されます。ここでも、戻りアドレスと id のパラメータを含むスタックフレームが作成されます。

ステップ 4. A行で、結果 x が返されます。id のスタックフレームが削除され、実行が戻りアドレス、B行にジャンプします。（値を返す方法はいくつかあります。一般的な 2 つの解決策は、結果をスタックに残すか、レジスタで渡すことです。ここでは、この実行部分を無視します。）

スタックは次のようになります

ステップ 5. B行で、id によって返された値が f の呼び出し元に返されます。ここでも、最上位のスタックフレームが削除され、実行が戻りアドレス、C行にジャンプします。

ステップ 6. C行は値 3 を受信し、それをログに記録します。

27.1.2 末尾呼び出し最適化

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

前のセクションを見ると、不要なステップが 1 つあります。ステップ 5 です。B行で起こることは、id() によって返された値が C行に渡されることだけです。理想的には、id() がそれ自体で行うことができ、中間のステップはスキップできます。

B行の関数呼び出しを異なる方法で実装することで、これを実現できます。呼び出しが発生する前に、スタックは次のようになります。

呼び出しを調べると、それが f() の最後のアクションであることがわかります。id() が完了すると、f() によって実行される残りのアクションは、id の結果を f の呼び出し元に渡すことだけです。したがって、f の変数はもう必要なく、呼び出しを行う前にそのスタックフレームを削除できます。id() に渡される戻りアドレスは、f の戻りアドレス、C行です。id() の実行中、スタックは次のようになります。

次に、id() は値 3 を返します。それは、f の呼び出し元である C行に値を転送するため、f() の値を返すと言うことができます。

確認してみましょう。B行の関数呼び出しは末尾呼び出しです。このような呼び出しは、スタックを増やさずに実行できます。関数呼び出しが末尾呼び出しであるかどうかを調べるには、それが末尾位置 (つまり、関数内の最後のアクション) にあるかどうかを確認する必要があります。その方法については、次のセクションで説明します。

27.2 関数呼び出しが末尾位置にあるかどうかの確認

末尾呼び出しは、より効率的に実行できる関数呼び出しであることを学びました。しかし、末尾呼び出しとは何でしょうか？

まず、関数を呼び出す方法は問題ではありません。次の呼び出しはすべて、末尾位置に表示された場合に最適化できます。

関数呼び出し: func(···)
ディスパッチされたメソッド呼び出し: obj.method(···)
call() を介した直接メソッド呼び出し: func.call(···)
apply() を介した直接メソッド呼び出し: func.apply(···)

27.2.1 式中の末尾呼び出し

アロー関数は本体として式を持つことができます。したがって、末尾呼び出し最適化のために、式の中で関数呼び出しが末尾位置にある場所を特定する必要があります。次の式のみが末尾呼び出しを含むことができます。

条件演算子 (? :)
論理 OR 演算子 (||)
論理 AND 演算子 (&&)
コンマ演算子 (,)

それぞれについて例を見てみましょう。

27.2.1.1 条件演算子 (`? :`)

const a = x => x ? f() : g();

f() と g() の両方が末尾位置にあります。

27.2.1.2 論理 OR 演算子 (`||`)

const a = () => f() || g();

f() は末尾位置にありませんが、g() は末尾位置にあります。その理由を確認するには、次のコードを見てください。これは前のコードと同等です。

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

論理 OR 演算子の結果は f() の結果に依存するため、その関数呼び出しは末尾位置にありません (呼び出し元はそれを返す以外の操作を行います)。ただし、g() は末尾位置にあります。

27.2.1.3 論理 AND 演算子

const a = () => f() && g();

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

論理 AND 演算子の結果は f() の結果に依存するため、その関数呼び出しは末尾位置にありません (呼び出し元はそれを返す以外の操作を行います)。ただし、g() は末尾位置にあります。

27.2.1.4 コンマ演算子 (`,`)

const a = () => (f() , g());

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

27.2.2 文中の末尾呼び出し

文については、次のルールが適用されます。

次の複合文のみが末尾呼び出しを含むことができます。

ブロック ({} で区切られ、ラベルの有無にかかわらず)
if: 「then」句または「else」句のいずれか。
do-while、while、for: それらの本体。
switch: その本体。
try-catch: catch 句のみ。try 句には、最適化できないコンテキストとして catch 句があります。
try-finally、try-catch-finally: finally 句のみ。これは、最適化できない他の句のコンテキストです。

すべての原子 (非複合) 文のうち、return のみで末尾呼び出しを含めることができます。他のすべての文には、最適化できないコンテキストがあります。次の文は、expr が末尾呼び出しを含む場合、末尾呼び出しを含みます。

return «expr»;

27.2.3 末尾呼び出し最適化は厳格モードでのみ可能

非厳格モードでは、ほとんどのエンジンには、コールスタックを調べることができる次の 2 つのプロパティがあります。

func.arguments: func の直近の呼び出しの引数を含みます。
func.caller: func を直近に呼び出した関数を参照します。

末尾呼び出し最適化では、これらのプロパティは機能しません。それらが依存する情報が削除されている可能性があるためです。したがって、厳格モードではこれらのプロパティが禁止されており(言語仕様に記載されているように)、末尾呼び出し最適化は厳格モードでのみ機能します。

27.2.4 落とし穴: 単独の関数呼び出しは決して末尾位置にない

次のコードの関数呼び出し bar() は末尾位置にありません。

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

その理由は、foo() の最後のアクションが関数呼び出し bar() ではなく、(暗黙的に) undefined を返すことです。言い換えれば、foo() は次のようになります。

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

呼び出し元は、foo() が常に undefined を返すことを前提としています。末尾呼び出し最適化により、bar() が foo() の結果を返す場合、それは foo の動作を変えることになります。

したがって、bar() を末尾呼び出しにするには、次のように foo() を変更する必要があります。

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

27.3 末尾再帰関数

関数が、行う主な再帰呼び出しが末尾位置にある場合、その関数は末尾再帰です。

たとえば、次の関数は、A行の主な再帰呼び出しが末尾位置にないため、末尾再帰ではありません。

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

factorial() は、末尾再帰ヘルパー関数 facRec() を使用して実装できます。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)
    }
}

つまり、一部の非末尾再帰関数は、末尾再帰関数に変換できます。

27.3.1 末尾再帰ループ

末尾呼び出し最適化により、スタックを増やさずに再帰によってループを実装できます。次に 2 つの例を示します。

27.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

27.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

次へ: 28. プロキシを使用したメタプログラミング