5

私は ocaml を学び始めており、この言語の再帰の力を本当に高く評価しています。ただ、一つ気になるのはスタックオーバーフローです。

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

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

最終的にスタックオーバーフローを引き起こす必要があります。C++ で (再帰を使用して) 同等のことを行うと、オーバーフローすることがわかっています。

私の質問は、関数型言語がスタックをオーバーフローするのを防ぐためのセーフガードが組み込まれているのでしょうか? そうでない場合、上記の合計アルゴリズムは for ループを使用した手続き型スタイルで記述されており、(整数オーバーフローを無視して) 任意の数を処理できるため、このようにあまり有用ではありませんか?

4

5 に答える 5

11

すべての (;-) 関数型言語は末尾再帰を最適化しますが、再帰呼び出しは LAST 操作ではないため (その後に追加する必要がある)、ここではそうしていません。

したがって、すぐに末尾再帰的な補助関数を使用することを学びます (そして、累積されている現在の合計を引数として取ります) ので、オプティマイザーはその仕事を行うことができます。

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

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

ここで、合計は再帰呼び出しの ARGUMENT として発生します。つまり、再帰自体の BEFORE であるため、末尾の最適化が開始されます (再帰は最後に発生する必要があるためです!)。

于 2009-08-18T02:02:49.467 に答える
6

通常、関数型言語には、はるかに大きなスタックがあります。たとえば、OCaml でスタック制限をテストするために特別に関数を作成したところ、バーフィードになる前に 10,000 回以上の呼び出しが行われました。ただし、あなたの主張は有効です。スタック オーバーフローは、関数型言語では依然として注意が必要です。

関数型言語が再帰への依存を軽減するために使用する戦略の 1 つは、末尾呼び出し最適化の使用です。現在の関数の次の再帰への呼び出しが関数の最後のステートメントである場合、現在の呼び出しをスタックから破棄し、その場所で新しい呼び出しをインスタンス化できます。生成されるアセンブリ命令は、命令型スタイルの 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;;
于 2009-08-18T02:04:03.757 に答える
4

初心者がスタックを吹き飛ばす深い再帰を書くのは確かに簡単です。Objective Caml は、ライブラリList関数が長いリストに対してスタックセーフではないという点で珍しいものです。Unisonのようなアプリケーションは、実際に Caml 標準Listライブラリをスタックセーフ バージョンに置き換えています。他のほとんどの実装は、スタックでより適切に機能します。(免責事項: 私の情報では Objective Caml 3.08 について説明しています。現在のバージョンである 3.11 の方が優れている可能性があります。)

ニュージャージーの標準 ML は、スタックを使用しないという点で珍しいため、ヒープがなくなるまで深い再帰が続行されます。Andrew Appel の優れた本Compiling with Continuationsで説明されています。

ここに重大な問題があるとは思いません。関数型言語で行う可能性が高い、多くの再帰コードを作成する場合は、末尾以外の呼び出しとスタック サイズに注意する必要があります。処理するデータのサイズと比較して。

于 2009-08-18T02:18:46.077 に答える
4

Scheme などの一部の関数型言語では、反復と同等になるように末尾再帰を最適化する 必要があると指定されています。したがって、Scheme の末尾再帰関数は、何度再帰してもスタック オーバーフローを引き起こすことはありません (もちろん、末尾以外の場所で再帰したり、相互再帰を行ったりしないことが前提です)。

他のほとんどの関数型言語では、末尾再帰を効率的に実装する必要はありません。そうすることを選択する人もいれば、そうしない人もいますが、実装は比較的簡単なので、ほとんどの実装でそうすると思います。

于 2009-08-18T01:59:20.237 に答える
1

これはトリッキーです -- 原理的にはそうですが、関数型言語のコンパイラとランタイムは、関数型言語の再帰の程度の増加を説明しています。最も基本的なことは、ほとんどの関数型言語ランタイムは、通常の反復プログラムが使用するよりもはるかに大きなスタックを要求するということです。しかし、それに加えて、関数型言語コンパイラは、言語の制約がはるかに厳しいため、再帰コードを非再帰コードに変換する能力がはるかに優れています。

于 2009-08-18T02:05:46.220 に答える