3

継続渡しスタイルのフィボナッチ関数の次の F# 定義を見てきましたが、これは常に末尾再帰的であると想定していました。

let fib k =
  let rec fib' k cont =
    match k with
    | 0 | 1 -> cont 1
    | k -> fib' (k-1) (fun a -> fib' (k-2) (fun b -> cont (a+b)))
  fib' k id

Scala で同等のコードを試してみたときに、既存の @tailrec を使用しましたが、Scala コンパイラーが再帰呼び出しが末尾位置にないことを通知したとき、不意を突かれました。

  def fib(k: Int): Int = {
    @tailrec def go(k: Int, cont: Int => Int): Int = {
      if (k == 0 || k == 1) cont(1)
      else go(k-1, { a => go(k-2, { b => cont(a+b) })})
    }
    go(k, { x => x })
  }

私の Scala 実装は F# のものと同等だと思うので、なぜ関数が末尾再帰的でないのか疑問に思っています。

4

3 に答える 3

3

4 行目の 2 番目の呼び出しgoは、末尾の位置ではなく、無名関数内にラップされています。(それはその関数の末尾の位置にありますが、それ自体の位置ではありませんgo。)

継続渡しスタイルには適切な末尾呼び出しが必要ですが、残念ながら Scala にはありません。(JVM で PTC を提供するには、独自のスタックを管理する必要があり、他の言語との相互運用性を損なう JVM コール スタックを使用しないでください。ただし、相互運用性は Scala の主要な設計目標です。)

于 2015-06-23T08:08:30.027 に答える
2

テール コールの除去に対する JVM のサポートは制限されています。

F# の実装について話すことはできませんが、scala ではネストされた呼び出しがあるため、末尾の位置にはありません。それについて考える最も簡単な方法は、スタックの観点からです。再帰呼び出しを行うときに、スタックが「覚えておく」必要がある他の情報はありますか?

ネストされた go 呼び出しの場合、計算が「戻って」外側の呼び出しを完了する前に内側の呼び出しを完了する必要があるため、明らかにそうです。

Fib は次のように再帰的に定義できます。

def fib(k:Int) = {
  @tailrec
  def go(k:Int, p:Int, c:Int) : Int = {
    if(k == 0) p
    else { go(k-1, c p+c) }
  }
  go(k,0 1)
}
于 2015-06-23T08:08:06.237 に答える