関数型言語のプログラムはスタックオーバーフローを起こしやすいでしょうか？

Question

私はocamlを学び始めており、実際には言語の再帰の力に感謝しています。しかし、私が心配していることの1つはスタックオーバーフローです。

ocamlが関数呼び出しにスタックを使用する場合、最終的にスタックをオーバーフローしませんか？たとえば、次の関数があるとします。

let rec sum x = 
    if x > 1 then f(x - 1) + x 
    else x;; 

最終的にスタックオーバーフローが発生する必要があります。私がC++で（再帰を使用して）同等のことをしなければならない場合、私はそれがオーバーフローすることを知っています。

私の質問は、機能的な言語がスタックをオーバーフローするのを防ぐためのセーフガードが組み込まれているということですか？もしそうでなければ、forループで手続き型で書かれた上記の加算アルゴリズムは、任意の数（dis-に関する整数オーバーフロー）を扱うことができるので、あまり有用ではないでしょうか？

Answer 1

すべての（;-)機能的な言語の適切な実装は、テール再帰を最適化しますが、再帰呼び出しが最後の操作ではないので（ここでは追加が必要です）、ここで行っていることではありません。

したがって、ISテール再帰的な補助関数（現在の合計が引数として累積される）を使用することをすぐに知っているので、オプティマイザはそのジョブを実行できます。つまり、可能なO'Caml構文のnet 「さびメートル：

let sum x = 
    aux(x)(0);; 

let rec aux x accum = 
    if x > 1 then aux(x - 1)(accum + x) 
    else (accum + x);; 

ここで、合計は再帰自体前、つまり再帰呼び出し、引数として発生し、その尾最適化がで蹴ることができます（再帰が起こる必要がある最後の事であるため、 ！）。

Answer 2

Schemeなどの一部の機能言語では、tail recursionはをイテレーションと同等にする必要があります。したがって、Schemeのtail-recursive関数は、何度繰り返してもスタックオーバーフローを起こすことはありません（終わり以外の他の場所でも再帰的に再帰的に関与しないと仮定します）。

他のほとんどの関数型言語では、テール再帰を効率的に実装する必要はありません。そうしたい人もあればそうでない人もいますが、実装するのは比較的簡単ですので、ほとんどの実装でそうすることが期待されます。

Answer 3

機能的な言語には、通常、大きなスタックがあります。たとえば、私はOCamlのスタック制限をテストするための関数を書いています。また、barfedする前に10,000以上の呼び出しがあります。ただし、あなたのポイントは有効です。スタックオーバーフローは、関数型言語に注意する必要があります。

再帰への依存を軽減するために関数型言語が使用する戦略の1つは、tail-call optimizationの使用です。現在の関数の次の再帰呼び出しが関数の最後のステートメントである場合、現在の呼び出しはスタックから破棄され、新しい呼び出しはその場所でインスタンス化されます。生成されるアセンブリ命令は、命令型のwhileループの命令と基本的に同じです。

あなたの関数は、再帰が最後のステップではないため、テールコール最適化ができません。最初に戻る必要があり、結果にxを加えることができます。はい、原則的に、しかし、関数型言語のためのコンパイラとランタイムが占める - 通常、これはあなただけでこれはトリッキーで、他のパラメータ

let rec sum x = 
    let sum_aux accum x = 
    if x > 1 then sum_aux (accum + x) (x - 1) 
    else x 
    in sum_aux 0 x;; 

Answer 4

とともにアキュムレータを渡すヘルパー関数を作成して、周りを取得するのは簡単です関数型言語における再帰の度合いが増加しました。最も基本的なことは、ほとんどの関数型言語ランタイムが、通常の反復プログラムよりもはるかに大きなスタックを要求することです。しかし、それに加えて、関数型言語コンパイラは、言語のより厳しい制約のために、再帰的コードを非再帰型に変換することが可能です。

Answer 5

初心者がスタックを爆破する深い再帰を書くのは簡単です。 ライブラリList関数は、長いリストのスタックセーフではありません。 Unisonのようなアプリケーションは、実際にCamlの標準Listライブラリをスタックセーフ版で置き換えました。他のほとんどの実装は、スタックでよりうまく機能します。 （免責事項：私の情報はObjective Caml 3.08について書かれていますが、現在のバージョン3.11はより良いかもしれません）

Standard ML of New Jerseyはスタックを使用しないので珍しいです。深い再帰は、 。それはAndrew Appelの優れた本Compiling with Continuationsに書かれています。

私はここに深刻な問題はないと思います。関数型言語で行う可能性が高い再帰的なコードをたくさん作成する場合、非テールコールとスタックサイズを次のように認識しなければならないということが「認識のポイント」です。あなたが処理するデータのサイズと比較します。