Haskell的严格性点是什么?

92
我们都知道(或者应该知道)Haskell默认是惰性的,直到必须对其进行求值才会进行任何计算。那么什么时候必须对某些内容进行求值呢?这些点我们称之为“严格性点”,尽管这个术语并不像我所以为的那样广泛。根据我的理解:

Haskell中的规约(或求值)在严格性点处发生。

所以问题是:什么是Haskell的严格性点? 我的直觉是main, seq / 爆炸模式,模式匹配以及通过main执行的任何IO操作是主要的严格性点,但我不知道为什么我知道这些。
(另外,如果它们不叫“严格性点”,它们被称为什么?)
我想一个好的答案将包括一些关于WHNF等方面的讨论。我也想象它可能会涉及到λ演算。
编辑:有关此问题的其他想法。 当我思考这个问题时,我认为向“严格性点”的定义中添加一些内容会更清晰。严格性点可以具有不同的上下文和不同的深度(或严格性)。回到我的定义,即“Haskell中的规约仅在严格性点处发生”,让我们在该定义中添加这个子句:“只有在其周围的上下文被求值或规约时,严格性点才会被触发。”
因此,让我开始回答所需的信息。 main是一个严格性点。它被特别指定为其上下文(程序)的主要严格性点。当程序(main的上下文)被求值时,会激活主函数的严格性点。Main的深度是最大的:它必须完全求值。通常,主函数由IO操作组成,这些操作也是严格性点,其上下文是main

现在轮到你了:用这些术语讨论seq和模式匹配。解释函数应用的细微差别:它有多严格?它是如何不严格的?deepseq呢?letcase语句呢?unsafePerformIO? Debug.Trace? 顶层定义?严格数据类型?Bang模式?等等。这些术语中有多少可以仅通过seq或模式匹配来描述?


10
你的直觉列表可能不太正交。我怀疑使用seq和模式匹配已足够,其余部分可以根据这些定义。我认为模式匹配可以确保IO操作的脊柱严格性,例如。 - C. A. McCann
原始类型,例如内置的数字类型上的 + 运算符也会强制执行严格性,我认为纯 FFI 调用也是如此。 - hammar
4
这里似乎混淆了两个概念。Pattern matching和seq以及bang patterns是一种使表达式在其子表达式中变为严格求值的方式--也就是说,如果顶层表达式被求值,那么子表达式也被求值。另一方面,执行IO操作是评估开始的方法。这些是不同的事情,将它们包含在同一个列表中有点像类型错误。 - Chris Smith
@ChrisSmith 我并不是试图混淆这两种不同的情况;如果有什么,我是在进一步询问它们如何相互作用的澄清。严格性以某种方式发生,而这两种情况都是严格性“发生”的重要但不同的部分。(还有 @monadic: ಠ_ಠ) - Dan Burton
如果您想/需要讨论此问题的某些方面,而不是试图给出完整的答案,我建议您利用我的/r/haskell帖子中的评论区(http://www.reddit.com/r/haskell/comments/klwdf/what_are_haskells_strictness_points/)。 - Dan Burton
8个回答

48
一个好的起点是理解这篇论文:A Natural Semantics for Lazy Evalution(Launchbury)。该论文将告诉您与GHC Core类似的小语言何时计算表达式。然后,剩下的问题就是如何将完整的Haskell映射到Core,并且大部分翻译都在Haskell报告中给出。在GHC中,我们称此过程为“去糖”,因为它消除了语法糖。
当然,这还没有全貌,因为GHC在去糖和代码生成之间包含了许多优化,其中许多转换会重新排列Core,以便在不同的时间进行评估(特别是强制性分析会导致事情更早地被评估)。因此,要真正了解您的程序如何进行评估,您需要查看GHC生成的Core。
也许这个回答对您来说有点抽象(我没有特别提到bang模式或seq),但您要求得很“精确”,这已经是我们能做的最好的了。

19
我一直觉得有趣的是,在 GHC 所谓的 "desugaring" 中,被移除的语法糖包括 Haskell 语言本身的 实际语法...这似乎暗示着,GHC 实际上是一个优化 GHC Core 语言的编译器,顺便还具备将 Haskell 翻译成 Core 的非常复杂的前端。:] - C. A. McCann
类型系统并不完全匹配...特别是在将类型类转换为显式字典方面,我记得有些问题。而且据我所知,所有最新的TF/GADT内容都使这个差距变得更大了。 - sclv
1
GCC 也不会优化 C 语言:http://gcc.gnu.org/onlinedocs/gccint/Passes.html#Passes - György Andrasek

20

我建议将这个问题改为:在什么情况下Haskell会评估表达式?(或许可以加上“到弱头归一形式"的限定条件)。

首先我们可以简单概括如下:

  • 执行IO操作将评估其所需的任何表达式。(因此需要知道是否执行了IO操作,例如它的名称为main或者是从main中调用的,并且需要知道该操作所需的内容。)
  • 正在评估的表达式(嘿,这就是递归定义!)将评估其需要的任何表达式。

从你提供的直觉列表来看,主函数和IO操作属于第一类,而seq和模式匹配则属于第二类。但我认为第一类更符合您对“严格性点”的想法,因为实际上这是我们使Haskell评估成为对用户可观察效果的方式。

给出所有细节是一个大任务,因为Haskell是一种复杂的语言。这也相当微妙,因为并发Haskell可能会猜测地评估一些东西,尽管最终我们没有使用结果:这是导致评估的第三个原因。第二类已经被广泛研究:您要查看涉及的函数的“严格性”。第一类也可以被认为是某种形式的“严格性”,尽管这有点棘手,因为evaluate xseq x $ return ()实际上是不同的东西!如果给IO单子赋予一些语义(对于简单情况,显式传递一个RealWorld#标记即可),那么可以正确地处理它,但我不知道是否有一个通用的层次化严格性分析的名称。


18

C具有序列点的概念,它们是对于特定操作的保证,其中一个操作数将在另一个操作数之前被评估。我认为这是最接近现有概念的术语,但本质上等效的术语严格点(或可能是强制点)更符合Haskell思想。

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

程序员还可以使用seq原语来强制表达式的计算,而不管结果是否会被使用。

$!是根据seq定义的。

惰性与非严格

因此,您对于/$!seq的想法基本上是正确的,但是模式匹配受到更微妙的规则的约束。当然,您始终可以使用来强制惰性模式匹配。从同一篇文章中得出一个有趣的观点:

严格性分析器还寻找子表达式始终被外部表达式所需的情况,并将其转换为急切评估。它可以这样做,因为语义(以“底部”为基础)不会改变。

让我们继续深入研究并查看GHC执行的优化文档:

严格性分析是 GHC 在编译时尝试确定哪些数据“肯定会一直需要”的过程。 GHC 可以建立代码,只计算这些数据,而不是存储计算并稍后执行的常规(开销较高)过程。换句话说,当数据将始终需要(或仅可能使用一次)时,可以在任何地方生成严格代码作为优化。 —GHC 优化:严格性分析 换句话说,在值上不能再执行任何评估时,它被称为“正常形式”。如果我们处于任何中间步骤,以至少对值进行了一些评估,它处于“弱头部正常形式”(WHNF)。 (还有一个“头部正常形式”,但它不在 Haskell 中使用。)完全评估 WHNF 中的内容可将其缩小为正常形式… —Wikibooks Haskell:惰性

(如果头部位置没有beta-redex,则术语处于head normal form1。如果红式是头部红式,并且仅由非红式的lambda抽象器前置2,则称为头部红式。) 因此,当您开始强制执行一个thunk时,您正在使用WHNF; 当没有更多的thunk需要强制执行时,您就进入了正常形式。另一个有趣的观点:

......如果在某个时刻我们需要将z打印给用户,我们需要完全评估它......

这自然意味着,确实,从main执行的任何IO操作都会强制评估,这应该是显而易见的,因为Haskell程序实际上会做一些事情。需要经过main定义的序列的任何内容必须处于正常形式,因此受到严格评估的约束。

不过,在评论中C. A. McCann说得很对:唯一特殊的是main被定义为特殊;模式匹配构造函数足以确保IO单子所施加的序列。在这方面,只有seq和模式匹配是基本的。


4
实际上,引用“如果我们需要将z打印给用户,我们需要完全评估它”的说法并不完全正确。这与要打印的值的“Show”实例一样严格。 - nominolo

10

Haskell不是纯惰性语言,而是一种非严格语言。这意味着它不一定会在最后一刻评估项。

关于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


6

懒惰并不意味着什么都不做。每当程序模式匹配一个case表达式时,它会评估某些内容——至少足够了解哪个RHS要使用。在您的代码中没有看到任何case表达式?别担心,编译器正在将您的代码转换为Haskell的简化形式,这种情况下很难避免使用。

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


2
请注意,虽然 case 在 GHC Core 中总是强制求值,但在常规的 Haskell 中并不会这样做。例如,请尝试 case undefined of _ -> 42 - hammar
2
在 GHC Core 中,case 会将其参数评估为 WHNF,而在 Haskell 中,case 会根据需要评估其参数以选择适当的分支。在 hammar 的示例中,根本不需要评估,但在 case 1:undefined of x:y:z -> 42 中,它会比 WHNF 更深入地评估。 - Max
@Ingo - 这是不正确的。something需要被评估为WHNF才能到达元组构造函数。 - John L
顺便说一句 - 实际上解释器似乎仍然会对其进行评估。但在严格的意义上,它不需要这样做。 - Ingo
我相信这是Haskell语义的一部分。没有~,模式匹配将会对数据进行求值,即使严格来说并不必要。而有了~,求值将会被延迟执行。 - John L
显示剩余3条评论

4

这并不是为了获取声望的完整答案,而只是谜题的一部分。在语义方面,需要注意的是有多种提供相同语义的评估策略。一个很好的例子是 Eager Haskell 项目,该项目彻底改变了评估策略,同时保持了相同的语义。该项目还展示了我们通常如何思考 Haskell 语义:http://csg.csail.mit.edu/pubs/haskell.html


2
Glasgow Haskell编译器将您的代码转换为名为“core”的类似Lambda演算的语言。在这种语言中,只有通过case语句进行模式匹配时,才会对某些内容进行评估。因此,如果调用函数,则仅对最外层构造函数(如果没有强制字段)进行评估。其他任何内容都存储在thunk中(由let绑定引入)。
当然,这并不完全是实际语言中发生的情况。编译器以非常复杂的方式将Haskell转换为Core,使尽可能多的事情变得惰性,并且任何始终需要惰性的东西也是惰性的。此外,还有未打包的值和始终严格的元组。
如果您手动尝试评估函数,则可以基本思考:
- 尝试评估返回值的最外层构造函数。 - 如果需要其他内容来获取结果(但仅在确实需要时),则还会对其进行评估。顺序无关紧要。 - 在IO的情况下,必须评估从第一个到最后一个语句的所有语句的结果。这有点更复杂,因为IO单子会一些技巧以强制按特定顺序进行评估。

0
我们都知道(或者应该知道)Haskell默认是惰性的。在必须评估之前,不会评估任何内容。
不。
Haskell不是一种惰性语言。
Haskell是一种无副作用的语言,因此评估顺序并不重要。
虽然语言允许无限循环,但评估顺序并不完全无关紧要。如果不小心,可能会陷入一个死胡同,在那里你会永远评估子表达式,而不是以有限时间终止的不同评估顺序。因此,更准确地说:
Haskell实现必须以可以终止的方式评估程序,如果存在任何终止的评估顺序,则只有在每个可能的评估顺序都无法终止时,实现才会失败。
这仍然为实现提供了巨大的自由度来评估程序。
Haskell程序是一个单一的表达式,即let {所有顶级绑定} in Main.main。评估可以被理解为一系列缩减(小)步骤,这些步骤改变了表达式(表示执行程序的当前状态)。

你可以将规约步骤分为两类:那些可以被证明是必要的(在任何终止规约序列中都是必须的),以及那些不是。你可以将可以被证明是必要的规约步骤有点模糊地分为两个子类:那些“显然”必要的,以及那些需要一些非平凡的分析来证明它们是必要的。

只执行显然必要的规约步骤就是所谓的“惰性求值”。我不知道是否存在纯粹的惰性求值实现Haskell。Hugs可能是其中之一。GHC肯定不是。

GHC在编译时执行了一些不可证明必要的规约步骤;例如,即使它无法证明结果将被使用,它也会用3::Int替换1+2::Int

在某些情况下,GHC也可以在运行时执行不必要的规约。例如,在生成用于评估f(x+y)的代码时,如果xyInt类型,并且它们的值将在运行时知道,但无法证明f使用其参数,则没有理由在调用f之前不计算x+y。即使不使用参数,它也使用更少的堆空间和代码空间,可能更快。但是,我不知道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 表达式,那么你别无选择,只能对条件执行缩减操作,直到它变成 TrueFalse<exc>,因为这是你摆脱 if 表达式并希望达到与 I/O 规则之一匹配的状态的唯一方法。但是语言规范并没有用这么多的话告诉你要这样做。

这些隐式的排序约束是强制发生评估的唯一方式。这是初学者经常感到困惑的一个原因。例如,人们有时会尝试通过编写foldl (\x y -> x `seq` x+y)而不是foldl (+)来使foldl更加严格。这是行不通的,也永远不可能行得通,因为没有表达式可以使自己评估。评估只能“从上面”进行。在这方面,seq并没有任何特殊之处。

规约无处不在

Haskell中的规约(或评估)仅在严格性点发生。[...] 我的直觉是主函数、seq / bang模式、模式匹配以及通过主函数执行的任何IO操作都是主要的严格性点[...]。

我不明白如何理解这个说法。程序的每个部分都有一定的含义,并且该含义由规约规则定义,因此规约无处不在。

为了减少函数应用<expr1> <expr2>,您必须评估<expr1>,直到它具有类似于(\x -> <expr1'>)(getChar >>=)的形式,或者其他与规则匹配的内容。但由于某种原因,函数应用不倾向于出现在声称“强制评估”的表达式列表中,而case总是会出现。
您可以在Haskell维基百科的一句话中看到这种误解,该语句在另一个答案中找到:
实际上,Haskell不是纯惰性语言:例如,模式匹配通常是严格的
我不明白谁写下这句话可能会被认为是“纯惰性语言”,除非是每个程序都挂起,因为运行时从未执行任何操作。如果模式匹配是您的语言的特性,则必须在某个时候实际执行它。要执行它,您必须评估足够的scrutinee以确定它是否与模式匹配。这是原则上可能的最懒惰的匹配模式的方法。

~前缀模式通常被程序员称为“懒惰”,但语言规范将其称为“不可反驳的”。它们的定义属性是始终匹配。由于它们总是匹配,因此您不必评估检查者以确定它们是否匹配,因此懒惰实现不会这样做。普通模式和不可反驳的模式之间的区别在于它们匹配的表达式,而不是您应该使用的评估策略。规格说明没有提到任何评估策略。


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

我不确定这些内容是否有任何意义。

main的深度是最大的:必须完全评估。

不,main只需要进行“浅层次”的评估,以使I/O操作出现在顶层。 main是整个程序,而程序并非在每次运行时都完全评估,因为不是所有代码都与每次运行相关(一般情况下)。

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

我已经谈到了模式匹配。 seq 可以通过类似于 case 和应用的规则来定义:例如,(\x -> <expr1>) `seq` <expr2> 简化为 <expr2>。这样做可以“强制评估”,就像 case 和应用程序一样。 WHNF 只是这些表达式“强制评估”的名称。

解释函数应用的细微差别:它如何严格? 它又如何不是?

它在左侧表达式中是严格的,就像 case 在其选择器中是严格的一样。在替换后的函数体中也是严格的,就像在替换后的选定替代品的 RHS 中一样。

deepseq 呢?

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

顺便提一下,deepseq 的语义很奇怪。它应该只接受一个参数。我认为发明它的人只是盲目地复制了 seq,并没有理解为什么 seq 需要两个参数。我认为 deepseq 的名称和规范表明,即使是经验丰富的 Haskell 程序员也普遍存在对 Haskell 评估的理解不足。

letcase 语句?

我谈到了 case。在展开和类型检查之后,let 只是一种以树形式编写任意表达式图的方式。这里有一篇论文

unsafePerformIO

在某种程度上,它可以通过规约规则来定义。例如,case unsafePerformIO <expr> of <alts> 规约为 unsafePerformIO (<expr> >>= \x -> return (case x of <alts>)),而仅在顶层,unsafePerformIO <expr> 规约为 <expr>
这不会进行任何记忆化。您可以尝试通过将每个 unsafePerformIO 表达式重写为显式记忆化自身,并创建相关的 IORef... 在某个地方来模拟记忆化。但是,您永远无法复制 GHC 的记忆化行为,因为它取决于优化过程的不可预测细节,并且甚至不是类型安全的(正如 GHC 文档中臭名昭著的多态 IORef 示例所示)。

Debug.Trace?

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

顶层定义?

顶层变量绑定与嵌套的let绑定相同。dataclassimport等则完全不同。

严格数据类型?Bang模式?

只是seq的语法糖。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接