replace - 替换序言中的部分表达式

Question

我需要简化 prolog 中的恒等式(例如 x+0 = x、x-x=0 等)。为此，我需要替换部分表达式(比如 x+0 为 x)。

你能帮我做替换吗？

Answer 1

Prolog 的一个优点是您可以非常轻松地解构算术表达式。您的基本模板将如下所示:

simplify(X, X)       :- number(X) ; atom(X) ; var(X).    
simplify(X+Y, X1+Y1) :- simplify(X, X1), simplify(Y, Y1).
simplify(X-Y, X1-Y1) :- simplify(X, X1), simplify(Y, Y1).
simplify(X*Y, X1*Y1) :- simplify(X, X1), simplify(Y, Y1).
simplify(X/Y, X1/Y1) :- simplify(X, X1), simplify(Y, Y1).

除了递归地遍历表达式之外，这并没有真正做任何事情。我们在运算符的两边递归调用 simplify 以便简化模式匹配，无论它们出现在表达式中的什么位置。但现在它似乎什么也没做:

?- simplify(3+X*y, Q).
Q = 3+X*y

将其视为您的空循环。有了这个，您就可以通过将“特殊情况”置于此遍历之上来开始处理您的身份。身份是您可以通过这种方式处理的一件事:

simplify(1*X, X1) :- simplify(X, X1).
simplify(X*1, X1) :- simplify(X, X1).
simplify(0+X, X1) :- simplify(X, X1).
simplify(X+0, X1) :- simplify(X, X1).

尝试一下:

?- simplify(x*1+0, Q).
Q = x 

你可以在这里看到我们为什么使用递归例程:

?- simplify(x+(y+(z*43)+0)*1, Q).
Q = x+(y+z*43)

即使 +0 深深地嵌套在结构中，它也被删除了。我们也可以做一些更彻底的简化:

simplify(_*0, 0).
simplify(0*_, 0).

这里不用递归，整个子表达式基本删除:

?- simplify(x+(y+(z*43)+1)*0, Q).
Q = x+0 ;

你还可以做一些更有趣的事情:

simplify(X*Y+Z*Y, Y1*(X1+Z1)) :- 
  simplify(X, X1), simplify(Y, Y1), simplify(Z, Z1).

尝试一下:

?- simplify(34*z+17*z, X).
X = z* (34+17) 

?- simplify(34*z+z*17, X).
X = 34*z+z*17 

此处的第二个示例揭示了此类处理的局限性。您不想必须给出模板的所有排列。如果你想让它们更智能，你可能不得不采用更智能的中间表示，或者比简单统一更智能的应用模板的方法。统一是伟大的，但它不理解交换属性或结合属性。

要更进一步，您可能想要更深入地研究 Prolog。这类问题在大多数 Prolog 书籍中都有研究；我偏爱Programming Prolog 和Art of Prolog，但我听说 Bratko 的书很棒。我建议您亲 body 验其中之一并开始深入研究。不要犹豫，问更多问题!