「テールコール最適化」記事に関する質問

Question

質問があります これ 記事。

このコード間

function odds(n, p) {
  if(n == 0) {
    return 1
  } else {
    return (n / p) * odds(n - 1, p - 1)
  }
}

そして、このコード

(function(){
  var odds1 = function(n, p, acc) {
    if(n == 0) {
      return acc
    } else {
      return odds1(n - 1, p - 1, (n / p) * acc)
    }
  }

  odds = function(n, p) {
    return odds1(n, p, 1)
  }  
})()

1）これがどれだけ役立つかについて混乱しています。 2番目のスニペットには、再び電話をかける前に必要なものを計算するため、オーバーヘッドが少なくなるテールコールがありますか、それとも私が欠けているものがありますか？

私が理解しているように、テールコールはまだ排除されておらず、最適化するだけです。

2）そして、なぜ必要なのか odds と odds1 とりあえず？それはまだ私にも明らかではありません。

Answer 1

これがどれだけ役立つかについて混乱しています。 2番目のスニペットには、再び電話をかける前に必要なものを計算するため、オーバーヘッドが少なくなるテールコールがありますか、それとも私が欠けているものがありますか？

私が理解しているように、テールコールはまだ排除されておらず、最適化するだけです。

手順の終了が次のようになる場合：

push args
call foo
return

その後、コンパイラはそれをまさに最適化できます

jump startOfFoo

手順呼び出しを完全に排除します。

とにかく、なぜオッズとオッズが必要なのですか？それはまだ私にも明らかではありません。

の「契約」 odds 2つの引数のみを指定します。3番目の引数は、実装の詳細です。したがって、内部の方法でそれを隠し、「ラッパー」を外部APIとして提示します。

あなたは電話することができます odds1 何かのようなもの oddsImpl そして、それはそれをより明確にするだろうと思います。

Answer 2

最初のバージョンはそうではありません 尾の再帰 の価値を取得した後 odds(n - 1, p - 1) その後、それを掛ける必要があります (n / p), 、2番目のバージョンはこれを、 odds1 適切にテールを再帰的にするための機能。

コールスタックを見ると、最初は次のようになります。

odds(2, 3)
  odds(1, 2)
    odds(0, 1)
    return 1
  return 1/2 * 1
return 2/3 * 1/2

一方、2番目は次のとおりです。

odds(2, 3)
  odds1(2, 3, 1)
    odds1(1, 2, 2/3)
      odds1(0, 1, 1/2 * 2/3)
      return 1/3
    return 1/3
  return 1/3
return 1/3

あなたは単に再帰的な呼び出しの価値を返すだけなので、コンパイラはこれを簡単に最適化できます：

odds(2, 3)
#discard stackframe
odds1(2, 3, 1)
#discard stackframe
odds1(1, 2, 2/3)
#discard stackframe
odds1(0, 1, 1/3)
return 1/3

持っている理由 odds と odds1 他のコードがこの関数を呼び出す場合、単に初期アキュムレータ値を提供することです。

Answer 3

尾の再帰の最適化は、乗算の結果を計算できないため、最初の例では次のとおりです。 return (n / p) * odds(n - 1, p - 1) Odds（N-1）を呼び出すまで、インターペレーターは現在のメモリ（スタック上）に現在の位置を保持し、オッズへの新しい呼び出しを開く必要があります。

再帰的に、それは次の電話でも起こり、その後の電話でも発生します。したがって、再帰の終了に達し、価値の返品と製品の計算を開始するまでに、保留中の運用があります。

2番目の例では、実行されたリターンステートメントは単に return odds1(n - 1, p - 1, (n / p) * acc) 関数引数を計算し、Odds1（n-1）を呼び出すだけです 現在の位置を保持することなく. 。これが最適化の場所です。なぜなら、スタックで新しいフレームを開くたびに自分がどこにいるかを覚えておく必要がないからです。

本の参照のように考えてください。料理本を開いて特定のレシピに移動することを想像してください。成分は次のようにリストされています。

1. 塩
2. 次のページの材料

次のページにはあります

1. コショウ
2. 次のページの材料

など。すべての材料が何であるかをどのように伝えますか？すべてのページで見たものを覚えておく必要があります！

2番目の例は、次の成分リストに似ていますが、

1. 塩
2. これを忘れて、次のページに表示されているものを使用してください

次のページには次のようなものがあります。

1. 塩
2. コショウ
3. これを忘れて、次のページに表示されているものを使用してください

など。最後のページに到達するまでに（両方とも同じ量の関数呼び出しを取るという点で類推が正確であることに注意してください）、すべてのページで見たものを「メモリに保つ」ことなく、すべての成分があります。最後のページにすべてがそこにあるからです！