末尾再帰と変換

多くのプログラムにはループが含まれており、これが合計処理時間のかなりの部分を占めます。多くの場合、これらのループは複数の変数を繰り返し更新し、また各変数の更新は更新される他の変数の値に依存します。

これらの変数は、反復が末尾再帰関数 として表現されている場合、関数に渡されるパラメーターとして表現されます。(注意: ある再帰呼び出しの戻り値が、その関数を呼び出す側の関数の値として直接戻される場合、その呼び出しを末尾再帰呼び出しと言います。呼び出しを行うときに呼び出し元関数のコンテキストを記憶している必要はありません。)

こうした特性があるため、末尾再帰関数とループの間にはちょうどよい対応関係があります。つまり、それぞれの再帰呼び出しは、単純に、ループをもう1回反復することであると考えることができます。しかし、変数パラメーターの値は一度に再帰呼び出しに送られるため、ループの場合よりも簡単にそれらの値を更新することができます。さらに、多くの場合、使いにくいブレーク・ステートメントの代わりに、関数からの単純な戻り値を使用することができます。

しかしJavaプログラミングでは、この方法で反復を表現すると、大量の再帰呼び出しによってスタックがオーバーフローする恐れがあるため、効率が悪くなる可能性があります。

解決策は比較的単純です。これらの末尾再帰関数は、実際には、ループをより簡単に書くため手段にすぎないので、コンパイラーによって末尾再帰関数が自動的にループに変換されればよいのです。それにより、両方の方法の良いところを十分に活用できます。

しかし、末尾再帰関数を単純なループに自動的に変換する方法はよく知られているにもかかわらず、Java仕様ではこの変換を行うことが要件となっていません。おそらく、これが要件となっていない理由の1つは、一般にオブジェクト指向言語ではこの変換を静的に行うことができないためであると思われます。したがって、末尾再帰関数から単純なループへの変換は、JITコンパイラーによって動的に行う必要があります。

なぜこのようになるのかを理解するために、次に、複数の整数からなる集合に、反復子のエレメントを乗算するサンプルのバグをあげます。

次のプログラムにはバグが含まれているため、実行時に例外がthrowされます。しかし、このシリーズの以前の多くの記事で示したように、プログラムがthrowする例外は、(バグの種類を識別する手掛かりであるのと同時に) バグがプログラムのどこにあるのかを判断するための貴重な手掛かりであるので、コンパイラーによってプログラムが変更されて、その変更されたコードが異なる例外をthrowするようになることは望ましくありません。

                
import java.util.Iterator;

public class Example {

  public int product(Iterator i) {
    return productHelp(i, 0);
  }

  int productHelp(Iterator i, int accumulator) {
    if (i.hasNext()) {
      return productHelp(i, accumulator * ((Integer)i.next()).intValue());
    }
    else {
      return accumulator;
    }
  }
}

product メソッドのバグに注意してください。このメソッドはaccumulatorの値 "0" で productHelp を呼び出しています。accumulatorの値は "1" でなければなりません。そうしないと、クラス Example のどのインスタンスで product を呼び出しても、どのようなIteratorが渡されたかにかかわらず、結果が "0" になってしまいます。

リスト2に示すように、このバグはたまたま修正され、一方でクラス Example のサブクラスが作成されていたとします。

                
import java.util.*;

class Example {

  public int product(Iterator i) {
    return productHelp(i, 1);
  }

  int productHelp(Iterator i, int accumulator) {
    if (i.hasNext()) {
      return productHelp(i, accumulator * ((Integer)i.next()).intValue());
    }
    else {
      return accumulator;
    }
  }
}


// And, in a separate file:

import java.util.*;

public class Example2 extends Example {
  int productHelp(Iterator i, int accumulator) {
    if (accumulator < 1) {
      throw new RuntimeException("accumulator to productHelp must be >= 1");
    }
    else {
      return super.productHelp(i, accumulator);
    }
  }

  public static void main(String[] args) {
    LinkedList l = new LinkedList();
    l.add(new Integer(0));
    new Example2().product(l.listIterator());
  }
}

クラス Example2 のオーバーライドされた productHelp メソッドは、accumulatorが "1" 未満の場合に実行時例外をthrowすることにより、 productHelp に対する上記のような不適切な呼び出しを捕そくしようとします。残念ながら、このようにすることにより新しいバグが生まれます。 Iterator に "0" のインスタンスが含まれていると、 productHelp は再帰呼び出しを行ったときにクラッシュしてしまいます。

ここで、クラス Example2 のメイン・メソッドで Example2 のインスタンスが作成され、その product メソッドが呼び出されていることに注意してください。このメソッドに渡される Iterator には "0" が含まれるので、このプログラムはクラッシュすることになります。

ただし、クラス Example 内の productHelp は、確かに末尾再帰的であることはわかります。1つの静的コンパイラーが、リスト3のように、このメソッドの本体をループに変換したとします。

                
  int productHelp(Iterator i, int accumulator) {
    while (i.hasNext()) {
      accumulator *= ((Integer)i.next()).intValue();
    }
    return accumulator;
  }

変換の後、productHelp に対して最初の呼び出しを行うと、スーパー・メソッドが呼び出されます。スーパー・メソッドは、単に、その結果を計算するためにIteratorをループします。例外はthrowされません。

このコードを2つの異なる静的コンパイラーでコンパイルして、一方の場合には生成されるコードが例外をthrowし、もう一方の場合には例外をthrowしない、ということになると非常に混乱します。

上に戻る

JITが変換を行うかどうか?

リスト3の例で示されているように、静的コンパイラーがJava言語のセマンティクスを維持しながらJavaコードで末尾再帰の変換を行うことは期待できません。静的コンパイルではなく、JITによる動的コンパイルが必要となります。JVMによって、JITがこれを行う場合と行わない場合があります。

使用しているJITが末尾再帰メソッドを変換するかどうかは、次の小さなテスト・クラスをコンパイルして実行してみるとわかります。

                
public class TailRecursionTest {

  private static int loop(int i) {
    return loop(i);
  }

  public static void main(String[] args) {
    loop(0);
  }
}

このクラスの loop メソッドについて、しばらく考えてみましょう。このメソッドは、それ自体を可能な限り、再帰的に呼び出します。このメソッドは戻ることがなく、外部の変数にどのような影響も与えることがないため、リスト5のように本体を置き換えても、プログラムのセマンティクスが保持されます。

                
public class TailRecursionTest {

  private static int loop(int i) {
    while (true) {
    }
  }

  public static void main(String[] args) {
    loop(0);
  }
}

これは、実際に、十分な機能を持つコンパイラーならば行える変換そのものです。

使用しているJITコンパイラーが末尾再帰呼び出しを反復に変換する場合は、このプログラムはいつまでも同じように実行され続けます。このプログラムに必要なメモリーは少なく、時間がたっても増えません。

一方、JITが変換を行わない場合は、プログラムはすぐにスタック・スペースを使い尽くして、スタック・オーバーフロー・エラーを報告します。

このプログラムをいくつかのJava SDKで実行したところ、驚くべき結果が得られました。SunのHotspot JVMのバージョン1.3で実行してみると、Hotspotはこの変換を行わないことが分かりました。デフォルト設定の場合、私のマシンではスタック・スペースが1秒足らずで使い尽くされてしまいました。

一方、IBMのJVMのバージョン1.3は問題なく実行されました。つまり、この方法でコードを変換するこということになります。

上に戻る

まとめ

私たちの書いたコードが、常に、末尾再帰呼び出しを変換するJVMで実行されることは期待できない、ということは覚えておかなければなりません。したがって、さまざまなJVMで納得できるパフォーマンスが得られるようにするには、末尾再帰的パターンを、反復のスタイルに適合するようなコードとして書くことを、常に心がける必要があります。

しかし、注意が必要です。上記の例が示すように、この方法でのコード変換は、人間の手によって行う場合にも、ソフトウェアによって行う場合にも、バグを発生させる恐れがきわめて高いからです。

参考文献

• Hotspot の詳細については、Sunのドキュメンテーションを参照してください。
  
  
• EricのJavaコード診断に関する全シリーズを参照してください。
  • バグ・パターン： Javaプログラムで頻発しがちなバグの分析と修正
  • 「宙ぶらりん複合型」バグ・パターン： ヌル・ポインター例外の最もよくある原因を鎮圧する
  • 「ヌル・フラグ」バグ・パターン： 例外状況を表すフラグとしてヌル・ポインターを使うことを避ける
  • 「二段たどり」バグ・パターン： 再帰的なクラス・キャストという概念上のエラーを最初から克服する
  • うそつきビューのバグ・パターン： GUIの最良の友になってうそつきビューを暴き出しましょう
  • 破壊工作データのバグ・パターン： 隠れたデータ爆弾が奇妙なクラッシュの原因かもしれません
  • 破綻したディスパッチのバグ・パターン： 引き数のアップ・キャストによって、不正確なメソッドの呼び出しを修正する
  
  
  

著者について

この記事を評価する

コメント

上に戻る

目次

• 末尾再帰と変換
• JITが変換を行うかどうか?
• まとめ
• 参考文献
• 著者について
• コメント