3

次の 3 つの述語があるとします。

Predicate<int> pred1 = x => x > 0;
Predicate<int> pred2 = x => x > 0 && true;
Predicate<int> pred3 = x => false;

人間の観点からは、pred1とpred2が等価であると言うのは自明ですが、そうでpred3はありません。同等とは、考えられるすべての入力値に対して、両方によって出力される値が同じであることを意味しpred1ますpred2。

特定の述語の一意のハッシュを計算したいと思います。同等である 2 つの述語は同じハッシュを持つ必要があり ( と のようpred1にpred2)、同等でない 2 つの述語は同じであってはなりません ( と のようpred1にpred3)。

以前に (これも .NET 言語で) 実行されたことはありますか? 副作用は基本的にそのような分析の悩みの種であることを私は知っています。しかし、副作用を「禁止」する場合、.NET で (迅速に) 実行できますか?

この要件に対する最善のアプローチは何でしょうか?

4

1 に答える 1

8

コメントで既に述べたように、これを解決することは理論的には不可能です。少なくとも、述語が終了しない可能性のあるコードを実行できる場合 (再帰呼び出しなど)、一般的なケースでは、プログラムを実装できないという証拠があることを意味します。すべての入力でこれを正しく行うことができます。

実際には、それは本当にあなたが何をしたいかによって異なります。述語を単純化するためにいくつかの単純な規則を適用したい場合は、それを行うことができます。すべての状況を処理できるわけではありませんが、実際に重要なケースを処理できる場合もあります。

F# は ML ファミリの言語 (これらの種類の問題を解決するために設計されている) から継承されているため、F# で簡単な例を記述します。C# では、式ツリーに対してビジターを使用して同じことを行うことができますが、おそらく 10 倍長くなります。

したがって、F# の引用符を使用すると、2 つの述語を次のように記述できます。

let pred1 = <@ fun x -> x > 0 @>
let pred2 = <@ fun x -> x > 0 && true @>

ここで、式ツリーをたどって、次のような単純なリダクションを実行します。

if true then e1 else e2   ~> e1
if false then e1 else e2  ~> e2
if e then true else false ~> e

F# でこれを行うには、式を再帰的に反復処理します。

open Microsoft.FSharp.Quotations

// Function that implements the reduction logic
let rec simplify expr =
  match expr with
  // Pattern match on 'if then else' to handle the three rules
  | Patterns.IfThenElse(Simplify(True), t, f) -> t
  | Patterns.IfThenElse(Simplify(False), t, f) -> f
  | Patterns.IfThenElse(cond, Simplify(True), Simplify(False)) -> cond      

  // For any other expression, we simply apply rules recursively
  | ExprShape.ShapeCombination(shape, exprs) ->
      ExprShape.RebuildShapeCombination(shape, List.map simplify exprs)
  | ExprShape.ShapeVar(v) -> Expr.Var(v)
  | ExprShape.ShapeLambda(v, body) -> Expr.Lambda(v, simplify body)

// Helper functions and "active patterns" that simplify writing the rules    
and isValue value expr = 
  match expr with
  | Patterns.Value(v, _) when v = value -> Some()
  | _ -> None

and (|Simplify|) expr = simplify expr
and (|True|_|) = isValue true
and (|False|_|) = isValue false

ここで and を呼び出すsimplify pred1とsimplify pred2、結果は同じ式になります。明らかに、完全な説明を 1 つの回答に収めることはできませんが、その考え (および、F# がここで本当に最適なツールである理由) を理解していただければ幸いです。

于 2014-06-13T15:24:16.953 に答える