末尾再帰

💡 お知らせ: このドキュメントはAIによって翻訳されています。表現に違和感がある場合は、原文（英語）を参照するか、翻訳にご協力ください。

Flix では、そして一般に関数型プログラミングでは、反復処理は再帰によって表現されます。

例えば、リストがある要素を含むかどうかを判定したい場合、再帰関数を次のように書くことができます：

def memberOf(x: a, l: List[a]): Bool with Eq[a] = 
    match l {
        case Nil     => false
        case y :: ys => if (x == y) true else memberOf(x, ys)
    }

memberOf 関数はリスト l に対してパターンマッチを行います。リストが空であれば false を返します。そうでなければ、要素 y とリストの残り ys が得られます。x == y であれば要素が見つかったので true を返します。そうでなければ、リストの残り ys に対して再帰します。

memberOf への再帰呼び出しは 末尾位置(Tail position) にあります。つまり、memberOf 関数の中で最後に行われる処理です。これには 2 つの重要な利点があります。(a) Flix コンパイラが memberOf を（関数呼び出しよりも効率的な）通常のループに書き換えられること、そしてより重要なのは (b) 呼び出しスタックの高さが決して増えないため、memberOf の呼び出しでスタックがオーバーフローすることが あり得ない ことです。

ヒント: Flix は完全な末尾呼び出し除去をサポートしています。これは、末尾位置にある再帰呼び出しがスタックの高さを決して増やさず、したがってスタックオーバーフローを引き起こし得ないことを意味します！

特筆すべき点として、Flix が備えているのは単なる末尾呼び出し最適化ではなく、完全な 末尾呼び出し除去です。これにより、次のプログラムは正常にコンパイルされ、実行されます：

def isOdd(n: Int32): Bool =
    if (n == 0) false else isEvn(n - 1)

def isEvn(n: Int32): Bool =
    if (n == 0) true else isOdd(n - 1)

def main(): Unit \ IO =
    isOdd(12345) |> println

これは他の多くのプログラミング言語では成り立たないことです。

非末尾呼び出しとスタックオーバーフロー

Flix コンパイラは末尾呼び出しがスタックをオーバーフローさせないことを保証しますが、末尾位置にない関数呼び出しについては同じことは言えません。

例えば、次の階乗関数の実装は呼び出しスタックをオーバーフローさせます：

def factorial(n: Int32): Int32 = match n {
    case 0 => 1
    case _ => n * factorial(n - 1)
}

それは次のプログラムで確認できます：

def main(): Unit \ IO = 
    println(factorial(1_000_000))

これをコンパイルして実行すると、次の出力が得られます：

java : Exception in thread "main" java.lang.StackOverflowError
	at Cont%Int32.unwind(Cont%Int32)
	at Def%factorial.invoke(Unknown Source)
	at Cont%Int32.unwind(Cont%Int32)
	at Def%factorial.invoke(Unknown Source)
	at Cont%Int32.unwind(Cont%Int32)
    ... many more frames ...

よく知られたテクニックとして、factorial をアキュムレータ(Accumulator)を使う形に書き換える方法があります：

def factorial(n: Int32): Int32 = 
    def visit(x, acc) = match x {
        case 0 => acc
        case _ => visit(x - 1, x * acc)
    };
    visit(n, 1)

ここでは visit 関数が末尾再帰になっているため、スタックをオーバーフローさせることはありません。

@Tailrec アノテーション

Flix は @Tailrec アノテーションを提供しています。これは、関数内のすべての自己再帰呼び出しが末尾位置にあることを検証するようコンパイラに指示するものです。このアノテーションは省略可能で、実行時の挙動を変えることはありません。ドキュメントおよび検証のためのツールとして機能します。

例えば、アキュムレータスタイルの sum 関数は末尾再帰です：

@Tailrec
def sum(l: List[Int32], acc: Int32): Int32 = match l {
    case Nil     => acc
    case x :: xs => sum(xs, acc + x)
}

sum への再帰呼び出しは関数内の最後の操作であり、その結果に対してそれ以上の処理は行われないため、コンパイラはこれを受理します。

対照的に、次の関数は拒否されます：

@Tailrec
def length(l: List[Int32]): Int32 = match l {
    case Nil     => 0
    case _ :: xs => length(xs) + 1
}

ここでは length(xs) の結果が加算（+ 1）に使われているため、再帰呼び出しは末尾位置に ありません。コンパイラは次のエラーを報告します：

>> Non-tail recursive call in @Tailrec function 'length'.

   ... length(xs) + 1
       ^^^^^^^^^^
       non-tail recursive call

これを修正するには、前述のようにアキュムレータを使う形に関数を書き換えます。

ヒント: @Tailrec アノテーションは純粋にコンパイル時のチェックです。コード生成には影響しません。Flix はアノテーションの有無にかかわらず、末尾位置にあるあらゆる呼び出しに対して既に完全な末尾呼び出し除去を行います。コードが進化しても関数が末尾再帰の ままである ことをコンパイラに保証してほしい場合に、@Tailrec を使ってください。

Keyboard shortcuts

Programming Flix

末尾再帰

非末尾呼び出しとスタックオーバーフロー

@Tailrec アノテーション