Ocaml/F＃の関数がデフォルトで再帰的でないのはなぜですか？

Question

F＃とOcaml（そしておそらく他の言語）の関数がデフォルトで再帰的でないのはなぜですか？デフォルトでは、関数の再帰的機能を与える

let rec foo ... = ... 

及びません。言い換えれば

は、なぜ言語設計者は、あなたのような宣言でrecを入力し、明示的に作成することをお勧めだったのですか？なぜ明示的なrec構成の必要性？

Answer 1

オリジナルのMLのフランス語と英国の子孫は、さまざまな選択肢を作り、その選択肢は何十年も前から現代のものに継承されています。これはただの遺産ですが、これらの言語のイディオムには影響します。

フランス語のCAMLファミリーの言語（OCamlを含む）では、関数はデフォルトで再帰的ではありません。この選択は、新しい定義の本体内の前の定義を参照することができるため、これらの言語でletを使用して関数（および変数）定義を置き換えることを容易にします。 F＃はこの構文をOCamlから継承しました。例えば

、OCamlの中の配列のシャノンエントロピーを計算する際に機能pを取っ：高次shannon関数の引数pが最初の行に別のpによって取って代わられている方法

let shannon fold p = 
    let p x = p x *. log(p x) /. log 2.0 in 
    let p t x = t +. p x in 
    -. fold p 0.0 

注身体の2番目の行にもう1つpと表示されます。

逆に、MLファミリの英国のSMLブランチがもう1つの選択肢をとり、SMLのfunの受信機能はデフォルトで再帰的です。ほとんどの関数定義で関数名の以前のバインディングにアクセスする必要がない場合は、コードが単純になります。しかし、置き換えられた関数はスコープを汚染し、間違って関数の誤った "バージョン"を呼び出すことを可能にする別の名前（f1、f2など）を使用するように作られています。暗黙的に再帰的なfunの受信機能と非再帰的なvalの受信機能との間には矛盾があります。

Haskellでは、定義間の依存関係を純粋なものに限定することで推論することができます。これにより、おもちゃのサンプルがよりシンプルに見えますが、他の場所では重大なコストがかかります。

ガネシュとエディによって与えられた答えは、赤ちゃんです。彼らはなぜ関数群が巨大なlet rec ... and ...の中に置かれないのかを説明しました。なぜなら、型変数が一般化されるときに影響を与えるからです。これは、recがSMLではデフォルトであり、OCamlではデフォルトではありません。

Answer 2

いくつかの推測：

• letが機能するだけでなく、他の定期的な値をバインドするために使用されていないだけ。ほとんどの形式の値は再帰的に使用することはできません。特定の形式の再帰的な値（関数、遅延表現など）が許可されているため、これを示すためには明示的な構文が必要です。
• 非再帰関数を最適化する方が簡単かもしれません
• 再帰関数を作成するときに作成されるクロージャは、関数自体を指すエントリを含める必要があります（関数が再帰的に呼び出すことができるため再帰的クロージャ非再帰的クロージャよりも複雑です。したがって、再帰を必要としない場合に、より簡単な非再帰的クロージャを作成できるのはいいかもしれません。
• これは、以前定義された関数または同じ名前の値で関数を定義することを可能にします。私はこれが悪い練習だと思っていますが、
• 安全性はさらに高いですか？あなたが意図したことをしていることを確認します。例えば再帰的に意図していないが、関数自体と同じ名前の関数の中で誤って名前を使用した場合、おそらく不平を言います（名前が前に定義されていない限り）。
• letの構造は似ていますLispとSchemeのletコンストラクトへ;これは非再帰的です。スキームで別のletrecコンストラクトは、再帰レッツ・

Answer 3

ための2つの主な理由は、これは良いアイデアですがありがありますされています

まず、あなたが再帰的な定義を有効にした場合、あなたは、以前のバインディングを参照することはできません同じ名前の値。これは、既存のモジュールを拡張するようなことをしているときに、しばしば役に立つイディオムです。

第2に、再帰的な値、特に相互に再帰的な値のセットは、すでに定義されているものの上に構築された新しい定義が順番に進んでいく定義であることを考えるのがずっと難しくなります。このようなコードを読んで、再帰的に明示的にマークされた定義を除いて、新しい定義は以前の定義のみを参照することができることを保証することは良いことです。

Answer 4

recを明示的に使用する重要な理由の1つは、静的に型指定されたすべての関数型プログラミング言語（さまざまな方法で変更および拡張されています）の基礎となるHindley-Milner型の推論です。

let f x = xの定義がある場合は、タイプが'a -> 'aで、異なるポイントの別の'aタイプに適用されると考えられます。しかし、同様に、let g x = (x + 1) + ...と書くと、xはgの残りの部分でintとして扱われます。

ヒンドレーミルナーの推論がこの区別を扱う方法は、明示的な一般化の手順です。あなたのプログラムを処理する際には、型システムが停止して「OK」と言います。この時点で定義の型が一般化されるので、誰かが型を使用したときに型の自由型変数はになります。したがって、この定義の他の用途に干渉することはありません。

この一般化を実行するには、相互に再帰的な関数セットをチェックした後であることがわかります。それ以前は、一般化しすぎて、型が実際に衝突する可能性のある状況につながります。後であれ、あなたは一般化しすぎて、複数の型のインスタンス化では使用できない定義を作成します。

したがって、タイプチェッカーは、どのセットの定義が相互に再帰的であるかを知る必要があるので、何ができますか？ 1つの可能性は、スコープ内のすべての定義に対する依存関係分析を単純に行い、できるだけ小さなグループに並べ替えることです。ハスケルは実際にこれを行っていますが、副作用が制限されていないF＃（とOCamlとSML）のような言語では、副作用の順序を変える可能性があるため、これは悪い考えです。その代わりに、どの定義が相互に再帰的であるかを明示するように、そして一般化が行われるべき拡張によって、ユーザーに明示的にマークするように求めます。

Answer 5

大きな部分は、プログラマーがローカルスコープの複雑さをより詳細に制御できることです。 let,let*およびlet recのスペクトルは、電力およびコストの両方のレベルを増加させる。 let*とlet recは基本的に単純なletのネストされたバージョンなので、いずれかを使用するとより高価になります。このグレーディングを使用すると、プログラムの最適化をマイクロマニュアすることができます。これにより、必要なタスクのレベルを選択することができます。再帰や以前のバインディングを参照する必要がない場合は、単純なletを使用して少しのパフォーマンスを節約することができます。

Schemeの等級述語に似ています。 （すなわちeq?,とequal?）

Answer 6

を考えると、この：

let f x = ... and g y = ...;; 

比較：これで

let f a = f (g a) 

：

let rec f a = f (g a) 

かつての再定義fは、以前にgを適用した結果にfを定義し適用しますa。後者は、gをaに永久に適用するためにfを再定義します。これは通常、MLバリアントでは望ましくありません。

つまり、それは言語デザイナースタイルのものです。ちょうどそれと一緒に行く。