按需调用:在Haskell中什么时候使用？

Question

http://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_need说：

call-by-need是call-by-name的记忆版本，如果函数参数被求值，该值将被存储以供后续使用。……Haskell是使用按需求值的最知名语言。

然而，计算的值并不总是为了更快的访问而存储(例如，考虑fibonacci数的递归定义)。我在#haskell上问了一个人，答案是这种记忆是自动完成的，“只在一个实例中，例如，如果你有‘`let foo = bar baz'，foo将被评估一次”。

我的问题是:实例的确切含义是什么，除了let之外，是否还有其他自动完成记忆的情况？

Answer 1

将这种行为描述为“记忆化”是一种误导。"Call by need“仅仅意味着函数的给定输入将被计算0到1次，不会超过一次。(它也可以部分求值，这意味着函数只需要该输入的一部分。)相反，"call by name“只是简单的表达式替换，这意味着如果您将表达式2 + 3作为一个函数的输入，如果该输入被多次使用，它可能会被多次求值。call by need和call by name都是非严格的:如果不使用输入，则永远不会对其求值。大多数编程语言都是严格的，并且使用"call by value“方法，这意味着无论是否使用输入，在开始计算函数之前都要计算所有输入。这一切都与let表达式无关。

Haskell不执行任何自动记忆。Let表达式不是记忆化的一个例子。但是，大多数编译器都会以按需调用的方式对let绑定进行评估。如果您将let表达式建模为一个函数，那么"call by need“的思路确实适用：

let foo = expression one in expression two that uses foo
==>
(\foo -> expression two that uses foo) (expression one)

这并不能正确地对递归绑定建模，但是您可以理解其中的含义。

Answer 2

haskell语言定义没有定义调用代码的时间和频率。无限循环是根据'the bottom‘(写入的⊥)定义的，它是一个表示错误条件的值(存在于所有类型中)。编译器可以自由地决定何时以及以多长时间计算一次程序(以及错误条件的存在/不存在，包括无限循环！)根据规范进行操作。

也就是说，通常的做法是大多数表达式都会生成“thunks”--基本上是指向一些代码和上下文数据的指针。当您第一次尝试检查表达式的结果(即，模式匹配它)时，thunk是“强制的”；指向的代码被执行，thunk被实际数据覆盖。这反过来可以递归地计算其他thunks。

当然，一直这样做是很慢的，所以编译器通常会尝试分析你什么时候会立即强制执行thunk (例如，当某些东西对有问题的值“严格”时)，如果它发现了这一点，它就会跳过整个thunk的事情，直接调用代码。如果它不能证明这一点，它仍然可以进行这种优化，只要它确保立即执行thunk不会崩溃或导致无限循环(或者它以某种方式处理这些条件)。

Answer 3

如果你不想在这方面变得非常技术性，要点是，当你有一个像some_expensive_computation of all these arguments这样的表达式时，你可以对它做任何你想做的事情；将它存储在一个数据结构中，创建一个包含53个副本的列表，将它传递给其他6个函数，等等，然后甚至将它返回给调用者，让调用者对它做任何它想做的事情。

Haskell将(主要)做的是最多对其求值一次；如果程序需要知道该表达式返回的内容以便做出决策，那么它将被求值(至少足以知道决策应该采用哪种方式)。这种求值将影响对同一表达式的所有其他引用，即使它们现在散布在整个程序中的数据结构和其他尚未求值的表达式中。