5

我正在研究 scala TCO 并编写了以下代码

import scala.annotation.tailrec
final def tailReccursionEx(str:String):List[String]={

  @tailrec 
  def doTailRecursionEx(str:String,pos:Int,accu:List[String]):List[String]={
    if(pos==str.length) return accu
    else{
      doTailRecursionEx(str,pos+1,accu++accu.foldLeft(List[String](str(`pos`).toString)){
                                            (l,ch)=>l:+ch+str(`pos`)})
  }
}

  doTailRecursionEx(str,0,List[String]())
}

我已经通过了@tailrec 测试，并且我相信我的函数是自递归尾调用。然而，当我查看 java 字节码时

javap -c -private RecursionEx\$\$anonfun\$doTailRecursionEx\$1\$1

对于自递归函数，我没有看到 TCO 承诺的goto。这是字节码。

public RecursionEx$$anonfun$doTailRecursionEx$1$1(java.lang.String, int);
  Code:
   0:   aload_0
   1:   aload_1
   2:   putfield    #35; //Field str$2:Ljava/lang/String;
   5:   aload_0
   6:   iload_2
   7:   putfield    #41; //Field pos$1:I
   10:  aload_0
   11:  invokespecial   #93; //Method scala/runtime/AbstractFunction2."<init>":()V
   14:  return

}
4

1 回答 1

10

我认为您需要javap在不同的生成类文件上运行。您目前正在检查的文件对应于您作为foldLeft. 如果您尝试查看“RecursionEx$.class”文件，您应该会看到尾调用递归。当我编译代码时：

import scala.annotation.tailrec

object RecursionEx {
    @tailrec
    final def doTailRecursionEx(str: String, pos: Int, accu: List[String]): List[String] = {
        if (pos == str.length) return accu
        doTailRecursionEx(str, pos + 1 , accu ++ accu.foldLeft(List[String](str(`pos`).toString)) {
                            (l, ch) => l :+ ch + str(`pos`)
                        })
    }
    def main(args: Array[String]) {
        doTailRecursionEx("mew",0,List[String]())
    }
}

然后运行javap -c -private RecursionEx$我看到以下代码的相关部分：

public final scala.collection.immutable.List doTailRecursionEx(java.lang.String, int, scala.collection.immutable.List);

  Code:
   0:   iload_2
   1:   aload_1
   2:   invokevirtual   #21; //Method java/lang/String.length:()I
   5:   if_icmpne   10
   8:   aload_3
   9:   areturn
   10:  iload_2
   11:  iconst_1
   12:  iadd
   13:  aload_3
   14:  aload_3
   15:  getstatic   #26; //Field scala/collection/immutable/List$.MODULE$:Lscala/collection/immutable/List$;
   18:  getstatic   #31; //Field scala/Predef$.MODULE$:Lscala/Predef$;
   21:  iconst_1
   22:  anewarray   #17; //class java/lang/String
   25:  dup
   26:  iconst_0
   27:  getstatic   #31; //Field scala/Predef$.MODULE$:Lscala/Predef$;
   30:  aload_1
   31:  invokevirtual   #35; //Method scala/Predef$.augmentString:(Ljava/lang/String;)Lscala/collection/immutable/StringOps;
   34:  iload_2
   35:  invokeinterface #41,  2; //InterfaceMethod scala/collection/immutable/StringLike.apply:(I)C
   40:  invokestatic    #47; //Method scala/runtime/BoxesRunTime.boxToCharacter:(C)Ljava/lang/Character;
   43:  invokevirtual   #53; //Method java/lang/Object.toString:()Ljava/lang/String;
   46:  aastore
   47:  checkcast   #55; //class "[Ljava/lang/Object;"
   50:  invokevirtual   #59; //Method scala/Predef$.wrapRefArray:([Ljava/lang/Object;)Lscala/collection/mutable/WrappedArray;
   53:  invokevirtual   #62; //Method scala/collection/immutable/List$.apply:(Lscala/collection/Seq;)Lscala/collection/immutable/List;
   56:  new #64; //class RecursionEx$$anonfun$doTailRecursionEx$1
   59:  dup
   60:  aload_1
   61:  iload_2
   62:  invokespecial   #67; //Method RecursionEx$$anonfun$doTailRecursionEx$1."<init>":(Ljava/lang/String;I)V
   65:  invokeinterface #73,  3; //InterfaceMethod scala/collection/LinearSeqOptimized.foldLeft:(Ljava/lang/Object;Lscala/Function2;)Ljava/lang/Object;
   70:  checkcast   #75; //class scala/collection/TraversableOnce
   73:  getstatic   #26; //Field scala/collection/immutable/List$.MODULE$:Lscala/collection/immutable/List$;
   76:  invokevirtual   #79; //Method scala/collection/immutable/List$.canBuildFrom:()Lscala/collection/generic/CanBuildFrom;
   79:  invokevirtual   #85; //Method scala/collection/immutable/List.$plus$plus:(Lscala/collection/TraversableOnce;Lscala/collection/generic/CanBuildFrom;)Ljava/lang/Object;
   82:  checkcast   #81; //class scala/collection/immutable/List
   85:  astore_3
   86:  istore_2
   87:  goto    0

goto正如您所期望的那样，最后是a 。

于 2011-11-21T22:53:38.833 回答