4

http://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_need说:
“Call-by-need 是 call-by-name 的记忆版本,如果函数参数被评估,该值将被存储以供后续使用。 [...] Haskell 是最知名的使用按需调用评估的语言。”

然而,计算的值并不总是为了更快的访问而存储(例如考虑斐波那契数的递归定义)。我在#haskell 上问过某人,答案是“仅在一种情况下,例如,如果你有 `let foo = bar baz',foo 将被评估一次”,这种记忆是自动完成的。

我的问题是: instance 到底是什么意思,除了 let 之外还有其他情况可以自动完成记忆吗?

4

3 回答 3

7

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

Haskell 不执行任何自动记忆。Let 表达式不是记忆的例子。但是,大多数编译器将以按需调用的方式评估 let 绑定。如果将 let 表达式建模为函数,则“按需调用”的心态确实适用:

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

这不能正确地模拟递归绑定,但你明白了。

于 2012-04-28T11:45:26.303 回答
6

haskell 语言定义没有定义代码被调用的时间或频率。无限循环是根据“底部”(写成⊥)定义的,它是一个代表错误条件的值(存在于所有类型中)。只要程序(以及是否存在/不存在错误条件,包括无限循环!)按照规范运行,编译器就可以自由地决定何时以及多久评估一次。

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

当然,一直这样做很慢,因此编译器通常会尝试分析您何时最终会立即强制执行 thunk(即,当某些值对所讨论的值“严格”时),以及它是否发现这样,它会跳过整个 thunk 的事情并立即调用代码。如果它不能证明这一点,它仍然可以进行这种优化,只要它确保立即执行 thunk 不会崩溃或导致无限循环(或者它以某种方式处理这些情况)。

于 2012-04-28T09:13:53.810 回答
0

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

Haskell 将(主要)做的是最多评估一次;如果程序需要知道该表达式返回的内容才能做出决定,那么它将被评估(至少足以知道该决定应该走哪条路)。该评估将影响对同一表达式的所有其他引用,即使它们现在分散在整个程序中的数据结构和其他尚未评估的表达式中。

于 2012-04-28T09:56:16.850 回答