9

私の問題: 記号式の操作。

シンボリック式は、+、-、*、/、min、max などの演算子を使用して、整数の定数と変数から作成されます。より正確には、式を次のように表現します (Caml コード):

type sym_expr_t = 
  | PlusInf
  | MinusInf
  | Const of int
  | Var of var_t
  | Add of sym_expr_t * sym_expr_t
  | Sub of sym_expr_t * sym_expr_t
  | Mul of sym_expr_t * sym_expr_t
  | Div of sym_expr_t * sym_expr_t
  | Min of sym_expr_t * sym_expr_t
  | Max of sym_expr_t * sym_expr_t

有用で効率的な計算 (例: a + b - a = 0 または a + 1 > a) を実行するには、ある種の正規形が必要であり、それを操作する必要があると思います。上記の表現はおそらくうまく機能しません。

誰かがこれにどのようにアプローチすべきか教えてもらえますか? コードは必要ありません。やり方がわかれば簡単に書けます。構築/単純化/比較のための正規形および/またはアルゴリズムの表現を提示する論文へのリンクも役立ちます。

また、これを行う Ocaml ライブラリを知っていれば教えてください。

4

2 に答える 2

4

と をドロップアウトした場合Min、Max正規形は簡単です。それらは変数の分数体の要素です。つまりP[Vars]/Q[Vars]、PはQ多項式です。最小値と最大値についてはわかりません。最も簡単な方法は、それらを if/then/else テストと見なし、式の先頭にフロートさせることです (プロセス内のものを複製します)。たとえば、P(Max(Q,R))に書き換えてP(if Q>R then Q else R)からに書き換えif Q>R then P(Q) else P(R)ます。

式の正規形を見つけるには、次の 2 つの方法を知っていますexpr。

  • expr -> expr直感に対応する書き換えルールを定義し、それらが正規化されていることを示します。これは、正しいことがわかっている方程式を導き出すことによって行うことができます。そこから、Add(a,Add(b,c)) = Add(Add(a,b),c)どちらかまたはその逆を導き出すことができますAdd(a,Add(b,c)) -> Add(Add(a,b),c)。しかし、Church-Rosser と正規化を示す必要がある方程式系があります。確かに汚いビジネス。

  • あなたの値の「セマンティック」を与えるというよりセマンティックなアプローチをとってください: の要素exprは、実際には type に存在する数学オブジェクトの表記ですsem。のオブジェクトの適切な (一意の) 表現を見つけsem、次に評価関数を見つけ、expr -> sem最後に (必要に応じて、たとえば等価性チェックを行う必要はありませんが) 具体化を見つけsem -> exprます。両方の変換の合成により、自然に正規化手順が得られます。たとえば、Add 書き換えの方向について心配する必要はありません (具体化関数から任意の選択が自然に発生します)。たとえば、多項式分数の意味空間は次のようになります。

.

  type sem = poly * poly
  and poly = (multiplicity * var * degree) list
  and multiplicity = int
  and degree = int

もちろん、これは必ずしも簡単ではありません。Min 関数と Max 関数を使用してセマンティック空間にどのような表現を与えるかはよくわかりません。

編集：外部ライブラリに関しては、私は何も知りませんし、あるかどうかもわかりません。他の記号代数ソフトウェアへのバインドを探す必要があるかもしれませんが、私は聞いたことがありません (数年前にジェーン ストリートのサマー プロジェクトがありましたが、成果物が作成されたかどうかはわかりません)。
本番アプリケーションでそれが必要な場合は、バインディングを自分で書くことを直接検討する必要があります。セージまたはマキシマに。私はそれがどのようになるかわかりません。

于 2011-04-21T14:20:44.177 に答える
3

このような問題に対する通常のアプローチは次のとおりです。

  1. のような文字列で開始します。"a + 1 > a"
  2. レクサーを通過し、入力を個別のトークンに分割します。[Variable('a'); Plus; Number(1); GreaterThan; Variable('a')]
  3. トークンを構文ツリーに解析します (現在のもの)。ここで、演算子の優先順位規則を使用します。Max( Add( Var('a'), Const(1)), Var('a'))

  4. 構文ツリーを解釈して最終結果を取得できる関数を作成する

    let eval_expr expr = match expr with
    | Number n -> n
    | Add a b -> (eval_expr a) + (eval_expr b)
    ...

構文を許してください。私はしばらく Ocaml を使用していません。

ライブラリについては、頭に浮かんだことは何も覚えていませんが、確かに簡単に利用できる優れたライブラリがあります。これは、FP コミュニティが好んで行う種類のタスクです。

于 2011-04-21T14:11:07.773 に答える