Mar*_*urg 7 haskell functional-programming lazy-evaluation
在函数式语言中,函数是一等公民,因此调用它们不是我能做的唯一事情.我也可以把它们存起来.
现在,当我有一种默认情况下严格的语言时,我仍然没有被迫评估函数调用.我可以选择将函数及其参数存储在元组中以供以后评估.
而不是
x = f a b c
我做的事情
x = (f,a,b,c)
后来,我可以用类似的东西评估这件事
eval (f,a,b,c) = f a b c
好吧,可能还有更多内容,因为我只想评估每个未评估的函数调用一次,但在我看来,这也可以通过一个比仅仅元组更有趣的数据结构来解决.
逆也似乎是这种情况,因为例如在Haskell中,懒惰是默认的,我可以用seq或强制执行评估BangPatterns.
所以说每个函数语言都有可能是懒惰的,这是正确的,但是大多数函数语言默认都不是懒惰的,因此需要额外的编程工作才能懒惰地调用函数,而haskell 在默认情况下是惰性的,需要额外的编程努力以严格的方式调用函数？
如果是这样的话,对于程序员来说更难的是:用严格的语言编写惰性函数调用或者用惰性语言编写严格的函数调用？
作为旁注:Simon P. Jone严肃地说:"下一版的haskell将是严格的".我首先想到这是一个笑话.但是现在我认为严格默认并不是那么糟糕,只要你可以在需要时懒惰.
低级别的懒惰评估是通过一个名为thunk的概念实现的,它包含两件事:
第一部分,闭包,可以用比函数及其参数的元组更简单的方式建模.您可以使用一个接受单位或无参数的函数(取决于您的语言的工作方式),并在其正文中将函数应用于参数.要计算结果,只需调用该函数即可.
保罗约翰逊提到计划,这是一个完美的语言来证明这一点.作为Scheme宏(伪代码,未经测试):
(define-syntax delay
(syntax-rules ()
((delay expr ...)
;; `(delay expr)` evaluates to a lambda that closes over
;; two variables—one to store the result, one to record
;; whether the thunk has been forced.
(let ((value #f)
(done? #f))
(lambda ()
(unless done?
(set! value (begin expr ...))
(set! done? #t))
value)))))
(define (force thunk)
;; Thunks are procedures, so to force them you just invoke them.
(thunk))
但是要回到这个问题的标题:这是否意味着每种功能语言都可能是懒惰的？答案是否定的.渴望的语言可以实现thunking并使用它在用户选择的位置提供opt-in延迟评估,但这与Haskell实现提供的普遍延迟评估不同.
答案是肯定的。您的直觉是，惰性可以用严格的语言来实现，其中函数是第一类对象，这是正确的。但深入细节就会发现一些微妙之处。
\n\n让我们采用一种函数式语言（我的意思是一种可以将函数作为一流对象进行构造和操作的语言，就像在 lambda 演算中一样），其中函数应用是严格的（即函数\xc2\xb9 及其在应用函数之前对参数进行全面评估）。我将使用标准 ML 的语法，因为这是一种流行且历史上重要的严格函数式语言。严格的应用（其中和F AFA是两个表达式）可以通过将其编码为来延迟
重击（F、A）\n\n
该对象包含一个函数和一个参数，称为thunk参数。我们可以定义一种 thunk 类型：
\n\ndatatype (\'a, \'b) thunk = Thunk of (\'a -> \'b) * \'a;\n以及评估 thunk 的函数：
\n\n fun evaluate (Thunk (f, x)) = f x;\n到目前为止很好很容易。但事实上，我们还没有实现惰性求值！我们实现的是正常顺序评估，也称为按名称调用。不同之处在于，如果多次使用 thunk 的值，则每次都会计算它。惰性求值（也称为按需调用）要求最多对表达式求值一次。
\n\n在纯粹、严格的语言中，惰性求值实际上是不可能实现的。原因是评估 thunk 会修改系统的状态：它从未评估变为已评估。实现惰性求值需要一种改变系统状态的方法。
\n\n这里有一个微妙之处：如果语言的语义纯粹是根据表达式的终止状态和终止表达式的值来定义的，那么，在纯语言中，按需要调用和按名称调用是无法区分。按值调用（即严格求值）是可区分的，因为较少的表达式终止 \xe2\x80\x94 按需要调用，而按名称调用隐藏了从未求值的 thunk 中发生的任何非终止。按需要调用和按名称调用的等效性允许将惰性求值视为正常顺序求值的优化（具有良好的理论属性）。但在许多程序中，使用按名称调用而不是按值调用会一遍又一遍地计算相同表达式的值，从而增加运行时间。
\n\n在具有可变状态的语言中，惰性求值可以通过在计算时将值存储到 thunk 中来表达。
\n\ndatatype (\'a, \'b) lazy_state = Lazy of (\'a -> \'b) * \'a | Value of \'a;\ntype (\'a, \'b) lazy_state = (\'a, \'b) lazy_state ref;\nlet lazy (f, x) = ref (Lazy (f, x));\nfun force r =\n case !r of Value y => y\n | Lazy (f, x) => let val y = f x in r := Value y; y end;\n这段代码并不是很复杂，因此即使在提供惰性求值作为库功能（可能带有语法糖）的 ML 方言中，它在实践中也不会经常使用 \xe2\x80\x94\xc2\xa0often，需要该值的点是程序中的已知位置，程序员只需使用一个函数并将其参数传递到该位置即可。
\n\n虽然这进入了主观领域，但我想说，实现这样的惰性求值比用 Haskell 这样的语言实现严格求值要容易得多。在 Haskell 中强制进行严格评估基本上是不可能的（除非将所有内容包装到状态 monad 中并本质上用 Haskell 语法编写 ML 代码）。当然，严格评估不会改变程序计算的值，但它会对性能产生重大影响（特别是，它有时会受到很大的赞赏，因为它使性能更加可预测\xe2\x80\ x94 预测 Haskell 程序的性能可能非常困难）。
\n\n这种评估和存储机制实际上是 Haskell 编译器底层工作的核心。Haskell 是纯粹的\xc2\xb2，所以你不能在语言本身中实现它！然而，编译器在幕后这样做是合理的，因为这种特殊的副作用使用不会破坏语言的纯粹性，因此它不会使任何程序转换无效。存储 thunk 值的原因是合理的，因为它将按名称调用评估转变为按需要调用，正如我们在上面看到的，这既不会改变终止表达式的值，也不会改变终止的表达式。
\n\n对于将纯函数本地计算与多线程环境以及线程之间的消息传递相结合的语言，这种方法可能会有些问题。（这尤其是Erlang的模型。）如果一个线程开始评估 thunk，而另一个线程正好需要它的值，会发生什么？如果不采取预防措施，那么两个线程都会计算该值并存储它。在纯语言中，这是无害的，因为两个线程无论如何都会计算相同的值\xc2\xb3。然而这可能会损害性能。为了确保 thunk 仅计算一次，值的计算必须包装在锁中；这有助于执行多次的长计算，但会损害仅执行一次的短计算，因为获取和释放锁需要一些时间。
\n\n\xc2\xb9函数，当然不是函数体。
\n\xc2\xb2或者更确切地说，不使用副作用 monad 的 Haskell 片段是纯粹的。
\n\xc2\xb3延迟 thunk 和计算值之间的转换必须是原子的 \xe2\x80\x94\xc2\xa0 并发线程必须能够读取惰性值并获得有效的延迟 thunk 或一个有效的计算值，而不是不是有效对象的两者的混合。在处理器级别，从延迟 thunk 到计算值的转换通常是指针分配，幸运的是，这在大多数体系结构上是原子的。