3

LISP や ML は末尾呼び出しの最適化をどのように実装していますか?

4

2 に答える 2

6

さまざまなコンパイラ/インタープリターの正確な実装の詳細について話すことはできませんが、一般的に言えば、末尾呼び出しの最適化は次のように動作します。

通常、関数呼び出しには次のようなものが含まれます。

  1. 戻り値にスタック スペースを割り当てる
  2. 現在の命令ポインタをスタックにプッシュします
  3. 関数パラメーターにスタック スペースを割り当て、適切に設定する
  4. 関数を呼び出す
  5. 戻るには、戻りスペースを適切に設定し、戻り先の命令ポインターをポップしてそこにジャンプします

ただし、関数が末尾の位置にある場合、つまり、呼び出そうとしている関数の結果を返すことを意味する場合は、注意が必要です。

  1. 呼び出しようとしている関数の戻り値に割り当てられたスタック領域として、独自の戻り値に割り当てられたスタック領域を再利用します
  2. 呼び出そうとしている関数が使用する命令ポインタとして、返すべき命令ポインタを再利用します。
  3. 独自のパラメーター スタック スペースを解放する
  4. パラメータにスペースを割り当て、適切に設定します
  5. パラメータの値を設定する
  6. 関数を呼び出す
  7. 戻るときは、発信者に直接返されます。

#1 と #2 は実際には何の作業も必要としないことに注意してください。#3 は実装に応じてトリッキーまたはシンプルになる可能性があり、4 ～ 7 は呼び出している関数から特別なものを必要としないことに注意してください。また、これらすべてがコール スタックに対して 0 スタックの成長をもたらすことにも注意してください。これにより、無限再帰が可能になり、一般的に少し高速化されます。

また、この種の最適化は、直接再帰関数だけでなく、相互再帰関数、および実際には末尾位置にあるすべての呼び出しにも適用できることに注意してください。

于 2012-10-22T19:01:45.930 に答える