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

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;

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

采用函数指针的高阶函数可能有问题，因为它们无法静态验证，但我最初的问题假设编译器有某种语言约束来指定只能将纯函数指针传递给某个参数。如果存在，则可以用来满足条件。

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

在这方面有更多知识的人知道我错过了什么吗？

Answer 1

您还需要注释每个系统调用、每个 FFI、...

此外，最微小的“泄漏”往往会泄漏到整个代码库中。

这在理论上不是一个棘手的问题，但在实践中很难以一种整个系统都不会感到脆弱的方式去做。

顺便说一句，我不认为这是一篇好的博士论文； Haskell 实际上已经有了这个(一个版本)，带有 IO monad。

而且我相信很多人会继续关注这个“实践”。 (疯狂猜测)20 年后我们可能会拥有这个。