什么是Haskell的严格点?

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

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

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

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

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


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

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

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

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


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

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

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


我可能会重申这个问题,在什么情况下Haskell会评估一个表达式? (也许应该坚持一个“弱头正常形式”。)

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

  • 执行IO动作将评估他们“需要”的任何表达式(所以你需要知道IO动作是否被执行,例如它的名字是main,或者从main调用它,你需要知道动作需要什么。)
  • 正在评估的表达式(嘿,这是一个递归定义!)将评估它需要的任何表达式。
  • 从直观的列表中,主要和IO操作属于第一类,seq和模式匹配属于第二类。 但我认为第一类更符合您的“严格点”的想法,因为事实上我们如何让Haskell的评估成为用户的可观察效果。

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


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

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

    ...

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

    $! 是根据seq定义的。

    -Lazy与非严格。

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

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

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

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

    -GHC优化:严格性分析。

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

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

    -Hikibooks Haskell:懒惰

    (如果头位没有beta-redex1,则术语是以正常形式存在的,如果redex仅在非redexes2的lambda抽取器前面,则redex是头redex。)因此,当你开始强制thunk时,在WHNF工作; 当没有剩下的强盗时,你就处于正常状态。 另一个有趣的点:

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

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

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

    链接地址: http://www.djcxy.com/p/42991.html

    上一篇: What are Haskell's strictness points?

    下一篇: Type of primitive functions in lazy evaluation