6

クラスで、再帰呼び出しの後にブール演算子が評価されるため、次の関数は末尾再帰ではないと言われました。

let rec exists p = function
    [] -> false
  | a::l -> p a || exists p l

しかし、これは1,000万サイズのリストのスタックを爆破するものではなく、さらに、標準ライブラリでの実装です。末尾再帰でなければ、一見同等で明らかに末尾再帰の代わりにこのフォームを使用する理由はありません。

let rec exists p = function
    [] -> false
  | a::l -> if p a then true else exists p l

したがって、OCamlコンパイラは、このような単純なケースでブール演算を最適化して、末尾再帰を利用できるようです。しかし、私がそのようにオペランドの順序を切り替えると、私は気づきました

let rec exists p = function
    [] -> false
  | a::l -> exists p l || p a

その後、スタックは実際に10mの要素に吹き飛ばされます。したがって、OCamlは、再帰呼び出しが右側に表示されている場合にのみこれを利用できるように見えます。これにより、コンパイラが行うのは、ブール値のopを同等の式に置き換えることだけであると思われますif。誰かがこれを確認または反論できますか？

4

3 に答える 3

12

これを言った人は間違っていました。

実際、||すぐにはif / then / elseに変換されませんが、コンパイラの中間言語を介して少し保存され、2つの異なる変換を簡単に有効にできます。

  1. あなたが言ったようにa || b、表現の位置はに翻訳されますif a then true else b
  2. しかしa || b、テスト位置では、つまり、の計算へのジャンプである場合は、のif a || b then c else dようなものに変換されます（に変換するだけでのコードが複製されます）。この最適化はより難解であり、ユーザーはプログラムのパフォーマンスについて推論するためにそれを意識する必要はありません。if a then goto c else if b then goto c else dgoto ccif a then c else if b then cc

コンパイラのソースで自分の目で確かめることができます。||プリミティブはとして表されPsequor、対象のファイルは、ネイティブコンパイルの場合はasmcomp / cmmgen.ml （ （1）、（2） ]）、バイトコードコンパイルの場合はbytecomp / bytegen.mlです（両方の側面が同時に処理されます）。 、結果を使用するために生成されたバイトコードの命令による）。

小さなポイント：このケースは「十分に単純」であるため、OCamlは「右側」で末尾呼び出しを最適化できるとおっしゃっているようですが、コンパイラが十分に賢くないため、「左側」では最適化できません。呼び出しが左側に表示される場合、それは末尾呼び出しではないため、最適化しないでください。これは、「単純な」末尾呼び出しであるかどうかの問題ではありません。

最後に、末尾が末尾呼び出しであるかどうかを確認する場合は、OCamlツールを使用できます。オプションを指定してコンパイルすると、プログラム式のタイプに関する情報を-annot含む注釈ファイルfoo.annot（ソースがの場合）が生成されます。foo.ml、関数呼び出しの場合、末尾呼び出しであるかどうかについて。caml-modeたとえば、Emacsの場合、afterを指すコマンドは、M-x caml-types-show-callこれが「末尾呼び出し」であることを確認しますが、呼び出されると「スタック呼び出し」を返します。exists||p x

于 2012-07-08T07:07:59.093 に答える
9

書いた場合：

let rec add_result p = function
  [] -> 0
| a::l -> p a + add_result p l

関数は再帰呼び出しの後に両方の結果を追加する必要があるため、これは末尾再帰にはなりません。

しかし、||これは正規作用素ではなく、A || B厳密にと同等if A then true else Bです。

let rec exists p = function
  [] -> false
| a::l -> p a || exists p l

それは

let rec exists p = function
  [] -> false
| a::l -> if p a then true else exists p l

関数は末尾再帰です。

let rec exists p = function
  [] -> false
| a::l -> exists p l || p a

と同等です

let rec exists p = function
  [] -> false
| a::l -> if exist p l then true else p a

これは末尾再帰ではありません。

于 2012-07-08T06:33:08.063 に答える
2

レミの答えは完全に正しいです。OCamlとは異なるタイピングシステムを持つ一部の言語は、特定の非ブール値を自動的にブール値に強制変換することに注意してください。これらの言語には、（||）のような演算子を選択できます。rhsの結果をブール値に強制しようとせず、与えられたものを返すか、強制するが、rhsの後にやるべきことがいくつかあります。が評価されるので、（||）のテール再帰性をあきらめます。両方を持つことはできません。おそらくあなたの情報提供者はそれらの線に沿って考えていたので、彼らはOCamlについて何をしたかを誤って言ったのです。true || succ 5OCamlの型の厳密な取り扱いを考えると、そもそもそのようなことを言うことはできません。

于 2012-07-08T07:17:46.693 に答える