代码之家 › 专栏 › 技术社区 › Mason Wheeler

为什么确定一个函数是纯困难的?

static-analysis functional-programming algorithm

Mason Wheeler · 技术社区 · 15 年前

我昨天参加了StackOverflow开发日大会,其中一个演讲者在谈论Python。他展示了一个记忆功能,我问是否有任何方法可以防止它被用于非纯功能。他说不,这基本上是不可能的,如果有人能想出一个方法来做,这将是一个伟大的博士论文。

这让我很困惑,因为对于编译器/解释器来说,递归求解似乎并不难。在伪代码中:

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;

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

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

显然,在编译语言中,这要比解释语言容易得多,因为所有这些数字计算都是在程序执行之前完成的,因此不会减慢任何操作的速度,但我没有真正看到任何根本性的问题,这些问题会使评估变得不可能。

在这方面有更多知识的人知道我遗漏了什么吗?

7 回复 | 直到 15 年前

RafaÅ Dowgird 15 年前

这在Python中特别困难。自从 anObject.aFunc 可以在运行时任意更改,不能在编译时确定哪个函数将 anObject.aFunc() 调用,甚至它将是一个函数。

Brian 15 年前

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

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

这不是一个理论上难以解决的问题,但在实践中,很难做到整个系统不感到脆弱。

顺便说一句,我认为这不是一个好的博士论文;哈斯克尔实际上已经有了这个(版本),有了IO Monad。

我相信很多人会继续在实践中看待这个问题。(胡思乱想)20年后,我们可能会有这种情况。

Craig Stuntz 15 年前

除了这里的其他优秀答案:您的伪代码只关注函数是否修改变量。但这并不是“纯”的意思。“纯”通常意味着更接近“引用透明”,换句话说,输出完全依赖于输入。所以一些简单的方法,比如读取当前时间并使结果中的一个因素(或者从输入中读取,或者读取机器的状态,或者…)使函数非纯,而不修改任何变量。

此外,还可以编写一个修改变量的“pure”函数。

JaredPar 15 年前

当我读到你的问题时,首先想到的是。

类层次结构

确定一个变量是否被修改包括挖掘每个方法的行为,这些方法对变量进行调用以确定它是否在变化。这是。。。对于具有非虚拟方法的密封类型,有点直截了当。

但是考虑虚拟方法。必须找到每个派生类型,并验证该方法的每个重写都不会改变状态。在任何允许动态代码生成的语言/框架中,确定这一点都是不可能的,或者只是动态的(如果可能的话,这是非常困难的)。原因是派生类型集不是固定的,因为可以在运行时生成新的派生类型集。

以C为例。没有什么能阻止我在运行时生成一个派生类来重写该虚拟方法并修改状态。静态验证将无法检测这种类型的修改,因此无法验证方法是否是纯的。

Egon 15 年前

我认为主要的问题是如何有效地做到这一点。

D语言有纯函数,但您必须自己指定它们,所以编译器会知道检查它们。我认为如果您手动指定它们,那么就更容易了。

yfeldblum 15 年前

一般来说,决定一个给定函数是否是纯函数可以简化为决定某个给定程序是否会停止——众所周知,停止问题是一种无法有效解决的问题。

RHSeeger 15 年前

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

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

每一块都可以随时修改。例如:

可以重写“if”命令以使用和更新全局变量
“返回”命令,沿着相同的行,可以做相同的事情
可以是if命令的执行跟踪,当使用“if”时,将根据if命令的输入重新定义返回命令

诚然,TCL是一个极端的例子,它是最具活力的语言之一。也就是说,它强调了一个问题,即即使你已经输入函数,也很难确定函数的纯度。