末尾呼出と末尾再帰

関数本体で関数 bar を呼び出す関数 foo を考えましょう。 ここで foo と bar は同じ関数でも問題ありません。 もし bar を呼び出した返値が foo の返値にもなるとしたら、この bar 呼び出しは末尾呼出です。 もし foo と bar が同じ関数の場合、この呼び出しは(再帰)自己末尾呼出です。 例えば、次のように定義された関数 f91 の本体で2つの再帰呼出があるとします:

fun f91 (n: int): int =
  if n >= 101 then n - 10 else f91 (f91 (n+11))

関数本体中のそれぞれの再帰呼出が末尾呼出なら、この関数は末尾再帰関数です。 例えば、次の関数 sum_iter は末尾再帰です:

fun sum_iter
  (n: int, res: int): int =
  if n > 0 then sum_iter (n-1, n+res) else res
// end of [sum_iter]

ATS において唯一もっとも重要な最適化は、 おそらく自己末尾呼出をローカルへのジャンプに変換することでしょう。 この最適化はあらゆる末尾再帰関数を同等のループに効果的に変換します。 ATS は for ループと while ループを生成する構文を直接サポートしていますが、 ATS においてループを生成する好ましいアプローチは、一般に末尾再帰関数を使用することです。 これは、末尾再帰関数を書くための構文が ATS における他のプログラミング機能の構文と適合できることが主たる理由です。 ループ構文はあまり適合しません。