什么是需求调用(call-by-need)？

Question

我想知道什么是按需调用。

虽然我在维基百科上搜索到了这里：http://en.wikipedia.org/wiki/Evaluation_strategy， 但我并不能完全理解。如果有人能够用例子来解释并指出与按值调用的区别，那将是一大帮助。

- Barshan Das

Answer 1

假设我们有以下函数：

square(x) = x * x

现在我们想要计算 square(1+2)。

在值调用中，我们执行以下步骤：

1. square(1+2)
2. square(3)
3. 3*3
4. 9

在名字调用中，我们执行以下步骤：

1. square(1+2)
2. (1+2)*(1+2)
3. 3*(1+2)
4. 3*3
5. 9

请注意，由于我们使用了两次参数，所以我们对它进行了两次计算。如果参数计算需要很长时间，那将是浪费的。这就是需要调用修复的问题。

在需要调用中，我们执行以下类似的步骤：

1. square(1+2)
2. let x = 1+2 in x*x
3. let x = 3 in x*x
4. 3*3
5. 9

在第二步中，我们不是像按名称调用那样复制参数，而是给它一个名称。然后在第三步中，当我们注意到我们需要 x 的值时，我们计算 x 的表达式。只有在这之后我们才进行替换。

顺便说一下，如果参数表达式产生了更复杂的东西，比如一个闭包，可能会有更多的 let 来消除复制的可能性。正式的规则写起来有些复杂。

请注意，对于原始操作（如 + 和 *），我们“需要”参数的值，但对于其他函数，我们采取“命名、等待和查看”的方法。我们会说原始算术运算是“严格”的。这取决于语言，但通常大多数原始操作都是严格的。

请注意，“评估”仍然意味着将其简化为一个值。函数调用总是返回一个值，而不是表达式。（其他答案中有人理解错误了。）另一方面，惰性语言通常具有惰性数据构造器，这些构造器可以具有在需要时才计算的组件，即提取时。这就是你可以拥有“无限”列表的方式——你返回的值是一个惰性数据结构。但按需调用与按值调用是与惰性与严格数据结构分开的问题。 Scheme具有惰性数据构造器（流），尽管由于Scheme是按值调用，因此构造器是语法形式，而不是普通函数。Haskell是按需调用的，但它有定义严格数据类型的方法。

如果考虑实现有所帮助，那么按名称调用的一种实现方法是将每个参数包装在thunk中；当需要参数时，您调用thunk并使用该值。按需调用的一种实现方式类似，但thunk是记忆化的；它只运行一次计算，然后保存它并在此之后仅返回保存的答案。

- Ryan Culpepper

---

Haskell不是按名调用，而是按需调用吗？ - dremodaris

Answer 2

假设有一个函数：

fun add(a, b) {
  return a + b
}

然后我们称它为：

 add(3 * 2, 4 / 2)

在按名字调用语言中，它将被计算为：

1. a = 3 * 2 = 6 2. b = 4 / 2 = 2 3. return a + b = 6 + 2 = 8

该函数将返回值8。

在延迟调用（也称为惰性调用）中，它的计算方式如下：

1. a = 3 * 2 2. b = 4 / 2 3. return a + b = 3 * 2 + 4 / 2

该函数将返回表达式3 * 2 + 4 / 2。到目前为止，几乎没有使用任何计算资源。只有在需要其值时才计算整个表达式，例如我们想要打印结果。

为什么这很有用？有两个原因。首先，如果您意外地包含了死代码，它不会拖慢程序，因此可以更高效。其次，它允许执行非常酷的操作，例如有效地计算无限列表。

fun takeFirstThree(list) {
  return [list[0], list[1], list[2]]
}

takeFirstThree([0 ... infinity])

如果使用按名称调用的语言，会在尝试创建从0到无限大的列表时挂起。而懒惰语言将简单地返回[0,1,2]。

- Jakub Hampl

---

我认为您可能将按名称调用与按值调用混淆了，并且将按需调用与按名称调用混淆了。 - Roly

我也认为这不是很准确。你所提到的“按名称调用”，实际上不是“按值调用”吗？ - mercury0114

很不幸，这个被接受的答案几乎完全错误，并没有解释什么是按需调用。人们应该知道这个答案有10个踩，有很好的理由。 - Jim Balter

Answer 3

Call-by-need 使用惰性求值。以下是一个简单而富有说明性的例子：

function choose(cond, arg1, arg2) {
   if (cond)
      do_something(arg1);
   else
      do_something(arg2);
}

choose(true, 7*0, 7/0);

现在假设我们使用渴望求值策略，那么它将急切地计算7*0和7/0。如果它是一种惰性求值的策略（按需调用），则它将仅将表达式7*0和7/0发送到函数中而不对它们进行评估。

区别在哪里？你会期望执行do_something(0)因为第一个参数被使用了，但实际上它取决于求值策略：

如果语言急切求值，则如上所述，它将首先评估7*0和7/0，那么7/0是什么？除以零错误。

但是如果求值策略是惰性的，则它将看到它不需要计算除法，它将调用do_something(0)，就像我们预期的那样，没有错误发生。

在这个例子中，惰性求值策略可以避免执行产生错误。类似地，它可以节省执行不必要的计算，因为它不会使用（就像这里没有使用7/0一样）。

- davin

---

即使是急切的编程语言也会这样做。 - Jakub Hampl

我觉得这很误导人，因为即使是自称渴望的语言，在这种情况下也不会给你一个除以零的错误 - 因为它们是渴望的，它们将首先评估布尔值，然后发现计算除法是无意义的。你所描述的渴望更像是一种评估所有内容的语言。 - Jakub Hampl

@JakubHampl 这并不是真的 - 急切求值语言首先评估函数的所有参数，然后调用它。所以在这种情况下，它会评估 true、7*0、7/0... 然后抛出错误/异常 - choose 永远不会被调用。你的论点只有在 choose 被内联化，并且编译器看到 7/0 是一个纯粹的（非副作用）计算，因此可以在没有任何语义变化的情况下删除它时才可能起作用（尽管看到保证的除以 0 错误可能构成副作用 - 定义取决于语言/编译器）。 - Adowrath

“急切求值”是一种技术，其中表达式在绑定到变量或作为参数传递时立即进行评估。7/0被绑定到arg2，因此会立即进行评估。（许多编译器实际上会在编译时对其进行评估并产生错误。） - Jim Balter

Answer 4

这里有一个具体的例子，涉及到用C语言编写的许多不同的求值策略。我将特别介绍按名称调用、按值调用和按需调用之间的区别，后者是前两者的一种组合，正如Ryan's answer所建议的那样。

#include<stdio.h>
int x = 1;
int y[3]= {1, 2, 3};
int i = 0;
int k = 0;
int j = 0;

int foo(int a, int b, int c) {
    i = i + 1;
    // 2 for call-by-name
    // 1 for call-by-value, call-by-value-result, and call-by-reference
    // unsure what call-by-need will do here; will likely be 2, but could have evaluated earlier than needed
    printf("a is %i\n", a);
    b = 2;
    // 1 for call-by-value and call-by-value-result
    // 2 for call-by-reference, call-by-need, and call-by-name
    printf("x is %i\n", x);

    // this triggers multiple increments of k for call-by-name
    j = c + c;

    // we don't actually care what j is, we just don't want it to be optimized out by the compiler
    printf("j is %i\n", j);

    // 2 for call-by-name
    // 1 for call-by-need, call-by-value, call-by-value-result, and call-by-reference
    printf("k is %i\n", k);
}

int main() {
    int ans = foo(y[i], x, k++);
    // 2 for call-by-value-result, call-by-name, call-by-reference, and call-by-need
    // 1 for call-by-value
    printf("x is %i\n", x);
    return 0;
}

我们最感兴趣的部分是 foo 被调用时，使用 k++ 作为形参 c 的实际参数。

需要注意的是 ++ 后缀运算符的工作原理 是这样的：首先 k++ 返回 k，然后将 k 加 1。也就是说，k++ 的结果只是 k。（但是，在返回该结果之后，k 将被加 1。）

我们可以忽略 foo 中第二个部分之前的所有代码，直到 j = c + c 这一行。

在按值传递的情况下，以下是此行发生的情况：

当函数第一次被调用时，在遇到行j = c + c之前，因为我们使用的是按值传递，c将具有评估k ++的值。由于评估k ++返回k，而k为0（来自程序顶部），c将为0。但是，我们确实评估了k ++一次，这将把k设置为1。

该行变为j = 0 + 0，其行为与您预期的完全相同，将j设置为0并使c保持为0。

然后，当我们运行printf("k is %i\n", k);时，我们得到k为1，因为我们评估了k ++一次。

以下是在按名称调用下发生的情况：

1. 由于该行包含 c 并且我们使用的是按需调用，因此我们将文本 c 替换为实际参数的文本 k++。因此，该行变成了 j = (k++) + (k++)。
2. 然后我们运行 j = (k++) + (k++)。其中一个 (k++) 将首先被评估，返回 0 并将 k 设置为 1。然后，第二个 (k++) 将被评估，返回 1（因为第一次评估 k++ 时将 k 设置为 1），并将 k 设置为 2。因此，我们最终得到 j = 0 + 1，并且 k 被设置为 2。
3. 然后，当我们运行 printf("k is %i\n", k); 时，我们得到 k 为 2，因为我们评估了两次 k++。

最后，这是在按需调用下发生的情况：

当我们遇到 j = c + c; 时，我们认识到这是第一次评估参数 c。因此，我们需要评估它的实际参数（一次），并将该值存储为 c 的评估结果。因此，我们评估实际参数 k++，它将返回 k，即0，因此 c 的评估结果将为0。然后，由于我们已经评估了 k++，k 将被设置为1。然后，我们使用这个 存储的评估结果 作为第二个 c 的评估结果。也就是说，与按名称调用不同，我们不会重新评估 k++。相反，我们重用以前评估出的 c 的初始值，即0。因此，我们得到 j = 0 + 0;，就像 c 是按值传递一样。而且，由于我们只评估了一次 k++，所以 k 的值为1。

如前面的步骤所述，在按需调用下，j = c + c 相当于 j = 0 + 0，并且运行结果正如你所期望的那样。

当我们运行 printf("k is %i\n", k); 时，我们得到 k 的值为1，因为我们只评估了 k++ 一次。

希望这有助于区分按值调用、按名调用和按需调用的工作方式。如果需要更清楚地区分按值调用和按需调用，可以在评论中告诉我，我会在foo中解释代码及其工作原理。

我认为维基百科上的这一行很好地总结了事情：

按需调用是按名调用的记忆化变体，如果函数参数被评估，则该值将存储以供后续使用。如果参数是纯的（即没有副作用），则这产生与按名调用相同的结果，节省了重新计算参数的成本。

- Pro Q