末尾呼び出し最適化¶

現在の状態¶

検出: ✅ 実装済み 変換: ✅ 実装済み

Onionコンパイラは、コンパイル時に末尾再帰メソッドを検出し、while(true) ループへと書き換えます。これにより、末尾位置での自己再帰呼び出しがJVMのコールスタックを消費しなくなり、深い再帰（例: 10,000回以上の呼び出し）による StackOverflowError を防ぎます。

このフェーズが書き換えるのは直接の自己再帰のみです。複数のメソッド間で成立する相互再帰は、パイプライン上でこの直後に実行される MutualRecursionOptimization が別途扱います。

仕組み¶

検出フェーズ¶

コンパイラは各メソッドを分析して末尾再帰呼び出しを特定します。

末尾位置の分析: 最後の文（または制御フローの分岐内の文）が自己呼び出しかどうかを確認
再帰的探索: StatementBlock と IfStatement ノードを再帰的に検索して末尾呼び出しを見つける
メソッド一致の確認: 呼び出し対象が現在のメソッドと一致することを確認（同じ名前、クラス、パラメータ型）
ディスパッチ安全性: オーバーライドされ得ないメソッド（private・static・final）のみが対象です。public なオーバーライド可能メソッド内の自己呼び出しは、実行時にサブクラスの override へ動的ディスパッチされる可能性があるため、本体をループへ書き換えると挙動が黙って変わってしまいます。そのため対象から除外されます。
相互再帰の除外: @TailRecursive アノテーションが付いたメソッド（相互再帰の参加者を示す）はここではスキップされ、MutualRecursionOptimization に委ねられます。

サポートされるパターン¶

検出器は以下の末尾再帰を認識します。

直接末尾呼び出し: return method(args)
条件分岐: if文の then と else の両方の分岐
ネストしたブロック: 文ブロックを再帰的に検索

例¶

def factorial(n: Int, acc: Int): Int {
  if (n <= 1) {
    return acc
  }
  return factorial(n - 1, n * acc)  // ✅ 検出され、変換される
}

変換フェーズ¶

末尾再帰かつ対象条件を満たすと確認されたメソッドは、以下のように書き換えられます。

ループ変数の割り当て: 各パラメータに対応するループ変数を用意する
パラメータの書き換え: メソッド本体内のパラメータ参照をすべて対応するループ変数の参照に書き換える
ループの構築: （書き換え後の）本体を while(true) ループで囲む
末尾呼び出しの置換: 各末尾呼び出しをループ変数への代入に置き換え、そのままループが継続する（continue キーワードは不要 — while(true) の本体末尾まで到達すると自然に再度ループへ入る）

// 変換前
def factorial(n: Int, acc: Int): Int {
  if (n <= 1) return acc
  return factorial(n - 1, n * acc)
}

// 変換後（概念的には）
def factorial(n: Int, acc: Int): Int {
  while (true) {
    if (n <= 1) return acc
    val n_next = n - 1
    val acc_next = n * acc
    n = n_next
    acc = acc_next
    // ループ継続
  }
}

`@TailRecursive` による相互再帰¶

互いに末尾呼び出しし合う2つ以上のメソッド（isEven が isOdd を呼び、isOdd が isEven を呼ぶ）は、上記の検出フェーズでは書き換えられません。各呼び出しの対象は「別のメソッド」であり、「自己呼び出し」チェックには一致しないためです。グループの全メソッドに @TailRecursive を付けると、MutualRecursionOptimization がそれらを 1つの状態機械メソッドへ統合します。

class Parity {
private:
  @TailRecursive
  def isEven(n: Int): Boolean {
    if n == 0 { return true }
    return isOdd(n - 1)
  }

  @TailRecursive
  def isOdd(n: Int): Boolean {
    if n == 0 { return false }
    return isEven(n - 1)
  }
public:
  def check(n: Int): Boolean = isEven(n)
}

グループが最適化されるのは、すべての条件を満たしたときだけです（MutualRecursionOptimization.validateGroup）。

グループ内の全メソッドが private であること（直接 TCO と同じ理由: public メソッドはオーバーライドされ得るため、共有ループへ書き換えると挙動が黙って変わるおそれがある）
全メソッドの 戻り値の型が同じ であること
全メソッドの パラメータ数と型が同じ であること
グループ内メソッドからの末尾呼び出しが、すべて同じグループ内の別メソッドを対象としていること（グループ外への末尾呼び出しがあると対象から外れる）

検証に失敗したグループはエラーにはならず、アノテーションが単に効かないだけ です。メソッド同士は通常の（末尾でない）呼び出しとして呼び合い続けます。アノテーションを見ても何も指摘されないため気づきにくく、十分深い再帰で初めて実行時に JVM スタックが溢れて発覚します。これをコンパイル時に検出できるよう、コンパイラは最適化できなかった @TailRecursive グループの各メソッドについて W0016 を出力し、満たせなかった条件（例: "All methods must be private for mutual recursion optimization"）を示します。意図的に最適化しないままにする場合は --Wno で抑制してください。

最適化の様子を確認する¶

--verbose フラグを付けてコンパイルすると、どのメソッドが変換され、どのメソッドがなぜスキップされたかを追跡できます。

sbt 'runScript --verbose your_program.on'

出力例:

[TCO] Method YourClass.factorial: hasTailCall=true
[TCO] Optimizing tail-recursive method: YourClass.factorial
[TCO] Skipping overridable method: YourClass.someOverridableMethod
[TCO] Skipping @TailRecursive annotated method: YourClass.mutuallyRecursiveMethod

実装の詳細¶

ファイルの場所¶

ソース: src/main/scala/onion/compiler/optimization/TailCallOptimization.scala
パイプライン統合: Typing と AsmCodeGeneration の間、MutualRecursionOptimization の直前で実行される

コンパイラパイプライン¶

Parsing → Rewriting → Typing → [TailCallOptimization] → MutualRecursionOptimization → AsmCodeGeneration

テスト¶

スペック: src/test/scala/onion/compiler/tools/TailCallOptimizationSpec.scala
src/test/run/ 内のサンプルプログラム: tail_recursion_factorial.on、tail_recursion_simple.on、tail_recursion_direct.on、tail_recursion_private.on、tail_recursion_public.on、tail_recursion_test.on

参考¶

Tail Call Optimization (Wikipedia)
関連実装: Scala の @tailrec アノテーション
同様の最適化を持つ関数型言語: Haskell、Scheme、OCaml