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

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年后我们可能会有这个.

Answer 2

在Python中尤其困难.由于anObject.aFunc可以在运行时任意更改,因此无法在编译时确定将anObject.aFunc()调用哪个函数,或者甚至根本不是函数.