12

@tailrec注釈を使用して読んで、末尾再帰メソッドを使用しました。私はそれを説明する多くのリンクを調べました。たとえば、自己呼び出し関数の場合にのみ機能し、オーバーライドするべきではありません。

どこでも、compiler optimizes. しかし、末尾再帰にするためにコンパイラが行う魔法/概念は何ですか。以下の単純な関数の場合、コンパイラは何をしますか:

@tailrec def fact(acc: Int, n: Int): Int = {
  if (n <= 1) acc
  else fact(n * acc, n - 1)
}
fact(1,10)

つまり、それを繰り返し呼び出してから最終値を返すループに変換しますか? それを説明する紙へのリンクはありますか

4

2 に答える 2

12

あなたの質問に対する私のコメントに加えて（ここにコードを貼り付けます）：

  var acc = 1 
  var n = 10
start: 
  if (n <= 1) return acc 
  else { 
    acc = n * acc
    n = n - 1
    goto start
  }

factたまたま持っていた最近のビルドでメソッドをコンパイルしようとしましたがscalac -Xprint:all、どういうわけかコンパイラがicodeファイルを出力しました。したがって、これはテールコールを最適化する方法を実際に示しています。

  // methods
  def fact(acc: Int (INT), n: Int (INT)): Int {
  locals: value acc, value n, value _$this
  startBlock: 1
  blocks: [1,2,3,4,5]

  1: 
    2   JUMP 2

  2: // huynhjl's comment: IF condition is here
    3   LOAD_LOCAL(value n)
    3   CONSTANT(1)
    3   CJUMP (INT)LE ? 3 : 4

  3: // huynhjl's comment: first branch of IF, will return acc
    3   LOAD_LOCAL(value acc)
    3   JUMP 5

  5: 
    2   RETURN(INT)

  4: // huynhjl's comment: else branch of IF, update acc and n and jump back
    4   LOAD_LOCAL(value n)
    4   LOAD_LOCAL(value acc)
    4   CALL_PRIMITIVE(Arithmetic(MUL,INT))
    4   LOAD_LOCAL(value n)
    4   CONSTANT(1)
    4   CALL_PRIMITIVE(Arithmetic(SUB,INT))
    4   STORE_LOCAL(value n)
    4   STORE_LOCAL(value acc)
    4   JUMP 2

  }
于 2013-06-26T13:14:59.590 に答える
10

これは、この件に関する素敵なブログ投稿です

@tailrecコンパイラが末尾呼び出しの最適化を実行できない場合にのみ、エラーが発行されることを保証します。Scala はデフォルトで末尾呼び出しの最適化を実行します。

論文で説明されている条件が満たされると、フレームのスタックの代わりに最後のフレームを保持し、ループを実行することができます。プロセスはここでよりよく説明されています

于 2013-06-26T12:11:20.587 に答える