0

スタック オーバーフローを防ぐために、単一の再帰関数に末尾再帰の最適化を適用できますが、相互再帰関数についてはどうでしょうか。

この回答は、F# で相互再帰関数を定義する方法を示しています。

let rec F() = 
    G()
and G() =
    F()

生成されたネイティブ マシン コードまたはバイトコードが最終的に F と G の両方に末尾再帰の最適化が適用された 1 つの関数だけで構成されるように、このように定義されていますか? これはスタックオーバーフローを防ぎますか?

相互再帰関数の末尾呼び出しのアルゴリズムはどのように機能しますか?

一方、Haskell ではそのような構文は必要ありません。Haskell の遅延評価のせいでしょうか。または@augustssが示唆するように、Haskellコンパイラも上記と同じことをしていますか?

4

2 に答える 2

5

関数型言語は通常、再帰から完全に独立した、いわゆる適切な末尾呼び出しの最適化を行います。末尾の呼び出しは、再帰呼び出し、以前に定義された関数の呼び出し、部分的に適用された関数、またはファーストクラス関数の呼び出しでさえも、ジャンプに最適化されます。例えば：

g x = let y = 2*x in abs x  -- tail call
add x = (+) x  -- tail call
apply f x = f x  -- tail call

CLR には末尾呼び出し命令があるため (低速であることが知られていますが)、F# はそのすべてを実行できるはずです。

于 2015-02-28T08:40:11.460 に答える
1

F# は ML ファミリーに属しているため、これはかなり単純な問題だと思います。plainletはまったく再帰的ではなく、相互に再帰的な関数はlet rec. これにより、コンパイラの分析がある程度単純化されます。Haskell では、型推論をサポートし、最適化を実行するために、コンパイラはコードを同様のブロック自体に分割します。ML の方法は間違いなくより予測可能です。どちらのアプローチも本質的に優れているとは思いません。

あなたは遅延評価に言及していますが、それは各言語である程度バランスを変えるのに役立つと思います. ML では、再帰的に定義された値はほぼ関数でなければなりませんが、Haskell では、任意の型の値を再帰的に定義できます。

于 2015-02-28T06:11:44.603 に答える