Clojure - 如何测试函数表达式的相等性？

Question

假设我有以下的Clojure函数：

(defn a [x] (* x x))

(def b (fn [x] (* x x)))

(def c (eval (read-string "(defn d [x] (* x x))")))

有没有一种方法可以测试函数表达式的相等性 - 类似于某种等价的方式？

(eqls a b)

返回 true 吗？

- hawkeye

---

不可能的--函数等价性是不可判定的。 - Fred Foo

抱歉，关于赏金评论格式的问题——我没有意识到格式化不会以同样的方式工作。 - Omri Bernstein

嗨，Omri。如果你看到我的回答，你会发现我谈到了两个函数，它们的JVM字节码相同。这实际上是意图相等。我还指出，意图相等意味着外延相等（但反之不成立）。如果字节码最终不同（就像你提供的一些示例可能会出现的情况），那么我们又回到了试图实现外延相等的问题 - 我们知道这是不可判定的。希望这能让事情变得更清晰一些 - 意图相等（加上一些特殊情况）可能是我们所能期望的最好结果。 - kittylyst

@kittylyst 谢谢您的回复，我认为您的答案很有思考性。我越来越相信特殊情况（正如您所说）的数量实际上相当大，以至于我们可以有意义地测试函数等价性。例如，我认为 (* x x) 等同于 (* x x 1) 的情况可以通过注意到 * 函数的恒等值是 1 来解决。更一般地，我们可以通过获取 (f) 的结果来测试恒等值。如果给定的 f 确实具有恒等值，我们可以在等价性测试中忽略所有这些值在某个 (f ...) 中的情况。 - Omri Bernstein

@kittylyst 如果您知道如何获得函数体的JVM字节码，我很乐意学习——这对我来说听起来非常酷。 - Omri Bernstein

Answer 1

这取决于你对 “函数表达式相等性” 的确切理解。

这些函数最终会以字节码的形式存在，因此我可以将每个函数对应的字节码转储到一个 byte[] 中，然后比较这两个字节码数组。

然而，有许多不同的编写语义等效方法的方式，它们在字节码中并没有相同的表示。

通常情况下，无法在运行代码之前确定代码的作用。因此，在所有可能的输入上运行这两个代码片段是确定它们是否等效的不可能的任务。

从计算角度来看，这至少和停机问题一样糟糕，甚至可能更糟。

由于停机问题是不可判定的，所以一般情况下的答案肯定是否定的（不仅仅适用于Clojure，而是适用于所有编程语言）。

- kittylyst

Answer 2

关于Clojure没有内置能力来确定两个函数的等价性，我同意以上回答。已经证明，您无法通过功能测试（也称为黑盒测试）来确定程序的等式，因为存在停机问题（除非输入集是有限和定义的）。

我想指出，即使它们具有不同的形式（不同的字节码），也可以代数地确定两个函数的等价性。

证明等价性的代数方法是由Alonzo Church在1930年代开发的，称为Lambda演算中的beta缩减。这种方法当然适用于您问题中的简单形式（也会产生相同的字节码），也适用于产生不同字节码的更复杂的形式。

- dansalmo

Answer 3

我不能对其他人的优秀答案进行补充，但我想提供另一个帮助我的观点。例如，如果您正在测试从自己的函数返回正确函数，而不是比较函数对象，您可以尝试将该函数作为'symbol返回。

我知道这可能不是作者要求的，但对于简单的情况，这可能会起到作用。

- sp3ctum