programming-languages - 什么是按需调用？

Question

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

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

score 41 · Accepted Answer

假设我们有函数

square(x) = x * x

我们要评估square(1+2).

在call-by-value中，我们做

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

在call-by-name中，我们这样做

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

请注意，由于我们使用了两次参数，因此我们对其进行了两次评估。如果参数评估需要很长时间，那将是一种浪费。这就是按需调用解决的问题。

在call-by-need中，我们执行如下操作：

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

在第 2 步中，我们没有复制参数（如按名称调用），而是给它一个名称。然后在第 3 步中，当我们注意到我们需要的值时x，我们计算的表达式x。只有这样我们才能替代。

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

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

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

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

score 10 · Accepted Answer

想象一个函数：

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

然后我们称之为：

 add(3 * 2, 4 / 2)

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

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

该函数将返回值8。

在按需调用（也称为惰性语言）中，它的评估如下：

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

score 3 · Accepted Answer

一个简单但说明性的示例：

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此处未使用的方式相同）。

score 0 · Accepted Answer

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

#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，然后递增k1。也就是说，结果k++只是k. （但是，在返回该结果之后，k将增加 1。）

我们可以忽略里面的所有代码foo，直到该行j = c + c（第二部分）。

下面是call-by-value下这条线的情况：

当函数第一次被调用时，在它遇到 line 之前j = c + c，因为我们正在执行按值调用，所以c将具有评估的值k++。由于评估k++返回k和k为 0（从程序顶部开始），c将是0. 但是，我们确实评估了k++一次，它将设置k为 1。
该行变为j = 0 + 0，其行为与您期望的完全一样，设置j为 0 并离开c0。
然后，当我们运行时，printf("k is %i\n", k);我们得到k1，因为我们评估k++了一次。

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

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

最后，下面是call-by-need下的行的情况：

当我们遇到时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);，我们得到k1，因为我们只评估了k++一次。

希望这有助于区分按值调用、按名称调用和按需要调用的工作方式。如果更清楚地区分按值调用和按需要调用会有所帮助，请在评论中告诉我，我将在前面解释代码foo以及为什么它会以这种方式工作。

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

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

programming-languages - 什么是按需调用？

4 回答 4

Related

Reference