92

我们都知道（或应该知道）Haskell 默认是惰性的。在必须评估之前，不会评估任何内容。那么什么时候必须评估一些东西呢？Haskell 在某些方面必须严格。我称这些为“严格点”，尽管这个特定的术语并不像我想象的那么普遍。据我说：

Haskell 中的缩减（或评估）只发生在严格点上。

所以问题是： Haskell 的严格点究竟是什么？我的直觉说main, seq/ bang 模式、模式匹配以及IO通过执行的任何操作main都是主要的严格点，但我真的不知道为什么我知道这一点。

（另外，如果它们不被称为“严格点”，它们叫什么？）

我想一个好的答案将包括一些关于 WHNF 等的讨论。我还想它可能会涉及 lambda 演算。

编辑：关于这个问题的其他想法。

正如我对这个问题的反思，我认为在严格点的定义中添加一些内容会更清楚。严格点可以有不同的上下文和不同的深度（或严格性）。回到我的定义，“Haskell 中的缩减只发生在严格点”，让我们在该定义中添加这个子句：“严格点只在其周围的上下文被评估或缩减时才被触发。”

所以，让我试着让你开始我想要的那种答案。main是一个严格点。它被特别指定为其上下文的主要严格点：程序。当程序（main的上下文）被评估时， main 的严格点被激活。Main 的深度最大：必须对其进行全面评估。Main 通常由 IO 动作组成，这些动作也是严格点，其上下文为main.

现在你试试：seq用这些术语讨论和模式匹配。解释函数应用的细微差别：它有多严格？怎么不是？怎么样deepseq？let和case声明？unsafePerformIO? Debug.Trace? 顶级定义？严格的数据类型？爆炸模式？等等。这些项目中有多少可以仅用 seq 或模式匹配来描述？

4

8 回答 8

48

一个好的起点是理解这篇论文：A Natural Semantics for Lazy Evalution (Launchbury)。这将告诉您何时为类似于 GHC 核心的小型语言评估表达式。然后剩下的问题是如何将完整的 Haskell 映射到 Core，而大部分翻译由 Haskell 报告本身给出。在 GHC 中，我们称这个过程为“脱糖”，因为它去除了语法糖。

好吧，这还不是全部，因为 GHC 在脱糖和代码生成之间包含大量优化，其中许多转换将重新排列核心，以便在不同时间对事物进行评估（特别是严格性分析会导致对事物进行评估较早）。因此，要真正了解如何评估您的 程序，您需要查看 GHC 生成的 Core。

也许这个答案对你来说似乎有点抽象（我没有特别提到爆炸模式或序列），但你要求一些精确的东西，这是我们能做的最好的。

于 2011-09-20T22:49:27.850 回答
20

我可能会将这个问题改写为，在什么情况下 Haskell 会评估一个表达式？（也许附加一个“弱头正常形式”。）

对于第一个近似值，我们可以指定如下：

  • 执行 IO 操作将评估他们“需要”的任何表达式。（因此您需要知道 IO 操作是否已执行，例如它的名称是 main，还是从 main 调用，并且您需要知道该操作需要什么。）
  • 正在评估的表达式（嘿，这是一个递归定义！）将评估它需要的任何表达式。

从你直观的列表来看，main 和 IO 操作属于第一类，seq 和模式匹配属于第二类。但是我认为第一类更符合您的“严格点”的想法，因为这实际上是我们如何使 Haskell 中的评估成为用户可观察到的效果。

由于 Haskell 是一门大型语言，因此具体给出所有细节是一项艰巨的任务。这也很微妙，因为 Concurrent Haskell 可能会推测性地评估事物，即使我们最终没有使用结果：这是导致评估的第三种事物。第二类研究得很好：你想看看所涉及的函数的严格性。第一类也可以被认为是一种“严格”，虽然这有点狡猾，因为evaluate x实际上seq x $ return ()是不同的东西！如果您为 IO monad 提供某种语义（显式传递RealWorld#令牌适用于简单情况），您可以正确对待它，但我不知道这种分层严格性分析是否有一个名称。

于 2011-09-20T21:24:21.743 回答
18

C 有序列点的概念，这是对特定操作的保证，即一个操作数将在另一个操作数之前被评估。我认为这是最接近的现有概念，但本质上等价的术语严格点（或可能是力点）更符合 Haskell 的想法。

实际上，Haskell 并不是一种纯粹的惰性语言：例如，模式匹配通常是严格的（因此尝试模式匹配会强制评估发生至少足够远以接受或拒绝匹配。

…</p>

程序员也可以使用seq原语来强制表达式进行评估，而不管结果是否会被使用。

$!是根据 定义的seq。

—<a href="http://www.haskell.org/haskellwiki/Lazy_vs._non-strict" rel="noreferrer">懒惰与非严格。

!所以你对/$!和的想法seq基本上是正确的，但模式匹配受制于更微妙的规则。当然，您总是可以使用~强制惰性模式匹配。同一篇文章中的一个有趣的观点：

严格性分析器还查找外部表达式始终需要子表达式的情况，并将其转换为急切求值。它可以做到这一点，因为语义（就“底部”而言）不会改变。

让我们继续深入兔子洞，看看 GHC 执行的优化文档：

严格性分析是 GHC 在编译时尝试确定哪些数据肯定“总是需要”的过程。然后 GHC 可以构建代码来仅计算此类数据，而不是存储计算并稍后执行的正常（更高开销）过程。

—<a href="http://www.haskell.org/haskellwiki/GHC_optimisations#Strictness_analysis" rel="noreferrer">GHC 优化：严格性分析。

换句话说，可以在任何地方生成严格的代码作为优化，因为当总是需要数据（和/或可能只使用一次）时，创建 thunk 会不必要地昂贵。

…无法对该值进行更多评估；据说是正常形式。如果我们处于任何中间步骤，因此我们至少对一个值执行了一些评估，那么它就是弱头范式（WHNF）。（还有一个“头范式”，但它没有在 Haskell 中使用。）在 WHNF 中完全评估某事会将其简化为范式……</p>

—<a href="http://en.wikibooks.org/wiki/Haskell/Laziness" rel="noreferrer">Wikibooks Haskell：懒惰

（如果在头部位置1没有 beta-redex，则一个术语是头部正常形式。如果一个 redex 前面只有非 redexes 2的 lambda 抽象，那么它就是一个头部 redex 。）所以当你开始强制一个 thunk 时，你在WHNF工作；当没有更多的 thunk 可以强制执行时，您处于正常状态。另一个有趣的点：

...如果在某些时候我们需要，例如，将 z 打印给用户，我们需要对其进行全面评估...</p>

这自然意味着，实际上，IO执行的任何动作main 都强制进行评估，考虑到 Haskell 程序确实在做事情，这应该是显而易见的。任何需要通过定义的序列的东西都main必须是正常的形式，因此要经过严格的评估。

不过，CA McCann 在评论中说得对：唯一的特别之处main在于它main被定义为特别；构造函数上的模式匹配足以确保IOmonad 强加的序列。只有在这方面seq，模式匹配才是基础。

于 2011-09-20T21:41:21.837 回答
10

Haskell 是 AFAIK 不是一种纯粹的惰性语言，而是一种非严格的语言。这意味着它不一定在最后一刻评估术语。

可以在这里找到 haskell 的“懒惰”模型的一个很好的来源：http ://en.wikibooks.org/wiki/Haskell/Laziness

基本上，了解 thunk 和弱标头范式 WHNF 之间的区别很重要。

我的理解是，与命令式语言相比，haskell 将计算向后拉。这意味着在没有“seq”和 bang 模式的情况下，最终会产生某种副作用，迫使对 thunk 进行评估，这可能会反过来导致先前的评估（真正的懒惰）。

由于这会导致可怕的空间泄漏，因此编译器会提前计算出如何以及何时评估 thunk 以节省空间。然后，程序员可以通过给出严格性注释（en.wikibooks.org/wiki/Haskell/Strictness，www.haskell.org/haskellwiki/Performance/Strictness）来支持这个过程，以进一步减少嵌套 thunk 形式的空间使用。

我不是 haskell 操作语义方面的专家，所以我将链接作为资源保留。

更多资源：

http://www.haskell.org/haskellwiki/Performance/Laziness

http://www.haskell.org/haskellwiki/Haskell/Lazy_Evaluation

于 2011-09-20T21:13:00.153 回答
6

懒惰并不意味着什么都不做。每当你的程序模式匹配一​​个case表达式时，它就会计算一些东西——反正就够了。否则它无法确定使用哪个 RHS。在您的代码中看不到任何大小写表达式？不用担心，编译器会将您的代码转换为 Haskell 的精简形式，在这种情况下很难避免使用它们。

对于初学者来说，一个基本的经验法则let是懒惰，case不那么懒惰。

于 2011-09-20T21:39:53.563 回答
4

这不是针对业力的完整答案，而只是拼图的一部分——就语义而言，请记住，有多种评估策略提供相同的语义。这里的一个很好的例子——该项目也说明了我们通常如何看待 Haskell 语义——是 Eager Haskell 项目，它从根本上改变了评估策略，同时保持了相同的语义：http ://csg.csail.mit.edu/酒吧/haskell.html

于 2011-09-23T21:18:10.747 回答
2

Glasgow Haskell 编译器将您的代码翻译成类似于 Lambda 演算的语言，称为core。在这种语言中，只要您通过 - 语句对其进行模式匹配，就会对某些内容进行评估case。因此，如果调用了一个函数，则将评估最外层的构造函数并且只有它（如果没有强制字段）将被评估。其他任何东西都可以装在一个thunk中。（thunk 由let绑定引入）。

当然，这并不是真正的语言中发生的事情。编译器以一种非常复杂的方式将 Haskell 转换为 Core，使尽可能多的东西变得懒惰，而任何总是需要的东西都变得懒惰。此外，还有一些未装箱的值和元组总是严格的。

如果您尝试手动评估一个函数，您基本上可以认为：

  • 尝试评估返回的最外层构造函数。
  • 如果需要其他任何东西来获得结果（但仅在确实需要时）也将被评估。顺序无关紧要。
  • 在 IO 的情况下，您必须评估从第一个到最后一个语句的所有语句的结果。这有点复杂，因为 IO monad 做了一些技巧来强制按特定顺序进行评估。
于 2011-09-26T13:40:50.340 回答
0

我们都知道（或应该知道）Haskell 默认是惰性的。在必须评估之前，不会评估任何内容。

不。

Haskell 不是一种懒惰的语言

Haskell 是一种语言，其中评估顺序无关紧要，因为没有副作用。

评估顺序无关紧要并不完全正确，因为该语言允许无限循环。如果您不小心，可能会陷入死胡同，当不同的评估顺序会导致在有限时间内终止时，您将永远评估子表达式。所以更准确的说法是：

  • 如果有任何终止的评估顺序，Haskell 实现必须以终止的方式评估程序。只有当每个可能的评估顺序都未能终止时，执行才能终止。

这仍然使实现在如何评估程序方面拥有巨大的自由。

Haskell 程序是一个单一的表达式，即let {所有顶级绑定} in Main.main。评估可以理解为一系列减少（小）步骤，这些步骤改变了表达式（表示执行程序的当前状态）。

您可以将归约步骤分为两类：那些被证明是必要的（可证明是任何终止归约序列的一部分），以及那些不是。您可以模糊地将可证明必要的减少分为两个子类别：那些“显然”必要的，以及需要一些非平凡分析来证明它们必要的那些。

仅执行明显必要的缩减是所谓的“惰性评估”。我不知道是否曾经存在过 Haskell 的纯粹惰性求值实现。拥抱可能就是其中之一。GHC 绝对不是。

GHC 在编译时执行一些可证明不必要的缩减步骤；例如，即使不能证明结果会被使用，它也会1+2::Int替换为。3::Int

在某些情况下，GHC 还可能在运行时执行不可证明的必要缩减。例如，当生成代码来评估时f (x+y)，如果x和y是类型Int并且它们的值将在运行时知道，但f不能证明使用它的参数，没有理由x+y在调用之前不计算f。它使用更少的堆空间和更少的代码空间，即使不使用参数也可能更快。但是，我不知道 GHC 是否真的抓住了这些优化机会。

GHC 肯定会在运行时执行评估步骤，这些步骤仅通过相当复杂的跨模块分析证明是必要的。这是非常普遍的，可能代表了对现实项目的大部分评估。惰性评估是最后的后备评估策略；这不是通常发生的事情。

GHC有一个“乐观评估”分支，它在运行时进行了更多的推测性评估。它被放弃是因为它的复杂性和持续的维护负担，而不是因为它表现不佳。如果 Haskell 像 Python 或 C++ 一样流行，那么我相信会有一些具有更复杂的运行时评估策略的实现，由财力雄厚的公司维护。非惰性求值不是对语言的改变，它只是一个工程挑战。

减少由顶级 I/O 驱动，仅此而已

您可以通过特殊的副作用缩减规则对与外部世界的交互进行建模，例如：“如果当前程序是形式getChar >>= <expr>，则从标准输入中获取一个字符并将程序缩减为<expr>应用于您获得的字符。”

运行时系统的整个目标是评估程序，直到它具有这些副作用形式之一，然后执行副作用，然后重复直到程序具有某种意味着终止的形式，例如return ().

关于什么时候减少什么没有其他规则。只有关于什么可以减少到什么的规则。

例如，if表达式的唯一规则是if True then <expr1> else <expr2>可以简化为<expr1>，if False then <expr1> else <expr2>可以简化为<expr2>，并且if <exc> then <expr1> else <expr2>，其中<exc>是异常值，可以简化为异常值。

如果表示程序当前状态的表达式是一个if表达式，那么您别无选择，只能对条件执行约简，直到它是Trueor Falseor ，因为这是您摆脱表达式并有希望达到<exc>的唯一方法if匹配 I/O 规则之一的状态。但是语言规范并没有用很多话告诉你这样做。

这些类型的隐式排序约束是评估可以“强制”发生的唯一方式。对于初学者来说，这是一个常见的困惑来源。例如，人们有时会尝试foldl通过写作foldl (\x y -> x `seq` x+y)而不是foldl (+). 这是行不通的，而且没有任何类似的东西可以工作，因为没有表达式可以让自己进行评估。评价只能“自上而下”。seq在这方面没有任何特别之处。

减少无处不在

Haskell 中的缩减（或评估）只发生在严格点上。[...] 我的直觉认为 main、seq / bang 模式、模式匹配以及通过 main 执行的任何 IO 操作都是主要的严格点 [...]。

我不明白如何理解这种说法。程序的每个部分都有一些含义，而那个含义是由归约规则定义的，所以归约无处不在。

要减少函数应用程序<expr1> <expr2>，您必须进行评估<expr1>，直到它具有类似(\x -> <expr1'>)or(getChar >>=)或其他与规则匹配的形式。但是由于某种原因，函数应用程序并不倾向于出现在据称“强制评估”的表达式列表中，而case总是出现。

您可以在 Haskell wiki 的引用中看到这种误解，在另一个答案中找到：

实际上，Haskell 并不是一种纯粹的惰性语言：例如，模式匹配通常是严格的

我不明白对于编写该语言的人来说，什么可以称为“纯粹的惰性语言”，也许除了一种语言，每个程序都挂起，因为运行时从不做任何事情。如果模式匹配是你的语言的一个特性，那么你必须在某个时候真正做到这一点。要做到这一点，您必须对受检者进行足够的评估，以确定它是否与模式匹配。这是匹配原则上可能的模式的最懒惰的方式。

~-前缀模式通常被程序员称为“懒惰”，但语言规范称它们为“无可辩驳的”。它们的定义属性是它们总是匹配的。因为它们总是匹配，所以您不必评估检查者来确定它们是否匹配，因此惰性实现不会。常规模式和无可辩驳的模式之间的区别在于它们匹配的表达式，而不是您应该使用的评估策略。该规范没有说明评估策略。

main是一个严格点。它被特别指定为其上下文的主要严格点：程序。当程序（main的上下文）被评估时， main 的严格点被激活。[...] Main 通常由 IO 动作组成，这些动作也是严格点，其上下文为main.

我不相信这些有任何意义。

Main 的深度最大：必须对其进行全面评估。

不，main只需要“浅层地”评估，以使 I/O 操作出现在顶层。main是整个程序，并且在每次运行时都不会完全评估程序，因为并非所有代码都与每次运行相关（通常）。

在这些术语中讨论seq和模式匹配。

我已经讨论过模式匹配。seq可以通过类似于case和应用程序的规则来定义：例如，(\x -> <expr1>) `seq` <expr2>归约到<expr2>. 这以case与应用程序相同的方式“强制评估”。WHNF 只是这些表达式“强制评估”的名称。

解释函数应用的细微差别：它有多严格？怎么不是？

它的左表达式很严格，就像case它的受检者很严格一样。替换后的函数体中也是严格的，就像case替换后所选替代的 RHS 中的严格一样。

怎么样deepseq？

它只是一个库函数，而不是内置函数。

顺便说一句，deepseq在语义上很奇怪。它应该只需要一个参数。我认为发明它的人只是盲目地复制seq，不明白为什么seq需要两个论据。我将deepseq的名称和规范视为证据，即使在有经验的 Haskell 程序员中，对 Haskell 评估的理解也很普遍。

let和case声明？

我谈到了case。let，在脱糖和类型检查之后，只是一种以树形式编写任意表达式图的方法。这是一篇关于它的论文。

unsafePerformIO?

在一定程度上，它可以通过归约规则来定义。例如，case unsafePerformIO <expr> of <alts>归约为unsafePerformIO (<expr> >>= \x -> return (case x of <alts>))，并且仅在顶层，unsafePerformIO <expr>归约为<expr>。

这不会做任何记忆。您可以尝试通过重写每个unsafePerformIO表达式来显式地记忆自己，并在IORef某处创建关联的 s... 来模拟记忆。但是你永远无法重现 GHC 的记忆行为，因为它依赖于优化过程的不可预知的细节，而且它甚至不是类型安全的（如IORefGHC 文档中臭名昭著的多态示例所示）。

Debug.Trace?

Debug.Trace.trace只是一个简单的包装unsafePerformIO。

顶级定义？

顶级变量绑定与嵌套let绑定相同。data, class, import, 等等是完全不同的球类游戏。

严格的数据类型？爆炸模式？

只是糖seq。

于 2020-12-11T21:54:44.577 回答