Effective ATS:
末尾再帰関数としてのループ

以降で示すコードの全体は tailrec.dats から入手できます。

末尾再帰とは何ですか？

fun foo (x: int): int =
  if x > 0 then bar(x) else baz(x)+1

もし末尾呼出で呼び出す関数が自分自身を呼び出しているなら、この末尾呼出はしばしば末尾再帰呼出と呼ばれます。 関数本体内のあらゆる再帰呼出が末尾呼出であれば、その関数は末尾再帰です。 末尾再帰関数は反復関数と呼ばれることもあることに注意してください。 次の例では、 外側の [f91] 呼び出しは末尾再帰ですが、内側の呼び出しはそうではありません:

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

なぜ末尾再帰が望ましいのですか？

再帰を末尾再帰に変換する

例 1

fun tally (n: int): int =
  if n > 0 then n + tally (n-1) else 0

int tally (int n)
{
  return (n > 0) ? n + tally (n-1) : 0 ;
}

int tally2 (int n)
{
  int i ;
  int res = 0 ;
  for (i = n ; i > 0 ; i--) res += i ;
  return res ;
}

C言語における [tally2] の上記の実装は、容易に次のような ATS コードに変換できます:

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

一般的に、再帰関数を末尾再帰関数に変換は、その関数を実行中に生成されるスタックをエンコードする効率の良い方法を見つけられるかで決まります。 例えば、[tally] を 100 に対して呼び出したと仮定しましょう; この呼び出しは 99 に対する再帰呼出を生成し、そして 98 に対する再帰呼出、などと続きます; [tally] を 50 に対して呼び出した時、そのコールスタックは本質的に次のような評価コンテキストを表わします:

100 + (99 + (98 + (... + (51 + []) ...)))

例 2

fun fib (n: int): int =
  if n >= 2 then fib(n-1) + fib(n-2) else n

fun fib2
  (n: int): int = let
//
fun loop
  (i: int, f0: int, f1: int): int =
  if i < n then loop (i+1, f1, f0+f1) else f0
//
in
  loop (0, 0, 1)
end // end of [fib2]

[fib] を [fib2] に変換する背後にあるアイデアは、n >=2 の n 番目のフィボナッチ数を計算するために2つ前に計算されたフィボナッチ数のみを保持する必要がある、という単純な観察によっています。

例 3

fun
{a:t@ype}
list_append
  {m,n:nat} (
  xs: list (a, m)
, ys: list (a, n)
) : list (a, m+n) =
(
case+ xs of
| list_cons
    (x, xs) => list_cons (x, list_append (xs, ys))
| list_nil ((*void*)) => ys
) // end of [list_append]

[list_append] を末尾再帰実装にするためには、リストの結合に関するいくつかの知識が必要です。 list_cons(x, xs) の評価は本質的に2つのステップです; はじめにリストノードを格納するために必要なメモリを確保し; それからこのノードを x と xs で初期化します。 ATS では、これら2つのステップは形式的に分離することができます。 この分離は、次のコードで示すような、リスト連結の適切な末尾再帰実装を得るための鍵になります:

fun
{a:t@ype}
list_append2
  {m,n:nat} (
  xs: list (a, m)
, ys: list (a, n)
) : list (a, m+n) = let
//
fun loop{m:nat}
(
  xs: list (a, m)
, ys: list (a, n)
, res: &ptr? >> list (a, m+n)
) : void =
(
case+ xs of
| list_cons
    (x, xs1) => let
    val () = // allocate a list node with
    res := list_cons{a}{0}(x, _) // uninitialized tail
    val+list_cons (_, res1) = res // [res1] points to the tail
    // put into [res1] the concatenation
    val () = loop (xs1, ys, res1) // of [xs1] and [ys]
  in
    fold@(res) // folding translates into a no-op at run-time
  end // end of [list_cons]
| list_nil ((*void*)) => res := ys
)
//
var res: ptr
val () = loop (xs, ys, res)
//
in
  res
end // end of [list_append2]

ところで、この [loop] の実装に見られる再帰のスタイルはしばしば 末尾再帰を法とするアロケーション (tail-recursion modulo allocation) と呼ばれます。 これは一般に弱い型の言語 (例: LISP や C言語) 見られますが、(適切に型を付けることが非常に困難なため) 型付き言語ではあまり見られません。

相互末尾再帰関数

fun isevn (n: int): bool =
  if n > 0 then isodd (n-1) else true
and isodd (n: int): bool =
  if n > 0 then isevn (n-1) else false

[isevn] と [isadd] のこの実装をコンパイルすると、 ATS コンパイラ (ATS/Postiats) は [isevn] と [isodd] を別々に扱います。 したがって、[isevn] ([isodd]) 本体内の [isodd] ([isevn]) 呼び出しをローカルジャンプに変換できません。 2つの関数を混合してコンパイルする必要があることをコンパイラに指示するために、キーワード [fun] を別のキーワード [fnx] で置き換えなければなりません:

fnx isevn (n: int): bool =
  if n > 0 then isodd (n-1) else true
and isodd (n: int): bool =
  if n > 0 then isevn (n-1) else false