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是多项式。对于 Min 和 Max，我不知道；我想最简单的方法是将它们视为 if/then/else 测试，并使它们浮动到表达式的顶部（在过程中复制内容），例如P(Max(Q,R))将被重写为P(if Q>R then Q else R)，然后在if Q>R then P(Q) else P(R).

我知道为您的表达式找到范式的两种不同方法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实际上是一个存在于类型中的数学对象的符号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 函数的语义空间的表示形式是什么。

编辑：关于外部库，我不知道，也不确定是否有。您也许应该寻找与其他符号代数软件的绑定，但我还没有听说过（几年前有一个 Jane Street Summer Project 关于它，但我不确定是否有任何可交付成果）。
如果您需要将其用于生产应用程序，也许您应该直接考虑自己编写绑定，例如。到圣人或千里马。我不知道会是什么样子。

于 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 回答