関数が純粋であるかどうかを判断することが難しいのはなぜですか？

StackOverflow https://stackoverflow.com/questions/1609303

質問

私は昨日StackOverflow Dev Daysコンベンションに参加し、講演者の一人がPythonについて話していました。彼はMemoize関数を示し、非純粋関数で使用されないようにする方法があるかどうかを尋ねました。彼はいいえ、それは基本的に不可能であり、誰かがそれを行う方法を見つけ出すことができれば、素晴らしい博士論文になるでしょう。

コンパイラー/インタープリターが再帰的に解決することはそれほど難しくないと思われるので、その種の混乱を招きました。擬似コード：

function isPure(functionMetadata): boolean;
begin
   result = true;
   for each variable in functionMetadata.variablesModified
      result = result and variable.isLocalToThisFunction;
   for each dependency in functionMetadata.functionsCalled
      result = result and isPure(dependency);
end;

それが基本的な考え方です。明らかに、相互に依存する関数の無限再帰を防ぐために何らかのチェックが必要ですが、設定するのはそれほど難しくありません。

関数ポインターを取る高階関数は静的に検証できないため問題があるかもしれませんが、私の元の質問は、コンパイラーが純粋な関数ポインターのみを渡すことができるように何らかの言語の制約があることを前提としています特定のパラメーター。存在する場合、それを使用して条件を満たすことができます。

明らかに、これは解釈された言語よりもコンパイルされた言語の方が簡単です。これは、プログラムの実行前にすべてのこの数値計算が行われ、速度が低下しないためですが、根本的な問題は実際にはありません評価できないようにします。

この分野でもう少し知識がある人は、私が何を失っているのか知っていますか？

役に立ちましたか？

解決

Pythonでは特に困難です。 anObject.aFunc は実行時に任意に変更できるため、コンパイル時に anObject.aFunc（）を呼び出す関数を決定することはできません。 。

他のヒント

また、すべてのシステムコール、すべてのFFIに注釈を付ける必要があります...

さらに、最も小さな「リーク」は、コードベース全体に漏れる傾向があります。

これは理論的に難解な問題ではありませんが、実際には、システム全体が脆く感じられないようにするのは非常に困難です。

余談ですが、これが良い博士論文になるとは思いません。 Haskellは、IOモナドを使用して、事実上これ（のバージョン）をすでに持っています。

そして、私は多くの人がこの「実践」を見続けていると確信しています。 （野生の憶測）20年後にはこれが起こるかもしれません。

ここにある他の優れた答えに加えて：擬似コードは、関数が変数を変更するかどうかだけを調べます。しかし、それは実際には「純粋」ではありません。手段。 ＆quot; Pure＆quot;通常、「参照的に透明」に近いものを意味します。つまり、出力は入力に完全に依存します。そのため、現在の時間を読み取り、結果の要素を作成する（または入力から読み取る、またはマシンの状態を読み取る、など）だけで、変数を変更せずに関数を非純粋にします。

また、「純粋な」と書くこともできます。変数を変更した関数。

質問を読んだときに最初に思い浮かんだことがあります。

  

クラス階層

変数が変更されたかどうかの判断には、変数で呼び出されたすべてのメソッドを掘り下げて、変数が変化しているかどうかを判断する行為が含まれます。これは...非仮想メソッドを使用した密閉型の場合、やや単純です。

ただし、仮想メソッドを検討してください。すべての単一の派生型を見つけ、そのメソッドのすべての単一のオーバーライドが状態を変化させないことを確認する必要があります。これを決定することは、動的なコード生成を可能にするか、単に動的な言語/フレームワークではまったく不可能です（可能であれば、非常に困難です）。理由は、実行時に新しいタイプを生成できるため、派生タイプのセットが固定されていないためです。

例としてC＃を取り上げます。実行時にその仮想メソッドをオーバーライドして状態を変更する派生クラスを生成することを妨げるものは何もありません。静的検証では、このタイプの変更を検出できないため、メソッドが純粋であるかどうかを検証できませんでした。

主な問題はそれを効率的に行うことだと思います。

D言語には純粋な関数がありますが、自分で指定する必要があるため、コンパイラはそれらをチェックする必要があります。手動で指定すると、簡単に実行できると思います。

特定の関数が純粋であるかどうかを判断することは、一般に、特定のプログラムが停止するかどうかを判断することで軽減できます。

複雑さは言語にも依存することに注意してください。より動的な言語の場合は、いつでも再定義できます。たとえば、Tclでは

proc myproc {a b} {
    if { $a > $b } {
        return $a
    } else {
        return $b
    }
}

そのすべてをいつでも変更できます。例：

  • ＆quot; if＆quot;コマンドを書き換えて、グローバル変数を使用および更新することができます
  • 「戻る」コマンドは、同じ行に沿って、同じことを行うことができます
  • ifコマンドの実行トレースは、「if」使用される場合、ifコマンドへの入力に基づいてreturnコマンドが再定義されます

確かに、Tclは極端なケースです。最も動的な言語の1つです。そうは言っても、関数を一度入力しても関数の純度を判断するのは難しいという問題を強調しています。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top