什么是Haskell的严格要点？

Question

我们都知道(或应该知道)Haskell默认是懒惰的.在必须对其进行评估之前,不评估任何内容.那么什么时候必须评估一下？Haskell必须严格要点.我把这些称为"严格点",虽然这个术语并不像我想象的那么广泛.据我说:

Haskell中的减少(或评估)仅发生在严格点处.

所以,问题是:什么,准确地说,是Haskell的严格点？我的直觉说main,seq/爆炸模式,模式匹配以及IO通过执行的任何动作main都是主要的严格点,但我不知道为什么我知道这一点.

(另外,如果他们不叫"严点",什么是他们叫什么名字？)

我想一个好的答案将包括一些关于WHNF等的讨论.我也想象它可能触及lambda演算.

---

编辑:关于这个问题的其他想法.

正如我在这个问题上的反思,我认为在严格点的定义中添加一些东西会更清楚.严格点可以具有不同的上下文和不同的深度(或严格性).回到我的定义"Haskell的减少只发生在严格点",让我们在这个定义中添加这个子句:"只有在评估或减少周围环境时才会触发严格点."

所以,让我试着让你开始我想要的那种答案.main是严格的一点.它被特别指定为其上下文的主要严格点:程序.当main评估程序(的上下文)时,激活main的严格点.主要深度是最大的:必须进行全面评估.Main通常由IO动作组成,它们也是严格点,其背景是main.

现在你尝试:seq用这些术语讨论和模式匹配.解释功能应用的细微差别:它是如何严格的？怎么回事？怎么样deepseq？let和case陈述？unsafePerformIO？Debug.Trace？顶级定义？严格的数据类型？邦模式？等等.这些项目中有多少只能用seq或模式匹配来描述？

Answer 1

一个好的开始是理解本文:懒惰评估的自然语义学(Launchbury).这将告诉你什么时候表达式被评估为类似于GHC的核心的小语言.然后剩下的问题是如何将完整的Haskell映射到Core,并且大部分翻译是由Haskell报告本身给出的.在GHC中,我们称这个过程为"desugaring",因为它会消除语法糖.

嗯,这不是整个故事,因为GHC包括在desugaring和代码生成之间的大量优化,并且许多这些转换将重新排列Core以便在不同时间对事物进行评估(特别是严格性分析将导致事物被评估更早).因此,要真正了解如何 评估您的程序,您需要查看GHC生成的Core.

也许这个答案对你来说似乎有点抽象(我没有特别提到爆炸模式或seq),但是你要求精确的东西,这是我们能做的最好的.

Answer 2

我可能会重新提出这个问题,在什么情况下Haskell会评估一个表达式？(或许可以解决"弱势正常形式".)

首先,我们可以指定如下:

• 执行IO操作将评估他们"需要"的任何表达式.(因此,您需要知道IO操作是否已执行,例如,它的名称是主要的,还是从主要AND调用它,您需要知道操作需要什么.)
• 正在评估的表达式(嘿,这是一个递归定义!)将评估它需要的任何表达式.

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

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

Answer 3

C具有序列点的概念,它是特定操作的保证,即一个操作数将在另一个操作数之前进行评估.我认为这是最接近的现有概念,但基本上等同的术语严格点(或可能的力点)更符合Haskell思想.

在实践中,Haskell并不是一种纯粹的懒惰语言:例如,模式匹配通常是严格的(因此尝试模式匹配迫使评估发生至少足以接受或拒绝匹配.

...

seq无论是否使用结果,程序员也可以使用原语强制表达式进行评估.

$!是根据的定义seq.

- 懒惰与非严格.

所以,你想!/ $!和seq本质上是正确的,但模式匹配受到微妙的规则.当然,您总是可以使用~强制进行惰性模式匹配.同一篇文章中有趣的一点:

严格性分析器还查找外部表达式总是需要子表达式并将其转换为急切评估的情况.它可以这样做,因为语义(就"底部"而言)不会改变.

让我们继续沿着兔子洞走下去,看看GHC执行的优化文档:

严格性分析是GHC在编译时尝试确定哪些数据肯定"始终需要"的过程.然后GHC可以构建代码来计算这样的数据,而不是用于存储计算并在以后执行它的正常(更高开销)过程.

- GHC优化:严格性分析.

换句话说,可以在任何地方生成严格的代码作为优化,因为当始终需要数据(和/或可能仅使用一次)时创建thunk不必要地昂贵.

......不能再对价值进行评估; 据说它处于正常状态.如果我们处于任何中间步骤,以便我们至少对某个值进行了一些评估,则它处于弱头正常形式(WHNF).(还有一个'头部正常形式',但它没有在Haskell中使用.)在WHNF中完全评估某些内容会将其减少到正常形式......

- Wikibooks Haskell:懒惰

(如果头部位置¹没有beta-redex,则一个术语是头部正常形式.如果redex是一个头部重新索引,如果它仅在非重新索引²的lambda抽象之前.)所以当你开始强制thunk时,你在WHNF工作; 当没有更多的力量留给你时,你就处于正常状态.另一个有趣点:

...如果在某些时候我们需要将z打印给用户,我们需要对其进行全面评估......

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

然而,CA McCann在评论中说得对:唯一特别的main是main被定义为特殊; 构造函数上的模式匹配足以确保IOmonad 强加的序列.在这方面,只有seq模式匹配才是基础.

Answer 4

Haskell是AFAIK不是一种纯粹的懒惰语言,而是一种非严格的语言.这意味着它不一定在最后可能的时刻评估术语.

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

基本上,理解thunk和弱标头正常形式WHNF之间的区别很重要.

我的理解是,与命令式语言相比,haskell通过向后推算计算.这意味着,在没有"seq"和爆炸模式的情况下,最终会出现一种强制评估thunk的副作用,这可能会导致先前的评估(真正的懒惰).

由于这将导致可怕的空间泄漏,编译器然后会计算出如何以及何时提前评估thunks以节省空间.然后,程序员可以通过严格注释(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

Answer 5

懒惰并不意味着什么都不做.每当你的程序模式与case表达式匹配时,它就会评估一些东西 - 无论如何都是足够的.否则无法确定使用哪种RHS.在代码中看不到任何case表达式？不用担心,编译器正在将您的代码转换为Haskell的简化形式,而这些形式很难避免使用.

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