9

別のスレッドからの投稿によると、結果を変更せずに複数回呼び出すことができる場合、関数はべき等であると言われています。

ただし、使用されている用語 (副作用なしや同じ結果を返すなど) は比較的あいまいです。次のコードを検討してください。

public class test {

    int x = 0;
    java.util.Random r = new java.util.Random();

    public int F() {
        return x + 1;
    }

    public void F2() {
        x = r.nextInt();
    }
}

F()を連続して呼び出すとF()同じ値が返されるため、これはべき等であると言えますか?

または、 が途中で呼び出された場合、を連続して呼び出すと同じ値が返されないため、べき等ではありませんか?F()F2()

PS:数学ではなく、コンピュータ サイエンスで定義されている「冪等性」。

4

4 に答える 4

10

私は他の答えに同意しません (実際、私はそれらに同意することがわかりました!)、最も一般的なコンピューター サイエンスの使用法 (関数型プログラミングではなく、副作用を伴う関数呼び出し) では、関数は関数の呼び出しを、関数を 2 回呼び出して 2 番目の結果のみを保持することで安全に置き換えることができる場合は、べき等です。

たとえば、ファイルを名前で削除するための 2 つの関数を考えてみましょう。

1) ファイルが存在しない場合に成功を返す関数。(削除操作の目的は、ファイルを存在させないためです。)

2) ファイルが存在しない場合に「ファイルが存在しません」というエラーを返す関数。（ファイルを削除できなかったため）

最初のものは冪等です。呼び出して結果を無視すると、再度呼び出しても正しい情報を取得できます。完了すると、ファイルは存在しません。

2 つ目は冪等ではありません。1 回呼び出して結果を無視すると、2 回目の呼び出しは失敗し、ファイルを削除していないと見なされます。

現在の時刻を取得する関数は、結果が異なる場合でも、この定義ではべき等です。関数を 2 回呼び出しても害はありません。

この概念は、クライアント サーバー プロトコルにおいて重要です。コマンドを送信しても応答がない場合、接続が切断されたり、サーバーがクラッシュしたとします。したがって、コマンドを再度送信すると、応答が返されます。しかし、最初のコマンドでは、コマンドが失われたのか、それとも応答なのか? コマンドがべき等である場合、それは問題ではありません。結果をそのまま使用できます。

プロトコルがすべての操作が冪等であることを保証する場合、下位レベルのコードは失敗した操作を再試行し、サーバーを切り替え、操作のセマンティクスを壊すことなく「物事を機能させる」ことを試みることができます。

冪等プロトコルを作成するには、ある程度の作業が必要です。たとえば、「ファイルの削除」操作を適切に行うにはどうすればよいか疑問に思うかもしれません。1 つの方法は、ファイルが削除されて再作成されると変更される一意の ID を各ファイルに割り当てることです。次に、削除を 2 つに分割します。最初の「名前から ID を取得」は冪等であり、ファイルが存在しない場合は失敗します。2 番目の「存在する場合は ID を削除する」は冪等であり、あなたまたは他の誰かがファイルを削除した場合に成功します。(1 つの癖は、ファイルを削除したのが自分であるかどうかを確認できないことです。) 2 つの冪等操作を組み合わせることで、必要な非冪等削除操作が提供されます。

于 2012-02-02T11:40:29.460 に答える
5

あなたの関数はべき等ではありません。さまざまな結果が返される可能性があります。同じ入力が与えられた場合、べき等関数は常に同じ出力を返します。

より明示的に、f() が冪等である場合 (コンピューター サイエンスの定義によると)、次のようになります。

int result1 = f(x);
// ... some arbitrary code
int result2 = f(x);
assert(result1 == result2);
于 2012-02-02T11:36:27.990 に答える
3

他の回答やコメントで出てきたものを要約しようとしています：

「べき等」の定義は1つだけです。の定義域内のすべてが等しいf場合に限り、関数はべき等です。f(f(x))f(x)xf

「等しい」の定義は複数あります。多くの文脈で、私たちは平等を表す「同等性」の考えを持っており、「同等性」の定義は文脈によって異なる場合があります。

「機能」には複数の定義があります。数学（従来の集合論的構成）では、関数はペアのセットです。関数の「ドメイン」は、ペアの最初の位置に表示されるすべての要素のセットです。関数内の複数のペアの最初の位置にドメインの要素は表示されません。関数の「範囲」は、ペアの2番目の位置に表示されるすべての要素のセットです。範囲の要素が複数回表示される場合があります。関数は、その定義域の各要素をその範囲の特定の要素に「マップ」すると言い、「最初の要素として持つf(x)ペアの2番目の要素」を意味すると書きます。fx

したがって、関数がべき等であるためには、その範囲がその定義域のサブセットでなければならないことは明らかです。そうでなければ、f(f(x))意味がありません。

コンピューティング、特に命令型言語では、関数は、いくつかの名前付き入力および出力（ほとんどの言語では1つの出力のみ）とともに、ステートメント/命令のシーケンスとして定義されることがよくあります。関数の「呼び出し」は、命令を実行することを意味する命令操作です。ただし、命令型言語での命令には副作用があります。出力以外のものを変更する可能性があります。この概念は、数学や純粋関数型プログラミングにはありません。

これから「ルーチン」と呼ぶこれらの命令型の「関数」は、次の2つの方法で関数の数学的定義と一致させることができます。

  1. 副作用を無視し、ルーチンは、ドメインが引数値のすべての可能な組み合わせのセットであり、それらをルーチンの出力にマップする関数であると言います。関数が「純粋」でない場合、つまり、その出力が引数を超えて可変状態に依存している場合、または出力を超えて状態を変更する場合、これは弱い理論的根拠に基づいています。その理由は、数学関数は、定義上、その入力を異なる時間に異なる出力にマップしないためです。また、数学関数は特定の回数「呼び出される」わけではないため、「呼び出される」ときに数学関数は物事を「変更」しません。彼らは単に「です」。

  2. ルーチンの呼び出しがマシンの完全な状態に与える影響を説明する数学関数に副作用を組み込みます。これには、ルーチンからの出力だけでなく、すべてのグローバル状態なども含まれます。これはCSの標準的なトリックであり、すべてのステートメント、命令、ルーチンの呼び出しなどに対して、呼び出し前のマシンの状態を呼び出し後のマシンの状態にマップする対応する関数があることを意味します。

ここで、ケース1で「べき等」の定義を適用すると、特定のルーチンが実装するように設計された数学関数がべき等であるかどうかを評価しています。ルーチンが数学関数を実装する以外のことを行う場合、たとえば、副作用がある場合、ここでは非常に不安定な状況にあり、誤解を招く結果が発生します。たとえば、この関数int f(int i) { puts("hello!"); return i; }は、「恒等関数の実装です！」という理由でべき等であると見なすことができます。そして、副作用を無視すればそれは真実ですが、それは、副作用が考慮されると、式f(f(0))を実行することは式を実行することとは異なるため、実際の目的には定義が役に立たないことを意味しますf(0)。f(f(0))戻り値が等しい場合でも、は同等f(0)ではありません。プログラムの出力（のその部分）を気にしない場合にのみ、一方を他方に置き換えることができます。

ケース2のマシン状態の関数に「べき等」の定義を適用すると、関数の呼び出し（特定の引数を使用）がマシンの状態に対するべき等操作であるかどうかを評価します。次に、f上記の私の関数は明らかにべき等ではありません。出力デバイスに「hello！\ n」が書き込まれたマシンの状態は、「hello！\ nhello！\n」が書き込まれたマシンの状態と同じではありません。出力機器。この場合、関数がべき等であることも明らかだと思いますF（ただし、戻り値は正式なパラメーター以外の状態に依存するため、「純粋」ではありません。したがって、関数は単なる数学関数の実装ではありません）。 、および関数F2はべき等ではありません。test不変だったので、F純粋であると合理的に説明し始めることができました。F2その後、無効になります。

私の知る限り、compscisが命令型言語でべき等について話すとき、彼らは通常、ケース2で定義されたマシン状態の関数がべき等であるかどうかについて話します。ただし、使用法はさまざまです。ルーチンが純粋である場合、ルーチンが表す数学関数がべき等であるかどうかについて話し合う可能性があります。純粋関数型言語では、話す機械の状態がないため、ケース2は不適切であり、関数に関連する「べき等」という用語の使用はケース1でなければなりません。純粋関数型言語の関数は常に数学関数のようなものです。 。

于 2012-02-02T14:28:39.163 に答える
2

また、冪等性が実際に何を意味するのかを理解しようとしており、冪等性の複数の定義が浮かんでいることに気付きました。定義が従う 2 つの陣営があります。数学関数および関数プログラミング関数の定義、またはコンピューター サイエンスの定義です。

数学的定義: f(f(x)) = f(x) for any value x. 言い換えれば、関数の効果が構成下で不変である場合、関数はべき等です。

コンピューター サイエンスの定義: 「N > 0 の同一のリクエストの副作用が単一のリクエストと同じである」場合、関数はべき等です。言い換えれば、効果が呼び出し回数に対して不変である場合、関数はべき等です。

たとえば、 として定義されたインクリメント関数を考えますint f(int x) { return x+1; }。この関数は、f(f(x)) != f(x) であるため、合成では不変ではないため、数学的な定義に失敗します。一方、Steve McLeod が述べたように、これはコンピュータ サイエンスの定義に適合します。

int result1 = f(x);
// ... some arbitrary code
int result2 = f(x);
assert(result1 == result2);

さて、あなたの質問に戻りますが、あなたの例の F() は冪等ですか? 私はそう言っています F() はべき等ですが、一連の呼び出しはそうではないかもしれません。冪等性の HTTP/1.1 プロトコル定義によると、「そのシーケンスで実行されるすべてのメソッドがべき等であっても、複数のリクエストのシーケンスがべき等でない可能性があります」。

これが可能なのは、プログラムの状態を関数 F() の隠しパラメーターと見なす必要があるためです。たとえば、F()、F()、F2()、F() の一連の要求の例を考えてみましょう。最後の F() リクエストは、最初の 2 つと同じ結果を生成しませんが、リクエストが同一ではないため問題ありません。プログラムの状態を関数の隠しパラメーターと見なす必要があります。最後の要求では、状態は x が新しいランダム値に等しいというものでしたが、最初の要求では x の状態は最初はゼロでした。

ソース:

于 2014-01-30T06:40:51.980 に答える