末尾呼び出し最適化と継続(CPS)

末尾呼び出しとは「戻り先で何もしない」呼び出し

再帰で触れたとおり、関数を呼ぶたびにコールスタックには戻り先や局所変数を保持するスタックフレームが積まれます。普通はこのフレームが呼び出し連鎖のあいだ生き続けるため、深い再帰はスタックを食いつぶします。

ところが、ある呼び出しが関数の末尾位置(tail position)にある場合、事情が変わります。末尾位置とは「その呼び出しが返した値を、呼び出し元がそのまま自分の戻り値として返すだけ」の位置です。つまり呼び出しから戻ってきた後に、加工も後処理も一切残っていない。

function f(n) {
  return g(n);     // 末尾呼び出し：g の結果をそのまま返すだけ
}
function h(n) {
  return g(n) + 1; // 末尾ではない：戻った後に +1 が残る
}

fではg(n)が戻った瞬間、fにはもう仕事がありません。であればfのスタックフレームはもはや不要です。gが最終的に返す値は、fを飛び越してfの呼び出し元へ直接返ってよいのです。

スタックフレーム再利用の原理

末尾呼び出し最適化(TCO / 末尾呼び出し除去)は、この「戻り先で何もしない」性質を使い、新しいフレームを積まずに現在のフレームを上書き再利用します。通常の呼び出しとの違いはコード生成のレベルで見ると明快です。

要は、末尾呼び出しは機械語レベルではcallではなくジャンプへ落ちます。戻りアドレスを積まないので、呼び出された関数がreturnするときは「今の関数の呼び出し元」へ直接戻る。結果として、何段呼び出しを連ねてもスタックは深くならず、末尾再帰はループと同じO(1)空間で回ります。

// 末尾再帰版の階乗：累算器 acc に途中結果を持ち回る
function fact(n, acc = 1) {
  if (n === 0) return acc;      // ベースケース
  return fact(n - 1, acc * n);  // 末尾位置：戻った後に掛け算が残らない
}

最初の素朴なreturn n * fact(n - 1)は、戻った後にn *が残るので末尾ではありません。累算器accに途中結果を退避することで、掛け算を呼び出しの前に済ませ、末尾位置を作り出しているのがポイントです。

末尾位置の判定は構文で決まる

「末尾かどうか」は実行時ではなく、構文的に静的に決まります。判定基準は「その式の値が、関数の戻り値として何も足されずに使われるか」です。代表的なパターンを整理します。

重要なのは、try/catchの内側にある呼び出しは末尾になり得ないことです。万一例外が飛んだら捕まえねばならず、そのためのハンドラ枠をスタックに残す義務があるからです。同様に、finallyを持つtry、ループ内で結果を集計する処理なども末尾位置を壊します。制御構文が末尾性に直結している好例です。

TCOは「言語仕様の保証」かどうかが分かれる

末尾呼び出しを最適化するかどうかは、言語と処理系の方針に強く依存します。ここを誤解すると本番でスタックオーバーフローを踏みます。

Pythonが採用しない理由は技術的不能ではなく設計判断です。フレームを使い回すと、エラー時のスタックトレースから途中の呼び出し履歴が消え、デバッグ性が落ちる。トレースの可読性を空間効率より優先した、という背景があります。

継続(CPS)：すべてを末尾呼び出しに変える

ここから一段抽象を上げます。継続(continuation)とは「今の計算が終わった後にやるべき残りの計算全体」を指す概念です。return g(x) + 1なら、g(x)の継続は「その結果に1を足して、関数から返す」という処理です。普通この継続はスタックに暗黙に積まれていますが、これを関数として明示的に引数で持ち回る書き方が**継続渡しスタイル(CPS / Continuation-Passing Style)**です。

// 直接スタイル（結果を return で返す）
function add(a, b) { return a + b; }
function square(x) { return x * x; }
const result = square(add(1, 2)); // 9

// CPS：戻り値を返さず、「次にやること」k を呼ぶ
function addK(a, b, k) { k(a + b); }
function squareK(x, k) { k(x * x); }
addK(1, 2, sum =>          // sum = 3
  squareK(sum, sq =>       // sq = 9
    console.log(sq)));     // ここが最終の継続

CPSでは関数は決して値を返しません。代わりに、計算結果を継続kに渡して呼ぶ。注目すべきは、addKの本体k(a + b)も、squareKの本体k(x * x)も、すべてが末尾呼び出しになっている点です。CPS変換を施すと、プログラム中のあらゆる呼び出しが末尾位置に移るため、TCOが効く処理系ではスタックを一切伸ばさずに任意の計算を実行できます。これがコンパイラ内部でCPSが重宝される理由の一つです。

CPSが一般化する制御フロー

継続を第一級の値として手に持てると、通常は言語機能として組み込まれている制御の飛びを、自前で構成できるようになります。CPSが「制御フローの一般化」と呼ばれるゆえんです。

• 早期脱出・例外：継続を呼ばずに別の継続を呼ぶことは、途中の残り計算を捨てて飛ぶこと、すなわち例外の送出や非局所脱出に相当します。成功継続と失敗継続の2本を渡せば、try/catchを関数だけで表現できます。
• 非同期：I/O完了後の処理を継続kとして渡し、完了時に呼んでもらえば、それはコールバックそのものです。awaitは本質的に「中断点で継続を登録し、完了したら再開する」ので、CPSの構文糖と見なせます。
• ジェネレータ・コルーチン：継続を保存しておき後で再呼び出しすれば、中断と再開（yield/resume）が実現します。

// 成功 ok と失敗 err の2継続で、例外なしに分岐を表現する
divK(a, b, ok, err):
  if b == 0:
    err("division by zero")   // 残りの計算（ok）を捨てて err へ飛ぶ
  else:
    ok(a / b)                 // 通常の継続へ

まとめ

末尾呼び出し最適化の核心は「呼び出しが末尾位置にあるなら、戻った後にやることが無いので現在のスタックフレームを再利用でき、深さがO(1)に保たれる」という一点です。末尾位置は構文的に静的判定でき、算術の残り・代入・例外ハンドラがあると壊れます。ただしTCOが保証されるかは言語仕様しだいで、JavaScriptやPythonでは末尾再帰でも安全にはなりません。

そして継続(CPS)は、この「戻った後にやること」を関数として明示化し、すべての呼び出しを末尾化する変換です。例外・非同期・ジェネレータといった制御の飛びを単一の枠組みで説明でき、ラムダ計算を土台に処理系の内部で広く使われています。直接スタイルで書くコードの裏に、こうした継続の機械が動いていると見えると、非同期やコルーチンの挙動まで一本の線で理解できます。