什么是按需呼叫？

Question

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

虽然我在维基百科中搜索并在这里找到它： http://en.wikipedia.org/wiki/Evaluation_strategy, 但无法正确理解。 如果有人可以用一个例子来解释并指出按值调用的区别，那将是一个很大的帮助。

Answer 1

假设我们有这个函数

square(x) = x * x

，并且想要计算 square(1+2)。

在按值调用中，我们执行

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

在call-by-name中，我们执行

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

在步骤 2 中，不要复制参数（如 call-by- name），我们给它一个名字。然后在第 3 步中，当我们注意到需要 x 的值时，我们会计算 x 的表达式。只有这样我们才可以替代。

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

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

另请注意，“评估”仍然意味着减少到一个值。函数调用始终返回一个值，而不是表达式。 （其他答案之一犯了这个错误。）OTOH，惰性语言通常具有惰性数据构造函数，它可以具有按需评估的组件，即在提取时评估的组件。这就是您如何拥有“无限”列表的方法——您返回的值是一个惰性数据结构。 但是按需要调用与按值调用是与惰性数据结构与严格数据结构不同的问题。Scheme 具有惰性数据构造函数（流），尽管由于Scheme 是按值调用，因此构造函数是语法形式，而不是普通函数。 Haskell 是按需调用的，但它有定义严格数据类型的方法。

如果有助于思考实现，那么 call-by-name 的一种实现是将每个参数包装在一个 thunk 中；当需要参数时，您可以调用 thunk 并使用该值。 call-by-need 的一种实现是类似的，但是 thunk 是 memoizing；它只运行一次计算，然后保存它并返回保存的答案。

Answer 2

想象一个函数：

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

然后我们调用它：

 add(3 * 2, 4 / 2)

在按名称调用语言中，它将被评估为：

1. a = 3 * 2 = 6
2. b = 4 / 2 = 2 code>
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]。

Answer 3

按需调用使用惰性求值。一个简单但说明性的示例：

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 一样）。

Answer 4

这是用 C 编写的一堆不同评估策略的具体示例。我将具体介绍按名称调用、按值调用和按需要调用之间的区别，这是一种组合前两个，正如 Ryan 的回答所建议的。

#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（第二部分）。

以下是按值调用下这一行发生的情况：

1. 首次调用函数时，在遇到 j = c + c 行之前，因为我们正在执行按值调用，c 将具有计算 k++ 的值。由于计算 k++ 返回 k，并且 k 为 0（从程序顶部开始），因此 c 将是<代码>0。但是，我们确实计算了 k++ 一次，这会将 k 设置为 1。
2. 该行变为 j = 0 + 0，其行为与正如您所期望的，将 j 设置为 0，并将 c 保留为 0。
3. 然后，当我们运行 printf("k is %i\n", k ); 我们明白了k 为 1，因为我们计算了 k++ 一次。

以下是 call-by-name 下的行发生的情况：

1. 由于该行包含 c 并且我们正在使用 call-by-name，因此我们替换文本 c 与实际参数的文本 k++。因此，该行变为j = (k++) + (k++)。
2. 然后我们运行j = (k++) + (k++)。其中一个 (k++) 将首先被求值，返回 0 并将 k 设置为 1。然后，第二个 (k++ ) 将被求值，返回 1 （因为 k 在第一次求值 k++ 时被设置为 1），并设置 < code>k 到 2。因此，我们最终得到j = 0 + 1 和 k 设置为 2。
3. 然后，当我们运行 printf("k is %i\n", k);，我们得到 k 是 2，因为我们计算了 k++ 两次。

最后，call-by-need 下的行会发生以下情况：

1. 当我们遇到 j = c + c; 时，我们认识到这是参数 c 被评估。因此，我们需要评估其实际参数（一次）并将该值存储为 c 的评估。因此，我们计算实际参数k++，它将返回k，即0，因此c的计算将为0。然后，由于我们评估了 k++，k 将被设置为 1。然后我们使用这个存储的评估作为第二个 c 的评估。也就是说，与按名称调用不同，我们不会重新评估 k++。相反，我们重用之前评估的 c 初始值，即 0。因此，我们得到 j = 0 + 0; 就像 c 一样> 是按值传递的。而且，由于我们仅计算 k++ 一次，因此 k 为 1。
2. 如上一步所述，j = c + c 为 j = 0 + 0 在按需调用下，它的运行完全按照您的预期。
3. 当我们运行 printf("k is %i\n", k); 时，我们得到 k 为 1，因为我们只计算了 k++一次。

希望这有助于区分按值调用、按名称调用和按需要调用的工作方式。如果更清楚地区分按值调用和按需要调用有帮助，请在评论中告诉我，我将在 foo 中解释前面的代码及其工作原理就是这样。

我认为维基百科的这句话很好地总结了事情：

按需要调用是按名称调用的记忆变体，其中，如果对函数参数进行求值，则存储该值以供后续使用。如果参数是纯参数（即没有副作用），则这会产生与按名称调用相同的结果，从而节省了重新计算参数的成本。