什么是Haskell的严格点?

我们都知道(或者应该知道)Haskell默认是懒惰的。 评估之前,没有任何评估。 那么什么时候必须进行评估? 有几点Haskell必须严格。 我称之为“严格点”,虽然这个特定的术语并不像我想象的那样广泛。 据我所知:

Haskell中的减less(或评估) 发生在严格点上。

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

(另外,如果他们不被称为“严格点”,他们叫什么?)

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


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

正如我在这个问题上所反映的那样,我认为在严格点的定义中增加一些内容会更清楚些。 严格点可以有不同的背景和不同的深度 (或严格性)。 回到我的定义:“减lessHaskell只发生在严格点上”,让我们在这个定义中增加这样一个条款:“一个严格点只有当它的周围环境被评估或减less时才会触发”。

所以,让我试着让你开始我想要的答案。 main是一个严格点。 它被特别指定为其上下文的主要严格点:程序。 当程序( main的上下文)被评估时,main的严格点被激活。 主要的深度是最大的:它必须充分评估。 主要通常由IO操作组成,这些操作也是严格点,其上下文是main

现在您尝试:以这些术语讨论seq和模式匹配。 解释function应用的细微差别:它是如何严格的? 它怎么样? 那么deepseq呢? letcase陈述? unsafePerformIODebug.Trace ? 顶级定义? 严格的数据types? 爆炸模式? 等等这些项目中有多less可以用seq或模式匹配来描述?

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

好吧,这不是全部,因为GHC包含了一系列优化,包括脱钩和代码生成,其中许多转换将重新安排Core,以便在不同的时间进行评估(严格分析尤其会导致评估更早)。 所以为了真正理解你的程序如何评估,你需要看看GHC生成的Core。

也许这个答案对你来说似乎有些抽象(我没有具体提到爆炸模式或seq),但你要求一些确切的东西,这是我们能做的最好的。

我可能会重申这个问题, 在什么情况下,Haskell会评估一个expression式? (也许是用“弱头常态”来表示)

对于第一个近似,我们可以指定如下:

  • 执行IO动作将评估他们“需要”的任何expression式(所以你需要知道IO动作是否被执行,例如它的名字是main,或者从main调用它,你需要知道动作需要什么)。
  • 正在评估的expression式(嘿,这是一个recursion定义!)将评估它需要的任何expression式。

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

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

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

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

程序员也可以使用seq原语强制执行expression式,而不pipe结果是否被使用。

$! 是根据seq定义的。

懒惰与非严格 。

所以你的想法! / $! seq本质上是正确的,但模式匹配是受到微妙的规则。 当然,你总是可以使用~强制延迟模式匹配。 这篇文章有趣的一点是:

严格性分析器还查找外部expression式总是需要子expression式的情况,并将其转换为急切的评估。 它可以做到这一点,因为语义(根据“底部”)不会改变。

让我们继续下面的兔子洞,看看由GHC进行优化的文档:

严格分析是GHC试图在编译时确定哪些数据肯定会“总是需要”的过程。 然后,GHC可以构build代码来计算这些数据,而不是用于存储计算和稍后执行的正常(更高的开销)过程。

– GHC优化:严格性分析 。

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

…没有更多的价值评估可以执行; 据说是正常的forms 。 如果我们处于任何中间步骤,以至于我们至less对一个值进行了一些评估,那么它就是弱头标准forms (WHNF)。 (也有一个'头部正常forms',但是它并没有在Haskell中使用。)在WHNF中充分评估一些东西会将其减less到正常forms。

– 维基教科书,自由的教学读本

(如果头位没有beta-redex,那么术语是以正常forms表示的,redex是一个头部redex,如果它只在非redexes 2的lambda抽象前面出现)所以当你开始强制thunk的时候,你在WHNF工作; 当没有更多的强权时,你是正常的forms。 另一个有趣的点:

…如果在某个时候我们需要将用户打印出来,我们需要对其进行全面的评估。

这自然意味着,从main执行的任何IO操作确实影响评估,考虑到Haskell程序实际上是做事情的,这应该是显而易见的。 任何需要经过main定义的序列的东西都必须是正常的forms,因此需要经过严格的评估。

CA McCann在评论中说得很对,但是关于main的唯一特别的是main被定义为特殊的; 在构造函数上进行模式匹配足以确保IO monad施加的序列。 在这方面,只有seq和模式匹配才是根本。

哈斯克尔是AFAIK不是一个纯粹的懒惰的语言,而是一个非严格的语言。 这意味着它不一定在最后一刻评估条款。

哈斯克尔的“懒惰”模型的一个很好的来源可以在这里find: http : //en.wikibooks.org/wiki/Haskell/Laziness

基本上,理解一个thunk和弱头正常formsWHNF之间的区别是很重要的。

我的理解是,与命令式语言相比,哈斯克尔通过倒退来计算。 这意味着在没有“seq”和“bang”模式的情况下,最终会是某种副作用,这会强制对thunk进行评估,从而可能导致事先评估(真正的懒惰)。

由于这会导致可怕的空间泄漏,编译器会提前知道如何以及何时对thunk进行评估以节省空间。 然后,程序员可以通过给予严格注释(en.wikibooks.org/wiki/Haskell/Strictness,www.haskell.org/haskellwiki/Performance/Strictness)来支持这个过程,以嵌套thunkforms进一步减less空间使用。

我不是haskell的操作语义方面的专家,所以我将把链接作为一个资源。

一些更多的资源:

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

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

懒惰并不意味着什么都不做。 无论何时你的程序模式匹配一​​个caseexpression式,它都会评估一些东西 – 只要足够了。 否则,它不能找出使用哪个RHS。 在你的代码中没有看到任何caseexpression式? 不要担心,编译器会将您的代码转换为Haskell的精简forms,难以避免使用。

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

这不是一个针对业力的完整答案,而只是一个难题 – 在一定程度上这是关于语义的,要记住,有多种评估策略可以提供相同的语义。 这里有一个很好的例子 – 这个项目还谈到了我们通常如何看待Haskell语义 – 是Eager Haskell项目,它从根本上改变了评估策略,同时保持了相同的语义: http : //csg.csail.mit.edu/酒吧/ haskell.html

格拉斯哥Haskell编译器将您的代码转换为称为核心的类似Lambda演算的语言。 在这种语言中,每当你通过一个case -statement来匹配它时,就会评估一些东西。 因此,如果函数被调用,最外层的构造函数将被评估,只有它(如果没有强制字段)。 其他任何事情都是在一个thunkjar头。 (Thunk通过绑定来引入)。

当然这并不是真正的语言。 编译器以一种非常复杂的方式将Haskell转换成Core,使尽可能多的事情变得懒惰,任何总是需要懒惰的东西。 另外,还有非盒装的值和元组总是严格的。

如果你试图用手来评估一个函数,你基本上可以这样认为:

  • 尝试评估返回的最外层构造函数。
  • 如果需要其他任何东西来获得结果(但只有在真正需要时)才会被评估。 订单不重要。
  • 在IO的情况下,您必须评估从第一个到最后一个的所有语句的结果。 这有点复杂,因为IO单元会按照特定的顺序做一些技巧来强制评估。