为什么确定一个函数是否纯粹很困难？

Question

我昨天参加了StackOverflow Dev Days大会，其中一位演讲者谈到了Python。他展示了一个Memoize函数，我问他是否有办法防止它被用于非纯函数。他说不行，这基本上是不可能的，如果有人能找出方法来做到这一点，那就很有可能成为一篇博士论文。

这让我感到困惑，因为一个编译器/解释器似乎可以递归解决这个问题。伪代码如下：

function isPure(functionMetadata): boolean;
begin
   result = true;
   for each variable in functionMetadata.variablesModified
      result = result and variable.isLocalToThisFunction;
   for each dependency in functionMetadata.functionsCalled
      result = result and isPure(dependency);
end;

这就是基本思想。 显然，您需要某种检查来防止相互依赖的函数无限递归，但这不太难设置。

接受函数指针的高阶函数可能存在问题，因为它们无法在静态上进行验证，但我的原始问题假定编译器具有某种语言约束，以指定只能将纯函数指针传递给某个参数。 如果存在一个这样的约束条件，那么可以用它来满足要求。

显然，在编译语言中比在解释语言中更容易实现，因为所有这些数字运算都会在程序执行之前完成，因此不会减慢任何速度，但我真的看不出任何根本性问题会使其无法评估。

是否有更多了解这个领域的人知道我缺少什么？

- Mason Wheeler

---

必须是任何被访问的变量都必须是本地的，而不仅仅是修改的。一个函数的结果取决于全局变量的当前值，即使它不修改该全局变量，也显然不是纯函数。 - caf

显而易见的问题是：日志记录是否会影响纯度？我认为相反，实际上修改全局值（如果这不会抛出异常）并不会影响方法的结果，因此即使它明显不是纯的，也允许进行记忆化！ - Matthieu M.

Answer 1

你还需要注释每个系统调用，每个FFI...

而且最微小的“泄漏”往往会泄漏到整个代码库中。

这不是一个理论上难以解决的问题，但在实践中，以一种使整个系统不感到脆弱的方式实现非常非常困难。

顺便说一句，我认为这并不是一个好的博士论文课题；Haskell 已经有效地使用了 IO monad（其中一个版本）。

我相信很多人仍在继续研究这个问题在实践中的应用。（猜测）20年后我们可能会有这个技术。

- Brian

---

计算机人工智能虽然仅有4-6年的时间，但它肯定能够为我们解决这个问题 :) - JaredPar

在 Haskell 中，每个函数都是纯的。IO 也不改变这一点。嗯，除了那些使用 unsafePerformIO 的函数。 - Andrey Vlasovskikh

批注所有系统类是.NET在其代码合约中所做的。如果有疑问，它会假设该方法不是纯净的。 - Jonathan Allen

Jared：计算机人工智能不是在过去的30年里一直“只有4-6年”的距离吗？ :P - Mason Wheeler

@梅森 或者甚至可能50年左右 %) - Vanya

@Mason - 我认为Jared在开玩笑。 - Chris Lutz

Answer 2

在Python中这尤其困难。因为anObject.aFunc可以在运行时任意更改，所以你无法在编译时确定anObject.aFunc()将调用哪个函数，甚至无法确定它是否是一个函数。

- Rafał Dowgird

---

哎呀！好的，我明白那会让事情变得更加困难。 - Mason Wheeler

还有更多 - eval，setattr（），__gettattr __（）做一些奇怪的事情等等。像这样的功能使语言难以静态分析。 - Rafał Dowgird

Answer 3

除了其他优秀的回答之外：您的伪代码只考虑函数是否修改变量。但这并不是“纯”的真正含义。“纯”通常意味着更接近“引用透明”。换句话说，输出完全取决于输入。因此，即使不修改任何变量，读取当前时间并将其作为结果的因素（或从输入读取，或读取机器的状态等）也会使函数非纯。

此外，您可以编写一个修改变量的“纯”函数。

- Craig Stuntz

---

+1 无副作用并不意味着只使用不可变值。 - Andrey Vlasovskikh

Answer 4

当我看到你的问题时，第一时间蹦出来的是以下内容：

类层次结构

确定变量是否被修改包括查找每个调用该变量的方法，以确定它是否被改变。对于具有非虚拟方法的密封类型来说，这是相当直接的。

但是考虑到虚拟方法。您必须找到每一个派生类型，并验证该方法的每一个覆盖是否不会更改状态。在任何允许动态代码生成或仅仅是动态的语言/框架中，这是根本不可能的。原因是派生类型的集合不是固定的，因为可以在运行时生成新的派生类型。

以C#为例。没有任何限制我在运行时生成一个派生类，覆盖该虚拟方法并修改状态。静态验证将无法检测到此类修改，因此无法验证该方法是纯净的还是不纯的。

- JaredPar

---

哦，说得好。多态肯定会使事情变得复杂。不过这可以通过在基本虚拟函数上放置“纯约束”来解决。 - Mason Wheeler

Answer 5

请注意复杂性也取决于编程语言。对于更动态的语言，可以随时重新定义任何东西。例如，在Tcl中。

proc myproc {a b} {
    if { $a > $b } {
        return $a
    } else {
        return $b
    }
}

每一个部分都可以随时修改。例如：

• "if"命令可以重写以使用和更新全局变量
• "return"命令也可以做同样的事情
• 在if命令上可能有执行跟踪，当使用“if”时，基于if命令的输入重新定义return命令

诚然，Tcl是一个极端的例子；它是最动态的语言之一。尽管如此，它突显了一个问题：即使你已经输入了函数，确定其纯度也可能很困难。

- RHSeeger

Answer 6

我认为主要问题在于高效地完成它。

D语言具有纯函数，但您必须自己指定它们，以便编译器知道要检查它们。我认为如果您手动指定它们，那么完成它会更容易。

- Egon

Answer 7

通常情况下，判断一个给定的函数是否为纯函数可以归结为判断任何给定程序是否会停机——而众所周知，停机问题是一种无法有效解决的问题。

- yfeldblum

---

我知道停机问题，但你为什么说它是等价的？ - Mason Wheeler

假设我编写了一个程序P，它模拟了一些输入函数F的执行（即P是一个解释器）。假设P被编写成在完全评估F并立即在执行任何F的不纯步骤后停止运行（同时输出指示其停止的原因）。由于某些F可能具有“f a = f a”的形式 - Haskell语法表示使用相同参数递归调用自身的带有一个参数的函数 - 因此存在某个F，使得P执行F将不会停止。因此，OP的问题可归约为停机问题。 - yfeldblum

请注意，在 Haskell 中，如果我们摆脱允许在纯代码内部使用某些不纯代码的漏洞，编译器可以通过查看类型轻松确定哪些代码是确定纯净的，哪些代码不确定纯净。Haskell 在类型层面上表示不纯洁性。 - yfeldblum

一般来说，计算机中的纯函数并不排除非终止（或异常终止）函数，正是出于这个原因。Haskell实际上将非终止定义为一种特殊的返回值（“底部”），它有效地破坏了任何试图检查它的操作。 - bdonlan