foo と bar が2つの相互再帰関数として定義されているとします。 foo もしくは bar の本体にある、foo もしくは bar への末尾呼出は相互末尾再帰呼出です。 例えば、次の2つの関数 isevn と isodd は相互再帰です:
// 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 //
// 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 //
C言語や Java のような命令型プログラミング言語の組み込みループに相当するコードを書く場合には、 相互末尾再帰呼出がローカルジャンプにコンパイルされるかしばしば確認する必要があります。 次の関数 print_multable ではゼロではない桁の九九の表の印字を実装しています:
fun print_multable ((*void*)) = let // #define N 9 // fnx loop1 (i: int): void = if i <= N then loop2 (i, 1) else () // and loop2 (i: int, j: int): void = if j <= i then let val () = if j >= 2 then print " " val () = $extfcall(void, "printf", "%dx%d=%2.2d", j, i, j*i) in loop2 (i, j+1) end // end of [then] else let val () = print_newline () in loop1 (i+1) end // end of [else] // end of [if] // in loop1 (1) end // end of [print_multable]
呼び出されると、関数 print_multable は次のような九九の表を印字します:
1x1=01 1x2=02 2x2=04 1x3=03 2x3=06 3x3=09 1x4=04 2x4=08 3x4=12 4x4=16 1x5=05 2x5=10 3x5=15 4x5=20 5x5=25 1x6=06 2x6=12 3x6=18 4x6=24 5x6=30 6x6=36 1x7=07 2x7=14 3x7=21 4x7=28 5x7=35 6x7=42 7x7=49 1x8=08 2x8=16 3x8=24 4x8=32 5x8=40 6x8=48 7x8=56 8x8=64 1x9=09 2x9=18 3x9=27 4x9=36 5x9=45 6x9=54 7x9=63 8x9=72 9x9=81
要約すると、 相互末尾再帰呼出をローカルジャンプへ変換する能力は、 組み込みループを相互末尾再帰関数で実装することを可能にします。 この能力は、ループを ATS の再帰関数で置換するのに実用上不可欠です。