我想知道什么是按需调用。
虽然我在维基百科上搜索到了这里:http://en.wikipedia.org/wiki/Evaluation_strategy, 但我并不能完全理解。如果有人能够用例子来解释并指出与按值调用的区别,那将是一大帮助。
我想知道什么是按需调用。
虽然我在维基百科上搜索到了这里:http://en.wikipedia.org/wiki/Evaluation_strategy, 但我并不能完全理解。如果有人能够用例子来解释并指出与按值调用的区别,那将是一大帮助。
square(x) = x * x
现在我们想要计算 square(1+2)
。
在值调用中,我们执行以下步骤:
square(1+2)
square(3)
3*3
9
在名字调用中,我们执行以下步骤:
square(1+2)
(1+2)*(1+2)
3*(1+2)
3*3
9
请注意,由于我们使用了两次参数,所以我们对它进行了两次计算。如果参数计算需要很长时间,那将是浪费的。这就是需要调用修复的问题。
在需要调用中,我们执行以下类似的步骤:
square(1+2)
let x = 1+2 in x*x
let x = 3 in x*x
3*3
9
在第二步中,我们不是像按名称调用那样复制参数,而是给它一个名称。然后在第三步中,当我们注意到我们需要 x
的值时,我们计算 x
的表达式。只有在这之后我们才进行替换。
顺便说一下,如果参数表达式产生了更复杂的东西,比如一个闭包,可能会有更多的 let
来消除复制的可能性。正式的规则写起来有些复杂。
请注意,对于原始操作(如 +
和 *
),我们“需要”参数的值,但对于其他函数,我们采取“命名、等待和查看”的方法。我们会说原始算术运算是“严格”的。这取决于语言,但通常大多数原始操作都是严格的。
假设有一个函数:
fun add(a, b) {
return a + b
}
然后我们称它为:
add(3 * 2, 4 / 2)
在按名字调用语言中,它将被计算为:fun takeFirstThree(list) {
return [list[0], list[1], list[2]]
}
takeFirstThree([0 ... infinity])
如果使用按名称调用的语言,会在尝试创建从0到无限大的列表时挂起。而懒惰语言将简单地返回[0,1,2]
。
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
一样)。
true
、7*0
、7/0
... 然后抛出错误/异常 - choose
永远不会被调用。你的论点只有在 choose
被内联化,并且编译器看到 7/0
是一个纯粹的(非副作用)计算,因此可以在没有任何语义变化的情况下删除它时才可能起作用(尽管看到保证的除以 0 错误可能构成副作用 - 定义取决于语言/编译器)。 - Adowrath这里有一个具体的例子,涉及到用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 ++
一次。以下是在按名称调用下发生的情况:
c
并且我们使用的是按需调用,因此我们将文本 c
替换为实际参数的文本 k++
。因此,该行变成了 j = (k++) + (k++)
。j = (k++) + (k++)
。其中一个 (k++)
将首先被评估,返回 0
并将 k
设置为 1。然后,第二个 (k++)
将被评估,返回 1
(因为第一次评估 k++
时将 k
设置为 1),并将 k
设置为 2。因此,我们最终得到 j = 0 + 1
,并且 k
被设置为 2。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
中解释代码及其工作原理。按需调用是按名调用的记忆化变体,如果函数参数被评估,则该值将存储以供后续使用。如果参数是纯的(即没有副作用),则这产生与按名调用相同的结果,节省了重新计算参数的成本。