110

F# と OCaml (およびおそらく他の言語) の関数がデフォルトで再帰的でないのはなぜですか?

言い換えれば、言語設計者は、次recのような宣言を明示的に入力させることが良い考えだと判断したのはなぜですか。

let rec foo ... = ...

デフォルトで関数に再帰機能を与えませんか？なぜ明示的なrec構造が必要なのですか?

4

6 に答える 6

90

元のMLのフランス人とイギリス人の子孫は異なる選択をし、それらの選択は何十年にもわたって現代の変種に受け継がれてきました。したがって、これは単なるレガシーですが、これらの言語のイディオムには影響します。

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

たとえばp、OCamlでシーケンスのシャノンエントロピーを計算するときに関数を置き換えます。

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

p高階shannon関数の引数pが、本文の1行目で別の引数に置き換えられ、次に本体の2行目で別の引数に置き換えられていることに注意してくださいp。

逆に、MLファミリーの言語のBritish SMLブランチは他の選択肢を採用し、SMLのfunバインドされた関数はデフォルトで再帰的です。ほとんどの関数定義が関数名の以前のバインディングにアクセスする必要がない場合、これによりコードが単純になります。ただし、置き換えられた関数は異なる名前（など）を使用するように作成されているためf1、f2スコープが汚染され、関数の誤った「バージョン」が誤って呼び出される可能性があります。funまた、暗黙的に再帰的にバインドされた関数と非再帰的にバインドされた関数の間に不一致がありvalます。

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

ガネーシュとエディによって与えられた答えは赤いニシンであることに注意してください。let rec ... and ...彼らは、型変数が一般化されるときに影響を与えるため、関数のグループを巨人の中に配置できない理由を説明しました。これはrecSMLのデフォルトとは関係ありませんが、OCamlとは関係ありません。

于 2009-12-11T23:37:50.493 に答える
54

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

definition がある場合は、 type があり、さまざまな時点でさまざまな型に適用できるlet f x = xことが期待されます。しかし同様に、 と書くと、 の残りの部分でとして扱われることが予想されます。'a -> 'a'alet g x = (x + 1) + ...xintg

Hindley-Milner 推論がこの区別を処理する方法は、明示的な一般化ステップです。プログラムを処理している特定の時点で、型システムは停止し、「OK、これらの定義の型はこの時点で一般化されるため、誰かがそれらを使用すると、その型の任意の型変数が新たにインスタンス化されるため、この定義の他の使用を妨げることはありません。」

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

では、どの定義セットが相互に再帰的であるかを型チェッカーが知る必要があるとすれば、何ができるでしょうか? 1 つの可能性は、スコープ内のすべての定義に対して単純に依存関係の分析を行い、それらを可能な限り最小のグループに並べ替えることです。Haskell は実際にこれを行いますが、F# (および OCaml と SML) のような無制限の副作用を持つ言語では、副作用の順序も変更される可能性があるため、これは悪い考えです。代わりに、どの定義が相互に再帰的であるかを明示的にマークするようにユーザーに要求します。

于 2009-05-24T21:37:57.227 に答える
11

これが良いアイデアである主な理由は 2 つあります。

まず、再帰的な定義を有効にすると、同じ名前の値の以前のバインディングを参照できなくなります。これは、既存のモジュールの拡張などを行う場合に便利なイディオムです。

第二に、再帰的な値、特に相互に再帰的な値のセットは、定義が順番に進行し、それぞれの新しい定義が既に定義されているものの上に構築されるため、推論するのがはるかに困難です。そのようなコードを読むとき、再帰的であると明示的にマークされた定義を除いて、新しい定義は以前の定義のみを参照できるという保証があると便利です。

于 2009-05-23T02:05:55.170 に答える
5

いくつかの推測：

  • let関数をバインドするためだけでなく、他の通常の値にも使用されます。ほとんどの形式の値は再帰的であることが許可されていません。特定の形式の再帰値（関数、遅延式など）が許可されているため、これを示すための明示的な構文が必要です。
  • 非再帰関数を最適化する方が簡単な場合があります
  • 再帰関数を作成するときに作成されるクロージャには、関数自体を指すエントリを含める必要があります（したがって、関数はそれ自体を再帰的に呼び出すことができます）。これにより、再帰クロージャは非再帰クロージャよりも複雑になります。したがって、再帰が必要ないときに、より単純な非再帰的なクロージャーを作成できると便利な場合があります。
  • これにより、以前に定義された関数または同じ名前の値に関して関数を定義できます。これは悪い習慣だと思いますが
  • 余分な安全？あなたが意図したことをしていることを確認してください。たとえば、再帰的にするつもりはないが、関数内で関数自体と同じ名前の名前を誤って使用した場合、（名前が以前に定義されていない限り）文句を言う可能性があります。
  • コンストラクトはLispとSchemeのコンストラクトに似letています。letこれは非再帰的です。letrec再帰的なLet'sのSchemeには別の構成があります
于 2009-05-23T01:29:35.337 に答える
4

これを考えると：

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

比較：

let f a = f (g a)

これとともに：

let rec f a = f (g a)

前者は、に適用した結果にf以前に定義したものを適用するように再定義します。後者は、に永久ループを適用するように再定義します。これは通常、MLバリアントで必要なものではありません。fgafga

そうは言っても、それは言語デザイナースタイルのものです。それに合わせてください。

于 2010-12-22T05:30:16.877 に答える
1

その大きな部分は、プログラマーがローカル スコープの複雑さをより細かく制御できるようになることです。、およびのスペクトルはlet、電力とコストの両方のレベルを向上させます。とは本質的に simple のネストされたバージョンであるため、どちらかを使用するとコストが高くなります。このグレーディングにより、目前のタスクに必要なレベルを選択できるため、プログラムの最適化を細かく管理できます。再帰や以前のバインディングを参照する機能が必要ない場合は、単純な let にフォールバックしてパフォーマンスを少し節約できます。let*let reclet*let reclet

これは、Scheme の段階的等価述語に似ています。(すなわちeq?、eqv?およびequal?)

于 2009-05-24T22:36:23.147 に答える