[Kotlin] Kotlinで末尾再帰最適化 その2

その1ではtailrecを使って、フィボナッチ数を生成してみたけど、実際最適化されているのだろうか？

ホントか？

今度は実行用のjarではなく、クラスファイル単体を作成する。

$ kotlinc fibonacci.kt

とすると、FibonacciKt.classが作成されるので、これをjavapで見てみる。

$ javap -p -c FibonacciKt.class

Compiled from "fibonacci.kt"
public final class FibonacciKt {
(中略)
  public static final java.util.List fibonacci0(int, java.util.List);
    Code:
       0: aload_1
       1: ldc           #61                 // String list
       3: invokestatic  #15                 // Method kotlin/jvm/internal/Intrinsics.checkParameterIsNotNull:(Ljava/lang/Object;Ljava/lang/String;)V
       6: aload_1
       7: invokeinterface #65,  1           // InterfaceMethod java/util/List.size:()I
      12: iload_0
      13: if_icmplt     20
      16: aload_1
      17: goto          45
      20: aload_1
      21: checkcast     #67                 // class java/util/Collection
      24: aload_1
      25: iconst_2
      26: invokestatic  #71                 // Method kotlin/collections/CollectionsKt.takeLast:(Ljava/util/List;I)Ljava/util/List;
      29: checkcast     #73                 // class java/lang/Iterable
      32: invokestatic  #77                 // Method kotlin/collections/CollectionsKt.sumOfInt:(Ljava/lang/Iterable;)I
      35: invokestatic  #42                 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
      38: invokestatic  #81                 // Method kotlin/collections/CollectionsKt.plus:(Ljava/util/Collection;Ljava/lang/Object;)Ljava/util/List;
      41: astore_1
      42: goto          0
      45: areturn
}

重要そうなところを抜き出すと

       7: invokeinterface #65,  1           // InterfaceMethod java/util/List.size:()I

で、list.sizeを呼び出して

      13: if_icmplt     20

list.size < n なら 20:へジャンプ。ループが継続する方がこっち。

      17: goto          45

20:へジャンプしない場合はここに来て、45:へジャンプ。これで、ループ終了。

      42: goto          0

ループ最下部。0:へジャンプして、ループ継続。

確かに fibonacci0 の再帰呼び出しが存在せず、ループに展開されている。

tailrecがない場合

今度は fibonacci0 関数から tailrec を取ってクラスファイルを作ってみる。

fibonacci.kt(一部)

fun fibonacci0(n: Int, list: List): List
    = if (list.size >= n) list
      else fibonacci0(n, list.plus(list.takeLast(2).sum()))

$ kotlinc fibonacci.kt
$ javap -p -c FibonacciKt.class

Compiled from "fibonacci.kt"
public final class FibonacciKt {
(中略)
  public static final java.util.List fibonacci0(int, java.util.List);
    Code:
       0: aload_1
       1: ldc           #61                 // String list
       3: invokestatic  #15                 // Method kotlin/jvm/internal/Intrinsics.checkParameterIsNotNull:(Ljava/lang/Object;Ljava/lang/String;)V
       6: aload_1
       7: invokeinterface #65,  1           // InterfaceMethod java/util/List.size:()I
      12: iload_0
      13: if_icmplt     20
      16: aload_1
      17: goto          45
      20: iload_0
      21: aload_1
      22: checkcast     #67                 // class java/util/Collection
      25: aload_1
      26: iconst_2
      27: invokestatic  #71                 // Method kotlin/collections/CollectionsKt.takeLast:(Ljava/util/List;I)Ljava/util/List;
      30: checkcast     #73                 // class java/lang/Iterable
      33: invokestatic  #77                 // Method kotlin/collections/CollectionsKt.sumOfInt:(Ljava/lang/Iterable;)I
      36: invokestatic  #42                 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
      39: invokestatic  #81                 // Method kotlin/collections/CollectionsKt.plus:(Ljava/util/Collection;Ljava/lang/Object;)Ljava/util/List;
      42: invokestatic  #55                 // Method fibonacci0:(ILjava/util/List;)Ljava/util/List;
      45: areturn
}

変数のロード処理なんかが変わっている箇所もあるけど、一番重要なのは最後のリターンの直前が

      42: goto          0

ではなく、fibonacci0の呼び出しに変わっているところ。

      42: invokestatic  #55                 // Method fibonacci0:(ILjava/util/List;)Ljava/util/List;

確かに tailrec を付けていない場合は、通常の再帰処理になっている。