9

来自另一个线程的帖子说，如果一个函数可以多次调用而不改变结果，则称该函数是幂等的。

然而，使用的术语（如无副作用和返回相同结果）相对模棱两可。考虑这段代码：

public class test {

    int x = 0;
    java.util.Random r = new java.util.Random();

    public int F() {
        return x + 1;
    }

    public void F2() {
        x = r.nextInt();
    }
}

我们可以说这F()是幂等的，因为连续调用F()返回相同的值吗？

或者它不是幂等的，因为如果在两者之间调用连续调用F()不会返回相同的值F2()？

PS：计算机科学中定义的“幂等”，而不是数学。

4

4 回答 4

10

我将不同意其他答案（实际上，我现在看到我同意他们！）并说，在最常见的计算机科学用途（具有副作用的函数调用，而不是函数式编程）中，函数是如果您可以安全地用调用函数两次并仅保留第二个结果来替换函数的任何调用，则为幂等。

例如，考虑两个按名称删除文件的函数：

1) 如果文件不存在则返回成功的函数。（因为删除操作的目的是使文件不存在。）

2) 如果文件不存在，则返回“文件不存在”错误的函数。（因为无法删除文件。）

第一个是幂等的。如果你调用它并忽略结果，你可以再次调用它并且仍然得到正确的信息。完成后该文件不存在。

第二个不是幂等的。如果你调用它一次并忽略结果，你的第二次调用将失败，让你认为你没有删除文件。

在此定义下，获取当前时间的函数是幂等的，即使结果可能不同。调用该函数两次没有害处。

这个概念在客户端-服务器协议中很重要。假设您发送命令但没有得到回复，也许连接中断，也许服务器崩溃。所以你再次发送命令并得到回复。但是在第一个命令上，是命令丢失还是回复？如果命令是幂等的，那没关系。你可以只使用结果。

如果一个协议保证所有操作都是幂等的，那么较低级别的代码可以重试失败的操作、切换服务器，或者在不破坏操作语义的情况下尝试“让事情工作”。

制作一个幂等协议需要做一些事情。例如，您可能想知道如何进行明智的“删除文件”操作。一种方法是为每个文件分配一个唯一的 ID，该 ID 在文件被删除和重新创建时会发生变化。然后你把一个删除分成两半。第一个，“从名称中获取 ID”是幂等的，如果文件不存在则失败。第二个，“如果存在则删除 ID”是幂等的，如果您或其他任何人删除了文件，则成功。（一个怪癖是这并不能确定您是删除文件的那个人。）这两个幂等操作的组合提供了所需的非幂等删除操作。

于 2012-02-02T11:40:29.460 回答
5

你的函数不是幂等的。它可以返回不同的结果。给定相同的输入，幂等函数总是返回相同的输出。

更明确地说，如果 f() 是幂等的（根据计算机科学定义），那么：

int result1 = f(x);
// ... some arbitrary code
int result2 = f(x);
assert(result1 == result2);
于 2012-02-02T11:36:27.990 回答
3

试图总结其他答案和评论中出现的内容：

“幂等”只有一种定义。一个函数f是幂等的当且仅当在 的域中所有都f(f(x))相等。f(x)xf

“等于”的定义不止一种。在很多情况下，我们都有一个“等价”的概念，它代表平等，而“等价”的定义在不同的情况下可能会有所不同。

“功能”的定义不止一种。在数学中（具有传统的集合论结构），函数是一组对。函数的“域”是出现在一对第一个位置的所有元素的集合。域的任何元素都不会出现在函数中超过一对的第一个位置。函数的“范围”是出现在一对的第二个位置的所有元素的集合。范围的元素可能出现不止一次。我们说一个函数将其域的每个元素“映射”到其范围的特定元素，我们写作f(x)的意思是“其中的第二个元素f作为x其第一个元素”。

因此，很明显，要使函数具有幂等性，其范围必须是其域的子集。否则，f(f(x))是没有意义的。

在计算中，特别是在命令式语言中，函数通常被定义为一系列语句/指令，以及一些命名的输入和输出（在大多数语言中只有一个输出）。“调用”函数是一种命令式操作，意味着执行指令。但是命令式语言中的指令可能会产生副作用：它们可以改变输出以外的东西。数学以及纯函数式编程中都没有这个概念。

这些命令式“函数”，我从现在开始将其称为“例程”，可以通过两种方式与函数的数学定义相协调：

  1. 忽略副作用，并说例程是一个函数，其域是参数值的所有可能组合的集合，并将这些组合映射到例程的输出。如果函数不是“纯”的，即它的输出是否依赖于其参数之外的可变状态，或者它是否修改了其输出之外的状态，则这站在薄弱的理论基础上。原因是根据定义，数学函数不会在不同时间将其输入映射到不同的输出。数学函数在“调用”时也不会“改变”事物，因为数学函数不会被“调用”特定次数。他们只是“是”。

  2. 将副作用合并到一个数学函数中，该函数描述调用例程对机器完整状态的影响，包括例程的输出，还包括所有全局状态等。这是 CS 中的一个标准技巧，这意味着对于每个语句、指令、对例程的调用或其他任何内容，都有一个相应的函数将调用之前的机器状态映射到调用之后的机器状态。

现在，如果我们在案例 1 中应用“幂等”的定义，我们正在评估特定例程旨在实现的数学函数是否是幂等的。如果例程除了实现数学函数之外还做了任何事情，例如，如果它有任何副作用，那么我们在这里就处于非常不稳定的基础上，并且会得出误导性的结果。例如，该函数int f(int i) { puts("hello!"); return i; }可以被认为是幂等的，基于“它是恒等函数的实现！”。如果您忽略副作用，这是正确的，但这意味着该定义对于任何实际目的都是无用的，因为一旦考虑到副作用，执行表达式f(f(0))与执行表达式是不同的f(0)。f(f(0))不等于f(0)即使它们的返回值相等，如果我们不关心程序的（那部分）输出，我们只能用另一个替换一个。

如果我们在案例 2 中将“幂等”的定义应用于机器状态的函数，我们正在评估对函数的调用（带有特定参数）是否是对机器状态的幂等操作。那么我f上面的函数显然不是幂等的 - 将“hello！\n”写入其输出设备的机器状态与将“hello！\nhello！\n”写入其输出设备的机器状态不同输出设备。我认为在这种情况下也很清楚，您的函数F是幂等的（尽管它不是“纯”的，因为它的返回值取决于其形式参数以外的状态，因此它不仅仅是数学函数的实现） ，并且您的函数F2不是幂等的。test是不可变的，那么我们可以合理地开始描述F为纯的。F2那么将是无效的。

据我所知，当 compscis 在命令式语言中谈论幂等性时，他们通常是在谈论案例 2 定义的机器状态的函数是否是幂等的。但是用法可能会有所不同——如果例程是纯的，那么他们可能会谈论它所代表的数学函数是否是幂等的。在纯函数式语言中没有可讨论的机器状态，因此情况 2 不合适，并且任何与函数相关的“幂等”一词的使用都必须是情况 1。纯函数式语言中的函数总是像数学函数.

于 2012-02-02T14:28:39.163 回答
2

我也一直在试图弄清楚幂等性的真正含义，我意识到幂等性有多种定义。定义遵循两个阵营，要么是数学和函数编程函数的定义，要么是计算机科学的定义。

数学定义：f(f(x)) = f(x) for any value x。换句话说，如果函数的效果在组合下是不变的，则函数是幂等的。

计算机科学定义：如果“N > 0 个相同请求的副作用与单个请求的副作用相同”，则函数是幂等的。换句话说，如果效果在调用次数上是不变的，则函数是幂等的。

例如，采用定义为 的增量函数int f(int x) { return x+1; }。由于 f(f(x)) != f(x)，此函数将无法通过数学定义，因为它在合成下不是不变的。另一方面，它符合计算机科学的定义，因为正如史蒂夫麦克劳德所说，

int result1 = f(x);
// ... some arbitrary code
int result2 = f(x);
assert(result1 == result2);

现在，回到您的问题，您的示例中的 F() 是幂等的吗？我说是的 F() 是幂等的，但一系列调用可能不是。根据 HTTP/1.1 协议对幂等性的定义，“即使在该序列中执行的所有方法都是幂等的，一系列请求也可能不是幂等的”。

这是可能的，因为您必须将程序的状态视为函数 F() 的隐藏参数。例如，考虑 F()、F()、F2()、F() 的示例请求序列。最后一个 F() 请求不会产生与前两个相同的结果，但这没关系，因为请求不相同。您必须将程序的状态视为函数的隐藏参数，并且在最后一个请求中，状态是 x 等于一个新的随机值，但在第一个请求中，x 的状态最初为零。

资料来源：

于 2014-01-30T06:40:51.980 回答