使用未知变量简化 Prolog 中的表达式

Question

我想简化如下表达式：

2+x+3 = 5+x

我设法写了这段代码：

simplify(K, K):-
    atomic(K),!.
simplify(_ * 0, 0).
simplify(0 * _, 0).
simplify(0 + X, X).
simplify(0 + X, X).
simplify(X - 0, X).
simplify(X - 0, X).
simplify(0 / _, 0).
simplify(K + 0, E):-
    simplify(K, E).
simplify(K - 0, E):-
    simplify(K, E).
simplify(K1 + K2, R):-
    simplify(K1, E1),
    simplify(K2, E2),
    simplify_addition(E1 + E2, R).
simplify(K1 - K2, R):-
    simplify(K1, E1),
    simplify(K2, E2),
    simplify_substraction(E1 - E2, R).
simplify(K1 * K2, R):-
    simplify(K1, E1),
    simplify(K2, E2),
    simplify_multiplication(E1 * E2, R).
simplify(K1 / K2, R):-
    simplify(K1, E1),
    simplify(K2, E2),
    simplify_division(E1 / E2, R).

simplify_addition(K1 + K2, R):-
    number(K1),
    number(K2),
    R is K1 + K2.
simplify_addition(K1 + K2, K1 + K2):-
    atom(K1),
    number(K2);
    atom(K2),
    number(K1).

simplify_substraction(K1 - K2, R):-
    number(K1),
    number(K2),
    R is K1 - K2.
simplify_substraction(K1 - K2, K1 - K2):-
    atom(K1),
    number(K2);
    atom(K2),
    number(K1).

simplify_multiplication(K1 * K2, R):-
    number(K1),
    number(K2),
    R is K1 * K2.
simplify_multiplication(K1 * K2, K1 * K2):-
    atom(K1),
    number(K2);
    atom(K2),
    number(K1).

simplify_division(K1 / K2, R):-
    number(K1),
    number(K2),
    R is K1 / K2.
simplify_division(K1 / K2, K1 / K2):-
    atom(K1),
    number(K2);
    atom(K2),
    number(K1).
simplify_division(K / K, 1):-
    number(K).

现在我运行遇到的问题是我不知道如何解决 x+3 这样的问题，因为在当前状态下，如果我运行代码会简化 (2 +x+3,R)。例如，它将到达 K1 = 2+x 和 K2 = 3 的阶段，它将尝试在 simplify_addition.

中获得这两者的总和

Answer 1

这不是真正的 Prolog 问题（也许看看像 algorithm 这样的标签是否合适，即使它很笼统？），但这里有一个 Prolog 角度。具体来说，这个：

simplify_addition(K1 + K2, K1 + K2):-
    atom(K1),
    number(K2);
    atom(K2),
    number(K1).

是非常非常糟糕的 Prolog 代码，不应该这样写。在一行中终止目标的正常预期方式是逗号 ,。析取 ; 具有截然不同的含义。而且它看起来和逗号太相似了，太容易错过了！

如果您使用 ;（您不一定要这样做），您必须以真正使 ; 坚持。仅从代码的形状来看，肯定会清楚发生了与线性连词不同的事情。如果我必须使用 ; 来编写它，它将看起来像这样：

simplify_addition(K1 + K2, K1 + K2):-
    (   atom(K1),
        number(K2)
    ;   atom(K2),
        number(K1) ).

请注意，; 位于一行的开头，而通常没有 ,。缩进清楚地表明 ; 是顶级操作，而两个 , 是从属的。括号清楚地表明析取的开始和结束位置。可能会有更多的间距（在 ; 之后换行而不是在同一行上继续），但我发现这已经足够明确了。

然而，这绝不应该首先使用 ; 来编写。使用单独的子句来表达析取更清楚：

simplify_addition(K1 + K2, K1 + K2):-
    atom(K1),
    number(K2).
simplify_addition(K1 + K2, K1 + K2):-
    atom(K2),
    number(K1).

此时我们可以开始算法部分了。编译器经常使用术语“规范化”来表示表达式的转换，这些表达式不一定会简化它们，但会将它们变成更“标准”或“规范”的形状。

一个非常典型的规范化是将常量（在您的情况下，直接表示为数字）从交换运算符的左侧移动到右侧。所以 x + 2 是规范形式，但 2 + x 不是；它应该规范化为 x + 2。我们快完成了，但是第二条规则需要进行操作数的交换：

simplify_addition(K1 + K2, K1 + K2):-
    atom(K1),
    number(K2).
simplify_addition(K1 + K2, K2 + K1):-
    atom(K2),
    number(K1).

这样，当您尝试简化 2 + x + 3（实际上是 (2 + x) + 3）时，仍然会失败。但是在内部将 (2 + x) + 3 转换为 (x + 2) + 3 后它将失败。进步！

您可以做的另一个规范化是在明确定义的方向上移动关联运算中的括号：

simplify_addition((K1 + K2) + K3, K1 + (K2 + K3)).

然后上面的表达式规范化如下：

?- simplify(2 + x + 3, R).
R = x+(2+3) ;
false.

你还没有完成！即使在您完成了更多的递归简化之后，仍然存在一个根本问题，即如果 simplify_addition/2 不能进一步简化加法，则 不应失败。但我想我已经把这个 prolog 的答案延伸得够远了 :-)

使用未知变量简化 Prolog 中的表达式

Simplify Expressions in Prolog With unknown variables

prolog