两个Python函数是否功能等价，有办法知道吗？

Question

假设我有两个 Python 函数 f 和 g:

def f(x):
    y = x**2 + 1
    return y

def g(x):
    a = x**2
    b = a + 1
    return b

这两个函数在功能上是明显等价的（都返回 x**2+1）。

我的“功能等价”定义如下：

如果两个函数 f 和 g 在相同的输入下总是产生相同的输出，则 f 和 g 是功能等价的。

此外，假设 f 和 g 中没有全局变量。

是否有可能自动确定（无需人工检查）Python 函数 f 和 g 是否功能等价？

- applecider

---

我猜你可以检查它们是否编译成相同的字节码，但这可能会产生错误的结果。 - TigerhawkT3

@TigerhawkT3，你知道上面例子中的f和g是否会编译成相同的字节码吗？ - applecider

根据我的经验，字节码检查更多的是相似的样式而不是实际功能。例如，你如何编写for循环会在不改变其他任何东西的情况下彻底改变字节码。@TigerhawkT3 - Slater Victoroff

你可以尝试访问https://en.wikipedia.org/wiki/Mathematical_induction。 - ashwinjv

您可以使用 dis.dis(myfunction) 检查字节码。如果两个函数编译成相同的字节码，则它们必须在功能上等效（至少根据编译器）。然而，正如我上面提到的和 Slater 注意到的那样，可能会出现假阴性 - 对于两个在功能上等效的函数存在不同的字节码。 - TigerhawkT3

Answer 1

根据 莱斯定理，不行。如果你能做到这一点，就可以解决停机问题。（即使保证f和g总是会停机，这仍然是真的。）

- user2357112

---

啊，实际上这并不是完全正确的，因为Python函数不是抽象的、不透明的对象。你可以比较它们是否具有相同的字节码。 - Marcin

@Marcin：首先，不，比较字节码根本行不通。 其次，即使您添加了其他需要比较的区别特征，该比较仍然无法将问题中的两个函数识别为等效。第三，图灵机也不是不透明的。您可以像比较和分析两个Python函数一样轻松地比较和分析两个图灵机，但是任何分析都无法回答“我的新算法是否与旧算法产生相同的结果？”这样的非平凡问题。 - user2357112

可以使用Z3 Python API证明一些函数的等价性。 - Anderson Green

@AndersonGreen：这些是数学意义上的函数。这个问题讨论的是Python函数对象的函数。有时可以证明两个Python函数对象的函数在意义上是等价的，但在实际有用的情况下不太可能，并且它看起来与数学意义上的函数的证明非常不同。 - user2357112

Answer 2

如果这些函数确实是同一个对象，你可以简单地使用f == g来判断它们是否是同一对象。

其次，如果这些函数有相同的字节码（f.func_code.co_code），那么它们是等效的。

同样地（但可能更可移植），您可以使用dis.dis获取相同的信息。请注意，这将受到误报的影响，就像在这种情况下一样。

据我了解，dill会更好地处理这个问题，并允许您检索函数文本。有了这些信息，您可以使用ast分析文本，并执行类似于优化编译器的分析，以确定代码是否可以“优化”为相同的语法树。同样地，有些功能等效的函数不能简单地缩小为相同的ast。

因此，对于某些功能等效的函数对，可以进行此检测，但始终会存在误报。

- Marcin

---

相同的 co_code 并不能保证两个函数是等价的。def f(x): return x + 1和def f(x): return x + 2在相同的co_code下。 - user2357112

Answer 3

是的。你可以为实际的计算机做这个，因为它们不是具有无限内存的图灵机，你知道输入集是有限的，因此两个忙碌的海狸将限制运行时间，这意味着你有一个告诉你是否会停止的预言机。

例如，对于整数函数，你只需尝试每个可能的输入：

class integer_function:
    __eq__(self, other):
        for i in range(-sys.maxint - 1, sys.maxint):
            s = multiprocessing.Process(self, [i])
            o = multiprocessing.Process(other, [i])
            s.start
            o.start
            dont know how to write in python but basically wait a hugely many instructions which bounds the running time of s and o until they must halt or is known to run forever

            if s.is_alive() and not o.is_alive() or not s.is_alive() and o.is_alive():
                return False
            if s.is_alive() and o.is_alive():
                break
            if not self(i) == other(i):
                return False
    return True 

这将告诉你它们是否在功能上等效。

我非常确定这种方法适用于任何Python函数。

- Peixuan Song