什么是call-by-need？

Question

我想知道什么是call-by-need。

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

Answer 1

想象一个函数：

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

然后我们把它叫做：

 add(3 * 2, 4 / 2)

在call-by-name语言中，这将被计算如下：

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]。

Answer 2

假设我们有一个函数

square(x) = x * x

我们想要评估square(1+2)。

在call-by-value，中，我们做到了

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

请注意，由于我们使用了该参数两次，因此我们对其求值两次。如果参数评估花费了很长时间，这将是浪费的。这就是call-by-need解决的问题。

在call-by-need，中，我们执行类似以下操作：

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是按值调用的，但其构造函数是语法形式的，而不是普通的函数。Haskell是按名称调用的，但它有定义严格数据类型的方法。

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

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的方式相同)。